diff options
Diffstat (limited to 'shared/hammer')
| -rw-r--r-- | shared/hammer/gui.c | 224 | ||||
| -rw-r--r-- | shared/hammer/gui.h | 14 | ||||
| -rw-r--r-- | shared/hammer/tree.c | 494 | ||||
| -rw-r--r-- | shared/hammer/tree.h | 67 |
4 files changed, 612 insertions, 187 deletions
diff --git a/shared/hammer/gui.c b/shared/hammer/gui.c index ec6add7..7106a0a 100644 --- a/shared/hammer/gui.c +++ b/shared/hammer/gui.c @@ -5,6 +5,7 @@ /* FIXME use guiconnect */ #include <stdio.h> +#include <string.h> #include "m_pd.h" #include "g_canvas.h" #include "hammer/gui.h" @@ -12,7 +13,9 @@ //#define HAMMERGUI_DEBUG static t_class *hammergui_class = 0; -static t_hammergui *sink = 0; +static t_hammergui *hammergui_sink = 0; +static t_symbol *ps_hashhammergui; +static t_symbol *ps__hammergui; static t_symbol *ps__up; static t_symbol *ps__focus; static t_symbol *ps__vised; @@ -26,7 +29,7 @@ static void hammergui_anything(t_hammergui *snk, #ifdef HAMMERGUI_DEBUG startpost("%s", s->s_name); postatom(ac, av); - endpost(); + post(" (sink %x)", (int)snk); #endif } @@ -34,31 +37,36 @@ static void hammergui_anything(t_hammergui *snk, static void hammergui__up(t_hammergui *snk, t_floatarg f) { #ifdef HAMMERGUI_DEBUG - post("_up %g", f); + post("_up %g (sink %x)", f, (int)snk); #endif + if (!snk->g_psmouse) + { + bug("hammergui__up"); + return; + } if ((int)f) { - if (!snk->g_up) + if (!snk->g_isup) { - snk->g_up = 1; - if (snk->g_mouse->s_thing) + snk->g_isup = 1; + if (snk->g_psmouse->s_thing) { t_atom at; SETFLOAT(&at, 1); - pd_typedmess(snk->g_mouse->s_thing, ps__up, 1, &at); + pd_typedmess(snk->g_psmouse->s_thing, ps__up, 1, &at); } } } else { - if (snk->g_up) + if (snk->g_isup) { - snk->g_up = 0; - if (snk->g_mouse->s_thing) + snk->g_isup = 0; + if (snk->g_psmouse->s_thing) { t_atom at; SETFLOAT(&at, 0); - pd_typedmess(snk->g_mouse->s_thing, ps__up, 1, &at); + pd_typedmess(snk->g_psmouse->s_thing, ps__up, 1, &at); } } } @@ -67,28 +75,38 @@ static void hammergui__up(t_hammergui *snk, t_floatarg f) static void hammergui__focus(t_hammergui *snk, t_symbol *s, t_floatarg f) { #ifdef HAMMERGUI_DEBUG - if (s) post("_focus %s %g", s->s_name, f); + post("_focus %s %g (sink %x)", (s ? s->s_name : "???"), f, (int)snk); #endif - if (snk->g_focus->s_thing) + if (!snk->g_psfocus) + { + bug("hammergui__focus"); + return; + } + if (snk->g_psfocus->s_thing) { t_atom at[2]; SETSYMBOL(&at[0], s); SETFLOAT(&at[1], f); - pd_typedmess(snk->g_focus->s_thing, ps__focus, 2, at); + pd_typedmess(snk->g_psfocus->s_thing, ps__focus, 2, at); } } static void hammergui__vised(t_hammergui *snk, t_symbol *s, t_floatarg f) { #ifdef HAMMERGUI_DEBUG - if (s) post("_vised %s %g", s->s_name, f); + post("_vised %s %g (sink %x)", (s ? s->s_name : "???"), f, (int)snk); #endif - if (snk->g_vised->s_thing) + if (!snk->g_psvised) + { + bug("hammergui__vised"); + return; + } + if (snk->g_psvised->s_thing) { t_atom at[2]; SETSYMBOL(&at[0], s); SETFLOAT(&at[1], f); - pd_typedmess(snk->g_vised->s_thing, ps__vised, 2, at); + pd_typedmess(snk->g_psvised->s_thing, ps__vised, 2, at); } #if 0 /* How to be notified about changes of button state, prior to gui objects @@ -101,23 +119,31 @@ static void hammergui__vised(t_hammergui *snk, t_symbol *s, t_floatarg f) static void hammergui_dobindmouse(t_hammergui *snk) { +#ifdef HAMMERGUI_DEBUG + post("dobindmouse (sink %x)", (int)snk); +#endif #if 0 /* How to be notified about changes of button state, prior to gui objects in a canvas? LATER find a reliable way -- delete if failed */ sys_vgui("bind hammertag <<hammerdown>> {pd [concat %s _up 0 \\;]}\n", - snk->g_gui->s_name); + snk->g_psgui->s_name); sys_vgui("bind hammertag <<hammerup>> {pd [concat %s _up 1 \\;]}\n", - snk->g_gui->s_name); + snk->g_psgui->s_name); #endif sys_vgui("bind all <<hammerdown>> {pd [concat %s _up 0 \\;]}\n", - snk->g_gui->s_name); + snk->g_psgui->s_name); sys_vgui("bind all <<hammerup>> {pd [concat %s _up 1 \\;]}\n", - snk->g_gui->s_name); + snk->g_psgui->s_name); } static void hammergui__remouse(t_hammergui *snk) { - if (snk->g_mouse->s_thing) + if (!snk->g_psmouse) + { + bug("hammergui__remouse"); + return; + } + if (snk->g_psmouse->s_thing) { /* if a new master was bound in a gray period, we need to restore gui bindings */ @@ -132,15 +158,20 @@ static void hammergui_dobindfocus(t_hammergui *snk) { sys_vgui("bind Canvas <<hammerfocusin>> \ {if {[hammergui_ispatcher %%W]} \ - {pd [concat %s _focus %%W 1 \\;]}}\n", snk->g_gui->s_name); + {pd [concat %s _focus %%W 1 \\;]}}\n", snk->g_psgui->s_name); sys_vgui("bind Canvas <<hammerfocusout>> \ {if {[hammergui_ispatcher %%W]} \ - {pd [concat %s _focus %%W 0 \\;]}}\n", snk->g_gui->s_name); + {pd [concat %s _focus %%W 0 \\;]}}\n", snk->g_psgui->s_name); } static void hammergui__refocus(t_hammergui *snk) { - if (snk->g_focus->s_thing) + if (!snk->g_psfocus) + { + bug("hammergui__refocus"); + return; + } + if (snk->g_psfocus->s_thing) { /* if a new master was bound in a gray period, we need to restore gui bindings */ @@ -153,17 +184,25 @@ static void hammergui__refocus(t_hammergui *snk) static void hammergui_dobindvised(t_hammergui *snk) { +#ifdef HAMMERGUI_DEBUG + post("dobindvised (sink %x)", (int)snk); +#endif sys_vgui("bind Canvas <<hammervised>> \ {if {[hammergui_ispatcher %%W]} \ - {pd [concat %s _vised %%W 1 \\;]}}\n", snk->g_gui->s_name); + {pd [concat %s _vised %%W 1 \\;]}}\n", snk->g_psgui->s_name); sys_vgui("bind Canvas <<hammerunvised>> \ {if {[hammergui_ispatcher %%W]} \ - {pd [concat %s _vised %%W 0 \\;]}}\n", snk->g_gui->s_name); + {pd [concat %s _vised %%W 0 \\;]}}\n", snk->g_psgui->s_name); } static void hammergui__revised(t_hammergui *snk) { - if (snk->g_vised->s_thing) + if (!snk->g_psvised) + { + bug("hammergui__revised"); + return; + } + if (snk->g_psvised->s_thing) { /* if a new master was bound in a gray period, we need to restore gui bindings */ @@ -174,9 +213,35 @@ static void hammergui__revised(t_hammergui *snk) } } -static void hammergui_setup(void) +static int hammergui_setup(void) { - hammergui_class = class_new(gensym("_hammergui"), 0, 0, + ps_hashhammergui = gensym("#hammergui"); + ps__hammergui = gensym("_hammergui"); + ps__up = gensym("_up"); + ps__focus = gensym("_focus"); + ps__vised = gensym("_vised"); + if (ps_hashhammergui->s_thing) + { + char *cname = class_getname(*ps_hashhammergui->s_thing); +#ifdef HAMMERGUI_DEBUG + post("'%s' already registered as the global hammergui sink ", + (cname ? cname : "???")); +#endif + if (strcmp(cname, ps__hammergui->s_name)) + { + /* FIXME protect against the danger of someone else + (e.g. receive) binding to #hammergui */ + bug("hammergui_setup"); + return (0); + } + else + { + /* FIXME compatibility test */ + hammergui_class = *ps_hashhammergui->s_thing; + return (1); + } + } + hammergui_class = class_new(ps__hammergui, 0, 0, sizeof(t_hammergui), CLASS_PD | CLASS_NOINLET, 0); class_addanything(hammergui_class, hammergui_anything); @@ -186,13 +251,10 @@ static void hammergui_setup(void) gensym("_refocus"), 0); class_addmethod(hammergui_class, (t_method)hammergui__revised, gensym("_revised"), 0); - ps__up = gensym("_up"); class_addmethod(hammergui_class, (t_method)hammergui__up, ps__up, A_FLOAT, 0); - ps__focus = gensym("_focus"); class_addmethod(hammergui_class, (t_method)hammergui__focus, ps__focus, A_SYMBOL, A_FLOAT, 0); - ps__vised = gensym("_vised"); class_addmethod(hammergui_class, (t_method)hammergui__vised, ps__vised, A_SYMBOL, A_FLOAT, 0); @@ -255,21 +317,25 @@ static void hammergui_setup(void) sys_gui(" bind Canvas <<hammerunvised>> {}\n"); sys_gui(" pd [concat #hammergui _revised \\;]\n"); sys_gui("}\n"); + return (1); } static int hammergui_validate(int dosetup) { - if (dosetup) + if (dosetup && !hammergui_sink + && (hammergui_class || hammergui_setup())) { - if (!hammergui_class) hammergui_setup(); - if (!sink) + if (ps_hashhammergui->s_thing) + hammergui_sink = (t_hammergui *)ps_hashhammergui->s_thing; + else { - sink = (t_hammergui *)pd_new(hammergui_class); - sink->g_gui = gensym("#hammergui"); - pd_bind((t_pd *)sink, sink->g_gui); + hammergui_sink = (t_hammergui *)pd_new(hammergui_class); + hammergui_sink->g_psgui = ps_hashhammergui; + pd_bind((t_pd *)hammergui_sink, + ps_hashhammergui); /* never unbound */ } } - if (hammergui_class && sink) + if (hammergui_class && hammergui_sink) return (1); else { @@ -280,13 +346,13 @@ static int hammergui_validate(int dosetup) static int hammergui_mousevalidate(int dosetup) { - if (dosetup && !sink->g_mouse) + if (dosetup && !hammergui_sink->g_psmouse) { - sink->g_mouse = gensym("#hammermouse"); + hammergui_sink->g_psmouse = gensym("#hammermouse"); sys_gui("event add <<hammerdown>> <ButtonPress>\n"); sys_gui("event add <<hammerup>> <ButtonRelease>\n"); } - if (sink->g_mouse) + if (hammergui_sink->g_psmouse) return (1); else { @@ -297,12 +363,13 @@ static int hammergui_mousevalidate(int dosetup) static int hammergui_pollvalidate(int dosetup) { - if (dosetup && !sink->g_poll) + if (dosetup && !hammergui_sink->g_pspoll) { - sink->g_poll = gensym("#hammerpoll"); - pd_bind((t_pd *)sink, sink->g_poll); /* never unbound */ + hammergui_sink->g_pspoll = gensym("#hammerpoll"); + pd_bind((t_pd *)hammergui_sink, + hammergui_sink->g_pspoll); /* never unbound */ } - if (sink->g_poll) + if (hammergui_sink->g_pspoll) return (1); else { @@ -313,13 +380,13 @@ static int hammergui_pollvalidate(int dosetup) static int hammergui_focusvalidate(int dosetup) { - if (dosetup && !sink->g_focus) + if (dosetup && !hammergui_sink->g_psfocus) { - sink->g_focus = gensym("#hammerfocus"); + hammergui_sink->g_psfocus = gensym("#hammerfocus"); sys_gui("event add <<hammerfocusin>> <FocusIn>\n"); sys_gui("event add <<hammerfocusout>> <FocusOut>\n"); } - if (sink->g_focus) + if (hammergui_sink->g_psfocus) return (1); else { @@ -330,15 +397,15 @@ static int hammergui_focusvalidate(int dosetup) static int hammergui_visedvalidate(int dosetup) { - if (dosetup && !sink->g_vised) + if (dosetup && !hammergui_sink->g_psvised) { - sink->g_vised = gensym("#hammervised"); + hammergui_sink->g_psvised = gensym("#hammervised"); /* subsequent map events have to be filtered out at the caller's side, LATER investigate */ sys_gui("event add <<hammervised>> <Map>\n"); sys_gui("event add <<hammerunvised>> <Destroy>\n"); } - if (sink->g_vised) + if (hammergui_sink->g_psvised) return (1); else { @@ -349,20 +416,23 @@ static int hammergui_visedvalidate(int dosetup) void hammergui_bindmouse(t_pd *master) { +#ifdef HAMMERGUI_DEBUG + post("bindmouse, master %x", (int)master); +#endif hammergui_validate(1); hammergui_mousevalidate(1); - if (!sink->g_mouse->s_thing) - hammergui_dobindmouse(sink); - pd_bind(master, sink->g_mouse); + if (!hammergui_sink->g_psmouse->s_thing) + hammergui_dobindmouse(hammergui_sink); + pd_bind(master, hammergui_sink->g_psmouse); } void hammergui_unbindmouse(t_pd *master) { if (hammergui_validate(0) && hammergui_mousevalidate(0) - && sink->g_mouse->s_thing) + && hammergui_sink->g_psmouse->s_thing) { - pd_unbind(master, sink->g_mouse); - if (!sink->g_mouse->s_thing) + pd_unbind(master, hammergui_sink->g_psmouse); + if (!hammergui_sink->g_psmouse->s_thing) sys_gui("hammergui_remouse\n"); } else bug("hammergui_unbindmouse"); @@ -384,8 +454,9 @@ void hammergui_startpolling(t_pd *master) { if (hammergui_validate(0) && hammergui_pollvalidate(0)) { - int doinit = (sink->g_poll->s_thing == (t_pd *)sink); - pd_bind(master, sink->g_poll); + int doinit = + (hammergui_sink->g_pspoll->s_thing == (t_pd *)hammergui_sink); + pd_bind(master, hammergui_sink->g_pspoll); if (doinit) { /* visibility hack for msw, LATER rethink */ @@ -400,8 +471,8 @@ void hammergui_stoppolling(t_pd *master) { if (hammergui_validate(0) && hammergui_pollvalidate(0)) { - pd_unbind(master, sink->g_poll); - if (sink->g_poll->s_thing == (t_pd *)sink) + pd_unbind(master, hammergui_sink->g_pspoll); + if (hammergui_sink->g_pspoll->s_thing == (t_pd *)hammergui_sink) { sys_gui("after cancel hammergui_poll\n"); /* visibility hack for msw, LATER rethink */ @@ -415,18 +486,18 @@ void hammergui_bindfocus(t_pd *master) { hammergui_validate(1); hammergui_focusvalidate(1); - if (!sink->g_focus->s_thing) - hammergui_dobindfocus(sink); - pd_bind(master, sink->g_focus); + if (!hammergui_sink->g_psfocus->s_thing) + hammergui_dobindfocus(hammergui_sink); + pd_bind(master, hammergui_sink->g_psfocus); } void hammergui_unbindfocus(t_pd *master) { if (hammergui_validate(0) && hammergui_focusvalidate(0) - && sink->g_focus->s_thing) + && hammergui_sink->g_psfocus->s_thing) { - pd_unbind(master, sink->g_focus); - if (!sink->g_focus->s_thing) + pd_unbind(master, hammergui_sink->g_psfocus); + if (!hammergui_sink->g_psfocus->s_thing) sys_gui("hammergui_refocus\n"); } else bug("hammergui_unbindfocus"); @@ -434,20 +505,23 @@ void hammergui_unbindfocus(t_pd *master) void hammergui_bindvised(t_pd *master) { +#ifdef HAMMERGUI_DEBUG + post("bindvised, master %x", (int)master); +#endif hammergui_validate(1); hammergui_visedvalidate(1); - if (!sink->g_vised->s_thing) - hammergui_dobindvised(sink); - pd_bind(master, sink->g_vised); + if (!hammergui_sink->g_psvised->s_thing) + hammergui_dobindvised(hammergui_sink); + pd_bind(master, hammergui_sink->g_psvised); } void hammergui_unbindvised(t_pd *master) { if (hammergui_validate(0) && hammergui_visedvalidate(0) - && sink->g_vised->s_thing) + && hammergui_sink->g_psvised->s_thing) { - pd_unbind(master, sink->g_vised); - if (!sink->g_vised->s_thing) + pd_unbind(master, hammergui_sink->g_psvised); + if (!hammergui_sink->g_psvised->s_thing) sys_gui("hammergui_revised\n"); } else bug("hammergui_unbindvised"); diff --git a/shared/hammer/gui.h b/shared/hammer/gui.h index 13afd0a..3cab055 100644 --- a/shared/hammer/gui.h +++ b/shared/hammer/gui.h @@ -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. */ @@ -8,12 +8,12 @@ typedef struct _hammergui { t_pd g_pd; - t_symbol *g_gui; - t_symbol *g_mouse; - t_symbol *g_poll; - t_symbol *g_focus; - t_symbol *g_vised; - int g_up; + t_symbol *g_psgui; + t_symbol *g_psmouse; + t_symbol *g_pspoll; + t_symbol *g_psfocus; + t_symbol *g_psvised; + int g_isup; } t_hammergui; void hammergui_bindmouse(t_pd *master); 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); } diff --git a/shared/hammer/tree.h b/shared/hammer/tree.h index fcbc036..368fed2 100644 --- a/shared/hammer/tree.h +++ b/shared/hammer/tree.h @@ -1,17 +1,24 @@ -/* 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. */ #ifndef __HAMMERTREE_H__ #define __HAMMERTREE_H__ +#ifdef KRZYSZCZ #define HAMMERTREE_DEBUG +#endif + +typedef enum +{ + HAMMERTYPE_FLOAT, HAMMERTYPE_SYMBOL, HAMMERTYPE_ATOM, + HAMMERTYPE_CUSTOM, HAMMERTYPE_ILLEGAL +} t_hammertype; typedef struct _hammernode { - int n_index; - float n_value; - int n_black; + int n_key; + int n_black; struct _hammernode *n_left; struct _hammernode *n_right; struct _hammernode *n_parent; @@ -19,19 +26,61 @@ typedef struct _hammernode struct _hammernode *n_next; } t_hammernode; +typedef struct _hammernode_float +{ + t_hammernode nf_node; + t_float nf_value; +} t_hammernode_float; + +typedef struct _hammernode_symbol +{ + t_hammernode ns_node; + t_symbol *ns_value; +} t_hammernode_symbol; + +typedef struct _hammernode_atom +{ + t_hammernode na_node; + t_atom na_value; +} t_hammernode_atom; + typedef struct _hammertree { t_hammernode *t_root; t_hammernode *t_first; t_hammernode *t_last; + t_hammertype t_valuetype; + size_t t_nodesize; } t_hammertree; -t_hammernode *hammertree_insert(t_hammertree *tree, int ndx); +#define HAMMERNODE_GETFLOAT(np) (((t_hammernode_float *)(np))->nf_value) +#define HAMMERNODE_GETSYMBOL(np) (((t_hammernode_symbol *)(np))->ns_value) +#define HAMMERNODE_GETATOMPTR(np) (&((t_hammernode_atom *)(np))->na_value) + +typedef void (*t_hammernode_vshowhook)(t_hammernode *, char *, unsigned); + +t_hammernode *hammertree_search(t_hammertree *tree, int key); +t_hammernode *hammertree_closest(t_hammertree *tree, int key, int geqflag); + +t_hammernode *hammertree_insert(t_hammertree *tree, int key, int *foundp); +t_hammernode *hammertree_multiinsert(t_hammertree *tree, int key, int fifoflag); +t_hammernode *hammertree_insertfloat(t_hammertree *tree, int key, t_float f, + int replaceflag); +t_hammernode *hammertree_insertsymbol(t_hammertree *tree, int key, t_symbol *s, + int replaceflag); +t_hammernode *hammertree_insertatom(t_hammertree *tree, int key, t_atom *ap, + int replaceflag); void hammertree_delete(t_hammertree *tree, t_hammernode *np); -t_hammernode *hammertree_search(t_hammertree *tree, int ndx); -t_hammernode *hammertree_closest(t_hammertree *tree, int ndx, int geqflag); -void hammertree_init(t_hammertree *tree, int freecount); + +void hammertree_inittyped(t_hammertree *tree, + t_hammertype vtype, int freecount); +void hammertree_initcustom(t_hammertree *tree, + size_t nodesize, int freecount); void hammertree_clear(t_hammertree *tree, int freecount); -void hammertree_debug(t_hammertree *tree, int level); + +#ifdef HAMMERTREE_DEBUG +void hammertree_debug(t_hammertree *tree, int level, + t_hammernode_vshowhook hook); +#endif #endif |