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_ */
