DragonFly BSD
DragonFly kernel List (threaded) for 2011-05
[Date Prev][Date Next]  [Thread Prev][Thread Next]  [Date Index][Thread Index]

Augmented binary search tree

From: Brills Peng <brillsp@xxxxxxxxx>
Date: Thu, 26 May 2011 23:16:01 +0800

Hi, all:

I found that in sys/tree.h, the augmented rbtree is not supported by
DFBSD currently. However, the B-WF2Q+ algorithm needed by BFQ scheduler
which I am implementing as GSoC project needs augmented tree to achieve
effective search operations (O(lgn), instead of O(n) of worst case, if
simply uses rbtree). 

Is there any obstacles preventing us to port other BSD's tree.h with
augment support? I took a brief look at their tree.h, and it seemed not
hard to port. On the other hand, is there any rb-tree implementation
like the one of Linux that is BSD-licensed? I could probably use that
kind implementation to update augment information manually. Otherwise, I
will have to implement another balanced tree with augment support.


Brills Peng  

[Date Prev][Date Next]  [Thread Prev][Thread Next]  [Date Index][Thread Index]