From 60dd03eab0dbb0930ebf32290f26aa1766112efa Mon Sep 17 00:00:00 2001 From: Thadeu Lima de Souza Cascardo Date: Thu, 20 May 2010 06:24:35 -0400 Subject: [PATCH] rbtree and other types. --- 03types/types | 39 ++++++++++++++++++++++++++++++++++++--- 1 file changed, 36 insertions(+), 3 deletions(-) diff --git a/03types/types b/03types/types index d43e997..da8a825 100644 --- a/03types/types +++ b/03types/types @@ -138,10 +138,43 @@ Reference: * find\\_next\\_zero\\_bit * for\\_each\\_set\\_bit -# Trees and hashes +# Reb-black tree -* FIX_ME +# Files + +* Documentation/rbtree.txt +* lib/rbtree.c +* include linux/rbtree.h + +# Usage + +* Embed struct rb\\_node into your data structure +* There's no callback for comparison, write your own lookup and insertion + functions +* Locking is up to the user + +# API + +* rb\\_entry is the same as container\\_of +* Create the root with struct rb\\_root name = RB\\_ROOT; +* Lookup function (see example) uses rb\\_left and rb\\_right members +* Insertion: lookup insertion point, save the parent and use the functions + rb\\_link\\_node and rb\\_insert\\_color (example in Documentation) +* Erase with rb\\_erase +* Iterate with functions rb\\_first, rb\\_last, rb\\_next and rb\\_prev + +# Hashes + +* No hash table +* There are hash functions found at + - include linux/hash.h + - include linux/jhash.h +* Users usually do chaining to resolve collisions # Other data types -* FIX_ME +* IDR +* Flexible Array +* Plist +* Radix tree +* Btree -- 2.20.1