From 61ab39873f66649129872485ed721911999060b1 Mon Sep 17 00:00:00 2001 From: mescalinum Date: Sat, 15 Oct 2011 12:26:33 +0000 Subject: move hashtable functions outside svn path=/trunk/externals/loaders/tclpd/; revision=15602 --- Makefile | 2 +- hashtable.c | 77 ++++++++++++++++++++++++++++++++++ hashtable.h | 43 +++++++++++++++++++ tcl_class.c | 136 +++++++----------------------------------------------------- 4 files changed, 136 insertions(+), 122 deletions(-) create mode 100644 hashtable.c create mode 100644 hashtable.h diff --git a/Makefile b/Makefile index 752d57b..12a467c 100644 --- a/Makefile +++ b/Makefile @@ -19,7 +19,7 @@ EXAMPLES = bitmap-help.pd bitmap-madness.pd bitmap.tcl colorpicker.tcl dynreceiv MANUAL = # tclpd-specific source files -TCLPD_SOURCES = tcl_class.c tcl_loader.c tcl_proxyinlet.c tcl_typemap.c tcl_widgetbehavior.c +TCLPD_SOURCES = hashtable.c tcl_class.c tcl_loader.c tcl_proxyinlet.c tcl_typemap.c tcl_widgetbehavior.c # if you want to include any other files in the source and binary tarballs, # list them here. This can be anything from header files, test patches, diff --git a/hashtable.c b/hashtable.c new file mode 100644 index 0000000..ae32d38 --- /dev/null +++ b/hashtable.c @@ -0,0 +1,77 @@ +#include "hashtable.h" + +uint32_t hash_str(const char *s) { + const unsigned char *p = (const unsigned char *)s; + uint32_t h = 5381; + + while (*p) { + h *= 33; + h ^= *p++; + } + + return h ^ (h >> 16); +} + +list_node_t* list_add(list_node_t* head, const char* k, void* v) { + list_node_t* n = (list_node_t*)malloc(sizeof(list_node_t)); + n->next = head; + n->k = strdup(k); + n->v = v; + return n; +} + +list_node_t* list_remove(list_node_t* head, const char* k) { + list_node_t* tmp; + + // head remove + while(head && strcmp(head->k, k) == 0) { + tmp = head; + head = head->next; + free(tmp->k); + free(tmp); + } + + list_node_t* p = head; + + // normal (non-head) remove + while(p->next) { + if(strcmp(p->next->k, k) == 0) + { + tmp = p->next; + p->next = p->next->next; + free(tmp); + continue; + } + p = p->next; + } + + return head; +} + +void* list_get(list_node_t* head, const char* k) { + while(head) { + if(strcmp(head->k, k) == 0) { + return head->v; + } + head = head->next; + } + return (void*)0; +} + +hash_table_t* hashtable_new(size_t size) { + hash_table_t* ht = NULL; + if(size > 0) { + ht = (hash_table_t*)malloc(sizeof(hash_table_t)); + ht->sz = size; + ht->t = (list_node_t**)malloc(sizeof(list_node_t*) * size); + } + return ht; +} + +void hashtable_free(hash_table_t* ht) { + if(ht) { + free(ht->t); + free(ht); + } +} + diff --git a/hashtable.h b/hashtable.h new file mode 100644 index 0000000..1c3fea7 --- /dev/null +++ b/hashtable.h @@ -0,0 +1,43 @@ +#ifndef HASHTABLE_H_INCLUDED +#define HASHTABLE_H_INCLUDED + +#include +#include +#include + +typedef struct list_node { + const char* k; + void* v; + struct list_node* next; +} list_node_t; + +typedef struct hash_table { + list_node_t** t; + size_t sz; +} hash_table_t; + +uint32_t hash_str(const char *s); +list_node_t* list_add(list_node_t* head, const char* k, void* v); +list_node_t* list_remove(list_node_t* head, const char* k); +void* list_get(list_node_t* head, const char* k); + +hash_table_t* hashtable_new(size_t size); +void hash_table_free(hash_table_t* ht); + +static inline void hashtable_add(hash_table_t* ht, const char* name, void* c) { + uint32_t h = hash_str(name) % ht->sz; + ht->t[h] = list_add(ht->t[h], name, (void*)c); +} + +static inline void hashtable_remove(hash_table_t* ht, const char* name) { + uint32_t h = hash_str(name) % ht->sz; + ht->t[h] = list_remove(ht->t[h], name); +} + +static inline void* hashtable_get(hash_table_t* ht, const char* name) { + uint32_t h = hash_str(name) % ht->sz; + return list_get(ht->t[h], name); +} + +#endif // HASHTABLE_H_INCLUDED + diff --git a/tcl_class.c b/tcl_class.c index 6e700c2..03350a2 100644 --- a/tcl_class.c +++ b/tcl_class.c @@ -1,139 +1,31 @@ #include "tcl_extras.h" -#include #include #include #include +#include "hashtable.h" -#define CLASS_TABLE_SIZE (1 << 7) -#define OBJECT_TABLE_SIZE (1 << 8) +static hash_table_t* class_table = NULL; +static hash_table_t* object_table = NULL; -static inline uint32_t hash_str(const char *s) -{ - const unsigned char *p = (const unsigned char *)s; - uint32_t h = 5381; +#define class_table_add(n, c) hashtable_add(class_table, n, (void*)c) +#define class_table_remove(n) hashtable_remove(class_table, n) +#define class_table_get(n) ((t_class*)hashtable_get(class_table, n)) - while (*p) { - h *= 33; - h ^= *p++; - } - - return h ^ (h >> 16); -} - -typedef struct list_node -{ - const char* k; - void* v; - struct list_node* next; -} list_node_t; - -static inline list_node_t* list_add(list_node_t* head, const char* k, void* v) -{ - list_node_t* n = (list_node_t*)malloc(sizeof(list_node_t)); - n->next = head; - n->k = strdup(k); - n->v = v; - return n; -} - -static inline list_node_t* list_remove(list_node_t* head, const char* k) -{ - list_node_t* tmp; - - // head remove - while(head && strcmp(head->k, k) == 0) - { - tmp = head; - head = head->next; - free(tmp->k); - free(tmp); - } - - list_node_t* p = head; - - // normal (non-head) remove - while(p->next) - { - if(strcmp(p->next->k, k) == 0) - { - tmp = p->next; - p->next = p->next->next; - free(tmp); - continue; - } - p = p->next; - } - - return head; -} - -static inline void* list_get(list_node_t* head, const char* k) -{ - while(head) - { - if(strcmp(head->k, k) == 0) - { - return head->v; - } - head = head->next; - } -#ifdef DEBUG - debug_print("list_get(%lx, %s) = NULL\n", head, k); -#endif - return (void*)0; -} - -static list_node_t* class_tbl[CLASS_TABLE_SIZE]; -static list_node_t* object_tbl[OBJECT_TABLE_SIZE]; - -static inline void class_table_add(const char* name, t_class* c) -{ - uint32_t h = hash_str(name) % CLASS_TABLE_SIZE; - class_tbl[h] = list_add(class_tbl[h], name, (void*)c); -} - -static inline void class_table_remove(const char* name) -{ - uint32_t h = hash_str(name) % CLASS_TABLE_SIZE; - class_tbl[h] = list_remove(class_tbl[h], name); -} - -static inline t_class* class_table_get(const char* name) -{ - uint32_t h = hash_str(name) % CLASS_TABLE_SIZE; - return (t_class*)list_get(class_tbl[h], name); -} - -static inline void object_table_add(const char* name, t_tcl* o) -{ - uint32_t h = hash_str(name) % OBJECT_TABLE_SIZE; - object_tbl[h] = list_add(object_tbl[h], name, (void*)o); -} - -static inline void object_table_remove(const char* name) -{ - uint32_t h = hash_str(name) % OBJECT_TABLE_SIZE; - object_tbl[h] = list_remove(object_tbl[h], name); -} - -static inline t_tcl* object_table_get(const char* name) -{ - uint32_t h = hash_str(name) % OBJECT_TABLE_SIZE; - return (t_pd*)list_get(object_tbl[h], name); -} +#define object_table_add(n, c) hashtable_add(object_table, n, (void*)c) +#define object_table_remove(n) hashtable_remove(object_table, n) +#define object_table_get(n) ((t_tcl*)hashtable_get(object_table, n)) static unsigned long objectSequentialId = 0; -static list_node_t* class_tbl[CLASS_TABLE_SIZE]; -static list_node_t* object_tbl[OBJECT_TABLE_SIZE]; - /* set up the class that handles loading of tcl classes */ t_class* tclpd_class_new(const char* name, int flags) { t_class* c = class_new(gensym(name), (t_newmethod)tclpd_new, (t_method)tclpd_free, sizeof(t_tcl), flags, A_GIMME, A_NULL); + if(!class_table) + class_table = hashtable_new(1 << 7); if(!class_table_get(name)) - class_table_add(name, c); + class_table_add(name, c); class_addanything(c, tclpd_anything); @@ -213,8 +105,10 @@ t_tcl* tclpd_new(t_symbol* classsym, int ac, t_atom* at) { Tcl_IncrRefCount(x->dispatcher); // store in object table (for later lookup) + if(!object_table) + object_table = hashtable_new(1 << 10); if(!object_table_get(so)) - object_table_add(so, x); + object_table_add(so, x); // build constructor command Tcl_Obj *av[ac+3]; InitArray(av, ac+3, NULL); -- cgit v1.2.1