dummynet/hashtable.c

   1 /*
   2  * XXX Copyright
   3  */
   4 #include <sys/param.h>
   5 #include <sys/systm.h>
   6 #include <sys/malloc.h>
   7
   8 #include "hashtable.h"  // XXX fix path later
   9
  10 struct new_obj {
  11         struct new_obj *next;   /* Next object in the list */
  12         char obj[0];            /* actually bigger */
  13 };
  14
  15 /* Hash table */
  16 struct new_hash_table {
  17         int table_size;         /* Size of the table (buckets) */
  18         int table_obj;          /* number of object in the table */
  19         int obj_size;           /* size of object (key + value) */
  20         /* Hash function for this table */
  21         uint32_t (*hash)(const void *key, uint32_t size);
  22         int (*cmp)(const void *obj1, const void *obj2);
  23         int hash_arg;           /* hash function parameter */
  24         struct malloc_type *mtype;
  25         struct new_obj **table_ptr;     /* Pointer to the table */
  26 };
  27
  28 /*
  29  * initialize an hash table
  30  * - size:      size of table (number of buckets)
  31  * - obj_size:  size of the object to store in the table (key + value)
  32  * - hf:        pointer to the hash function for this table
  33  * - compare:   function to compare two objects
  34  *
  35  * Return value: pointer to the hash table, NULL if error occurs
  36  */
  37 struct new_hash_table *
  38 new_table_init (int size, int obj_size,
  39         uint32_t (hf)(const void *, uint32_t size),
  40         int (compare)(const void *, const void *),
  41         struct malloc_type *mtype)
  42 {
  43         struct new_hash_table *h;
  44
  45         printf("%s called\n", __FUNCTION__);
  46
  47         h = malloc(sizeof(struct new_hash_table), mtype, M_NOWAIT | M_ZERO);
  48         if (h == NULL)
  49                 return NULL;
  50
  51         h->table_ptr = malloc(size * sizeof(struct new_obj*), mtype,
  52                                M_NOWAIT | M_ZERO);
  53         if (h->table_ptr == NULL) { /* no memory */
  54                 free (h, mtype);
  55                 return 0;
  56         }
  57         h->table_size = size;
  58         h->hash = hf;
  59         h->cmp = compare;
  60         h->mtype = mtype;
  61         h->obj_size = obj_size;
  62
  63         return h;
  64 }
  65
  66 int
  67 new_table_insert_obj (struct new_hash_table *h, const void *obj)
  68 {
  69         int i; /* array index */
  70         struct new_obj *o, *ot;
  71
  72         i = h->hash(obj, h->table_size);
  73
  74         /* same key not allowed */
  75         for (ot = h->table_ptr[i]; ot; ot = ot->next) {
  76                 if (h->cmp(obj, ot->obj) == 0)
  77                         return 1; /* error */
  78         }
  79         /* allocate a single chunk of memory */
  80         o = malloc(sizeof(*o) + h->obj_size, h->mtype, M_NOWAIT);
  81         if (o == NULL)
  82                 return 1;
  83         bcopy(obj, o->obj, h->obj_size);
  84
  85         /* put at the head */
  86         o->next = h->table_ptr[i];
  87         h->table_ptr[i] = o;
  88
  89         h->table_obj++;
  90
  91         return 0;
  92 }
  93
  94 int
  95 new_table_delete_obj(struct new_hash_table *h, const void *obj)
  96 {
  97         int i;
  98         struct new_obj *obj1, *prev;
  99
 100         i = h->hash(obj, h->table_size);
 101
 102         for (prev = NULL, obj1 = h->table_ptr[i]; obj1; obj1 = obj1->next) {
 103                 if (h->cmp(obj, (void *)obj1->obj) != 0)
 104                         continue;
 105                 /* Object found, delete */
 106                 if (prev != NULL)
 107                         prev->next = obj1->next;
 108                 else
 109                         h->table_ptr[i] = obj1->next;
 110                 free(obj1, h->mtype);
 111                 h->table_obj--;
 112                 return 0;
 113         }
 114         return 1; /* Not found */
 115 }
 116
 117 const void *
 118 new_table_extract_obj(struct new_hash_table *h, const void *obj)
 119 {
 120         struct new_obj *o;
 121         int i;
 122         if (h == NULL || h->table_obj == 0)
 123                 return NULL;
 124
 125         i = h->hash(obj, h->table_size);
 126         for (o =  h->table_ptr[i]; o; o = o->next) {
 127                 if (h->cmp(o->obj, obj) == 0)
 128                         return o->obj;
 129         }
 130         return NULL;
 131 }
 132
 133 void *
 134 new_table_destroy(struct new_hash_table *h)
 135 {
 136         int i;
 137         struct new_obj *cur, *next;
 138
 139         if (!h || !h->table_ptr)
 140                 return NULL;
 141         for (i = 0; i < h->table_size; i++)  {
 142                 for (cur = h->table_ptr[i]; cur; cur = next) {
 143                         next = cur->next;
 144                         free(cur, h->mtype);
 145                 }
 146         }
 147         free (h->table_ptr, h->mtype);
 148         free (h, h->mtype);
 149
 150         return NULL;
 151 }
 152
 153 /* returns the number of elements in the table */
 154 int
 155 new_table_get_element(const struct new_hash_table *h)
 156 {
 157         return h ? h->table_obj : 0;
 158 }
 159
 160 const void *
 161 table_next(struct new_hash_table *h, const void *o)
 162 {
 163         int i;
 164         struct new_obj *obj;
 165
 166         printf("%s called\n", __FUNCTION__);
 167         if (h == NULL || h->table_obj == 0)
 168                 return NULL;
 169         if (o == NULL) {
 170                 for (i = 0; i < h->table_size; i++)
 171                         if (h->table_ptr[i])
 172                                 return h->table_ptr[i]->obj;
 173                 return NULL; /* XXX should not happen */
 174         }
 175
 176         /* here we can optimize if we can map o to the bucket,
 177          * otherwise locate o and find the next one.
 178          */
 179         i = h->hash(o, h->table_size);
 180         for (obj = h->table_ptr[i]; obj; obj = obj->next) {
 181                 if (h->cmp(obj->obj, o) == 0)
 182                         break;
 183         }
 184         if (obj && obj->next != NULL)
 185                 return obj->next->obj;
 186         /* take the first of the next bucket */
 187         for (i++; i < h->table_size; i++) {
 188                 if (h->table_ptr[i])
 189                         return h->table_ptr[i]->obj;
 190         }
 191         return NULL;
 192 }