I don't think that an AVL tree will work, at least without substantial
modification, for three reasons: (1) the intervals stored don't have to be
disjoint (read locks can overlap), (2) the overlap detection is
problematic (note that you're looking for overlaps only with a different
lockowner than yourself), (3) managing coalescence/splitting of lock
ranges is problematic, esp. in a way which is compatible with the AVL
balancing invariants.  Finding a data structure which supports all
operations in O(log N) time seems like a difficult problem to me, although
the interval trees in Ch. 15 of Cormen, Leiserson, Rivest, _An
Introduction to Algorithms_ seem like a step in the right direction...

Cheers,
Kendrick


On Wed, 2 May 2001, Eric Barton wrote:

> 
> > I'm not going to change it from a linear list until I've made these other
> > changes.  In the meantime, if anyone knows of a data structure which lets
> me
> > record ranges and check for overlaps, let me know...
> >
> 
> Would a threaded AVL tree (http://www.msu.edu/user/pfaffben/avl/) be over
> the top?  I'd have thought so if there were only tens of range locks on a
> file, but with hundreds or more...
> 
> --
> 
>                 Cheers,
>                         Eric
> 
> ----------------------------------------------------
> |Eric Barton        Barton Software                |
> |9 York Gardens     Tel:    +44 (117) 923 9831     |
> |Clifton            Mobile: +44 (7909) 680 356     |
> |Bristol BS8 4LL    Fax:    call first             |
> |United Kingdom     E-Mail: [EMAIL PROTECTED]|
> ----------------------------------------------------
> 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
> the body of a message to [EMAIL PROTECTED]
> 

-
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
the body of a message to [EMAIL PROTECTED]

Reply via email to