From: Thadeu Lima de Souza Cascardo <cascardo@holoscopio.com>
Date: Thu, 20 May 2010 10:24:35 +0000 (-0400)
Subject: rbtree and other types.
X-Git-Url: http://git.cascardo.eti.br/?p=cascardo%2Fkernel%2Fslides%2F.git;a=commitdiff_plain;h=60dd03eab0dbb0930ebf32290f26aa1766112efa

rbtree and other types.
---

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