[Freeciv-Dev] (PR#14097) improvements to hash bucket deletion

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

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

Because of the ugliness of many hash callers I looked at the hash 
interface/internals.

One of the first things I noticed is that hash_delete_all_entries is 
really inefficient.  It's hard to tell offhand exactly (the effect of 
hash_maybe_shrink is hard to judge) but I suspect it is at least O(n^2). 
  Of course it should only be O(n).

In a somewhat related issue, hash_free doesn't call 
hash_delete_all_entries.  Instead it just has its own, faster free.

This patch solves both problems.  A new function hash_delete_bucket is 
created, and called from hash_delete_entry and hash_delete_all_entries. 
  The latter just iterates over all buckets now so it is now O(n) (and 
calls hash_maybe_shrink - but just once, after all entries are gone). 
hash_free now also calls hash_delete_all_entries (which is a little 
slower than the old loop since it does have to zero the entries...but 
still just O(n)).

There are further inefficiencies here.  Hash resizing (a common 
operation) is slow since it zeroes all the buckets of the old hash 
bucket array...right before it frees the array.  I also didn't address 
any of the interface problems yet.  Generally the hash code could use 
some work I think.

-jason

Index: utility/hash.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/utility/hash.c,v
retrieving revision 1.28
diff -p -u -r1.28 hash.c
--- utility/hash.c      23 Sep 2005 19:23:32 -0000      1.28
+++ utility/hash.c      23 Sep 2005 20:33:05 -0000
@@ -376,18 +376,7 @@ static void hash_free_contents(struct ha
 **************************************************************************/
 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_delete_all_entries(h);
   hash_free_contents(h);
   free(h);
 }
@@ -591,6 +580,47 @@ void *hash_replace(struct hash_table *h,
 }
 
 /**************************************************************************
+  Deletes a single bucket from the hash.  You may call this on an unused
+  bucket.  old_key and old_value, if non-NULL, will be set to contain the
+  pointers to the key and value that are being deleted.  free_key_func
+  and free_data_func will (if set) be called on the key and data so these
+  return values may already have been freed.
+**************************************************************************/
+static void hash_delete_bucket(struct hash_table *h,
+                              struct hash_bucket *bucket,
+                              void **old_key,
+                              void **old_value)
+{
+  if (bucket->used == BUCKET_USED) {
+    if (old_key) {
+      *old_key = (void*)bucket->key;
+    }
+    if (old_value) {
+      *old_value = (void*)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++;
+    assert(h->num_entries > 0);
+    h->num_entries--;
+  } else {
+    if (old_key) {
+      *old_key = NULL;
+    }
+    if (old_value) {
+      *old_value = NULL;
+    }
+  }
+
+}
+
+/**************************************************************************
   Delete an entry with specified key.  Returns user-data of deleted
   entry, or NULL if not found.
 **************************************************************************/
@@ -609,29 +639,12 @@ void *hash_delete_entry_full(struct hash
                             void **old_key)
 {
   struct hash_bucket *bucket;
+  void *old_value;
 
   hash_maybe_shrink(h);  
   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++;
-    assert(h->num_entries > 0);
-    h->num_entries--;
-    return (void*) ret;
-  } else {
-    if (old_key) {
-      *old_key = NULL;
-    }
-    return NULL;
-  }
+  hash_delete_bucket(h, bucket, old_key, &old_value);
+  return old_value;
 }
 
 /**************************************************************************
@@ -639,8 +652,13 @@ void *hash_delete_entry_full(struct hash
 **************************************************************************/
 void hash_delete_all_entries(struct hash_table *h)
 {
-  while (hash_num_entries(h) > 0)
-    (void) hash_delete_entry(h, hash_key_by_number(h, 0));
+  unsigned int bucket_nr;
+
+  /* Modeled after hash_key_by_number and hash_delete_entry. */
+  for (bucket_nr = 0; bucket_nr < h->num_buckets; bucket_nr++) {
+    hash_delete_bucket(h, &h->buckets[bucket_nr], NULL, NULL);
+  }
+  hash_maybe_shrink(h);
 }
 
 /**************************************************************************