-/* 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>
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;
* 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"); }
*
/* 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:
*
*/
+/* 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
/*****************************************************************************
* 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
* 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) \
/*****************************************************************************
* 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
*/
/*****************************************************************************
* 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 */
/*****************************************************************************
* 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
projects / akaros.git / blobdiff