aboutsummaryrefslogtreecommitdiff
path: root/shared/hammer/tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'shared/hammer/tree.c')
-rw-r--r--shared/hammer/tree.c494
1 files changed, 398 insertions, 96 deletions
diff --git a/shared/hammer/tree.c b/shared/hammer/tree.c
index 549dd09..9957da7 100644
--- a/shared/hammer/tree.c
+++ b/shared/hammer/tree.c
@@ -1,4 +1,4 @@
-/* Copyright (c) 2003 krzYszcz and others.
+/* Copyright (c) 2003-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. */
@@ -10,8 +10,10 @@
/* LATER freelist */
+typedef t_hammernode *(*t_hammertree_inserthook)(t_hammernode *);
+
#ifdef HAMMERTREE_DEBUG
-/* returns bh or 0 if failed */
+/* returns black-height or 0 if failed */
static int hammernode_verify(t_hammernode *np)
{
if (np)
@@ -43,55 +45,129 @@ static int hammernode_verify(t_hammernode *np)
else return (1);
}
-/* returns bh or 0 if failed */
+/* returns black-height or 0 if failed */
static int hammertree_verify(t_hammertree *tree)
{
return (hammernode_verify(tree->t_root));
}
-static void hammernode_post(t_hammernode *np)
+static int hammernode_checkmulti(t_hammernode *np1, t_hammernode *np2)
{
- startpost("%d %g %d (", np->n_index, np->n_value, np->n_black);
+ if (np1 && np2 && np1->n_key == np2->n_key)
+ {
+ if (np1 == np2)
+ bug("hammernode_checkmulti");
+ else
+ return (1);
+ }
+ return (0);
+}
+
+static void hammernode_post(t_hammertree *tree, t_hammernode *np,
+ t_hammernode_vshowhook hook, char *message)
+{
+ startpost("%d ", np->n_key);
+ if (tree->t_valuetype == HAMMERTYPE_FLOAT)
+ startpost("%g ", HAMMERNODE_GETFLOAT(np));
+ else if (tree->t_valuetype == HAMMERTYPE_SYMBOL)
+ startpost("%s ", HAMMERNODE_GETSYMBOL(np)->s_name);
+ else if (tree->t_valuetype == HAMMERTYPE_ATOM)
+ {
+ t_atom *ap = HAMMERNODE_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)HAMMERNODE_GETSYMBOL(np));
+ startpost("%s ", (np->n_black ? "black" : "red"));
+
+ if (hammernode_checkmulti(np, np->n_parent) ||
+ hammernode_checkmulti(np, np->n_left) ||
+ hammernode_checkmulti(np, np->n_right) ||
+ hammernode_checkmulti(np->n_parent, np->n_left) ||
+ hammernode_checkmulti(np->n_parent, np->n_right) ||
+ hammernode_checkmulti(np->n_left, np->n_right))
+ startpost("multi ");
+
+ if (np->n_parent)
+ startpost("(%d -> ", np->n_parent->n_key);
+ else
+ startpost("(nul -> ");
if (np->n_left)
- startpost("%d, ", np->n_left->n_index);
+ startpost("%d, ", np->n_left->n_key);
else
startpost("nul, ");
if (np->n_right)
- post("%d)", np->n_right->n_index);
+ startpost("%d)", np->n_right->n_key);
else
- post("nul)");
+ startpost("nul)");
+ if (message)
+ post(": %s", message);
+ else
+ endpost();
}
-/* this is a standard stackless traversal, not the best one, obviously...
- (used only for debugging) */
-static int hammertree_traverse(t_hammertree *tree, int postit)
+/* Assert a standard stackless traversal producing the same sequence,
+ as the auxiliary list. */
+static int hammertree_checktraversal(t_hammertree *tree)
{
- t_hammernode *np = tree->t_root;
+ t_hammernode *treewalk = tree->t_root;
+ t_hammernode *listwalk = tree->t_first;
int count = 0;
- while (np)
+ while (treewalk)
{
- t_hammernode *prev = np->n_left;
+ t_hammernode *prev = treewalk->n_left;
if (prev)
{
- while (prev->n_right && prev->n_right != np) prev = prev->n_right;
+ while (prev->n_right && prev->n_right != treewalk)
+ prev = prev->n_right;
if (prev->n_right)
{
prev->n_right = 0;
- if (postit) hammernode_post(np);
count++;
- np = np->n_right;
+ if (treewalk == listwalk)
+ listwalk = listwalk->n_next;
+ else
+ {
+ bug("hammertree_checktraversal 1");
+ hammernode_post(tree, treewalk, 0, "treewalk");
+ if (listwalk)
+ hammernode_post(tree, listwalk, 0, "listwalk");
+ else
+ post("empty listwalk pointer");
+ listwalk = treewalk;
+ }
+ treewalk = treewalk->n_right;
}
else
{
- prev->n_right = np;
- np = np->n_left;
+ prev->n_right = treewalk;
+ treewalk = treewalk->n_left;
}
}
else
{
- if (postit) hammernode_post(np);
count++;
- np = np->n_right;
+ if (treewalk == listwalk)
+ listwalk = listwalk->n_next;
+ else
+ {
+ bug("hammertree_checktraversal 2");
+ hammernode_post(tree, treewalk, 0, "treewalk");
+ if (listwalk)
+ hammernode_post(tree, listwalk, 0, "listwalk");
+ else
+ post("empty listwalk pointer");
+ listwalk = treewalk;
+ }
+ treewalk = treewalk->n_right;
}
}
return (count);
@@ -108,22 +184,39 @@ static int hammernode_height(t_hammernode *np)
else return (0);
}
-void hammertree_debug(t_hammertree *tree, int level)
+void hammertree_debug(t_hammertree *tree, int level,
+ t_hammernode_vshowhook hook)
{
t_hammernode *np;
int count;
post("------------------------");
- count = hammertree_traverse(tree, level);
- if (level > 1)
+ count = hammertree_checktraversal(tree);
+ if (level)
{
- post("***");
- for (np = tree->t_last; np; np = np->n_prev)
- startpost("%d ", np->n_index);
- endpost();
+ for (np = tree->t_first; np; np = np->n_next)
+ hammernode_post(tree, np, hook, 0);
+ if (level > 1)
+ {
+ post("************");
+ for (np = tree->t_last; np; np = np->n_prev)
+ startpost("%d ", np->n_key);
+ endpost();
+ }
}
- post("count %d, height %d, root %d:",
- count, hammernode_height(tree->t_root),
- (tree->t_root ? tree->t_root->n_index : 0));
+ if (tree->t_root)
+ {
+ t_hammernode *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 %d",
+ count, hammernode_height(tree->t_root), tree->t_root->n_key);
+ post("first %d, root->left* %d, last %d, root->right* %d",
+ (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)", hammertree_verify(tree));
post("------------------------");
}
@@ -161,33 +254,101 @@ static void hammertree_rrotate(t_hammertree *tree, t_hammernode *np)
np->n_parent = target;
}
-/* returns a newly inserted or already existing node
- (or 0 if allocation failed) */
-t_hammernode *hammertree_insert(t_hammertree *tree, int ndx)
+static t_hammernode *hammertree_preinserthook(t_hammernode *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("hammertree_preinserthook");
+ return (0); /* do nothing */
+ }
+ }
+ return (np);
+}
+
+static t_hammernode *hammertree_postinserthook(t_hammernode *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("hammertree_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_hammernode *hammertree_doinsert(t_hammertree *tree, int key,
+ t_hammertree_inserthook hook,
+ int *foundp)
{
t_hammernode *np, *parent, *result;
+ int leftchild;
+ *foundp = 0;
if (!(np = tree->t_root))
{
- if (!(np = getbytes(sizeof(*np))))
+ if (!(np = getbytes(tree->t_nodesize)))
return (0);
- np->n_index = ndx;
+ np->n_key = key;
np->n_black = 1;
tree->t_root = tree->t_first = tree->t_last = np;
return (np);
}
do
- if (np->n_index == ndx)
- return (np);
- else
- parent = np;
- while (np = (ndx < np->n_index ? np->n_left : np->n_right));
-
- if (!(np = getbytes(sizeof(*np))))
+ {
+ if (np->n_key == key)
+ {
+ *foundp = 1;
+ if (hook && (parent = (*hook)(np)))
+ {
+ if (parent->n_left && parent->n_right)
+ {
+ bug("hammertree_insert, callback return 1");
+ parent = parent->n_next;
+ }
+ if (leftchild = (key < parent->n_key))
+ {
+ if (parent->n_left)
+ {
+ bug("hammertree_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_index = ndx;
+ np->n_key = key;
np->n_parent = parent;
- if (ndx < parent->n_index)
+ if (leftchild)
{
parent->n_left = np;
/* update the auxiliary linked list structure */
@@ -269,35 +430,63 @@ t_hammernode *hammertree_insert(t_hammertree *tree, int ndx)
}
/* assuming that requested node exists */
-void hammertree_delete(t_hammertree *tree, t_hammernode *np)
+void hammertree_delete(t_hammertree *tree, t_hammernode *gone)
{
- t_hammernode *gone, *parent, *child;
- /* gone is the actual node to be deleted
- -- it has to be the parent of no more than one child: */
- if (np->n_left && np->n_right)
+ t_hammernode *parent; /* parent of gone, after relinking */
+ t_hammernode *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)
{
- gone = np->n_next; /* gone always exists */
- child = gone->n_right; /* there is no left child of gone */
- /* gone is not a requested node, so we replace fields to be
- deleted with gone's fields: */
- np->n_index = gone->n_index;
- np->n_value = gone->n_value;
+ /* 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_hammernode *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 */
- /* np->n_prev is up-to-date */
- if (np->n_prev)
- np->n_prev->n_next = np;
- else tree->t_first = np;
- if (np->n_next = gone->n_next)
- np->n_next->n_prev = np;
- else tree->t_last = np;
+ if (successor->n_prev = gone->n_prev)
+ gone->n_prev->n_next = successor;
+ else
+ tree->t_first = successor;
}
else
{
- gone = np;
- if (gone->n_left)
- child = gone->n_left;
- else
- child = gone->n_right;
/* update the auxiliary linked list structure */
if (gone->n_prev)
gone->n_prev->n_next = gone->n_next;
@@ -307,25 +496,30 @@ void hammertree_delete(t_hammertree *tree, t_hammernode *np)
gone->n_next->n_prev = gone->n_prev;
else
tree->t_last = gone->n_prev;
- }
- /* connect gone's child with gone's parent */
- if (!(parent = gone->n_parent))
- {
- if (tree->t_root = child)
+
+ /* 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)
{
- child->n_parent = 0;
- child->n_black = 1; /* LATER rethink */
+ if (child) /* (sentinel not used) */
+ child->n_parent = parent;
+ if (gone == parent->n_left)
+ parent->n_left = child;
+ else
+ parent->n_right = child;
}
- goto done;
- }
- else
- {
- if (child) /* (sentinel not used) */
- child->n_parent = parent;
- if (gone == parent->n_left)
- parent->n_left = child;
else
- parent->n_right = child;
+ {
+ if (tree->t_root = child)
+ {
+ child->n_parent = 0;
+ child->n_black = 1; /* LATER rethink */
+ }
+ goto done;
+ }
}
if (gone->n_black)
@@ -431,41 +625,149 @@ void hammertree_delete(t_hammertree *tree, t_hammernode *np)
child->n_black = 1;
}
done:
- freebytes(gone, sizeof(*gone));
+ freebytes(gone, tree->t_nodesize);
#ifdef HAMMERTREE_DEBUG
hammertree_verify(tree);
#endif
}
-t_hammernode *hammertree_search(t_hammertree *tree, int ndx)
+t_hammernode *hammertree_search(t_hammertree *tree, int key)
{
t_hammernode *np = tree->t_root;
- while (np && np->n_index != ndx)
- np = (ndx < np->n_index ? np->n_left : np->n_right);
+ while (np && np->n_key != key)
+ np = (key < np->n_key ? np->n_left : np->n_right);
return (np);
}
-t_hammernode *hammertree_closest(t_hammertree *tree, int ndx, int geqflag)
+t_hammernode *hammertree_closest(t_hammertree *tree, int key, int geqflag)
{
t_hammernode *np, *parent;
if (!(np = tree->t_root))
return (0);
do
- if (np->n_index == ndx)
+ if (np->n_key == key)
return (np);
else
parent = np;
- while (np = (ndx < np->n_index ? np->n_left : np->n_right));
+ while (np = (key < np->n_key ? np->n_left : np->n_right));
if (geqflag)
- return (ndx > parent->n_index ? parent->n_next : parent);
+ return (key > parent->n_key ? parent->n_next : parent);
else
- return (ndx < parent->n_index ? parent->n_prev : parent);
+ return (key < parent->n_key ? parent->n_prev : parent);
+}
+
+t_hammernode *hammertree_insert(t_hammertree *tree, int key, int *foundp)
+{
+ return (hammertree_doinsert(tree, key, 0, foundp));
+}
+
+t_hammernode *hammertree_multiinsert(t_hammertree *tree, int key, int fifoflag)
+{
+ int found;
+ return (hammertree_doinsert(tree, key, (fifoflag ?
+ hammertree_postinserthook :
+ hammertree_preinserthook), &found));
+}
+
+t_hammernode *hammertree_insertfloat(t_hammertree *tree, int key, t_float f,
+ int replaceflag)
+{
+ int found;
+ t_hammernode *np = hammertree_doinsert(tree, key, 0, &found);
+ if (np && (!found || replaceflag))
+ {
+ if (tree->t_valuetype == HAMMERTYPE_FLOAT)
+ {
+ t_hammernode_float *npf = (t_hammernode_float *)np;
+ npf->nf_value = f;
+ }
+ else if (tree->t_valuetype == HAMMERTYPE_ATOM)
+ {
+ t_hammernode_atom *npa = (t_hammernode_atom *)np;
+ t_atom *ap = &npa->na_value;
+ SETFLOAT(ap, f);
+ }
+ else bug("hammertree_insertfloat");
+ }
+ return (np);
+}
+
+t_hammernode *hammertree_insertsymbol(t_hammertree *tree, int key, t_symbol *s,
+ int replaceflag)
+{
+ int found;
+ t_hammernode *np = hammertree_doinsert(tree, key, 0, &found);
+ if (np && (!found || replaceflag))
+ {
+ if (tree->t_valuetype == HAMMERTYPE_SYMBOL)
+ {
+ t_hammernode_symbol *nps = (t_hammernode_symbol *)np;
+ nps->ns_value = s;
+ }
+ else if (tree->t_valuetype == HAMMERTYPE_ATOM)
+ {
+ t_hammernode_atom *npa = (t_hammernode_atom *)np;
+ t_atom *ap = &npa->na_value;
+ SETSYMBOL(ap, s);
+ }
+ else bug("hammertree_insertsymbol");
+ }
+ return (np);
+}
+
+t_hammernode *hammertree_insertatom(t_hammertree *tree, int key, t_atom *ap,
+ int replaceflag)
+{
+ int found;
+ t_hammernode *np = hammertree_doinsert(tree, key, 0, &found);
+ if (np && (!found || replaceflag))
+ {
+ if (tree->t_valuetype == HAMMERTYPE_ATOM)
+ {
+ t_hammernode_atom *npa = (t_hammernode_atom *)np;
+ npa->na_value = *ap;
+ }
+ else bug("hammertree_insertatom");
+ }
+ return (np);
}
/* LATER preallocate 'freecount' nodes */
-void hammertree_init(t_hammertree *tree, int freecount)
+static void hammertree_doinit(t_hammertree *tree, t_hammertype 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 hammertree_inittyped(t_hammertree *tree,
+ t_hammertype vtype, int freecount)
+{
+ size_t nsize;
+ switch (vtype)
+ {
+ case HAMMERTYPE_FLOAT:
+ nsize = sizeof(t_hammernode_float);
+ break;
+ case HAMMERTYPE_SYMBOL:
+ nsize = sizeof(t_hammernode_symbol);
+ break;
+ case HAMMERTYPE_ATOM:
+ nsize = sizeof(t_hammernode_atom);
+ break;
+ default:
+ bug("hammertree_inittyped");
+ vtype = HAMMERTYPE_ILLEGAL;
+ nsize = sizeof(t_hammernode);
+ }
+ hammertree_doinit(tree, vtype, nsize, freecount);
+}
+
+void hammertree_initcustom(t_hammertree *tree,
+ size_t nodesize, int freecount)
+{
+ hammertree_doinit(tree, HAMMERTYPE_CUSTOM, nodesize, freecount);
}
/* LATER keep and/or preallocate 'freecount' nodes (if negative, keep all) */
@@ -476,7 +778,7 @@ void hammertree_clear(t_hammertree *tree, int freecount)
{
np = next;
next = next->n_next;
- freebytes(np, sizeof(*np));
+ freebytes(np, tree->t_nodesize);
}
- hammertree_init(tree, 0);
+ hammertree_doinit(tree, tree->t_valuetype, tree->t_nodesize, 0);
}