added functions to iterate through hash table and remove hash entries

[rocksndiamonds.git] / src / libgame / hash.c

diff --git a/src/libgame/hash.c b/src/libgame/hash.c
index e021da5c5959be418610e078e212d1e150e279e7..2b856f6810df38cc739c62e7b2695b5586b1cc69 100644 (file)
--- a/src/libgame/hash.c
+++ b/src/libgame/hash.c
@@ -41,9 +41,11 @@
 
 /*****************************************************************************/
 struct hashtable *
-create_hashtable(unsigned int minsize, float maxloadfactor,
-                 unsigned int (*hashf) (void*),
-                 int (*eqf) (void*, void*))
+create_hashtable_ext(unsigned int minsize, float maxloadfactor,
+                    unsigned int (*hashf) (void*),
+                    int (*eqf) (void*, void*),
+                     void (*freekfn) (void*),
+                     void (*freevfn) (void*))
 {
   struct hashtable *h;
   unsigned int i, size = 1u;
@@ -78,10 +80,21 @@ create_hashtable(unsigned int minsize, float maxloadfactor,
   h->hashfn       = hashf;
   h->eqfn         = eqf;
   h->loadlimit    = (unsigned int) ((float)size * maxloadfactor);
+  h->freekfn      = freekfn;
+  h->freevfn      = freevfn;
 
   return h;
 }
 
+struct hashtable *
+create_hashtable(unsigned int (*hashf) (void*),
+                 int (*eqf) (void*, void*),
+                 void (*freekfn) (void*),
+                 void (*freevfn) (void*))
+{
+  return create_hashtable_ext(16, 0.75, hashf, eqf, freekfn, freevfn);
+}
+
 /*****************************************************************************/
 static unsigned int
 hash(struct hashtable *h, void *k)
@@ -242,7 +255,8 @@ hashtable_change(struct hashtable *h, void *k, void *v)
     /* Check hash value to short circuit heavier comparison */
     if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
     {
-      free(e->v);
+      if (h->freevfn != NULL)
+       h->freevfn(e->v);
       e->v = v;
 
       return -1;
@@ -254,6 +268,29 @@ hashtable_change(struct hashtable *h, void *k, void *v)
   return 0;
 }
 
+/*****************************************************************************/
+int /* checks if key exists */
+hashtable_exists(struct hashtable *h, void *k)
+{
+  struct entry *e;
+  unsigned int hashvalue, index;
+
+  hashvalue = hash(h, k);
+  index = indexFor(h->tablelength, hashvalue);
+  e = h->table[index];
+
+  while (e != NULL)
+  {
+    /* Check hash value to short circuit heavier comparison */
+    if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
+      return 1;
+
+    e = e->next;
+  }
+
+  return 0;
+}
+
 /*****************************************************************************/
 void * /* returns value associated with key */
 hashtable_search(struct hashtable *h, void *k)
@@ -298,8 +335,13 @@ hashtable_remove(struct hashtable *h, void *k)
     {
       *pE = e->next;
       h->entrycount--;
-      v = e->v;
-      free(e->k);
+      v = NULL;
+      if (h->freekfn != NULL)
+       h->freekfn(e->k);
+      if (h->freevfn != NULL)
+       h->freevfn(e->v);
+      else
+       v = e->v;
       free(e);
 
       return v;
@@ -315,7 +357,7 @@ hashtable_remove(struct hashtable *h, void *k)
 /*****************************************************************************/
 /* destroy */
 void
-hashtable_destroy(struct hashtable *h, int free_values)
+hashtable_destroy(struct hashtable *h)
 {
   unsigned int i;
   struct entry *e, *f;
@@ -329,10 +371,10 @@ hashtable_destroy(struct hashtable *h, int free_values)
     {
       f = e;
       e = e->next;
-      free(f->k);
-
-      if (free_values)
-       free(f->v);
+      if (h->freekfn != NULL)
+       h->freekfn(f->k);
+      if (h->freevfn != NULL)
+       h->freevfn(f->v);
 
       free(f);
     }
@@ -342,7 +384,6 @@ hashtable_destroy(struct hashtable *h, int free_values)
   free(h);
 }
 
-
 /*****************************************************************************/
 /* hashtable_iterator    - iterator constructor */
 
@@ -442,3 +483,106 @@ hashtable_iterator_advance(struct hashtable_itr *itr)
 
   return -1;
 }
+
+/*****************************************************************************/
+/* call function for all hashtable entries */
+void
+hashtable_foreach(struct hashtable *h, hashtable_fn fn, void *userdata)
+{
+  if (h == NULL)
+    return;
+
+  if (hashtable_count(h) == 0)
+    return;
+
+  struct hashtable_itr *itr = hashtable_iterator(h);
+
+  do
+  {
+    fn(hashtable_iterator_key(itr), hashtable_iterator_value(itr), userdata);
+  }
+  while (hashtable_iterator_advance(itr));
+
+  free(itr);
+}
+
+/*****************************************************************************/
+/* call function for all hashtable entries and remove them, if function returned 1 */
+unsigned int
+hashtable_foreach_remove(struct hashtable *h, hashtable_remove_fn fn, void *userdata)
+{
+  if (h == NULL)
+    return 0;
+
+  if (hashtable_count(h) == 0)
+    return 0;
+
+  struct hashtable *remove = create_hashtable(h->hashfn, h->eqfn, NULL, NULL);
+  struct hashtable_itr *itr = hashtable_iterator(h);
+
+  do
+  {
+    if (fn(hashtable_iterator_key(itr), hashtable_iterator_value(itr), userdata))
+      hashtable_insert(remove, hashtable_iterator_key(itr), "1");
+  }
+  while (hashtable_iterator_advance(itr));
+
+  free(itr);
+
+  struct hashtable_itr *itr_remove = hashtable_iterator(remove);
+  unsigned int num_removed = 0;
+
+  do
+  {
+    hashtable_remove(h, hashtable_iterator_key(itr_remove));
+    num_removed++;
+  }
+  while (hashtable_iterator_advance(itr_remove));
+
+  free(itr_remove);
+
+  hashtable_destroy(remove);
+
+  return num_removed;
+}
+
+/*****************************************************************************/
+/* remove_all hashtable entries */
+unsigned int
+hashtable_remove_all(struct hashtable *h)
+{
+  /* TODO: this function should directly remove all hashtable entries */
+
+  if (h == NULL)
+    return 0;
+
+  if (hashtable_count(h) == 0)
+    return 0;
+
+  struct hashtable *remove = create_hashtable(h->hashfn, h->eqfn, NULL, NULL);
+  struct hashtable_itr *itr = hashtable_iterator(h);
+
+  do
+  {
+    hashtable_insert(remove, hashtable_iterator_key(itr), "1");
+  }
+  while (hashtable_iterator_advance(itr));
+
+  free(itr);
+
+  struct hashtable_itr *itr_remove = hashtable_iterator(remove);
+  unsigned int num_removed = 0;
+
+  do
+  {
+    hashtable_remove(h, hashtable_iterator_key(itr_remove));
+    num_removed++;
+  }
+  while (hashtable_iterator_advance(itr_remove));
+
+  free(itr_remove);
+
+  hashtable_destroy(remove);
+
+  return num_removed;
+}