Add AVL tree implementation and merge few RB tree related macros.

If you have comments or any claims, please send me feedback
and I will fix them. 

>>>>>>>>>>>>>>>> Inline patch::
--- /usr/src/sys/sys/tree.h     Mon Mar  2 11:42:55 2009
+++ tree.h      Thu May 19 20:16:36 2011
@@ -730,9 +730,367 @@
             (x) != NULL;                                               \
             (x) = name##_RB_NEXT(x))
 
+#define RB_FOREACH_FROM(x, name, y)                                    \
+       for ((x) = (y);                                                 \
+           ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);    \
+            (x) = (y))
+
+#define RB_FOREACH_SAFE(x, name, head, y)                              \
+       for ((x) = RB_MIN(name, head);                                  \
+           ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);    \
+            (x) = (y))
+
 #define RB_FOREACH_REVERSE(x, name, head)                              \
        for ((x) = RB_MAX(name, head);                                  \
             (x) != NULL;                                               \
             (x) = name##_RB_PREV(x))
+
+#define RB_FOREACH_REVERSE_FROM(x, name, y)                            \
+       for ((x) = (y);                                                 \
+           ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);    \
+            (x) = (y))
+
+#define RB_FOREACH_REVERSE_SAFE(x, name, head, y)                      \
+       for ((x) = RB_MAX(name, head);                                  \
+           ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);    \
+            (x) = (y))
+
+/* Macros that define a avl tree */
+#define AVL_MAX_HEIGHT 42
+#define AVL_HEAD(name, type)                                           \
+struct name {                                                          \
+       struct type *avlh_root; /* root of the tree */                  \
+       int avlh_height;                                                \
+       long avlh_count;                                                \
+}
+
+#define AVL_INITIALIZER(root)                                          \
+       { NULL, 0, 0 }
+
+#define AVL_INIT(root, height) do {                                    \
+       (root)->avlh_root = NULL;                                       \
+       (root)->avlh_height = !height ? AVL_MAX_HEIGHT : height;        \
+       (root)->avlh_count = 0;                                         \
+} while (0)
+
+#define AVL_ENTRY(type)                                                        
\
+struct {                                                               \
+       struct type *avle_left;         /* left element */              \
+       struct type *avle_right;        /* right element */             \
+       int avle_height;                /* node color */                \
+}
+
+#define AVL_LEFT(elm, field)           (elm)->field.avle_left
+#define AVL_RIGHT(elm, field)          (elm)->field.avle_right
+#define AVL_HEIGHT(elm, field)         (elm)->field.avle_height
+#define AVL_ROOT(head)                 (head)->avlh_root
+#define AVL_EMPTY(head)                        (AVL_ROOT(head) == NULL)
+#define AVL_ROOT_HEIGHT(head)          (head)->avlh_height
+#define AVL_ROOT_COUNT(head)           (head)->avlh_count
+
+/* Generates prototypes and inline functions */
+#define        AVL_PROTOTYPE(name, type, field, cmp)                           
\
+       AVL_PROTOTYPE_INTERNAL(name, type, field, cmp,)
+#define        AVL_PROTOTYPE_STATIC(name, type, field, cmp)                    
\
+       AVL_PROTOTYPE_INTERNAL(name, type, field, cmp, 
__attribute__((__unused__)) static)
+#define AVL_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)           \
+attr struct type *name##_AVL_REMOVE(struct name *, struct type *);     \
+attr struct type *name##_AVL_INSERT(struct name *, struct type *);     \
+attr struct type *name##_AVL_FIND(struct name *, struct type *);       \
+attr struct type *name##_AVL_NFIND(struct name *, struct type *);      \
+attr struct type *name##_AVL_NEXT(struct name *, struct type *);       \
+attr struct type *name##_AVL_PREV(struct name *, struct type *);       \
+attr struct type *name##_AVL_MIN(struct name *);                       \
+attr struct type *name##_AVL_MAX(struct name *);                       
+
+#define AVL_ROTATE_LEFT(parent, elm, type, field) do {                         
        \
+       struct type *_rl = AVL_LEFT(elm, field);                                
        \
+       struct type *_rr = AVL_RIGHT(elm, field);                               
        \
+       int _l = !_rl ? 0 : AVL_HEIGHT(_rl, field);                             
        \
+                                                                               
        \
+       if (_rr && AVL_HEIGHT(_rr, field) >= _l) {                              
        \
+               AVL_RIGHT(*parent, field) = _rl;                                
        \
+               AVL_HEIGHT(*parent, field) = _l + 1;                            
        \
+               AVL_LEFT(elm, field) = (*parent);                               
        \
+               AVL_HEIGHT(elm, field) = _l + 2;                                
        \
+               (*parent) = (elm);                                              
        \
+       } else {                                                                
        \
+               AVL_RIGHT(*parent, field) = AVL_LEFT(_rl, field);               
        \
+               AVL_HEIGHT(*parent, field) = _l;                                
        \
+               AVL_LEFT(elm, field) = AVL_RIGHT(_rl, field);                   
        \
+               AVL_HEIGHT(elm, field) = _l;                                    
        \
+               AVL_LEFT(_rl, field) = (*parent);                               
        \
+               AVL_RIGHT(_rl, field) = (elm);                                  
        \
+               AVL_HEIGHT(_rl, field) = _l + 1;                                
        \
+               (*parent) = _rl;                                                
        \
+       }                                                                       
        \
+} while (0)
+
+#define AVL_ROTATE_RIGHT(parent, elm, type, field) do {                        
                \
+       struct type *_ll = AVL_LEFT(elm, field);                                
        \
+       struct type *_lr = AVL_RIGHT(elm, field);                               
        \
+       int _r = !_lr ? 0 : AVL_HEIGHT(_lr, field);                             
        \
+                                                                               
        \
+       if (_ll && AVL_HEIGHT(_ll, field) >= _r) {                              
        \
+               AVL_LEFT(*(parent), field) = _lr;                               
        \
+               AVL_HEIGHT(*(parent), field) = _r + 1;                          
        \
+               AVL_RIGHT(elm, field) = *parent;                                
        \
+               AVL_HEIGHT(elm, field) = _r + 2;                                
        \
+               *(parent) = (elm);                                              
        \
+       } else {                                                                
        \
+               AVL_RIGHT(elm, field) = AVL_LEFT(_lr, field);                   
        \
+               AVL_HEIGHT(elm, field) = _r;                                    
        \
+               AVL_LEFT(*parent, field) = AVL_RIGHT(_lr, field);               
        \
+               AVL_HEIGHT(*parent, field) = _r;                                
        \
+               AVL_LEFT(_lr, field) = (elm);                                   
        \
+               AVL_RIGHT(_lr, field) = (*parent);                              
        \
+               AVL_HEIGHT(_lr, field) = _r + 1;                                
        \
+               (*parent) = _lr;                                                
        \
+       }                                                                       
        \
+} while (0)
+
+#define AVL_REBALANCE(_anc, type, field, count)        while (count-- > 0) {   
                \
+       int _lh, _rh;                                                           
        \
+       struct type *_el = NULL;                                                
        \
+                                                                               
        \
+       _lh = !AVL_LEFT(*_anc[count], field) ? 0 :                              
        \
+               AVL_HEIGHT(AVL_LEFT(*_anc[count], field), field);               
        \
+       _rh = !AVL_RIGHT(*_anc[count], field) ? 0 :                             
        \
+               AVL_HEIGHT(AVL_RIGHT(*_anc[count], field), field);              
        \
+                                                                               
        \
+       if (_rh - _lh < -1) {                                                   
        \
+               _el = AVL_LEFT(*_anc[count], field);                            
        \
+               AVL_ROTATE_RIGHT(_anc[count], _el, type, field);                
        \
+       } else if (_rh - _lh > 1) {                                             
        \
+               _el = AVL_RIGHT(*_anc[count], field);                           
        \
+               AVL_ROTATE_LEFT(_anc[count], _el, type, field);                 
        \
+       } else if (AVL_HEIGHT(*_anc[count], field) != ((_rh > _lh) ? _rh : _lh) 
+ 1)    \
+               AVL_HEIGHT(*_anc[count], field) = ((_rh > _lh) ? _rh : _lh) + 
1;        \
+       else                                                                    
        \
+               break;                                                          
        \
+}
+
+/* Main avl operation.
+ * Moves node close to the key of elm to top
+ */
+#define        AVL_GENERATE(name, type, field, cmp)                            
                \
+       AVL_GENERATE_INTERNAL(name, type, field, cmp,)
+#define        AVL_GENERATE_STATIC(name, type, field, cmp)                     
                \
+       AVL_GENERATE_INTERNAL(name, type, field, cmp, 
__attribute__((__unused__)) static)
+#define AVL_GENERATE_INTERNAL(name, type, field, cmp, attr)                    
        \
+attr struct type *                                                             
        \
+name##_AVL_MIN(struct name *head)                                              
        \
+{                                                                              
        \
+       struct type *t = AVL_ROOT(head);                                        
        \
+                                                                               
        \
+       while (t && AVL_LEFT(t, field))                                         
        \
+               t = AVL_LEFT(t, field);                                         
        \
+       return (t);                                                             
        \
+}                                                                              
        \
+                                                                               
        \
+attr struct type *                                                             
        \
+name##_AVL_MAX(struct name *head)                                              
        \
+{                                                                              
        \
+       struct type *t = AVL_ROOT(head);                                        
        \
+                                                                               
        \
+       while (t && AVL_RIGHT(t, field))                                        
        \
+               t = AVL_RIGHT(t, field);                                        
        \
+       return (t);                                                             
        \
+}                                                                              
        \
+                                                                               
        \
+/* Finds the node with the same key as elm */                                  
        \
+attr struct type *                                                             
        \
+name##_AVL_FIND(struct name *head, struct type *elm)                           
        \
+{                                                                              
        \
+       struct type *t = AVL_ROOT(head);                                        
        \
+       int comp;                                                               
        \
+       while (t) {                                                             
        \
+               comp = cmp(t, elm);                                             
        \
+               if (!comp)                                                      
        \
+                       return (t);                                             
        \
+               else if (comp < 0)                                              
        \
+                       t = AVL_LEFT(t, field);                                 
        \
+               else                                                            
        \
+                       t = AVL_RIGHT(t, field);                                
        \
+       }                                                                       
        \
+       return (NULL);                                                          
        \
+}                                                                              
        \
+                                                                               
        \
+/* Finds the first node less than or equal to the search key */                
                \
+attr struct type *                                                             
        \
+name##_AVL_NFIND(struct name *head, struct type *elm)                          
        \
+{                                                                              
        \
+       struct type *t = AVL_ROOT(head);                                        
        \
+       struct type *res = NULL;                                                
        \
+       int comp;                                                               
        \
+       while (t) {                                                             
        \
+               comp = cmp(t, elm);                                             
        \
+               if (!comp)                                                      
        \
+                       return (t);                                             
        \
+               else if (comp < 0) {                                            
        \
+                       res = t;                                                
        \
+                       t = AVL_LEFT(t, field);                                 
        \
+               } else                                                          
        \
+                       t = AVL_RIGHT(t, field);                                
        \
+       }                                                                       
        \
+       return (res);                                                           
        \
+}                                                                              
        \
+                                                                               
        \
+/* ARGSUSED */                                                                 
        \
+attr struct type *                                                             
        \
+name##_AVL_NEXT(struct name *head, struct type *elm)                           
        \
+{                                                                              
        \
+       struct type *t = AVL_ROOT(head);                                        
        \
+       struct type *res = NULL;                                                
        \
+       int comp;                                                               
        \
+       while (t) {                                                             
        \
+               comp = cmp(t, elm);                                             
        \
+               if (comp < 0) {                                                 
        \
+                       res = t;                                                
        \
+                       t = AVL_LEFT(t, field);                                 
        \
+               } else                                                          
        \
+                       t = AVL_RIGHT(t, field);                                
        \
+       }                                                                       
        \
+       return (res);                                                           
        \
+}                                                                              
        \
+                                                                               
        \
+/* ARGSUSED */                                                                 
        \
+attr struct type *                                                             
        \
+name##_AVL_PREV(struct name *head, struct type *elm)                           
        \
+{                                                                              
        \
+       struct type *t = AVL_ROOT(head);                                        
        \
+       struct type *res = NULL;                                                
        \
+       int comp;                                                               
        \
+       while (t) {                                                             
        \
+               comp = cmp(t, elm);                                             
        \
+               if (comp > 0) {                                                 
        \
+                       res = t;                                                
        \
+                       t = AVL_RIGHT(t, field);                                
        \
+               } else                                                          
        \
+                       t = AVL_LEFT(t, field);                                 
        \
+       }                                                                       
        \
+       return (res);                                                           
        \
+}                                                                              
        \
+                                                                               
        \
+/* Inserts a node into the AVL tree */                                         
        \
+attr struct type *                                                             
        \
+name##_AVL_INSERT(struct name *head, struct type *elm)                         
        \
+{                                                                              
        \
+       struct type *temp, **pt;                                                
        \
+       struct type ***ancestors;                                               
        \
+       register int i;                                                         
        \
+       int comp;                                                               
        \
+                                                                               
        \
+       ancestors = (struct type ***) alloca(AVL_ROOT_HEIGHT(head) * 
sizeof(void*));    \
+       if (!ancestors)                                                         
        \
+               return (struct type *) -1;                                      
        \
+       else                                                                    
        \
+               memset(ancestors, 0, AVL_ROOT_HEIGHT(head) * sizeof(void*));    
        \
+       for (i = 0, pt = &AVL_ROOT(head); i < AVL_ROOT_HEIGHT(head) && *pt; 
i++) {      \
+               temp = *pt;                                                     
        \
+               ancestors[i] = pt;                                              
        \
+               comp = (cmp)(temp, elm);                                        
        \
+               if (!comp)                                                      
        \
+                       return temp;                                            
        \
+               else if (comp < 0)                                              
        \
+                       pt = &AVL_LEFT(temp, field);                            
        \
+               else                                                            
        \
+                       pt = &AVL_RIGHT(temp, field);                           
        \
+       }                                                                       
        \
+       *pt = elm;                                                              
        \
+                                                                               
        \
+       AVL_LEFT(elm, field) = AVL_RIGHT(elm, field) = (struct type *) NULL;    
        \
+       AVL_HEIGHT(elm, field) = 1;                                             
        \
+                                                                               
        \
+       AVL_ROOT_COUNT(head)++;                                                 
        \
+       AVL_REBALANCE(ancestors, type, field, i);                               
        \
+       return (NULL);                                                          
        \
+}                                                                              
        \
+                                                                               
        \
+attr struct type *                                                             
        \
+name##_AVL_REMOVE(struct name *head, struct type *elm)                         
        \
+{                                                                              
        \
+       struct type *temp, *old, **dp, **pt;                                    
        \
+       struct type ***ancestors;                                               
        \
+       register int i;                                                         
        \
+       int comp, delcnt;                                                       
        \
+                                                                               
        \
+       ancestors = (struct type ***) alloca(AVL_ROOT_HEIGHT(head) * 
sizeof(void*));    \
+       if (!ancestors)                                                         
        \
+               return (NULL);                                                  
        \
+       else                                                                    
        \
+               memset(ancestors, 0, AVL_ROOT_HEIGHT(head) * sizeof(void*));    
        \
+       for (i = 0, pt = &AVL_ROOT(head); i < AVL_ROOT_HEIGHT(head); i++) {     
        \
+               if (!*pt)                                                       
        \
+                       return (NULL);                                          
        \
+               else                                                            
        \
+                       temp = *pt;                                             
        \
+               ancestors[i] = pt;                                              
        \
+               comp = (cmp)(temp, elm);                                        
        \
+               if (!comp)                                                      
        \
+                       break;                                                  
        \
+               else if (comp < 0)                                              
        \
+                       pt = &AVL_LEFT(temp, field);                            
        \
+               else                                                            
        \
+                       pt = &AVL_RIGHT(temp, field);                           
        \
+       }                                                                       
        \
+       old = temp;                                                             
        \
+                                                                               
        \
+       if (!AVL_LEFT(temp, field)) {                                           
        \
+               *pt = AVL_RIGHT(temp, field);                                   
        \
+               i--;                                                            
        \
+       } else {                                                                
        \
+               delcnt = i;                                                     
        \
+               dp = pt;                                                        
        \
+               for (pt = &AVL_LEFT(temp, field); i < AVL_ROOT_HEIGHT(head) &&  
        \
+                               AVL_RIGHT(temp, field); i++) {                  
        \
+                       temp = *pt;                                             
        \
+                       ancestors[i] = pt;                                      
        \
+                       pt = &AVL_RIGHT(temp, field);                           
        \
+               }                                                               
        \
+               *pt = AVL_LEFT(temp, field);                                    
        \
+                                                                               
        \
+               AVL_LEFT(temp, field) = AVL_LEFT(old, field);                   
        \
+               AVL_RIGHT(temp, field) = AVL_RIGHT(old, field);                 
        \
+               AVL_HEIGHT(temp, field) = AVL_HEIGHT(old, field);               
        \
+               *dp = temp;                                                     
        \
+                                                                               
        \
+               ancestors[delcnt] = &AVL_LEFT(temp, field);                     
        \
+       }                                                                       
        \
+                                                                               
        \
+       AVL_ROOT_COUNT(head)--;                                                 
        \
+       AVL_REBALANCE(ancestors, type, field, i);                               
        \
+       return (old);                                                           
        \
+}
+
+#define AVL_INSERT(name, x, y) name##_AVL_INSERT(x, y)
+#define AVL_REMOVE(name, x, y) name##_AVL_REMOVE(x, y)
+#define AVL_FIND(name, x, y)   name##_AVL_FIND(x, y)
+#define AVL_NFIND(name, x, y)  name##_AVL_NFIND(x, y)
+#define AVL_NEXT(name, x, y)   name##_AVL_NEXT(x, y)
+#define AVL_PREV(name, x, y)   name##_AVL_PREV(x, y)
+#define AVL_MIN(name, x)       name##_AVL_MIN(x)
+#define AVL_MAX(name, x)       name##_AVL_MAX(x)
+
+#define AVL_FOREACH(x, name, head)                                             
        \
+       for ((x) = name##_AVL_MIN(head);                                        
        \
+            (x) != NULL;                                                       
        \
+            (x) = name##_AVL_NEXT(head, x))
+
+#define AVL_FOREACH_REVERSE(x, name, head)                                     
        \
+       for ((x) = name##_AVL_MAX(head);                                        
        \
+            (x) != NULL;                                                       
        \
+            (x) = name##_AVL_PREV(head, x))
+
+#define AVL_FOREACH_SAFE(x, name, head, y)                                     
        \
+       for ((x) = name##_AVL_MIN(head);                                        
        \
+            (x) && ((y) = name##_AVL_NEXT(head, x), (x));                      
        \
+            (x) = (y))
+
+#define AVL_FOREACH_REVERSE_SAFE(x, name, head, y)                             
        \
+       for ((x) = name##_AVL_MAX(head);                                        
        \
+            (x) && ((y) = name##_AVL_PREV(head, x), (x));                      
        \
+            (x) = (y))
+
 
 #endif /* _SYS_TREE_H_ */

Reply via email to