vfs: Remove the guts of the VFS
[akaros.git] / kern / include / hashtable.h
index 471dc02..3e94257 100644 (file)
@@ -1,15 +1,15 @@
-/* Copyright (C) 2002 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
-
-#ifndef __ROS_KERN_HASHTABLE_H__
-#define __ROS_KERN_HASHTABLE_H__
-
-#ifdef __DEPUTY__
-#pragma nodeputy
-#endif
+/* 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.
+ *   - hash for each */
 
-#ifdef __SHARC__
-#pragma nosharc
-#endif
+#pragma once
 
 #include <ros/common.h>
 
@@ -31,16 +31,15 @@ typedef struct hashtable {
     ssize_t (*eqfn) (void *k1, void *k2);
 } hashtable_t;
 
-size_t hash(struct hashtable *h, void *k);
 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;
@@ -54,7 +53,7 @@ static inline size_t indexFor(unsigned int tablelength, unsigned int hashvalue)
  *      v = (struct some_value *)   kmalloc(sizeof(struct some_value));
  *
  *      (initialise k and v to suitable values)
- * 
+ *
  *      if (! hashtable_insert(h,k,v) )
  *      {     panic("Hashtable broken...\n");       }
  *
@@ -68,7 +67,7 @@ static inline size_t indexFor(unsigned int tablelength, unsigned int hashvalue)
 
 /* Macros may be used to define type-safe(r) hashtable access functions, with
  * methods specialized to take known key and value types as parameters.
- * 
+ *
  * Example:
  *
  * Insert this at the start of your file:
@@ -96,9 +95,16 @@ 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
-   
+
  * @name                    create_hashtable
  * @param   minsize         minimum initial size of hashtable
  * @param   hashfunction    function for hashing keys
@@ -113,11 +119,11 @@ create_hashtable(size_t minsize,
 
 /*****************************************************************************
  * hashtable_insert
-   
+
  * @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
@@ -130,7 +136,7 @@ create_hashtable(size_t minsize,
  * If in doubt, remove before insert.
  */
 
-ssize_t 
+ssize_t
 hashtable_insert(hashtable_t *h, void *k, void *v);
 
 #define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \
@@ -141,10 +147,10 @@ ssize_t fnname (hashtable_t *h, keytype *k, valuetype *v) \
 
 /*****************************************************************************
  * hashtable_search
-   
+
  * @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
  */
 
@@ -159,11 +165,13 @@ valuetype * fnname (hashtable_t *h, keytype *k) \
 
 /*****************************************************************************
  * hashtable_remove
-   
+
  * @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 */
@@ -178,48 +186,132 @@ valuetype * fnname (hashtable_t *h, keytype *k) \
 
 /*****************************************************************************
  * hashtable_count
-   
+
  * @name        hashtable_count
  * @param   h   the hashtable
  * @return      the number of items stored in the hashtable
  */
+
 size_t
 hashtable_count(hashtable_t *h);
 
 
 /*****************************************************************************
  * hashtable_destroy
-   
+
  * @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.  Be sure to kfree this when you are done.
+ */
+
+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 */
 
-#endif /* __ROS_KERN_HASHTABLE_H__ */
+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)); \
+}
+
+/* Runs func on each member of the hash table */
+void hash_for_each(struct hashtable *hash, void func(void *, void *),
+                                  void *opaque);
+/* Same, but removes the item too */
+void hash_for_each_remove(struct hashtable *hash, void func(void *, void *),
+                                                 void *opaque);
 
 /*
- * 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
  * 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