From 822b6eabf733011dbbb8b22b0daa860578182eac Mon Sep 17 00:00:00 2001 From: "N.N." Date: Fri, 26 Sep 2003 07:29:14 +0000 Subject: *** empty log message *** svn path=/trunk/externals/miXed/; revision=1046 --- shared/common/dict.c | 265 +++++++++++++++++++++++++++++++++++++++++++++++++++ shared/common/dict.h | 27 ++++++ 2 files changed, 292 insertions(+) create mode 100644 shared/common/dict.c create mode 100644 shared/common/dict.h (limited to 'shared/common') diff --git a/shared/common/dict.c b/shared/common/dict.c new file mode 100644 index 0000000..33ee365 --- /dev/null +++ b/shared/common/dict.c @@ -0,0 +1,265 @@ +/* Copyright (c) 1997-2003 Miller Puckette, krzYszcz, and others. + * For information on usage and redistribution, and for a DISCLAIMER OF ALL + * WARRANTIES, see the file, "LICENSE.txt," in this distribution. */ + +/* this is merely an abstraction layer over gensym() from m_class.c + with various additions adapted from m_pd.c */ + +#include +#include +#include "m_pd.h" +#include "common/dict.h" + +#define DICT_VERBOSE +//#define DICT_DEBUG + +#define DICT_HASHSIZE_DEFAULT 1024 +#define DICT_HASHSIZE_MIN 8 +#define DICT_HASHSIZE_MAX 16384 + +/* two structures local to m_pd.c */ +typedef struct _dict_bindelem +{ + t_pd *e_who; + struct _dict_bindelem *e_next; +} t_dict_bindelem; + +typedef struct _dict_bindlist +{ + t_pd b_pd; + t_dict_bindelem *b_list; +} t_dict_bindlist; + +/* adapted bindlist_anything() from m_pd.c */ +static void dict_bindlist_anything(t_dict_bindlist *x, t_symbol *s, + int argc, t_atom *argv) +{ + t_dict_bindelem *e; + for (e = x->b_list; e; e = e->e_next) + pd_typedmess(e->e_who, s, argc, argv); +} + +/* adapted m_pd_setup() from m_pd.c */ +static void dict_bindlist_setup(t_dict *x) +{ + x->d_bindlist_class = class_new(dict_key(x, "bindlist"), 0, 0, + sizeof(t_dict_bindlist), CLASS_PD, 0); + class_addanything(x->d_bindlist_class, dict_bindlist_anything); +} + +t_dict *dict_new(size_t hashsize) +{ + t_dict *x = getbytes(sizeof(*x)); + size_t sz; + if (x) + { + if (!hashsize) + sz = DICT_HASHSIZE_DEFAULT; + else if (hashsize >= DICT_HASHSIZE_MAX) + sz = DICT_HASHSIZE_MAX; + else if (hashsize <= DICT_HASHSIZE_MIN) + sz = DICT_HASHSIZE_MIN; + else for (sz = DICT_HASHSIZE_MAX; sz > DICT_HASHSIZE_MIN; sz >>= 1) + if (sz <= hashsize) break; +#ifdef DICT_DEBUG + post("allocating dictionary with %d-element hashtable", sz); +#endif + if (x->d_hashtable = + getbytes((x->d_hashsize = sz) * sizeof(*x->d_hashtable))) + { + dict_bindlist_setup(x); + return (x); + } + freebytes(x, sizeof(*x)); + } + return (0); +} + +void dict_free(t_dict *x) +{ + if (x->d_hashtable) + freebytes(x->d_hashtable, x->d_hashsize * sizeof(*x->d_hashtable)); + freebytes(x, sizeof(*x)); +} + +/* adapted dogensym() from m_class.c */ +t_symbol *dict_dokey(t_dict *x, char *s, t_symbol *oldsym) +{ + t_symbol **sym1, *sym2; + unsigned int hash1 = 0, hash2 = 0; + int length = 0; + char *s2 = s; + int mask = x->d_hashsize - 1; +#ifdef DICT_DEBUG + startpost("make symbol-key from \"%s\"", s); +#endif + while (*s2) + { + hash1 += *s2; + hash2 += hash1; + length++; + s2++; + } + sym1 = x->d_hashtable + (hash2 & mask); +#ifdef DICT_DEBUG + post(" in slot %d", (hash2 & mask)); +#endif + while (sym2 = *sym1) + { +#ifdef DICT_DEBUG + post("try \"%s\"", sym2->s_name); +#endif + if (!strcmp(sym2->s_name, s)) + { +#ifdef DICT_DEBUG + post("found at address %x", (int)sym2); +#endif + return(sym2); + } + sym1 = &sym2->s_next; + } + if (oldsym) sym2 = oldsym; + else + { + sym2 = (t_symbol *)t_getbytes(sizeof(*sym2)); + sym2->s_name = t_getbytes(length+1); + sym2->s_next = 0; + sym2->s_thing = 0; + strcpy(sym2->s_name, s); + } + *sym1 = sym2; +#ifdef DICT_DEBUG + post("appended at address %x", (int)sym2); +#endif + return (sym2); +} + +/* adapted gensym() from m_class.c */ +t_symbol *dict_key(t_dict *x, char *s) +{ + return (dict_dokey(x, s, 0)); +} + +/* adapted pd_bind() from m_pd.c */ +void dict_bind(t_dict *x, t_pd *obj, t_symbol *s) +{ +#ifdef DICT_DEBUG + post("bind %x to \"%s\" at %x", (int)obj, s->s_name, (int)s); +#endif + if (s->s_thing) + { +#ifdef DICT_DEBUG + post("(next one)"); +#endif + if (*s->s_thing == x->d_bindlist_class) + { + t_dict_bindlist *b = (t_dict_bindlist *)s->s_thing; + t_dict_bindelem *e = + (t_dict_bindelem *)getbytes(sizeof(t_dict_bindelem)); + e->e_next = b->b_list; + e->e_who = obj; + b->b_list = e; + } + else + { + t_dict_bindlist *b = + (t_dict_bindlist *)pd_new(x->d_bindlist_class); + t_dict_bindelem *e1 = + (t_dict_bindelem *)getbytes(sizeof(t_dict_bindelem)); + t_dict_bindelem *e2 = + (t_dict_bindelem *)getbytes(sizeof(t_dict_bindelem)); + b->b_list = e1; + e1->e_who = obj; + e1->e_next = e2; + e2->e_who = s->s_thing; + e2->e_next = 0; + s->s_thing = &b->b_pd; + } + } + else s->s_thing = obj; +} + +/* adapted pd_unbind() from m_pd.c */ +void dict_unbind(t_dict *x, t_pd *obj, t_symbol *s) +{ +#ifdef DICT_DEBUG + post("unbind %x from \"%s\" at %x", (int)obj, s->s_name, (int)s); +#endif + if (s->s_thing == obj) s->s_thing = 0; + else if (s->s_thing && *s->s_thing == x->d_bindlist_class) + { + /* bindlists always have at least two elements... if the number + goes down to one, get rid of the bindlist and bind the symbol + straight to the remaining element. */ + + t_dict_bindlist *b = (t_dict_bindlist *)s->s_thing; + t_dict_bindelem *e, *e2; + if ((e = b->b_list)->e_who == obj) + { + b->b_list = e->e_next; + freebytes(e, sizeof(t_dict_bindelem)); + } + else for (e = b->b_list; e2 = e->e_next; e = e2) + if (e2->e_who == obj) + { + e->e_next = e2->e_next; + freebytes(e2, sizeof(t_dict_bindelem)); + break; + } + if (!b->b_list->e_next) + { + s->s_thing = b->b_list->e_who; + freebytes(b->b_list, sizeof(t_dict_bindelem)); + pd_free(&b->b_pd); + } + } + else pd_error(obj, "%s: couldn't unbind", s->s_name); +} + +/* adapted pd_findbyclass() from m_pd.c */ +t_pd *dict_value(t_dict *x, t_symbol *s) +{ + if (!s->s_thing) return (0); + if (*s->s_thing == x->d_bindlist_class) + { + t_pd *x = 0; + t_dict_bindelem *e; + int warned = 0; + for (e = ((t_dict_bindlist *)s->s_thing)->b_list; e; e = e->e_next) + { + if (x && !warned) + { + post("warning: %s: multiply defined", s->s_name); + warned = 1; + } + x = e->e_who; + } + return (x); + } + return (s->s_thing); +} + +t_pd *dict_xvalue(t_dict *x, t_symbol *s) +{ + return (s && s != &s_ ? dict_value(x, dict_key(x, s->s_name)) : 0); +} + +int dict_forall(t_dict *x, t_symbol *s, t_dict_hook hook, void *hookarg) +{ + if (!s->s_thing) + return (0); + if (*s->s_thing == x->d_bindlist_class) + { + t_dict_bindelem *e = ((t_dict_bindlist *)s->s_thing)->b_list; + if (!e) + return (0); + if (!hook) + return (1); + do + if (!hook(e->e_who, hookarg)) + return (0); + while (e = e->e_next); + return (1); + } + return (hook ? hook(s->s_thing, hookarg) : 1); +} diff --git a/shared/common/dict.h b/shared/common/dict.h new file mode 100644 index 0000000..807bf9b --- /dev/null +++ b/shared/common/dict.h @@ -0,0 +1,27 @@ +/* Copyright (c) 2002-2003 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 __DICT_H__ +#define __DICT_H__ + +typedef struct _dict +{ + size_t d_hashsize; + t_symbol **d_hashtable; + t_class *d_bindlist_class; +} t_dict; + +typedef int (*t_dict_hook)(t_pd *x, void *arg); + +t_dict *dict_new(size_t hashsize); +void dict_free(t_dict *x); +t_symbol *dict_dokey(t_dict *x, char *s, t_symbol *oldsym); +t_symbol *dict_key(t_dict *x, char *s); +void dict_bind(t_dict *x, t_pd *obj, t_symbol *s); +void dict_unbind(t_dict *x, t_pd *obj, t_symbol *s); +t_pd *dict_value(t_dict *x, t_symbol *s); +t_pd *dict_xvalue(t_dict *x, t_symbol *s); +int dict_forall(t_dict *x, t_symbol *s, t_dict_hook hook, void *hookarg); + +#endif -- cgit v1.2.1