libredblack [Dev Diligence]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.

[[http://libredblack.sourceforge.net/|Libredblack]] is a C implementation of the classic red-black tree.  

===== Case Studies =====
  * FolderShare used this in the backend to hold trees with 1-50,000 items.  Performance was great, and we were really satisfied with it.  


===== Gotchas =====
  * Each non-inline item stored in the tree requires 4 pointers and an enum, which may take up to 40 bytes.  With heap overhead, this results in almost 50 bytes of overhead per tree item.  For some uses, this can be reduced by inlining your data in the tree item.  But, be sure to take into account this overhead when considering how many items a single server can hold in memory.  


===== Alternatives =====
* [[http://users.footprints.net/~kaz/kazlib.html|Kazlib]], the most solid, flexible, no-nonsense, gets-out-of-your-way data structures library you'll ever use.  Has a doubly-linked list, red-black tree, and hash table.  Lets you handle all your own allocation if you want to, and minimizes its memory footprint.

===== Other Resources ==== 
[[http://en.wikipedia.org/wiki/Red_black_tree|How a redblack tree works]]