-/***********************************************************
-* Artsoft Retro-Game Library *
-*----------------------------------------------------------*
-* (c) 1994-2003 Artsoft Entertainment *
-* Holger Schemel *
-* Detmolder Strasse 189 *
-* 33604 Bielefeld *
-* Germany *
-* e-mail: info@artsoft.org *
-*----------------------------------------------------------*
-* hash.h *
-***********************************************************/
+// ============================================================================
+// Artsoft Retro-Game Library
+// ----------------------------------------------------------------------------
+// (c) 1995-2014 by Artsoft Entertainment
+// Holger Schemel
+// info@artsoft.org
+// https://www.artsoft.org/
+// ----------------------------------------------------------------------------
+// hash.h
+// ============================================================================
/*
* Copyright (C) 2002 Christopher Clark <firstname.lastname@cl.cam.ac.uk>
* static unsigned int hash_from_key_fn( void *k );
* static int keys_equal_fn ( void *key1, void *key2 );
*
- * h = create_hashtable(16, 0.75, hash_from_key_fn, keys_equal_fn);
+ * h = create_hashtable(16, 0.75, hash_from_key_fn, keys_equal_fn, free, free);
* k = (struct some_key *) malloc(sizeof(struct some_key));
* v = (struct some_value *) malloc(sizeof(struct some_value));
*
/*****************************************************************************/
struct entry
{
- void *k, *v;
- unsigned int h;
- struct entry *next;
+ void *k, *v;
+ unsigned int h;
+ struct entry *next;
};
-struct hashtable {
- unsigned int tablelength;
- struct entry **table;
- unsigned int entrycount;
- unsigned int loadlimit;
- unsigned int (*hashfn) (void *k);
- int (*eqfn) (void *k1, void *k2);
+struct hashtable
+{
+ unsigned int tablelength;
+ struct entry **table;
+ unsigned int entrycount;
+ unsigned int loadlimit;
+ unsigned int (*hashfn) (void *k);
+ int (*eqfn) (void *k1, void *k2);
+ void (*freekfn) (void *k);
+ void (*freevfn) (void *v);
};
/*****************************************************************************/
struct hashtable_itr
{
- struct hashtable *h;
- struct entry *e;
- unsigned int index;
+ struct hashtable *h;
+ struct entry *e;
+ unsigned int index;
};
+typedef struct hashtable HashTable;
+
/*****************************************************************************
- * create_hashtable
+ * create_hashtable_ext
* @name create_hashtable
* @param minsize minimum initial size of hashtable
* @param maxloadfactor maximum ratio entries / tablesize
* @param hashfunction function for hashing keys
* @param key_eq_fn function for determining key equality
+ * @param key_free_fn function for freeing keys
+ * @param value_free_fn function for freeing values
* @return newly created hashtable or NULL on failure
*/
struct hashtable *
-create_hashtable(unsigned int minsize, float maxloadfactor,
- unsigned int (*hashfunction) (void*),
- int (*key_eq_fn) (void*,void*));
+create_hashtable_ext(unsigned int minsize, float maxloadfactor,
+ unsigned int (*hashfunction) (void*),
+ int (*key_eq_fn) (void*, void*),
+ void (*key_free_fn) (void*),
+ void (*value_free_fn) (void*));
+
+/* wrapper function using reasonable default values for some parameters */
+struct hashtable *
+create_hashtable(unsigned int (*hashfunction) (void*),
+ int (*key_eq_fn) (void*, void*),
+ void (*key_free_fn) (void*),
+ void (*value_free_fn) (void*));
/*****************************************************************************
* 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 - will be freed on removal if free function defined
+ * @param v the value - will be freed on removal if free function defined
* @return non-zero for successful insertion
*
* This function will cause the table to expand if the insertion would take
hashtable_insert(struct hashtable *h, void *k, void *v);
#define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \
-int fnname (struct hashtable *h, keytype *k, valuetype *v) \
+static int fnname (struct hashtable *h, keytype *k, valuetype *v) \
{ \
- return hashtable_insert(h,k,v); \
+ return hashtable_insert(h, k, v); \
}
/*****************************************************************************
hashtable_change(struct hashtable *h, void *k, void *v);
#define DEFINE_HASHTABLE_CHANGE(fnname, keytype, valuetype) \
-int fnname (struct hashtable *h, keytype *k, valuetype *v) \
+static int fnname (struct hashtable *h, keytype *k, valuetype *v) \
{ \
- return hashtable_change(h,k,v); \
+ return hashtable_change(h, k, v); \
+}
+
+/*****************************************************************************
+ * hashtable_exists
+
+ * @name hashtable_exists
+ * @param h the hashtable to search
+ * @param k the key to search for
+ * @return non-zero if key exists, else zero
+ */
+
+int
+hashtable_exists(struct hashtable *h, void *k);
+
+#define DEFINE_HASHTABLE_EXISTS(fnname, keytype, valuetype) \
+static int fnname (struct hashtable *h, keytype *k) \
+{ \
+ return hashtable_exists(h, k); \
}
/*****************************************************************************
* @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_search(struct hashtable *h, void *k);
#define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \
-valuetype * fnname (struct hashtable *h, keytype *k) \
+static valuetype * fnname (struct hashtable *h, keytype *k) \
{ \
- return (valuetype *) (hashtable_search(h,k)); \
+ return (valuetype *) (hashtable_search(h, 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
*/
hashtable_remove(struct hashtable *h, void *k);
#define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \
-valuetype * fnname (struct hashtable *h, keytype *k) \
+static valuetype * fnname (struct hashtable *h, keytype *k) \
{ \
- return (valuetype *) (hashtable_remove(h,k)); \
+ return (valuetype *) (hashtable_remove(h, k)); \
}
* hashtable_destroy
* @name hashtable_destroy
- * @param free_values whether to call 'free' on the remaining values
*/
void
-hashtable_destroy(struct hashtable *h, int free_values);
+hashtable_destroy(struct hashtable *h);
/*****************************************************************************/
hashtable_iterator(struct hashtable *h);
/*****************************************************************************/
-/* hashtable_iterator_key
- * - return the value of the (key,value) pair at the current position */
+/* key - return the key of the (key, value) pair at the current position */
-extern inline void *
-hashtable_iterator_key(struct hashtable_itr *i)
-{
- return i->e->k;
-}
+void *
+hashtable_iterator_key(struct hashtable_itr *i);
/*****************************************************************************/
-/* value - return the value of the (key,value) pair at the current position */
+/* value - return the value of the (key, value) pair at the current position */
-extern inline void *
-hashtable_iterator_value(struct hashtable_itr *i)
-{
- return i->e->v;
-}
+void *
+hashtable_iterator_value(struct hashtable_itr *i);
/*****************************************************************************/
/* advance - advance the iterator to the next element
int
hashtable_iterator_advance(struct hashtable_itr *itr);
+
+/*****************************************************************************/
+/* hashtable_fn - prototype of function to call for hashtable entry
+
+ * @name hashtable_fn
+ * @param k the key of the current hash entry
+ * @param v the value of the current hash entry
+ * @param u additional user data
+ */
+
+typedef void (*hashtable_fn) (void *k, void *v, void *u);
+
+/*****************************************************************************/
+/* hashtable_foreach - call function for all hashtable entries
+
+ * @name hashtable_foreach
+ * @param h the hashtable to iterate through
+ * @param fn the function to call for each entry
+ */
+
+void
+hashtable_foreach(struct hashtable *h, hashtable_fn fn, void *userdata);
+
+/*****************************************************************************/
+/* hashtable_remove_fn - prototype of function to call for hashtable entry
+
+ * @name hashtable_remove_fn
+ * @param k the key of the current hash entry
+ * @param v the value of the current hash entry
+ * @param u additional user data
+ * @return non-zero if entry should be removed, else zero
+ */
+
+typedef int (*hashtable_remove_fn) (void *k, void *v, void *u);
+
+/*****************************************************************************/
+/* hashtable_foreach_remove - call function for all hashtable entries and remove them,
+ * if function returned 1
+ * returns the number of removed entries
+
+ * @name hashtable_foreach_remove
+ * @param h the hashtable to iterate through
+ * @param fn the function to call for each entry
+ * @return the number of removed entries
+ */
+
+unsigned int
+hashtable_foreach_remove(struct hashtable *h, hashtable_remove_fn fn, void *userdata);
+
+/*****************************************************************************/
+/* hashtable_remove_all - remove_all hashtable entries
+
+ * @name hashtable_remove
+ * @param h the hashtable to remove all entries from
+ * @return the number of removed entries
+ */
+
+unsigned int
+hashtable_remove_all(struct hashtable *h);
+
#endif
projects / rocksndiamonds.git / blobdiff