Augmented binary search tree
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.
Thanks!
Brills Peng
討論串 (同標題文章)