On Thu, May 19, 2011 at 08:28:09PM +0300, Michael Pounov wrote: > 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) \
This macro modifies parameter y, which I do not expect from using it.
Please keep y its original value. Also, I want to be able to use an
rvalue for y.
> + for ((x) = (y); \
> + ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
> + (x) = (y))
> +
> +#define RB_FOREACH_SAFE(x, name, head, y) \
(Again, don't modify the value of y.)
> + for ((x) = RB_MIN(name, head); \
> + ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
> + (x) = (y))
> +
Is there a specific reason your wrote the above 2 macros? The pattern
where the for loop is written out is quite common and well understood by
developers.
> #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
No. Trees do not have a max height. On a modern amd64, I can
create code which will be able to fit more than 2 ** 42 items in the
tree (provided I had the physmem in my machine).
> +#define AVL_HEAD(name, type) \
> +struct name {
> \
> + struct type *avlh_root; /* root of the tree */ \
> + int avlh_height; \
> + long avlh_count; \
size_t, not long. K&R guarantee it'll fit for every future version C.
Why is there a count? For most trees in the system, we don't care how
large they are. And we don't care for the height either.
> +}
> +
> +#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; \
height? This is not the current height of the tree... Don't like it; if
the items in the tree are constrained in some way, other code will have
dealt with it.
> + (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 */ \
Comment copy-pasted from RB tree.
> +}
> +
> +#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
How about this instead: (AVL_EMPTY(head) ? 0 : AVL_HEIGHT(AVL_ROOT(head)))
> +#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*)); \
That is nasty, alloca in a macro. If I had a stack overflow, I'd never
found out it was the macro doing that.
Also, I doubt you need it, since you can use the parent pointer to
traverse up the tree. Kernel has very little stack space and no room to
grow more.
ancestors will overflow:
- either because the tree temporarily (prior to rebalancing) may be
deeper than max_height,
- or because the tree becomes too high (you never limit the number of
items I can put in the tree, thought your implementation requires
that).
You remedied this by limiting the for loop below to AVL_ROOT_HEIGHT
items, but this means you will drop subtrees when the tree approaches
its max size.
> + if (!ancestors)
> \
> + return (struct type *) -1;
> \
Bad return value. This breaks the symmetry between the other trees,
which will only return NULL or a colliding item. You make us test for 3
values.
> + else
> \
> + memset(ancestors, 0, AVL_ROOT_HEIGHT(head) * sizeof(void*));
> \
> + for (i = 0, pt = &AVL_ROOT(head); i < AVL_ROOT_HEIGHT(head) && *pt;
> i++) { \
Instead of i < AVL_ROOT_HEIGHT(head) why not only check on *pt != NULL?
The latter is a common pattern, while the former looks suspect to me:
the AVL tree is not guaranteed to be exactly AVL_ROOT_HEIGHT(head) high
everywhere. This is probably why the *pt is added to the test.
> + 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_ */
>
I don't like the array, use parent-pointer traversal instead (like
RBtree does).
I haven't checked the internals of your algorithm and would have to
dig up the AVL algorithm stuff to refresh myself on how it works. But I
thought it was possible to store only the balance between the left and
right node and rebalance based on that? That way, you can use an int
instead of a size_t (or long, as it is currently in your code) and lose
the artificial tree-size limit.
--
Ariane
