Rename RCU CB context to 'cannot block' context
[akaros.git] / kern / src / hashtable.c
index 5d1d25a..1465f2a 100644 (file)
@@ -1,5 +1,5 @@
 /* Copyright (C) 2002, 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.
  * 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.
 #include <string.h>
 #include <slab.h>
 #include <kmalloc.h>
 #include <string.h>
 #include <slab.h>
 #include <kmalloc.h>
-
-// File was not annotated and caused ivy based compilation to fail
-// Someone should really annotate it.
-#ifdef __DEPUTY__
-#pragma nodeputy
-#endif
-
-#ifdef __SHARC__
-#pragma nosharc
-#endif
+#include <hash.h>
+#include <arch/types.h>
 
 /*
 Credit for primes table: Aaron Krowne
 
 /*
 Credit for primes table: Aaron Krowne
@@ -49,17 +41,16 @@ struct kmem_cache *hentry_cache;
 /* Call this once on bootup, after initializing the slab allocator.  */
 void hashtable_init(void)
 {
 /* 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);
+       hentry_cache = kmem_cache_create("hash_entry",
+                                        sizeof(struct hash_entry),
+                                        __alignof__(struct hash_entry), 0,
+                                        NULL, 0, 0, NULL);
 }
 
 /* Common hash/equals functions.  Don't call these directly. */
 size_t __generic_hash(void *k)
 {
 }
 
 /* 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;        
+       return hash_long((unsigned long)k, BITS_PER_LONG);
 }
 
 ssize_t __generic_eq(void *k1, void *k2)
 }
 
 ssize_t __generic_eq(void *k1, void *k2)
@@ -96,7 +87,7 @@ create_hashtable(size_t minsize,
 }
 
 /*****************************************************************************/
 }
 
 /*****************************************************************************/
-size_t
+static size_t
 hash(hashtable_t *h, void *k)
 {
     /* Aim to protect against poor hash functions by adding logic here
 hash(hashtable_t *h, void *k)
 {
     /* Aim to protect against poor hash functions by adding logic here
@@ -140,7 +131,7 @@ hashtable_expand(hashtable_t *h)
         h->table = newtable;
     }
     /* Plan B: realloc instead */
         h->table = newtable;
     }
     /* Plan B: realloc instead */
-    else 
+    else
     {
         newtable = (hash_entry_t**)
                    krealloc(h->table, newsize*sizeof(hash_entry_t*), 0);
     {
         newtable = (hash_entry_t**)
                    krealloc(h->table, newsize*sizeof(hash_entry_t*), 0);
@@ -276,7 +267,8 @@ hashtable_destroy(hashtable_t *h)
 }
 
 /*****************************************************************************/
 }
 
 /*****************************************************************************/
-/* hashtable_iterator    - iterator constructor
+/* hashtable_iterator    - iterator constructor, be sure to kfree this when
+ * you're done.
  *
  * If the htable isn't empty, e and index will refer to the first entry. */
 
  *
  * If the htable isn't empty, e and index will refer to the first entry. */
 
@@ -424,26 +416,55 @@ hashtable_iterator_search(hashtable_itr_t *itr,
     return 0;
 }
 
     return 0;
 }
 
+/* Runs func on each member of the hash table */
+void hash_for_each(struct hashtable *hash, void func(void *, void *),
+                                  void *opaque)
+{
+       if (hashtable_count(hash)) {
+               struct hashtable_itr *iter = hashtable_iterator(hash);
+               do {
+                       void *item = hashtable_iterator_value(iter);
+                       func(item, opaque);
+               } while (hashtable_iterator_advance(iter));
+               kfree(iter);
+       }
+}
+
+/* Runs func on each member of the hash table, removing the item after
+ * processing it.  Make sure func frees the item, o/w you'll leak. */
+void hash_for_each_remove(struct hashtable *hash, void func(void *, void *),
+                                                 void *opaque)
+{
+       if (hashtable_count(hash)) {
+               struct hashtable_itr *iter = hashtable_iterator(hash);
+               do {
+                       void *item = hashtable_iterator_value(iter);
+                       func(item, opaque);
+               } while (hashtable_iterator_remove(iter));
+               kfree(iter);
+       }
+}
+
 /*
  * Copyright (c) 2002, 2004, Christopher Clark
  * All rights reserved.
 /*
  * 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:
  * 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 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.
  * * 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.
  * * 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
  * 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