Hash table changes
authorBarret Rhoden <brho@cs.berkeley.edu>
Sat, 7 Nov 2009 01:33:47 +0000 (17:33 -0800)
committerBarret Rhoden <brho@cs.berkeley.edu>
Mon, 9 Nov 2009 22:20:49 +0000 (14:20 -0800)
Changed how the hash table works, most notably that you must free your
keys on your own.  This way, you can either kfree, kmem_cache_free, or
just nothing, based on whatever is appropriate for what your key is.
(Just an int requires no freeing, but still requires a typecast).

This is a good example of packaged solutions being non-ideal, since they
make assumptions about its usage (kfree, let alone that the key is an
obkect).  I nearly ripped out the function pointers for hashing and
equality, in favor of the hashed value being passed to functions (where
needed), and the key just being a long.  It simplifies a lot and would
perform better, and I don't have an example of when I want an object for
a key where equivalence isn't the address of the object.  There may be a
case where the function pointers are nice, so I held off.

There are also generic functions for the hashfn and eqfn.  Don't call
these directly, etc.  Also, the hash entries (hentry) are now slab
allocated, instead of kmalloc'd.

NB: be warned that there is no checking for duplicate keys.

Also, another way to do these things is to embed the hash_entry in any
struct that will be hashed (like the struct proc).  You won't need
dynamic allocation of the hentry, you can check if you are hashed or
not, and the hentry doesn't need a pointer to you (can do something like
container_of()).  A downside is that concurrency can be weird - others
could temp touch your entry while walking a hash chain.  Not sure what's
best, overall.

kern/include/hashtable.h
kern/include/hashtable_itr.h [deleted file]
kern/include/testing.h
kern/src/Makefrag
kern/src/hashtable.c
kern/src/hashtable_itr.c [deleted file]
kern/src/init.c
kern/src/testing.c

index 471dc02..00c1d15 100644 (file)
@@ -1,4 +1,12 @@
-/* Copyright (C) 2002 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
+/* Copyright (C) 2002, 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk>
+ * 
+ * Modified 2009 by Barret Rhoden <brho@cs.berkeley.edu>
+ * Changes include:
+ *   - No longer frees keys or values.  It's up to the client to do that.
+ *   - Provides common hash and equality functions (meant for longs)
+ *   - Uses the slab allocator for hash entry allocation.
+ *   - Merges the iterator code with the main hash table code, mostly to avoid
+ *   externing the hentry cache. */
 
 #ifndef __ROS_KERN_HASHTABLE_H__
 #define __ROS_KERN_HASHTABLE_H__
@@ -36,11 +44,11 @@ static inline size_t indexFor(unsigned int tablelength, unsigned int hashvalue)
 {
        return (hashvalue % tablelength);
 };
-#define freekey(X) kfree(X)
 
 /*****************************************************************************/
 
 /* Example of use:
+ *             hashtable_init(); // Do this once during kernel initialization
  *
  *      struct hashtable  *h;
  *      struct some_key   *k;
@@ -96,6 +104,13 @@ static inline size_t indexFor(unsigned int tablelength, unsigned int hashvalue)
  *
  */
 
+/* Call this once on bootup, after initializing the slab allocator.  */
+void hashtable_init(void);
+
+/* Common hash/equals functions.  Don't call these directly. */
+size_t __generic_hash(void *k);
+ssize_t __generic_eq(void *k1, void *k2);
+
 /*****************************************************************************
  * create_hashtable
    
@@ -116,8 +131,8 @@ create_hashtable(size_t minsize,
    
  * @name        hashtable_insert
  * @param   h   the hashtable to insert into
- * @param   k   the key - hashtable claims ownership and will free on removal
- * @param   v   the value - does not claim ownership
+ * @param   k   the key
+ * @param   v   the value
  * @return      non-zero for successful insertion
  *
  * This function will cause the table to expand if the insertion would take
@@ -144,7 +159,7 @@ ssize_t fnname (hashtable_t *h, keytype *k, valuetype *v) \
    
  * @name        hashtable_search
  * @param   h   the hashtable to search
- * @param   k   the key to search for  - does not claim ownership
+ * @param   k   the key to search for
  * @return      the value associated with the key, or NULL if none found
  */
 
@@ -162,8 +177,10 @@ valuetype * fnname (hashtable_t *h, keytype *k) \
    
  * @name        hashtable_remove
  * @param   h   the hashtable to remove the item from
- * @param   k   the key to search for  - does not claim ownership
+ * @param   k   the key to search for
  * @return      the value associated with the key, or NULL if none found
+ *
+ * Caller ought to free the key, if appropriate.
  */
 
 void * /* returns value */
@@ -183,6 +200,7 @@ valuetype * fnname (hashtable_t *h, keytype *k) \
  * @param   h   the hashtable
  * @return      the number of items stored in the hashtable
  */
+
 size_t
 hashtable_count(hashtable_t *h);
 
@@ -192,16 +210,95 @@ hashtable_count(hashtable_t *h);
    
  * @name        hashtable_destroy
  * @param   h   the hashtable
- * @param       free_values     whether to call 'free' on the remaining values
+ *
+ * This will not free the values or the keys.  Each user of the hashtable may
+ * have a different way of freeing (such as the slab allocator, kfree, or
+ * nothing (key is just an integer)).
+ *
+ * If the htable isn't empty, you ought to iterate through and destroy manually.
+ * This will warn if you try to destroy an non-empty htable.
  */
 
 void
-hashtable_destroy(hashtable_t *h, int free_values);
+hashtable_destroy(hashtable_t *h);
+
+/***************************** Hashtable Iterator ****************************/
+/*****************************************************************************/
+/* This struct is only concrete here to allow the inlining of two of the
+ * accessor functions. */
+typedef struct hashtable_itr {
+    hashtable_t *h;
+    hash_entry_t *e;
+    hash_entry_t *parent;
+    size_t index;
+} hashtable_itr_t;
+
+/*****************************************************************************/
+/* hashtable_iterator
+ */
+
+hashtable_itr_t *
+hashtable_iterator(hashtable_t *h);
+
+/*****************************************************************************/
+/* hashtable_iterator_key
+ * - return the key of the (key,value) pair at the current position
+ *
+ * Keep this in sync with the non-externed version in the .c */
+
+extern inline void *
+hashtable_iterator_key(hashtable_itr_t *i)
+{
+    return i->e->k;
+}
+
+/*****************************************************************************/
+/* value - return the value of the (key,value) pair at the current position
+ *
+ * Keep this in sync with the non-externed version in the .c */
+
+extern inline void *
+hashtable_iterator_value(hashtable_itr_t *i)
+{
+    return i->e->v;
+}
+
+/*****************************************************************************/
+/* advance - advance the iterator to the next element
+ *           returns zero if advanced to end of table */
+
+ssize_t
+hashtable_iterator_advance(hashtable_itr_t *itr);
+
+/*****************************************************************************/
+/* remove - remove current element and advance the iterator to the next element
+ *          NB: if you need the key or value to free it, read it before
+ *          removing. ie: beware memory leaks!  this will not remove the key.
+ *          returns zero if advanced to end of table */
+
+ssize_t
+hashtable_iterator_remove(hashtable_itr_t *itr);
+
+/*****************************************************************************/
+/* search - overwrite the supplied iterator, to point to the entry
+ *          matching the supplied key.
+ *          h points to the hashtable to be searched.
+ *          returns zero if not found. */
+ssize_t
+hashtable_iterator_search(hashtable_itr_t *itr,
+                          hashtable_t *h, void *k);
+
+#define DEFINE_HASHTABLE_ITERATOR_SEARCH(fnname, keytype) \
+ssize_t fnname (hashtable_itr_t *i, hashtable_t *h, keytype *k) \
+{ \
+    return (hashtable_iterator_search(i,h,k)); \
+}
+
 
 #endif /* __ROS_KERN_HASHTABLE_H__ */
 
 /*
- * Copyright (c) 2002, Christopher Clark
+ * Copyright (c) 2002, 2004, Christopher Clark
  * All rights reserved.
  * 
  * Redistribution and use in source and binary forms, with or without
diff --git a/kern/include/hashtable_itr.h b/kern/include/hashtable_itr.h
deleted file mode 100644 (file)
index c0946bd..0000000
+++ /dev/null
@@ -1,110 +0,0 @@
-/* Copyright (C) 2002, 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
-
-#ifndef __ROS_KERN_HASHTABLE_ITR_H__
-#define ___ROS_KERN_HASHTABLE_ITR_H__
-
-#include <hashtable.h>
-
-/*****************************************************************************/
-/* This struct is only concrete here to allow the inlining of two of the
- * accessor functions. */
-typedef struct hashtable_itr {
-    hashtable_t *h;
-    hash_entry_t *e;
-    hash_entry_t *parent;
-    size_t index;
-} hashtable_itr_t;
-
-/*****************************************************************************/
-/* hashtable_iterator
- */
-
-hashtable_itr_t *
-hashtable_iterator(hashtable_t *h);
-
-/*****************************************************************************/
-/* hashtable_iterator_key
- * - return the value of the (key,value) pair at the current position */
-
-extern inline void *
-hashtable_iterator_key(hashtable_itr_t *i)
-{
-    return i->e->k;
-}
-
-/*****************************************************************************/
-/* value - return the value of the (key,value) pair at the current position */
-
-extern inline void *
-hashtable_iterator_value(hashtable_itr_t *i)
-{
-    return i->e->v;
-}
-
-/*****************************************************************************/
-/* advance - advance the iterator to the next element
- *           returns zero if advanced to end of table */
-
-ssize_t
-hashtable_iterator_advance(hashtable_itr_t *itr);
-
-/*****************************************************************************/
-/* remove - remove current element and advance the iterator to the next element
- *          NB: if you need the value to free it, read it before
- *          removing. ie: beware memory leaks!
- *          returns zero if advanced to end of table */
-
-ssize_t
-hashtable_iterator_remove(hashtable_itr_t *itr);
-
-/*****************************************************************************/
-/* search - overwrite the supplied iterator, to point to the entry
- *          matching the supplied key.
-            h points to the hashtable to be searched.
- *          returns zero if not found. */
-ssize_t
-hashtable_iterator_search(hashtable_itr_t *itr,
-                          hashtable_t *h, void *k);
-
-#define DEFINE_HASHTABLE_ITERATOR_SEARCH(fnname, keytype) \
-ssize_t fnname (hashtable_itr_t *i, hashtable_t *h, keytype *k) \
-{ \
-    return (hashtable_iterator_search(i,h,k)); \
-}
-
-
-
-#endif /* __ROS_KERN_HASHTABLE_ITR_H__*/
-
-/*
- * Copyright (c) 2002, 2004, Christopher Clark
- * All rights reserved.
- * 
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 
- * * Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * 
- * * Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- * 
- * * Neither the name of the original author; nor the names of any contributors
- * may be used to endorse or promote products derived from this software
- * without specific prior written permission.
- * 
- * 
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
- * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
- * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
- * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
- * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-*/
index 81d99a2..88a4e53 100644 (file)
@@ -25,6 +25,7 @@ void test_circ_buffer(void);
 void test_active_messages(void);
 void test_slab(void);
 void test_kmalloc(void);
+void test_hashtable(void);
 
 struct trapframe_t;
 
index 4bf15e7..8ea2092 100644 (file)
@@ -15,11 +15,7 @@ KERN_SRCFILES := $(KERN_ARCH_SRCFILES) \
                  $(KERN_SRC_DIR)/init.c \
                  $(KERN_SRC_DIR)/monitor.c \
                  $(KERN_SRC_DIR)/printf.c \
-                 $(KERN_SRC_DIR)/trap.c \
-                 $(KERN_SRC_DIR)/trapentry.S \
                  $(KERN_SRC_DIR)/sched.c \
-                 $(KERN_SRC_DIR)/kdebug.c \
-                 $(KERN_SRC_DIR)/apic.c \
                  $(KERN_SRC_DIR)/printfmt.c \
                  $(KERN_SRC_DIR)/smp.c \
                  $(KERN_SRC_DIR)/multiboot.c \
@@ -38,7 +34,6 @@ KERN_SRCFILES := $(KERN_ARCH_SRCFILES) \
                  $(KERN_SRC_DIR)/process.c \
                  $(KERN_SRC_DIR)/kmalloc.c \
                  $(KERN_SRC_DIR)/hashtable.c \
-                 $(KERN_SRC_DIR)/hashtable_itr.c \
                  $(KERN_SRC_DIR)/schedule.c \
                  $(KERN_SRC_DIR)/mm.c \
                  $(KERN_SRC_DIR)/resource.c \
index 1959788..5d1d25a 100644 (file)
@@ -1,9 +1,18 @@
-/* Copyright (C) 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
+/* Copyright (C) 2002, 2004 Christopher Clark  <firstname.lastname@cl.cam.ac.uk>
+ * 
+ * Modified 2009 by Barret Rhoden <brho@cs.berkeley.edu>
+ * Changes include:
+ *   - No longer frees keys or values.  It's up to the client to do that.
+ *   - Uses the slab allocator for hash entry allocation.
+ *   - Merges the iterator code with the main hash table code, mostly to avoid
+ *   externing the hentry cache. */
 
 #include <ros/common.h>
 #include <hashtable.h>
 #include <stdio.h>
+#include <assert.h>
 #include <string.h>
+#include <slab.h>
 #include <kmalloc.h>
 
 // File was not annotated and caused ivy based compilation to fail
@@ -35,6 +44,29 @@ const unsigned int prime_table_length = sizeof(primes)/sizeof(primes[0]);
     ((size * 13)/20)
 //const float max_load_factor = 0.65;
 
+struct kmem_cache *hentry_cache;
+
+/* Call this once on bootup, after initializing the slab allocator.  */
+void hashtable_init(void)
+{
+       hentry_cache = kmem_cache_create("hash_entry", sizeof(struct hash_entry),
+                                        __alignof__(struct hash_entry), 0, 0, 0);
+}
+
+/* Common hash/equals functions.  Don't call these directly. */
+size_t __generic_hash(void *k)
+{
+       /* 0x9e370001UL used by Linux (32 bit)
+        * (prime approx to the golden ratio to the max integer, IAW Knuth)
+        */
+       return (size_t)k * 0x9e370001UL;        
+}
+
+ssize_t __generic_eq(void *k1, void *k2)
+{
+       return k1 == k2;
+}
+
 /*****************************************************************************/
 hashtable_t *
 create_hashtable(size_t minsize,
@@ -158,7 +190,7 @@ hashtable_insert(hashtable_t *h, void *k, void *v)
          * element may be ok. Next time we insert, we'll try expanding again.*/
         hashtable_expand(h);
     }
-    e = (hash_entry_t *)kmalloc(sizeof(hash_entry_t), 0);
+    e = (hash_entry_t *)kmem_cache_alloc(hentry_cache, 0);
     if (NULL == e) { --(h->entrycount); return 0; } /*oom*/
     e->h = hash(h,k);
     index = indexFor(h->tablelength,e->h);
@@ -211,8 +243,7 @@ hashtable_remove(hashtable_t *h, void *k)
             *pE = e->next;
             h->entrycount--;
             v = e->v;
-            freekey(e->k);
-            kfree(e);
+                       kmem_cache_free(hentry_cache, e);
             return v;
         }
         pE = &(e->next);
@@ -224,35 +255,177 @@ hashtable_remove(hashtable_t *h, void *k)
 /*****************************************************************************/
 /* destroy */
 void
-hashtable_destroy(hashtable_t *h, int free_values)
+hashtable_destroy(hashtable_t *h)
 {
+       if (hashtable_count(h))
+               warn("Destroying a non-empty hashtable, clean up after yourself!\n");
+
     size_t i;
     hash_entry_t *e, *f;
     hash_entry_t **table = h->table;
-    if (free_values)
+       for (i = 0; i < h->tablelength; i++) {
+               e = table[i];
+               while (NULL != e) {
+                       f = e;
+                       e = e->next;
+                       kmem_cache_free(hentry_cache, f);
+               }
+       }
+    kfree(h->table);
+    kfree(h);
+}
+
+/*****************************************************************************/
+/* hashtable_iterator    - iterator constructor
+ *
+ * If the htable isn't empty, e and index will refer to the first entry. */
+
+hashtable_itr_t *
+hashtable_iterator(hashtable_t *h)
+{
+    size_t i, tablelength;
+    hashtable_itr_t *itr = (hashtable_itr_t *)
+        kmalloc(sizeof(hashtable_itr_t), 0);
+    if (NULL == itr) return NULL;
+    itr->h = h;
+    itr->e = NULL;
+    itr->parent = NULL;
+    tablelength = h->tablelength;
+    itr->index = tablelength;
+    if (0 == h->entrycount) return itr;
+
+    for (i = 0; i < tablelength; i++)
+    {
+        if (NULL != h->table[i])
+        {
+            itr->e = h->table[i];
+            itr->index = i;
+            break;
+        }
+    }
+    return itr;
+}
+
+/*****************************************************************************/
+/* key      - return the key of the (key,value) pair at the current position */
+/* value    - return the value of the (key,value) pair at the current position */
+
+void *
+hashtable_iterator_key(hashtable_itr_t *i)
+{ return i->e->k; }
+
+void *
+hashtable_iterator_value(hashtable_itr_t *i)
+{ return i->e->v; }
+
+/*****************************************************************************/
+/* advance - advance the iterator to the next element
+ *           returns zero if advanced to end of table */
+
+ssize_t
+hashtable_iterator_advance(hashtable_itr_t *itr)
+{
+    size_t j,tablelength;
+    hash_entry_t **table;
+    hash_entry_t *next;
+    if (NULL == itr->e) return 0; /* stupidity check */
+
+    next = itr->e->next;
+    if (NULL != next)
     {
-        for (i = 0; i < h->tablelength; i++)
+        itr->parent = itr->e;
+        itr->e = next;
+        return -1;
+    }
+    tablelength = itr->h->tablelength;
+    itr->parent = NULL;
+    if (tablelength <= (j = ++(itr->index)))
+    {
+        itr->e = NULL;
+        return 0;
+    }
+    table = itr->h->table;
+    while (NULL == (next = table[j]))
+    {
+        if (++j >= tablelength)
         {
-            e = table[i];
-            while (NULL != e)
-            { f = e; e = e->next; freekey(f->k); kfree(f->v); kfree(f); }
+            itr->index = tablelength;
+            itr->e = NULL;
+            return 0;
         }
     }
-    else
+    itr->index = j;
+    itr->e = next;
+    return -1;
+}
+
+/*****************************************************************************/
+/* remove - remove the entry at the current iterator position
+ *          and advance the iterator, if there is a successive
+ *          element.
+ *          If you want the value, read it before you remove:
+ *          beware memory leaks if you don't.
+ *          Returns zero if end of iteration. */
+
+ssize_t
+hashtable_iterator_remove(hashtable_itr_t *itr)
+{
+    hash_entry_t *remember_e, *remember_parent;
+    ssize_t ret;
+
+    /* Do the removal */
+    if (NULL == (itr->parent))
     {
-        for (i = 0; i < h->tablelength; i++)
+        /* element is head of a chain */
+        itr->h->table[itr->index] = itr->e->next;
+    } else {
+        /* element is mid-chain */
+        itr->parent->next = itr->e->next;
+    }
+    /* itr->e is now outside the hashtable */
+    remember_e = itr->e;
+    itr->h->entrycount--;
+
+    /* Advance the iterator, correcting the parent */
+    remember_parent = itr->parent;
+    ret = hashtable_iterator_advance(itr);
+    if (itr->parent == remember_e) { itr->parent = remember_parent; }
+       kmem_cache_free(hentry_cache, remember_e);
+    return ret;
+}
+
+/*****************************************************************************/
+ssize_t /* returns zero if not found */
+hashtable_iterator_search(hashtable_itr_t *itr,
+                          hashtable_t *h, void *k)
+{
+    hash_entry_t *e, *parent;
+    size_t hashvalue, index;
+
+    hashvalue = hash(h,k);
+    index = indexFor(h->tablelength,hashvalue);
+
+    e = h->table[index];
+    parent = NULL;
+    while (NULL != e)
+    {
+        /* Check hash value to short circuit heavier comparison */
+        if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
         {
-            e = table[i];
-            while (NULL != e)
-            { f = e; e = e->next; freekey(f->k); kfree(f); }
+            itr->index = index;
+            itr->e = e;
+            itr->parent = parent;
+            itr->h = h;
+            return -1;
         }
+        parent = e;
+        e = e->next;
     }
-    kfree(h->table);
-    kfree(h);
+    return 0;
 }
 
 /*
- * Copyright (c) 2002, Christopher Clark
+ * Copyright (c) 2002, 2004, Christopher Clark
  * All rights reserved.
  * 
  * Redistribution and use in source and binary forms, with or without
diff --git a/kern/src/hashtable_itr.c b/kern/src/hashtable_itr.c
deleted file mode 100644 (file)
index 6ee77d5..0000000
+++ /dev/null
@@ -1,188 +0,0 @@
-/* Copyright (C) 2002, 2004 Christopher Clark  <firstname.lastname@cl.cam.ac.uk> */
-
-#include <ros/common.h>
-#include <kmalloc.h>
-#include <hashtable.h>
-#include <hashtable_itr.h>
-
-/*****************************************************************************/
-/* hashtable_iterator    - iterator constructor */
-
-hashtable_itr_t *
-hashtable_iterator(hashtable_t *h)
-{
-    size_t i, tablelength;
-    hashtable_itr_t *itr = (hashtable_itr_t *)
-        kmalloc(sizeof(hashtable_itr_t), 0);
-    if (NULL == itr) return NULL;
-    itr->h = h;
-    itr->e = NULL;
-    itr->parent = NULL;
-    tablelength = h->tablelength;
-    itr->index = tablelength;
-    if (0 == h->entrycount) return itr;
-
-    for (i = 0; i < tablelength; i++)
-    {
-        if (NULL != h->table[i])
-        {
-            itr->e = h->table[i];
-            itr->index = i;
-            break;
-        }
-    }
-    return itr;
-}
-
-/*****************************************************************************/
-/* key      - return the key of the (key,value) pair at the current position */
-/* value    - return the value of the (key,value) pair at the current position */
-
-void *
-hashtable_iterator_key(hashtable_itr_t *i)
-{ return i->e->k; }
-
-void *
-hashtable_iterator_value(hashtable_itr_t *i)
-{ return i->e->v; }
-
-/*****************************************************************************/
-/* advance - advance the iterator to the next element
- *           returns zero if advanced to end of table */
-
-ssize_t
-hashtable_iterator_advance(hashtable_itr_t *itr)
-{
-    size_t j,tablelength;
-    hash_entry_t **table;
-    hash_entry_t *next;
-    if (NULL == itr->e) return 0; /* stupidity check */
-
-    next = itr->e->next;
-    if (NULL != next)
-    {
-        itr->parent = itr->e;
-        itr->e = next;
-        return -1;
-    }
-    tablelength = itr->h->tablelength;
-    itr->parent = NULL;
-    if (tablelength <= (j = ++(itr->index)))
-    {
-        itr->e = NULL;
-        return 0;
-    }
-    table = itr->h->table;
-    while (NULL == (next = table[j]))
-    {
-        if (++j >= tablelength)
-        {
-            itr->index = tablelength;
-            itr->e = NULL;
-            return 0;
-        }
-    }
-    itr->index = j;
-    itr->e = next;
-    return -1;
-}
-
-/*****************************************************************************/
-/* remove - remove the entry at the current iterator position
- *          and advance the iterator, if there is a successive
- *          element.
- *          If you want the value, read it before you remove:
- *          beware memory leaks if you don't.
- *          Returns zero if end of iteration. */
-
-ssize_t
-hashtable_iterator_remove(hashtable_itr_t *itr)
-{
-    hash_entry_t *remember_e, *remember_parent;
-    ssize_t ret;
-
-    /* Do the removal */
-    if (NULL == (itr->parent))
-    {
-        /* element is head of a chain */
-        itr->h->table[itr->index] = itr->e->next;
-    } else {
-        /* element is mid-chain */
-        itr->parent->next = itr->e->next;
-    }
-    /* itr->e is now outside the hashtable */
-    remember_e = itr->e;
-    itr->h->entrycount--;
-    freekey(remember_e->k);
-
-    /* Advance the iterator, correcting the parent */
-    remember_parent = itr->parent;
-    ret = hashtable_iterator_advance(itr);
-    if (itr->parent == remember_e) { itr->parent = remember_parent; }
-    kfree(remember_e);
-    return ret;
-}
-
-/*****************************************************************************/
-ssize_t /* returns zero if not found */
-hashtable_iterator_search(hashtable_itr_t *itr,
-                          hashtable_t *h, void *k)
-{
-    hash_entry_t *e, *parent;
-    size_t hashvalue, index;
-
-    hashvalue = hash(h,k);
-    index = indexFor(h->tablelength,hashvalue);
-
-    e = h->table[index];
-    parent = NULL;
-    while (NULL != e)
-    {
-        /* Check hash value to short circuit heavier comparison */
-        if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
-        {
-            itr->index = index;
-            itr->e = e;
-            itr->parent = parent;
-            itr->h = h;
-            return -1;
-        }
-        parent = e;
-        e = e->next;
-    }
-    return 0;
-}
-
-
-/*
- * Copyright (c) 2002, 2004, Christopher Clark
- * All rights reserved.
- * 
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 
- * * Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * 
- * * Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- * 
- * * Neither the name of the original author; nor the names of any contributors
- * may be used to endorse or promote products derived from this software
- * without specific prior written permission.
- * 
- * 
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
- * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
- * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
- * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
- * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-*/
index a58831e..ccc65e0 100644 (file)
@@ -27,6 +27,7 @@
 #include <manager.h>
 #include <testing.h>
 #include <kmalloc.h>
+#include <hashtable.h>
 
 #include <arch/init.h>
 #include <slab.h>
@@ -67,6 +68,7 @@ void kernel_init(multiboot_info_t *mboot_info)
        page_check();
        kmem_cache_init();
        kmalloc_init();
+       hashtable_init();
 
        idt_init();
        active_msg_init();
index b3ed697..579d484 100644 (file)
@@ -28,6 +28,7 @@
 #include <pmap.h>
 #include <slab.h>
 #include <kmalloc.h>
+#include <hashtable.h>
 
 #ifdef __i386__
 
@@ -853,3 +854,103 @@ void test_kmalloc(void)
        kfree(bufs[0]);
 }
 
+static size_t test_hash_fn_col(void *k)
+{
+       return (size_t)k % 2; // collisions in slots 0 and 1
+}
+
+void test_hashtable(void)
+{
+       struct test {int x; int y;};
+       struct test tstruct[10];
+
+       struct hashtable *h;
+       int k = 5;
+       struct test *v = &tstruct[0];
+
+       h = create_hashtable(32, __generic_hash, __generic_eq);
+       
+       // test inserting one item, then finding it again
+       printk("Tesing one item, insert, search, and removal\n");
+       if(!hashtable_insert(h, (void*)k, v))
+               printk("Failed to insert to hashtable!\n");
+       v = NULL;
+       if (!(v = hashtable_search(h, (void*)k)))
+               printk("Failed to find in hashtable!\n");
+       if (v != &tstruct[0])
+               printk("Got the wrong item! (got %p, wanted %p)\n", v, &tstruct[0]);
+       v = NULL;
+       if (!(v = hashtable_remove(h, (void*)k)))
+               printk("Failed to remove from hashtable!\n");
+       // shouldn't be able to find it again
+       if ((v = hashtable_search(h, (void*)k)))
+               printk("Should not have been able to find in hashtable!\n");
+       
+       printk("Tesing a bunch of items, insert, search, and removal\n");
+       for (int i = 0; i < 10; i++) {
+               k = i; // vary the key, we don't do KEY collisions
+               if(!hashtable_insert(h, (void*)k, &tstruct[i]))
+                       printk("Failed to insert iter %d to hashtable!\n", i);
+       }
+       // read out the 10 items
+       for (int i = 0; i < 10; i++) {
+               k = i;
+               if (!(v = hashtable_search(h, (void*)k)))
+                       printk("Failed to find in hashtable!\n");
+               if (v != &tstruct[i])
+                       printk("Got the wrong item! (got %p, wanted %p)\n", v, &tstruct[i]);
+       }
+       if (hashtable_count(h) != 10)
+               printk("Wrong accounting of number of elements!\n");
+       // remove the 10 items
+       for (int i = 0; i < 10; i++) {
+               k = i;
+               if (!(v = hashtable_remove(h, (void*)k)))
+                       printk("Failed to remove from hashtable!\n");
+       }
+       // make sure they are all gone
+       for (int i = 0; i < 10; i++) {
+               k = i;
+               if ((v = hashtable_search(h, (void*)k)))
+                       printk("Should not have been able to find in hashtable!\n");
+       }
+       if (hashtable_count(h))
+               printk("Wrong accounting of number of elements!\n");
+       hashtable_destroy(h);
+
+       // same test of a bunch of items, but with collisions.
+       printk("Tesing a bunch of items with collisions, etc.\n");
+       h = create_hashtable(32, test_hash_fn_col, __generic_eq);
+       // insert 10 items
+       for (int i = 0; i < 10; i++) {
+               k = i; // vary the key, we don't do KEY collisions
+               if(!hashtable_insert(h, (void*)k, &tstruct[i]))
+                       printk("Failed to insert iter %d to hashtable!\n", i);
+       }
+       // read out the 10 items
+       for (int i = 0; i < 10; i++) {
+               k = i;
+               if (!(v = hashtable_search(h, (void*)k)))
+                       printk("Failed to find in hashtable!\n");
+               if (v != &tstruct[i])
+                       printk("Got the wrong item! (got %p, wanted %p)\n", v, &tstruct[i]);
+       }
+       if (hashtable_count(h) != 10)
+               printk("Wrong accounting of number of elements!\n");
+       // remove the 10 items
+       for (int i = 0; i < 10; i++) {
+               k = i;
+               if (!(v = hashtable_remove(h, (void*)k)))
+                       printk("Failed to remove from hashtable!\n");
+       }
+       // make sure they are all gone
+       for (int i = 0; i < 10; i++) {
+               k = i;
+               if ((v = hashtable_search(h, (void*)k)))
+                       printk("Should not have been able to find in hashtable!\n");
+       }
+       if (hashtable_count(h))
+               printk("Wrong accounting of number of elements!\n");
+       hashtable_destroy(h);
+}
+