[Freeciv-Dev] (PR#12893) [PATCH] improved hash tables

["Vasco Alexandre da Silva Costa" <vasc@xxxxxxxxxxxxxx>]

<URL: http://bugs.freeciv.org/Ticket/Display.html?id=12893 >

This patch adds extra functionality to hash tables. This allows to
better keep track of freed memory, and adds a new lookup function.

It is 100% backwards compatible with the existing API, so it means it
has zero impact on existing code on CVS HEAD.

I would like to commit this ASAP, since besides being useful by itself,
it is required for PR#12706: Events framework.

Index: hash.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/utility/hash.c,v
retrieving revision 1.26
diff -u -u -r1.26 hash.c
--- hash.c      4 Apr 2003 15:47:49 -0000       1.26
+++ hash.c      26 Apr 2005 00:23:54 -0000
@@ -121,6 +121,8 @@
   struct hash_bucket *buckets;
   hash_val_fn_t fval;
   hash_cmp_fn_t fcmp;
+  hash_free_fn_t free_key_func;
+  hash_free_fn_t free_data_func;
   unsigned int num_buckets;
   unsigned int num_entries;    /* does not included deleted entries */
   unsigned int num_deleted;
@@ -149,6 +151,8 @@
   h->buckets = NULL;
   h->fval = NULL;
   h->fcmp = NULL;
+  h->free_key_func = NULL;
+  h->free_data_func = NULL;
   h->num_buckets = h->num_entries = h->num_deleted = 0;
   h->frozen = FALSE;
 }
@@ -279,6 +283,8 @@
 **************************************************************************/
 static struct hash_table *hash_new_nbuckets(hash_val_fn_t fval,
                                            hash_cmp_fn_t fcmp,
+                                           hash_free_fn_t free_key_func,
+                                           hash_free_fn_t free_data_func,
                                            unsigned int nbuckets)
 {
   struct hash_table *h;
@@ -293,6 +299,8 @@
   h->num_entries = 0;
   h->fval = fval;
   h->fcmp = fcmp;
+  h->free_key_func = free_key_func;
+  h->free_data_func = free_data_func;
 
   h->buckets = (struct hash_bucket *)
               fc_malloc(h->num_buckets*sizeof(struct hash_bucket));
@@ -304,12 +312,36 @@
 }
 
 /**************************************************************************
+  Full constructor specifying number of entries:
+**************************************************************************/
+struct hash_table *hash_new_nentries_full(hash_val_fn_t fval,
+                                         hash_cmp_fn_t fcmp,
+                                         hash_free_fn_t free_key_func,
+                                         hash_free_fn_t free_data_func,
+                                         unsigned int nentries)
+{
+  return hash_new_nbuckets(fval, fcmp, free_key_func, free_data_func,
+                          calc_appropriate_nbuckets(nentries));
+}
+
+/**************************************************************************
   Constructor specifying number of entries:
 **************************************************************************/
 struct hash_table *hash_new_nentries(hash_val_fn_t fval, hash_cmp_fn_t fcmp,
                                     unsigned int nentries)
 {
-  return hash_new_nbuckets(fval, fcmp, calc_appropriate_nbuckets(nentries));
+  return hash_new_nentries_full(fval, fcmp, NULL, NULL, nentries);
+}
+
+/**************************************************************************
+  Full constructor with unspecified number of entries:
+**************************************************************************/
+struct hash_table *hash_new_full(hash_val_fn_t fval,
+                                hash_cmp_fn_t fcmp,
+                                hash_free_fn_t free_key_func,
+                                hash_free_fn_t free_data_func)
+{
+  return hash_new_nentries_full(fval, fcmp, NULL, NULL, 0);
 }
 
 /**************************************************************************
@@ -317,7 +349,7 @@
 **************************************************************************/
 struct hash_table *hash_new(hash_val_fn_t fval, hash_cmp_fn_t fcmp)
 {
-  return hash_new_nentries(fval, fcmp, 0);
+  return hash_new_full(fval, fcmp, NULL, NULL);
 }
 
 /**************************************************************************
@@ -341,6 +373,18 @@
 **************************************************************************/
 void hash_free(struct hash_table *h)
 {
+  unsigned i;
+
+  for(i=0; i<h->num_buckets; i++) {
+    struct hash_bucket *bucket = &h->buckets[i];
+
+    if (h->free_key_func) {
+      h->free_key_func((void*)bucket->key);
+    }
+    if (h->free_data_func) {
+      h->free_data_func((void*)bucket->data);
+    }
+  }
   hash_free_contents(h);
   free(h);
 }
@@ -356,7 +400,9 @@
 
   assert(new_nbuckets >= h->num_entries);
 
-  h_new = hash_new_nbuckets(h->fval, h->fcmp, new_nbuckets);
+  h_new = hash_new_nbuckets(h->fval, h->fcmp,
+                           h->free_key_func, h->free_data_func,
+                           new_nbuckets);
   h_new->frozen = TRUE;
   
   for(i=0; i<h->num_buckets; i++) {
@@ -486,8 +532,16 @@
     assert(h->num_deleted>0);
     h->num_deleted--;
   }
+
+  if (h->free_key_func) {
+    h->free_key_func((void*)bucket->key);
+  }
   bucket->key = key;
+  if (h->free_data_func) {
+    h->free_data_func((void*)bucket->data);
+  }
   bucket->data = data;
+
   bucket->used = BUCKET_USED;
   bucket->hash_val = hash_val;
   h->num_entries++;
@@ -519,8 +573,16 @@
     h->num_entries++;
     bucket->used = BUCKET_USED;
   }
+
+  if (h->free_key_func) {
+    h->free_key_func((void*)bucket->key);
+  }
   bucket->key = key;
+  if (h->free_data_func) {
+    h->free_data_func((void*)bucket->data);
+  }
   bucket->data = data;
+
   bucket->hash_val = hash_val;
   return (void*)ret;
 }
@@ -537,6 +599,12 @@
   bucket = internal_lookup(h, key, HASH_VAL(h,key));
   if (bucket->used == BUCKET_USED) {
     const void *ret = bucket->data;
+    if (h->free_key_func) {
+      h->free_key_func((void*)bucket->key);
+    }
+    if (h->free_data_func) {
+      h->free_data_func((void*)bucket->data);
+    }
     zero_hbucket(bucket);
     bucket->used = BUCKET_DELETED;
     h->num_deleted++;
@@ -566,6 +634,30 @@
   return (bucket->used == BUCKET_USED);
 }
 
+bool hash_lookup(const struct hash_table *h, const void *key,
+                 const void **pkey, const void **pdata)
+{
+  struct hash_bucket *bucket = internal_lookup(h, key, HASH_VAL(h,key));
+
+  if (bucket->used == BUCKET_USED) {
+    if (pkey) {
+      *pkey = bucket->key;
+    }
+    if (pdata) {
+      *pdata = bucket->data;
+    }
+    return TRUE;
+  } else {
+    if (pkey) {
+      *pkey = NULL;
+    }
+    if (pdata) {
+      *pdata = NULL;
+    }
+    return FALSE;
+  }
+}
+
 /**************************************************************************
   Lookup: return user-data, or NULL.
   (Note that in other respects NULL is treated as a valid value, this is
@@ -573,8 +665,10 @@
 **************************************************************************/
 void *hash_lookup_data(const struct hash_table *h, const void *key)
 {
-  struct hash_bucket *bucket = internal_lookup(h, key, HASH_VAL(h,key));
-  return ((bucket->used == BUCKET_USED) ? (void*)bucket->data : NULL);
+  const void *data;
+
+  hash_lookup(h, key, NULL, &data);
+  return (void*)data;
 }
 
 /**************************************************************************
Index: hash.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/utility/hash.h,v
retrieving revision 1.7
diff -u -u -r1.7 hash.h
--- hash.h      14 Feb 2002 15:17:12 -0000      1.7
+++ hash.h      26 Apr 2005 00:23:54 -0000
@@ -25,6 +25,7 @@
 /* Function typedefs: */
 typedef unsigned int (*hash_val_fn_t)(const void *, unsigned int);
 typedef int (*hash_cmp_fn_t)(const void *, const void *);
+typedef void (*hash_free_fn_t)(void *);
 
 /* Supplied functions (matching above typedefs) appropriate for
    keys being normal nul-terminated strings: */
@@ -42,8 +43,17 @@
 
 /* General functions: */
 struct hash_table *hash_new(hash_val_fn_t fval, hash_cmp_fn_t fcmp);
+struct hash_table *hash_new_full(hash_val_fn_t fval,
+                                hash_cmp_fn_t fcmp,
+                                hash_free_fn_t free_key_func,
+                                hash_free_fn_t free_data_func);
 struct hash_table *hash_new_nentries(hash_val_fn_t fval, hash_cmp_fn_t fcmp,
                                     unsigned int nentries);
+struct hash_table *hash_new_nentries_full(hash_val_fn_t fval,
+                                         hash_cmp_fn_t fcmp,
+                                         hash_free_fn_t free_key_func,
+                                         hash_free_fn_t free_data_func,
+                                         unsigned int nentries);
 
 void hash_free(struct hash_table *h);
 
@@ -51,6 +61,8 @@
 void *hash_replace(struct hash_table *h, const void *key, const void *data);
 
 bool hash_key_exists(const struct hash_table *h, const void *key);
+bool hash_lookup(const struct hash_table *h, const void *key,
+                 const void **pkey, const void **pdata);
 void *hash_lookup_data(const struct hash_table *h, const void *key);
 
 void *hash_delete_entry(struct hash_table *h, const void *key);