X-Git-Url: https://git.artsoft.org/?a=blobdiff_plain;f=src%2Flibgame%2Fhash.c;h=2b856f6810df38cc739c62e7b2695b5586b1cc69;hb=96626a07ae084d613fd85fa9eb87fd8b3495af59;hp=fbf61ff00143430ed52f72b0a7dc0ff0c9938f78;hpb=abe44529b439ad39b4d8dbf19cbd67c9b9844279;p=rocksndiamonds.git

diff --git a/src/libgame/hash.c b/src/libgame/hash.c
index fbf61ff0..2b856f68 100644
--- a/src/libgame/hash.c
+++ b/src/libgame/hash.c
@@ -4,7 +4,7 @@
 // (c) 1995-2014 by Artsoft Entertainment
 //     		    Holger Schemel
 //		    info@artsoft.org
-//		    http://www.artsoft.org/
+//		    https://www.artsoft.org/
 // ----------------------------------------------------------------------------
 // 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;
@@ -70,7 +72,7 @@ create_hashtable(unsigned int minsize, float maxloadfactor,
     return NULL;
   }
 
-  for (i=0; i < size; i++)
+  for (i = 0; i < size; i++)
     h->table[i] = NULL;
 
   h->tablelength  = size;
@@ -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)
@@ -134,7 +147,7 @@ hashtable_expand(struct hashtable *h)
       while ((e = h->table[i]) != NULL)
       {
 	h->table[i] = e->next;
-	index = indexFor(newsize,e->h);
+	index = indexFor(newsize, e->h);
 	e->next = newtable[index];
 	newtable[index] = e;
       }
@@ -160,7 +173,7 @@ hashtable_expand(struct hashtable *h)
     {
       for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE)
       {
-	index = indexFor(newsize,e->h);
+	index = indexFor(newsize, e->h);
 
 	if (index == i)
 	{
@@ -216,8 +229,8 @@ hashtable_insert(struct hashtable *h, void *k, void *v)
     return 0;
   }
 
-  e->h = hash(h,k);
-  index = indexFor(h->tablelength,e->h);
+  e->h = hash(h, k);
+  index = indexFor(h->tablelength, e->h);
   e->k = k;
   e->v = v;
   e->next = h->table[index];
@@ -233,8 +246,8 @@ hashtable_change(struct hashtable *h, void *k, void *v)
   struct entry *e;
   unsigned int hashvalue, index;
 
-  hashvalue = hash(h,k);
-  index = indexFor(h->tablelength,hashvalue);
+  hashvalue = hash(h, k);
+  index = indexFor(h->tablelength, hashvalue);
   e = h->table[index];
 
   while (e != NULL)
@@ -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)
@@ -261,8 +298,8 @@ hashtable_search(struct hashtable *h, void *k)
   struct entry *e;
   unsigned int hashvalue, index;
 
-  hashvalue = hash(h,k);
-  index = indexFor(h->tablelength,hashvalue);
+  hashvalue = hash(h, k);
+  index = indexFor(h->tablelength, hashvalue);
   e = h->table[index];
 
   while (e != NULL)
@@ -287,7 +324,7 @@ hashtable_remove(struct hashtable *h, void *k)
   struct entry *e;
   struct entry **pE;
   void *v;
-  unsigned int index = indexFor(h->tablelength,hash(h,k));
+  unsigned int index = indexFor(h->tablelength, hash(h, k));
 
   pE = &(h->table[index]);
   e = *pE;
@@ -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 */
 
@@ -379,7 +420,7 @@ hashtable_iterator(struct hashtable *h)
 }
 
 /*****************************************************************************/
-/* key - return the key of the (key,value) pair at the current position */
+/* key - return the key of the (key, value) pair at the current position */
 
 void *
 hashtable_iterator_key(struct hashtable_itr *i)
@@ -388,7 +429,7 @@ 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 */
 
 void *
 hashtable_iterator_value(struct hashtable_itr *i)
@@ -403,7 +444,7 @@ hashtable_iterator_value(struct hashtable_itr *i)
 int
 hashtable_iterator_advance(struct hashtable_itr *itr)
 {
-  unsigned int j,tablelength;
+  unsigned int j, tablelength;
   struct entry **table;
   struct entry *next;
 
@@ -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;
+}