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

> [EMAIL PROTECTED] - Wed Jun 25 17:31:41 2008]:
> 
> Madeline Book wrote:
> 
> > The patch also implements hash_fast_clear which does
> > the same as hash_delete_all_entries but much more
> > quickly and efficiently. (It cannot be used unfortunately
> > if the keys or values have associated free_funcs.)
> 
> Why not just give hash_delete_all_entries a special case after
> a check for if there's a free_func?  Having a second function that
> does "almost" the same thing isn't so good.

Oh, very good point. Version 2 of the patch makes the body
of hash_fast_clear a special case of hash_delete_all_entries
when there are no free_funcs.

Also added is a wrapper macro for iteration, hash_iterate,
to make the iteration interface analogous to list iteration.

Finally, for the case when the programmer knows it would
be more efficient if the hash table did not shrink automatically,
a function hash_set_no_shrink is added.


----------------------------------------------------------------------
木曜日は働く代わりに木を食べようとします。
diff --git a/utility/hash.c b/utility/hash.c
index e2e7dc2..f1fbcb7 100644
--- a/utility/hash.c
+++ b/utility/hash.c
@@ -130,6 +130,7 @@ struct hash_table {
   unsigned int num_entries;	/* does not included deleted entries */
   unsigned int num_deleted;
   bool frozen;			/* do not auto-resize when set */
+  bool no_shrink; /* Do no shrink, settable by user. */
 };
 
 /* Calculate hash value given hash_table ptr and key: */
@@ -158,6 +159,7 @@ static void zero_htable(struct hash_table *h)
   h->free_data_func = NULL;
   h->num_buckets = h->num_entries = h->num_deleted = 0;
   h->frozen = FALSE;
+  h->no_shrink = FALSE;
 }
 
 
@@ -438,6 +440,9 @@ static void hash_maybe_resize(struct hash_table *h, bool expandingp)
   if (h->frozen) {
     return;
   }
+  if (!expandingp && h->no_shrink) {
+    return;
+  }
   num_used = h->num_entries + h->num_deleted;
   if (expandingp) {
     limit = FULL_RATIO * h->num_buckets;
@@ -663,9 +668,16 @@ void hash_delete_all_entries(struct hash_table *h)
 {
   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);
+  if (h->free_key_func == NULL && h->free_data_func == NULL) {
+    memset(h->buckets, 0, sizeof(struct hash_bucket) * h->num_buckets);
+    h->num_entries = 0;
+    h->num_deleted = 0;
+    h->frozen = FALSE;
+  } else {
+    /* 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);
 }
@@ -771,3 +783,84 @@ const void *hash_value_by_number(const struct hash_table *h,
 {
   return hash_lookup_data(h, hash_key_by_number(h, entry_number));
 }
+
+/**************************************************************************
+  If the hash table is not empty, sets 'iter' to point to the start of the
+  hash table and returns TRUE. Otherwise returns FALSE.
+**************************************************************************/
+bool hash_get_start_iter(const struct hash_table *h,
+                         struct hash_iter *iter)
+{
+  if (!h || !iter || hash_num_entries(h) < 1) {
+    return FALSE;
+  }
+
+  iter->table = h;
+  iter->index = -1;
+  return hash_iter_next(iter);
+}
+
+/**************************************************************************
+  Set the iterator 'iter' to the next item in the hash table. Returns
+  FALSE if there are no more items.
+**************************************************************************/
+bool hash_iter_next(struct hash_iter *iter)
+{
+  const struct hash_table *h;
+  struct hash_bucket *bucket;
+
+  if (!iter || !iter->table) {
+    return FALSE;
+  }
+
+  h = iter->table;
+  iter->index++;
+
+  while (iter->index < hash_num_buckets(h)) {
+    bucket = h->buckets + iter->index;
+    if (bucket && bucket->used == BUCKET_USED) {
+      iter->key = bucket->key;
+      iter->value = bucket->data;
+      return TRUE;
+    }
+    iter->index++;
+  }
+
+  return FALSE;
+}
+
+/**************************************************************************
+  Returns the key of the hash table item pointed to by this iterator.
+**************************************************************************/
+void *hash_iter_get_key(struct hash_iter *iter)
+{
+  if (!iter) {
+    return NULL;
+  }
+  return (void *) iter->key;
+}
+
+/**************************************************************************
+  Returns the value (or "data) of the hash table item pointed to by this
+  iterator.
+**************************************************************************/
+void *hash_iter_get_value(struct hash_iter *iter)
+{
+  if (!iter) {
+    return NULL;
+  }
+  return (void *) iter->value;
+}
+
+/**************************************************************************
+  Prevent or allow the hash table automatically shrinking. Returns
+  the old value of the setting.
+**************************************************************************/
+bool hash_set_no_shrink(struct hash_table *h, bool no_shrink)
+{
+  bool old = h->no_shrink;
+
+  h->no_shrink = no_shrink;
+
+  return old;
+}
diff --git a/utility/hash.h b/utility/hash.h
index 9dc6e1d..5f03593 100644
--- a/utility/hash.h
+++ b/utility/hash.h
@@ -79,4 +79,32 @@ unsigned int hash_num_entries(const struct hash_table *h);
 unsigned int hash_num_buckets(const struct hash_table *h);
 unsigned int hash_num_deleted(const struct hash_table *h);
 
+bool hash_set_no_shrink(struct hash_table *h,
+                        bool no_shrink);
+
+struct hash_iter {
+  const struct hash_table *table;
+  int index;
+  const void *key;
+  const void *value;
+};
+
+bool hash_get_start_iter(const struct hash_table *h,
+                         struct hash_iter *iter);
+bool hash_iter_next(struct hash_iter *iter);
+void *hash_iter_get_key(struct hash_iter *iter);
+void *hash_iter_get_value(struct hash_iter *iter);
+
+#define hash_iterate(ARG_hash_table, NAME_key, NAME_value) {\
+  struct hash_iter MY_iter;\
+  if (hash_get_start_iter((ARG_hash_table), &MY_iter)) {\
+    void *NAME_key, NAME_value;\
+    bool MY_more_items = TRUE:\
+    while (MY_more_items) {\
+      NAME_key = hash_iter_get_key(&MY_iter);\
+      NAME_value = hash_iter_get_value(&MY_iter);\
+      MY_more_items = hash_iter_next(&MY_iter);
+
+#define hash_iterate_end } } }
+
 #endif  /* FC__HASH_H */
_______________________________________________
Freeciv-dev mailing list
Freeciv-dev@gna.org
https://mail.gna.org/listinfo/freeciv-dev

Reply via email to