diff options
Diffstat (limited to 'shared/common/qtree.c')
| -rw-r--r-- | shared/common/qtree.c | 780 |
1 files changed, 780 insertions, 0 deletions
diff --git a/shared/common/qtree.c b/shared/common/qtree.c new file mode 100644 index 0000000..368e38c --- /dev/null +++ b/shared/common/qtree.c @@ -0,0 +1,780 @@ +/* Copyright (c) 2004 krzYszcz and others. + * For information on usage and redistribution, and for a DISCLAIMER OF ALL + * WARRANTIES, see the file, "LICENSE.txt," in this distribution. */ + +#include "m_pd.h" +#include "qtree.h" + +/* Since there is no sentinel node, the deletion routine has to have + a few extra checks. LATER rethink. */ + +/* LATER freelist */ + +typedef t_qnode *(*t_qtree_inserthook)(t_qnode *); + +#ifdef QTREE_DEBUG +/* returns black-height or 0 if failed */ +static int qnode_verify(t_qnode *np) +{ + if (np) + { + int bhl, bhr; + if (((bhl = qnode_verify(np->n_left)) == 0) || + ((bhr = qnode_verify(np->n_right)) == 0)) + return (0); + if (bhl != bhr) + { + /* failure: two paths rooted in the same node + contain different number of black nodes */ + bug("qnode_verify: not balanced"); + return (0); + } + if (np->n_black) + return (bhl + 1); + else + { + if ((np->n_left && !np->n_left->n_black) || + (np->n_right && !np->n_right->n_black)) + { + bug("qnode_verify: adjacent red nodes"); + return (0); + } + return (bhl); + } + } + else return (1); +} + +/* returns black-height or 0 if failed */ +static int qtree_verify(t_qtree *tree) +{ + return (qnode_verify(tree->t_root)); +} + +static int qnode_checkmulti(t_qnode *np1, t_qnode *np2) +{ + if (np1 && np2 && np1->n_key == np2->n_key) + { + if (np1 == np2) + bug("qnode_checkmulti"); + else + return (1); + } + return (0); +} + +static void qnode_post(t_qtree *tree, t_qnode *np, + t_qnode_vshowhook hook, char *message) +{ + startpost("%g ", np->n_key); + if (tree->t_valuetype == QTREETYPE_FLOAT) + startpost("%g ", QNODE_GETFLOAT(np)); + else if (tree->t_valuetype == QTREETYPE_SYMBOL) + startpost("%s ", QNODE_GETSYMBOL(np)->s_name); + else if (tree->t_valuetype == QTREETYPE_ATOM) + { + t_atom *ap = QNODE_GETATOMPTR(np); + if (ap->a_type == A_FLOAT) + startpost("%g ", ap->a_w.w_float); + else if (ap->a_type == A_SYMBOL) + startpost("%s ", ap->a_w.w_symbol->s_name); + } + else if (hook) + { + char buf[MAXPDSTRING]; + (*hook)(np, buf, MAXPDSTRING); + startpost("%s ", buf); + } + else startpost("0x%08x ", (int)QNODE_GETSYMBOL(np)); + startpost("%s ", (np->n_black ? "black" : "red")); + + if (qnode_checkmulti(np, np->n_parent) || + qnode_checkmulti(np, np->n_left) || + qnode_checkmulti(np, np->n_right) || + qnode_checkmulti(np->n_parent, np->n_left) || + qnode_checkmulti(np->n_parent, np->n_right) || + qnode_checkmulti(np->n_left, np->n_right)) + startpost("multi "); + + if (np->n_parent) + startpost("(%g -> ", np->n_parent->n_key); + else + startpost("(nul -> "); + if (np->n_left) + startpost("%g, ", np->n_left->n_key); + else + startpost("nul, "); + if (np->n_right) + startpost("%g)", np->n_right->n_key); + else + startpost("nul)"); + if (message) + post(": %s", message); + else + endpost(); +} + +/* Assert a standard stackless traversal producing the same sequence, + as the auxiliary list. */ +static int qtree_checktraversal(t_qtree *tree) +{ + t_qnode *treewalk = tree->t_root; + t_qnode *listwalk = tree->t_first; + int count = 0; + while (treewalk) + { + t_qnode *prev = treewalk->n_left; + if (prev) + { + while (prev->n_right && prev->n_right != treewalk) + prev = prev->n_right; + if (prev->n_right) + { + prev->n_right = 0; + count++; + if (treewalk == listwalk) + listwalk = listwalk->n_next; + else + { + bug("qtree_checktraversal 1"); + qnode_post(tree, treewalk, 0, "treewalk"); + if (listwalk) + qnode_post(tree, listwalk, 0, "listwalk"); + else + post("empty listwalk pointer"); + listwalk = treewalk; + } + treewalk = treewalk->n_right; + } + else + { + prev->n_right = treewalk; + treewalk = treewalk->n_left; + } + } + else + { + count++; + if (treewalk == listwalk) + listwalk = listwalk->n_next; + else + { + bug("qtree_checktraversal 2"); + qnode_post(tree, treewalk, 0, "treewalk"); + if (listwalk) + qnode_post(tree, listwalk, 0, "listwalk"); + else + post("empty listwalk pointer"); + listwalk = treewalk; + } + treewalk = treewalk->n_right; + } + } + return (count); +} + +static int qnode_height(t_qnode *np) +{ + if (np) + { + int lh = qnode_height(np->n_left); + int rh = qnode_height(np->n_right); + return (lh > rh ? lh + 1 : rh + 1); + } + else return (0); +} + +void qtree_debug(t_qtree *tree, int level, t_qnode_vshowhook hook) +{ + t_qnode *np; + int count; + post("------------------------"); + count = qtree_checktraversal(tree); + if (level) + { + for (np = tree->t_first; np; np = np->n_next) + qnode_post(tree, np, hook, 0); + if (level > 1) + { + post("************"); + for (np = tree->t_last; np; np = np->n_prev) + startpost("%g ", np->n_key); + endpost(); + } + } + if (tree->t_root) + { + t_qnode *first = tree->t_root, *last = tree->t_root; + while (first->n_left && first->n_left != tree->t_root) + first = first->n_left; + while (last->n_right && last->n_right != tree->t_root) + last = last->n_right; + post("count %d, height %d, root %g", + count, qnode_height(tree->t_root), tree->t_root->n_key); + post("first %g, root->left* %g, last %g, root->right* %g", + (tree->t_first ? tree->t_first->n_key : 0), first->n_key, + (tree->t_last ? tree->t_last->n_key : 0), last->n_key); + } + else post("empty"); + post("...verified (black-height is %d)", qtree_verify(tree)); + post("------------------------"); +} +#endif + +/* assuming that target node (np->n_right) exists */ +static void qtree_lrotate(t_qtree *tree, t_qnode *np) +{ + t_qnode *target = np->n_right; + if (np->n_right = target->n_left) + np->n_right->n_parent = np; + if (!(target->n_parent = np->n_parent)) + tree->t_root = target; + else if (np == np->n_parent->n_left) + np->n_parent->n_left = target; + else + np->n_parent->n_right = target; + target->n_left = np; + np->n_parent = target; +} + +/* assuming that target node (np->n_left) exists */ +static void qtree_rrotate(t_qtree *tree, t_qnode *np) +{ + t_qnode *target = np->n_left; + if (np->n_left = target->n_right) + np->n_left->n_parent = np; + if (!(target->n_parent = np->n_parent)) + tree->t_root = target; + else if (np == np->n_parent->n_left) + np->n_parent->n_left = target; + else + np->n_parent->n_right = target; + target->n_right = np; + np->n_parent = target; +} + +static t_qnode *qtree_preinserthook(t_qnode *np) +{ + while (np->n_prev && np->n_prev->n_key == np->n_key) + np = np->n_prev; + if (np->n_left) + { + np = np->n_prev; + if (np->n_right) + { + /* LATER revisit */ + bug("qtree_preinserthook"); + return (0); /* do nothing */ + } + } + return (np); +} + +static t_qnode *qtree_postinserthook(t_qnode *np) +{ + while (np->n_next && np->n_next->n_key == np->n_key) + np = np->n_next; + if (np->n_right) + { + np = np->n_next; + if (np->n_left) + { + /* LATER revisit */ + bug("qtree_postinserthook"); + return (0); /* do nothing */ + } + } + return (np); +} + +/* Returns a newly inserted or already existing node (or 0 if allocation + failed). A caller is responsible for assigning a value. If hook is + supplied, it is called iff key is found. In case of key being found + (which means foundp returns 1), a new node is inserted, unless hook is + either empty, or returns null. Hook's nonempty return is the parent + for the new node. It is expected to have no more than one child. */ +static t_qnode *qtree_doinsert(t_qtree *tree, double key, + t_qtree_inserthook hook, int *foundp) +{ + t_qnode *np, *parent, *result; + int leftchild; + *foundp = 0; + if (!(np = tree->t_root)) + { + if (!(np = getbytes(tree->t_nodesize))) + return (0); + np->n_key = key; + np->n_black = 1; + tree->t_root = tree->t_first = tree->t_last = np; + return (np); + } + + do + { + if (np->n_key == key) + { + *foundp = 1; + if (hook && (parent = (*hook)(np))) + { + if (parent->n_left && parent->n_right) + { + bug("qtree_insert, callback return 1"); + parent = parent->n_next; + } + if (leftchild = (key < parent->n_key)) + { + if (parent->n_left) + { + bug("qtree_insert, callback return 2"); + leftchild = 0; + } + } + else if (parent->n_right) + leftchild = 1; + goto addit; + } + else return (np); /* a caller may then keep or replace the value */ + } + else parent = np; + } + while (np = (key < np->n_key ? np->n_left : np->n_right)); + leftchild = (key < parent->n_key); +addit: + /* parent has no more than one child, new node becomes + parent's immediate successor or predecessor */ + if (!(np = getbytes(tree->t_nodesize))) + return (0); + np->n_key = key; + np->n_parent = parent; + if (leftchild) + { + parent->n_left = np; + /* update the auxiliary linked list structure */ + np->n_next = parent; + if (np->n_prev = parent->n_prev) + np->n_prev->n_next = np; + else + tree->t_first = np; + parent->n_prev = np; + } + else + { + parent->n_right = np; + /* update the auxiliary linked list structure */ + np->n_prev = parent; + if (np->n_next = parent->n_next) + np->n_next->n_prev = np; + else + tree->t_last = np; + parent->n_next = np; + } + result = np; + + /* balance the tree -- LATER clean this if possible... */ + np->n_black = 0; + while (np != tree->t_root && !np->n_parent->n_black) + { + t_qnode *uncle; + /* np->n_parent->n_parent exists (we always paint root node in black) */ + if (np->n_parent == np->n_parent->n_parent->n_left) + { + uncle = np->n_parent->n_parent->n_right; + if (!uncle /* (sentinel not used) */ + || uncle->n_black) + { + if (np == np->n_parent->n_right) + { + np = np->n_parent; + qtree_lrotate(tree, np); + } + np->n_parent->n_black = 1; + np->n_parent->n_parent->n_black = 0; + qtree_rrotate(tree, np->n_parent->n_parent); + } + else + { + np->n_parent->n_black = 1; + uncle->n_black = 1; + np = np->n_parent->n_parent; + np->n_black = 0; + } + } + else + { + uncle = np->n_parent->n_parent->n_left; + if (!uncle /* (sentinel not used) */ + || uncle->n_black) + { + if (np == np->n_parent->n_left) + { + np = np->n_parent; + qtree_rrotate(tree, np); + } + np->n_parent->n_black = 1; + np->n_parent->n_parent->n_black = 0; + qtree_lrotate(tree, np->n_parent->n_parent); + } + else + { + np->n_parent->n_black = 1; + uncle->n_black = 1; + np = np->n_parent->n_parent; + np->n_black = 0; + } + } + } + tree->t_root->n_black = 1; + return (result); +} + +/* assuming that requested node exists */ +void qtree_delete(t_qtree *tree, t_qnode *gone) +{ + t_qnode *parent; /* parent of gone, after relinking */ + t_qnode *child; /* gone's only child (or null), after relinking */ + /* gone has to be the parent of no more than one child */ + if (gone->n_left && gone->n_right) + { + /* Successor is the new parent of gone's children, and a new child + of gone's parent (if any). Successor always exists in this context, + and it has no left child. The simplistic scheme is to replace + gone's fields with successor's fields, and delete the successor. + We cannot do so, however, because successor may be pointed at... */ + t_qnode *successor = gone->n_next; + child = successor->n_right; + successor->n_left = gone->n_left; + successor->n_left->n_parent = successor; + if (successor == gone->n_right) + parent = successor; + else + { + /* successor's parent always exists in this context, + successor is the left child of its parent */ + parent = successor->n_parent; + parent->n_left = child; + if (child) /* (sentinel not used) */ + child->n_parent = parent; + successor->n_right = gone->n_right; + successor->n_right->n_parent = successor; + } + if (gone->n_parent) + { + int swp; + if (gone == gone->n_parent->n_left) + gone->n_parent->n_left = successor; + else + gone->n_parent->n_right = successor; + successor->n_parent = gone->n_parent; + swp = gone->n_black; + gone->n_black = successor->n_black; + successor->n_black = swp; + } + else + { + tree->t_root = successor; + successor->n_parent = 0; + gone->n_black = successor->n_black; + successor->n_black = 1; /* LATER rethink */ + } + + /* update the auxiliary linked list structure */ + if (successor->n_prev = gone->n_prev) + gone->n_prev->n_next = successor; + else + tree->t_first = successor; + } + else + { + /* update the auxiliary linked list structure */ + if (gone->n_prev) + gone->n_prev->n_next = gone->n_next; + else + tree->t_first = gone->n_next; + if (gone->n_next) + gone->n_next->n_prev = gone->n_prev; + else + tree->t_last = gone->n_prev; + + /* connect gone's child with gone's parent */ + if (gone->n_left) + child = gone->n_left; + else + child = gone->n_right; + if (parent = gone->n_parent) + { + if (child) /* (sentinel not used) */ + child->n_parent = parent; + if (gone == parent->n_left) + parent->n_left = child; + else + parent->n_right = child; + } + else + { + if (tree->t_root = child) + { + child->n_parent = 0; + child->n_black = 1; /* LATER rethink */ + } + goto done; + } + } + + if (gone->n_black) + { + /* balance the tree -- LATER clean this if possible... */ + /* on entry: tree is not empty, parent always exists, child + not necessarily... */ + while (child != tree->t_root && + (!child || /* (sentinel not used) */ + child->n_black)) + { + t_qnode *other; /* another child of the same parent */ + if (child == parent->n_left) + { + other = parent->n_right; + if (other && /* (sentinel not used) */ + !other->n_black) + { + other->n_black = 1; + parent->n_black = 0; + qtree_lrotate(tree, parent); + other = parent->n_right; + } + if (!other || /* (sentinel not used) */ + (!other->n_left || other->n_left->n_black) && + (!other->n_right || other->n_right->n_black)) + { + if (other) /* (sentinel not used) */ + other->n_black = 0; + child = parent; + parent = parent->n_parent; + } + else + { + if (!other || /* (sentinel not used) */ + !other->n_right || other->n_right->n_black) + { + if (other) /* (sentinel not used) */ + { + if (other->n_left) other->n_left->n_black = 1; + other->n_black = 0; + qtree_rrotate(tree, other); + other = parent->n_right; + } + } + if (other) /* (sentinel not used) */ + { + if (other->n_right) other->n_right->n_black = 1; + other->n_black = parent->n_black; + } + parent->n_black = 1; + qtree_lrotate(tree, parent); + tree->t_root->n_black = 1; /* LATER rethink */ + goto done; + } + } + else /* right child */ + { + other = parent->n_left; + if (other && /* (sentinel not used) */ + !other->n_black) + { + other->n_black = 1; + parent->n_black = 0; + qtree_rrotate(tree, parent); + other = parent->n_left; + } + if (!other || /* (sentinel not used) */ + (!other->n_left || other->n_left->n_black) && + (!other->n_right || other->n_right->n_black)) + { + if (other) /* (sentinel not used) */ + other->n_black = 0; + child = parent; + parent = parent->n_parent; + } + else + { + if (!other || /* (sentinel not used) */ + !other->n_left || other->n_left->n_black) + { + if (other) /* (sentinel not used) */ + { + if (other->n_right) other->n_right->n_black = 1; + other->n_black = 0; + qtree_lrotate(tree, other); + other = parent->n_left; + } + } + if (other) /* (sentinel not used) */ + { + if (other->n_left) other->n_left->n_black = 1; + other->n_black = parent->n_black; + } + parent->n_black = 1; + qtree_rrotate(tree, parent); + tree->t_root->n_black = 1; /* LATER rethink */ + goto done; + } + } + } + if (child) /* (sentinel not used) */ + child->n_black = 1; + } +done: + freebytes(gone, tree->t_nodesize); +#ifdef QTREE_DEBUG + qtree_verify(tree); +#endif +} + +t_qnode *qtree_search(t_qtree *tree, double key) +{ + t_qnode *np = tree->t_root; + while (np && np->n_key != key) + np = (key < np->n_key ? np->n_left : np->n_right); + return (np); +} + +t_qnode *qtree_closest(t_qtree *tree, double key, int geqflag) +{ + t_qnode *np, *parent; + if (!(np = tree->t_root)) + return (0); + do + if (np->n_key == key) + return (np); + else + parent = np; + while (np = (key < np->n_key ? np->n_left : np->n_right)); + if (geqflag) + return (key > parent->n_key ? parent->n_next : parent); + else + return (key < parent->n_key ? parent->n_prev : parent); +} + +t_qnode *qtree_insert(t_qtree *tree, double key, int *foundp) +{ + return (qtree_doinsert(tree, key, 0, foundp)); +} + +t_qnode *qtree_multiinsert(t_qtree *tree, double key, int fifoflag) +{ + int found; + return (qtree_doinsert(tree, key, (fifoflag ? + qtree_postinserthook : + qtree_preinserthook), &found)); +} + +t_qnode *qtree_insertfloat(t_qtree *tree, double key, t_float f, + int replaceflag) +{ + int found; + t_qnode *np = qtree_doinsert(tree, key, 0, &found); + if (np && (!found || replaceflag)) + { + if (tree->t_valuetype == QTREETYPE_FLOAT) + { + t_qnode_float *npf = (t_qnode_float *)np; + npf->nf_value = f; + } + else if (tree->t_valuetype == QTREETYPE_ATOM) + { + t_qnode_atom *npa = (t_qnode_atom *)np; + t_atom *ap = &npa->na_value; + SETFLOAT(ap, f); + } + else bug("qtree_insertfloat"); + } + return (np); +} + +t_qnode *qtree_insertsymbol(t_qtree *tree, double key, t_symbol *s, + int replaceflag) +{ + int found; + t_qnode *np = qtree_doinsert(tree, key, 0, &found); + if (np && (!found || replaceflag)) + { + if (tree->t_valuetype == QTREETYPE_SYMBOL) + { + t_qnode_symbol *nps = (t_qnode_symbol *)np; + nps->ns_value = s; + } + else if (tree->t_valuetype == QTREETYPE_ATOM) + { + t_qnode_atom *npa = (t_qnode_atom *)np; + t_atom *ap = &npa->na_value; + SETSYMBOL(ap, s); + } + else bug("qtree_insertsymbol"); + } + return (np); +} + +t_qnode *qtree_insertatom(t_qtree *tree, double key, t_atom *ap, + int replaceflag) +{ + int found; + t_qnode *np = qtree_doinsert(tree, key, 0, &found); + if (np && (!found || replaceflag)) + { + if (tree->t_valuetype == QTREETYPE_ATOM) + { + t_qnode_atom *npa = (t_qnode_atom *)np; + npa->na_value = *ap; + } + else bug("qtree_insertatom"); + } + return (np); +} + +/* LATER preallocate 'freecount' nodes */ +static void qtree_doinit(t_qtree *tree, t_qtreetype vtype, + size_t nodesize, int freecount) +{ + tree->t_root = tree->t_first = tree->t_last = 0; + tree->t_valuetype = vtype; + tree->t_nodesize = nodesize; +} + +void qtree_inittyped(t_qtree *tree, t_qtreetype vtype, int freecount) +{ + size_t nsize; + switch (vtype) + { + case QTREETYPE_FLOAT: + nsize = sizeof(t_qnode_float); + break; + case QTREETYPE_SYMBOL: + nsize = sizeof(t_qnode_symbol); + break; + case QTREETYPE_ATOM: + nsize = sizeof(t_qnode_atom); + break; + default: + bug("qtree_inittyped"); + vtype = QTREETYPE_ILLEGAL; + nsize = sizeof(t_qnode); + } + qtree_doinit(tree, vtype, nsize, freecount); +} + +void qtree_initcustom(t_qtree *tree, size_t nodesize, int freecount) +{ + qtree_doinit(tree, QTREETYPE_CUSTOM, nodesize, freecount); +} + +/* LATER keep and/or preallocate 'freecount' nodes (if negative, keep all) */ +void qtree_clear(t_qtree *tree, int freecount) +{ + t_qnode *np, *next = tree->t_first; + while (next) + { + np = next; + next = next->n_next; + freebytes(np, tree->t_nodesize); + } + qtree_doinit(tree, tree->t_valuetype, tree->t_nodesize, 0); +} |