[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 >

> [jdorje - Tue Apr 26 07:00:23 2005]:
> 
> Raimar Falke wrote:
> > <URL: http://bugs.freeciv.org/Ticket/Display.html?id=12893 >
> >
> > On Mon, Apr 25, 2005 at 05:47:10PM -0700, Vasco Alexandre da Silva
> Costa wrote:
> >
> >><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.
> >
> > It looks like we are implementing some kind of garbage collection?!
> 
> No, it's just a callback mechanism to be called when a hash is freed.
> 
> However Vasco you really must write some documentaion, i.e., comments.
> These functions are not nearly as obvious as you seem to think they
> are.
> 
> Also there's an unnecessary (void *) cast that is a bit ugly.

Which? The ones necessary when invoking hash_free_fn_t? I did not do
that, because it makes a user think hash_free_fn_t will not mess with
something, when it actually should.

I could probably live without the free functions for the scripting
engine, since I now have hash_lookup. But the free functions are more
efficient and can make the userland code simpler in other cases.

Here is a new patch, with lots of comments added.

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 12:50:23 -0000
@@ -61,20 +61,13 @@
      the key is available to be freed (or can just be freed as part of
      deleting the "object").  (This is done in registry hsec, but the
      allocation is still via sbuffer.)
+   - Specify key free function pointers upon hash table creation which
+     handle the freeing.
    - Keep another hash from object pointers to key pointers?!  Seems a
      bit too perverse...
 
-   Possible implementation changes to avoid/reduce this problem:
-
-   - As noted above, could restrict key type (e.g., strings), or pass
-     in more function pointers and user data to allow duplicating and
-     freeing keys within hash table code.
-   - Have some mechanism to allow external access to the key pointers
-     in the hash table, especially when deleting/replacing elements
-     -- and when freeing the hash table?
-
-   Actually, there are some potential problems with memory management
-   of the user-data pointers too:
+   There are some potential problems with memory management of the
+   user-data pointers too:
    
    - If may have multiple keys pointing to the same data, cannot just
      free the data when deleted/replaced from hash.  (Eg, tilespec;
@@ -86,6 +79,7 @@
 
    - Don't have hash table as only access to user-data.
    - Allocate user-data using sbuffer.
+   - Specify user-data free function pointers upon hash table creation.
 
    
 ***************************************************************************/
@@ -121,6 +115,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 +145,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;
 }
@@ -275,10 +273,15 @@
 }
 
 /**************************************************************************
-  Internal constructor, specifying exact number of buckets:
+  Internal constructor, specifying exact number of buckets.
+  Allows to specify functions to free the memory allocated for the key and
+  user-data that get called when removing the bucket from the hash table or
+  changing key/user-data values.
 **************************************************************************/
 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 +296,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 +309,42 @@
 }
 
 /**************************************************************************
+  Constructor specifying number of entries.
+  Allows to specify functions to free the memory allocated for the key and
+  user-data that get called when removing the bucket from the hash table or
+  changing key/user-data values.
+**************************************************************************/
+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);
+}
+
+/**************************************************************************
+  Constructor with unspecified number of entries.
+  Allows to specify functions to free the memory allocated for the key and
+  user-data that get called when removing the bucket from the hash table or
+  changing key/user-data values.
+**************************************************************************/
+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 +352,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 +376,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 +403,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 +535,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 +576,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 +602,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++;
@@ -567,14 +638,47 @@
 }
 
 /**************************************************************************
-  Lookup: return user-data, or NULL.
+  Lookup: looks up a key in the hash table returning the original key, and
+  the associated user-data, and a boolean which is TRUE if the key was
+  found.
+  (This is useful if you need to free the memory allocated for the
+  original key, for example before calling hash_delete_entry.)
+**************************************************************************/
+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 data: return user-data, or NULL.
   (Note that in other respects NULL is treated as a valid value, this is
   merely intended as a convenience when caller never uses NULL as value.)
 **************************************************************************/
 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 12:50:23 -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);