snap_hashtable.c

一个学习SNMP项目：tmoerlan.

/* 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/09/17 11:26:10 tmoerlan 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;
}