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]
