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
