I need some binary tree structure for concurrent access from multiple threads where some threads do searching and some other perform insert/delete operations. This structure must work both in kernel and user mode
Solutions
Lets add some sync primitive to each tree node - it is going to be SRWLock in user mode and EX_PUSH_LOCK in kernel mode. It`s clear that reader can acquire shared lock while writer will use exclusive one. Bcs order of locks always have to be the same - we need tree structure with top-down rebalancing (I hope this is right assumption). So lets see which kinds of trees allow such operations
- weight-balanced tree. Drawbacks: need to use floating point, so in kernel mode we must care about FPU context saving/restoring
- classical B-tree. I think there may be a problem with granularity - when node contains a big number of keys and we need to lock it exclusively - all search operations will be blocked from this node till the lowest level of its children
- red-black tree. Looks like it is a good candidate but sadly I cannot find implementation in plain C with top-down rebalancing :-(
Win8 has RTL_RB tree implementation that may be of use :)
ОтветитьУдалитьNo
ОтветитьУдалить1) Implementation of avl inside ntdll don`t have fain grained synchronization within each node
2) avl trees uses bottop-top pass for rebalancing. This is no-no - you will acquire locks in opposite order with simple searching and end up with dealock