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