+/*
+ * 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;
+}