Grab the lock before reading uid/gid related structure, this will

[ipfw.git] / dummynet / hashtable.c

diff --git a/dummynet/hashtable.c b/dummynet/hashtable.c
new file mode 100644 (file)
index 0000000..517cec6
--- /dev/null
+++ b/dummynet/hashtable.c
@@ -0,0 +1,192 @@
+/*
+ * XXX Copyright
+ */
+#include <sys/param.h>
+#include <sys/systm.h>
+#include <sys/malloc.h>
+
+#include "hashtable.h" // XXX fix path later
+
+struct new_obj {
+       struct new_obj *next;   /* Next object in the list */
+       char obj[0];            /* actually bigger */
+};
+
+/* Hash table */
+struct new_hash_table {
+       int table_size;         /* Size of the table (buckets) */
+       int table_obj;          /* number of object in the table */
+       int obj_size;           /* size of object (key + value) */
+       /* Hash function for this table */
+       uint32_t (*hash)(const void *key, uint32_t size);
+       int (*cmp)(const void *obj1, const void *obj2);
+       int hash_arg;           /* hash function parameter */
+       struct malloc_type *mtype;
+       struct new_obj **table_ptr;     /* Pointer to the table */
+};
+
+/*
+ * initialize an hash table
+ * - size:     size of table (number of buckets)
+ * - obj_size: size of the object to store in the table (key + value)
+ * - hf:       pointer to the hash function for this table
+ * - compare:  function to compare two objects
+ *
+ * Return value: pointer to the hash table, NULL if error occurs
+ */
+struct new_hash_table *
+new_table_init (int size, int obj_size,
+       uint32_t (hf)(const void *, uint32_t size),
+       int (compare)(const void *, const void *),
+       struct malloc_type *mtype)
+{
+       struct new_hash_table *h;
+
+       printf("%s called\n", __FUNCTION__);
+
+       h = malloc(sizeof(struct new_hash_table), mtype, M_NOWAIT | M_ZERO);
+       if (h == NULL)
+               return NULL;
+
+       h->table_ptr = malloc(size * sizeof(struct new_obj*), mtype,
+                              M_NOWAIT | M_ZERO);
+       if (h->table_ptr == NULL) { /* no memory */
+               free (h, mtype);
+               return 0;
+       }
+       h->table_size = size;
+       h->hash = hf;
+       h->cmp = compare;
+       h->mtype = mtype;
+       h->obj_size = obj_size;
+
+       return h;
+}
+
+int
+new_table_insert_obj (struct new_hash_table *h, const void *obj)
+{
+       int i; /* array index */
+       struct new_obj *o, *ot;
+       
+       i = h->hash(obj, h->table_size);
+       
+       /* same key not allowed */
+       for (ot = h->table_ptr[i]; ot; ot = ot->next) {
+               if (h->cmp(obj, ot->obj) == 0)
+                       return 1; /* error */
+       }
+       /* allocate a single chunk of memory */
+       o = malloc(sizeof(*o) + h->obj_size, h->mtype, M_NOWAIT);
+       if (o == NULL)
+               return 1;
+       bcopy(obj, o->obj, h->obj_size);
+
+       /* put at the head */
+       o->next = h->table_ptr[i];
+       h->table_ptr[i] = o;
+
+       h->table_obj++;
+
+       return 0;
+}
+
+int
+new_table_delete_obj(struct new_hash_table *h, const void *obj)
+{
+       int i;
+       struct new_obj *obj1, *prev;
+
+       i = h->hash(obj, h->table_size);
+
+       for (prev = NULL, obj1 = h->table_ptr[i]; obj1; obj1 = obj1->next) {
+               if (h->cmp(obj, (void *)obj1->obj) != 0)
+                       continue;
+               /* Object found, delete */
+               if (prev != NULL)
+                       prev->next = obj1->next;
+               else
+                       h->table_ptr[i] = obj1->next;
+               free(obj1, h->mtype);
+               h->table_obj--;
+               return 0;
+       }
+       return 1; /* Not found */
+}
+
+const void *
+new_table_extract_obj(struct new_hash_table *h, const void *obj)
+{
+       struct new_obj *o;
+       int i;
+       if (h == NULL || h->table_obj == 0)
+               return NULL;
+
+       i = h->hash(obj, h->table_size);
+       for (o =  h->table_ptr[i]; o; o = o->next) {
+               if (h->cmp(o->obj, obj) == 0)
+                       return obj;
+       }
+       return NULL;
+}
+
+void *
+new_table_destroy(struct new_hash_table *h)
+{
+       int i;
+       struct new_obj *cur, *next;
+
+       if (!h || !h->table_ptr)
+               return NULL;
+       for (i = 0; i < h->table_size; i++)  {
+               for (cur = h->table_ptr[i]; cur; cur = next) {
+                       next = cur->next;
+                       free(cur, h->mtype);
+               }
+       }
+       free (h->table_ptr, h->mtype);
+       free (h, h->mtype);
+
+       return NULL;
+}
+
+/* returns the number of elements in the table */
+int
+new_table_get_element(const struct new_hash_table *h)
+{
+       return h ? h->table_obj : 0;
+}
+
+const void * 
+table_next(struct new_hash_table *h, const void *o)
+{
+       int i;
+       struct new_obj *obj;
+
+       printf("%s called\n", __FUNCTION__);
+       if (h == NULL || h->table_obj == 0)
+               return NULL;
+       if (o == NULL) {
+               for (i = 0; i < h->table_size; i++)
+                       if (h->table_ptr[i])
+                               return h->table_ptr[i]->obj;
+               return NULL; /* XXX should not happen */
+       }
+
+       /* here we can optimize if we can map o to the bucket,
+        * otherwise locate o and find the next one.
+        */
+       i = h->hash(o, h->table_size);
+       for (obj = h->table_ptr[i]; obj; obj = obj->next) {
+               if (h->cmp(obj->obj, o) == 0)
+                       break;
+       }
+       if (obj && obj->next != NULL)
+               return obj->next->obj;
+       /* take the first of the next bucket */
+       for (i++; i < h->table_size; i++) {
+               if (h->table_ptr[i])
+                       return h->table_ptr[i]->obj;
+       }
+       return NULL;
+}