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 ipfw_ht {
  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, int sz);
  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 ipfw_ht *
  38 ipfw_ht_new(int size, int obj_size,
  39         uint32_t (hf)(const void *, uint32_t size),
  40         int (compare)(const void *, const void *, int),
  41         struct malloc_type *mtype)
  42 {
  43         struct ipfw_ht *h;
  44
  45         h = malloc(sizeof(*h), mtype, M_NOWAIT | M_ZERO);
  46         if (h == NULL)
  47                 return NULL;
  48
  49         h->table_ptr = malloc(size * sizeof(struct new_obj*), mtype,
  50                                M_NOWAIT | M_ZERO);
  51         if (h->table_ptr == NULL) { /* no memory */
  52                 free (h, mtype);
  53                 return 0;
  54         }
  55         h->table_size = size;
  56         h->hash = hf;
  57         h->cmp = compare;
  58         h->mtype = mtype;
  59         h->obj_size = obj_size;
  60
  61         return h;
  62 }
  63
  64 int
  65 ipfw_ht_insert(struct ipfw_ht *h, const void *obj)
  66 {
  67         int i; /* array index */
  68         struct new_obj *o, *ot;
  69
  70         i = h->hash(obj, h->table_size);
  71
  72         /* same key not allowed */
  73         for (ot = h->table_ptr[i]; ot; ot = ot->next) {
  74                 if (h->cmp(obj, ot->obj, h->obj_size) == 0)
  75                         return 1; /* error */
  76         }
  77         /* allocate a single chunk of memory */
  78         o = malloc(sizeof(*o) + h->obj_size, h->mtype, M_NOWAIT);
  79         if (o == NULL)
  80                 return 1;
  81         bcopy(obj, o->obj, h->obj_size);
  82
  83         /* put at the head */
  84         o->next = h->table_ptr[i];
  85         h->table_ptr[i] = o;
  86
  87         h->table_obj++;
  88
  89         return 0;
  90 }
  91
  92 int
  93 ipfw_ht_remove(struct ipfw_ht *h, const void *obj)
  94 {
  95         int i;
  96         struct new_obj *obj1, *prev;
  97
  98         i = h->hash(obj, h->table_size);
  99
 100         for (prev = NULL, obj1 = h->table_ptr[i]; obj1; obj1 = obj1->next) {
 101                 if (h->cmp(obj, obj1->obj, h->obj_size) != 0)
 102                         continue;
 103                 /* Object found, delete */
 104                 if (prev != NULL)
 105                         prev->next = obj1->next;
 106                 else
 107                         h->table_ptr[i] = obj1->next;
 108                 free(obj1, h->mtype);
 109                 h->table_obj--;
 110                 return 0;
 111         }
 112         return 1; /* Not found */
 113 }
 114
 115 const void *
 116 ipfw_ht_extract(struct ipfw_ht *h, const void *obj)
 117 {
 118         struct new_obj *o;
 119         int i;
 120         if (h == NULL || h->table_obj == 0)
 121                 return NULL;
 122
 123         i = h->hash(obj, h->table_size);
 124         for (o =  h->table_ptr[i]; o; o = o->next) {
 125                 if (h->cmp(o->obj, obj, h->obj_size) == 0)
 126                         return o->obj;
 127         }
 128         return NULL;
 129 }
 130
 131 void *
 132 ipfw_ht_destroy(struct ipfw_ht *h)
 133 {
 134         int i;
 135         struct new_obj *cur, *next;
 136
 137         if (!h || !h->table_ptr)
 138                 return NULL;
 139         for (i = 0; i < h->table_size; i++)  {
 140                 for (cur = h->table_ptr[i]; cur; cur = next) {
 141                         next = cur->next;
 142                         free(cur, h->mtype);
 143                 }
 144         }
 145         free (h->table_ptr, h->mtype);
 146         free (h, h->mtype);
 147
 148         return NULL;
 149 }
 150
 151 /* returns the number of elements in the table */
 152 int
 153 ipfw_ht_count(const struct ipfw_ht *h)
 154 {
 155         return h ? h->table_obj : 0;
 156 }
 157
 158 const void *
 159 table_next(struct ipfw_ht *h, const void *o)
 160 {
 161         int i;
 162         struct new_obj *obj;
 163
 164         if (h == NULL || h->table_obj == 0)
 165                 return NULL;
 166         if (o == NULL) {
 167                 for (i = 0; i < h->table_size; i++)
 168                         if (h->table_ptr[i])
 169                                 return h->table_ptr[i]->obj;
 170                 return NULL; /* XXX should not happen */
 171         }
 172
 173         /* here we can optimize if we can map o to the bucket,
 174          * otherwise locate o and find the next one.
 175          */
 176         i = h->hash(o, h->table_size);
 177         for (obj = h->table_ptr[i]; obj; obj = obj->next) {
 178                 if (h->cmp(obj->obj, o, h->obj_size) == 0)
 179                         break;
 180         }
 181         if (obj && obj->next != NULL)
 182                 return obj->next->obj;
 183         /* take the first of the next bucket */
 184         for (i++; i < h->table_size; i++) {
 185                 if (h->table_ptr[i])
 186                         return h->table_ptr[i]->obj;
 187         }
 188         return NULL;
 189 }