AMambrop7·Dec 25, 2014
I really prefer intrusive data structures, for the exact reasons outlined in the article.
I've myself written many implementations of intrusive structures. But now I'd like to present the greatest of them, a super-generic implementation of an intrusive AVL tree in C. See [1], and example [2].
- It relies on a user-defined concept of a "link". In particular, this means the structure can be in an array and linked with array indices, and can be copied correctly with a single memcpy. Of course the user may still use pointers as links.
- It supports implementation of user-defined associative operations (e.g. sum). This consists of operations:
CAvl_AssocSum: Calculate the sum of all the nodes.
CAvl_ExclusiveAssocPrefixSum: Calculate the sum of elements from the first one up to but not including node X.
CAvl_FindLastExclusiveAssocPrefixSumLesser
Read the rest
Equal: Find the first node where the sum of all preceding nodes is >=X.
Of course these all have O(log n) time complexity.
- The implementation is made generic by include files which rely on macros a lot. Other than the macro madness, I think this is better then C++ templates, due to easy #if, where in templates one would need to jump through hoops due to non-existence of static_if.
[1] https://github.com/ambrop72/badvpn/tree/master/structure (see CAvl_*
[2] https://github.com/ambrop72/badvpn/blob/master/examples/cavl... (also see cavl_test_tree.h in the same dir defining some parameters for the structure)