[insert project logo here (125x200px max)] Navigator Home Downloads Documentation Research News Forums Project Summary CVS repository Mailinglists Help Announcement Developer Please report any errors or ommissions you find to our `Help' mailinglist, or post a message in the Forums. Copyright and Licensing Information Snap is (c) Jonathan T. Moore, 1999-2002 and licensed under the GNU General Public License (GPL). All other parts of Splash are (c) Willem de Bruijn, 2002-2003 and licensed under the BSD Open Source License. All sourcecode is made publicly available. Acknowledgement Splash and the Splash website are hosted by SourceForge.net

Splash - Documentation SNMP Plus a Lightweight API for SNAP Handling             snap-1.1-wjdb/lib/snap_hashtable.c Go to the documentation of this file. /* snap-1.0. Copyright (C) 2000 by Jonathan T. Moore and Michael Hicks. * * hashtable.c : basic hash table library, used to manage the * node-resident service namespace * * $Id: snap_hashtable.c,v 1.2 2003/03/07 11:41:53 wdebruij Exp $ */ #ifdef __KERNEL__ #include <linux/slab.h> #include <linux/string.h> #include <snap/myassert.h> #include <snap/list.h> #include <snap/hashtable.h> #else #include <assert.h> #include "list.h" #include "memalloc.h" #include "hashtable.h" #endif /* __KERNEL__ */ #include "d_printf.h" /* hash function for the table */ int hash_string(char *s) { int ans = 0; int shift = 0; int i, sz; assert(s != NULL); sz = strlen(s); for(i=0; i < sz; ++i) { ans = ans ^ (s[i] << shift); shift += 8; if(shift == 32) shift = 0; } return ans; } int ht_errno = 0; static void resize(hash_table_t* t); hash_table_t *ht_create(int sz, int (*cmp)(const void *,const void *), int (*hash)(void *)) { hash_table_t *ht = NULL; list_t **tab = NULL; int tab_sizeb = sizeof(list_t *)*sz; #ifdef __KERNEL__ ht = (hash_table_t *)kmalloc(sizeof(hash_table_t),GFP_ATOMIC); if (!ht) { printk(KERN_WARNING "%s:%d: kmalloc failed\n",__FILE__,__LINE__); return NULL; } tab = (list_t **)kmalloc(tab_sizeb,GFP_ATOMIC); if (!tab) { printk(KERN_WARNING "%s:%d: kmalloc failed\n",__FILE__,__LINE__); return NULL; } memset(tab,0,tab_sizeb); #else memalloc(ht,hash_table_t *,sizeof(hash_table_t)); memalloc(tab,list_t **,tab_sizeb); bzero(tab,tab_sizeb); #endif /* __KERNEL__ */ ht->cmp = cmp; ht->hash = hash; ht->tab = tab; ht->max_len = 3; ht->tab_sz = sz; return ht; } void ht_insert(hash_table_t *t, void *key, void *val) { list_t **tab; int bucket; pair_t *elem; assert(t != NULL); d_printf(110,"snap_hashtable : inserting key %s\n",(char*) key); tab = t->tab; bucket = t->hash(key) % t->tab_sz; #ifdef __KERNEL__ elem = (pair_t *)kmalloc(sizeof(pair_t),GFP_ATOMIC); if (!elem) { printk(KERN_WARNING "%s:%d: kmalloc failed\n",__FILE__,__LINE__); return; } #else memalloc(elem,pair_t *,sizeof(pair_t)); #endif /* __KERNEL__ */ elem->key = key; elem->value = val; tab[bucket] = cons(elem,tab[bucket]); if (length_list (tab[bucket]) > t->max_len) resize(t); } static void *assoc_cmp(int (*cmp)(const void *,const void *), list_t *list, void *key) { list_t *iter = list; ht_errno = 0; while (iter != NULL) { pair_t *elem = (pair_t *)iter->v; if (!cmp(elem->key,key)) return elem->value; iter = iter->next; } ht_errno = 1; /* didn't find it */ return NULL; } void *ht_lookup(hash_table_t *t, void *key) { list_t **tab, *l; d_printf(110,"snap_hashtable : searching for key %s\n",(char*) key); assert(t != NULL); tab = t->tab; l = tab[t->hash(key) % t->tab_sz]; return assoc_cmp(t->cmp, l, key); } void ht_remove(hash_table_t * t, void *key) { int bucket; list_t *l, *prev; pair_t *elem; assert(t != NULL); bucket = t->hash(key) % t->tab_sz; l = t->tab[bucket]; if(l == NULL) return; elem = (pair_t *)l->v; if(t->cmp(key,elem->key)==0) { t->tab[bucket] = l->next; free(elem->key); free(elem); return; } prev = l; l = l->next; for(; l->next != NULL; prev = l, l=l->next) { elem = (pair_t *)l->v; if(t->cmp(key,elem->key)==0) { prev->next = l->next; free(elem->key); free(elem); return; } } } /* For resizing */ static void insert_bucket(list_t **tab, int tab_sz, int (*hash)(void *), list_t *elems) { pair_t *elem; int nidx; assert(tab != NULL); assert(tab_sz > 0); if (elems == NULL) return; insert_bucket(tab,tab_sz,hash,elems->next); // preserve the original order #ifdef __KERNEL__ elem = (pair_t *)kmalloc(sizeof(pair_t),GFP_ATOMIC); if (!elem) { printk(KERN_WARNING "%s:%d: kmalloc failed\n",__FILE__,__LINE__); return; } #else memalloc(elem,pair_t *,sizeof(pair_t)); #endif /* __KERNEL__ */ elem->key = ((pair_t *)(elems->v))->key; elem->value = ((pair_t *)(elems->v))->value; nidx = hash(elem->key) % tab_sz; tab[nidx] = cons(elem,tab[nidx]); } static void resize(hash_table_t *t) { list_t **odata, **ndata; int osize, nsize, ndata_sizeb; int i; assert(t != NULL); odata = t->tab; osize = t->tab_sz; nsize = 2 * osize + 1; ndata_sizeb = sizeof(list_t *)*nsize; #ifdef __KERNEL__ ndata = (list_t **)kmalloc(ndata_sizeb,GFP_ATOMIC); if (!ndata) { printk(KERN_WARNING "%s:%d: kmalloc failed\n",__FILE__,__LINE__); return; } memset(ndata,0,ndata_sizeb); #else memalloc(ndata,list_t **,ndata_sizeb); bzero(ndata,ndata_sizeb); #endif /* __KERNEL__ */ for (i = 0; i<osize; i++) insert_bucket(ndata,t->tab_sz,t->hash,odata[i]); t->tab = ndata; t->max_len = 2 * t->max_len; }