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

> [book - Thu Dec 11 06:52:46 2008]:
> 
> Attached patch improves hash key/value iteration using
> the iterator interface in 40596.

Here is the version using the second version of the
iterator interface.


-----------------------------------------------------------------------
これはなかなかいいですね。黄色のはありますか。
 client/editor.c               |   12 ++--
 client/gui-gtk-2.0/editprop.c |   30 ++-------
 server/edithand.c             |    4 +-
 utility/hash.c                |  137 ++++++++++++++++++++++++++---------------
 utility/hash.h                |   51 ++++++++-------
 5 files changed, 128 insertions(+), 106 deletions(-)

diff --git a/client/editor.c b/client/editor.c
index d5b89f8..9cae047 100644
--- a/client/editor.c
+++ b/client/editor.c
@@ -510,11 +510,11 @@ static void popup_properties(struct tile *ptile)
   tiles = tile_list_new();
 
   if (editor_tile_is_selected(ptile)) {
-    hash_iterate(editor->selected_tile_table, sel_tile, dummy) {
+    hash_keys_iterate(editor->selected_tile_table, sel_tile) {
       if (can_edit_tile_properties(sel_tile)) {
         tile_list_append(tiles, sel_tile);
       }
-    } hash_iterate_end;
+    } hash_keys_iterate_end;
   } else {
     if (can_edit_tile_properties(ptile)) {
       tile_list_append(tiles, ptile);
@@ -1023,9 +1023,9 @@ void editor_apply_tool_to_selection(void)
   }
 
   connection_do_buffer(&client.conn);
-  hash_iterate(editor->selected_tile_table, ptile, dummy) {
+  hash_keys_iterate(editor->selected_tile_table, ptile) {
     editor_apply_tool(ptile, TRUE);
-  } hash_iterate_end;
+  } hash_keys_iterate_end;
   editor_notify_edit_finished();
   connection_do_unbuffer(&client.conn);
 
@@ -1825,11 +1825,11 @@ const struct tile *editor_get_selection_center(void)
   }
 
   origin = map_pos_to_tile(0, 0);
-  hash_iterate(editor->selected_tile_table, ptile, dummy) {
+  hash_keys_iterate(editor->selected_tile_table, ptile) {
     map_distance_vector(&dx, &dy, origin, ptile);
     xsum += dx;
     ysum += dy;
-  } hash_iterate_end;
+  } hash_keys_iterate_end;
 
   cx = xsum / count;
   cy = ysum / count;
diff --git a/client/gui-gtk-2.0/editprop.c b/client/gui-gtk-2.0/editprop.c
index 8c0863c..9f2454b 100644
--- a/client/gui-gtk-2.0/editprop.c
+++ b/client/gui-gtk-2.0/editprop.c
@@ -539,29 +539,13 @@ static void property_page_remove_creation_tag(struct property_page *pp,
 static bool property_page_tag_is_known(struct property_page *pp, int tag);
 static void property_page_clear_tags(struct property_page *pp);
 
-#define property_page_objprop_iterate(ARG_pp, NAME_op) do {\
-  struct objprop *NAME_op;\
-  if (!(ARG_pp) || !(ARG_pp)->objprop_table) {\
-    break;\
-  }\
-  hash_iterate((ARG_pp)->objprop_table, MY_dummy, MY_value) {\
-    NAME_op = MY_value;
-
-#define property_page_objprop_iterate_end \
-  } hash_iterate_end;\
-} while (0)
-
-#define property_page_objbind_iterate(ARG_pp, NAME_ob) do {\
-  struct objbind *NAME_ob;\
-  if (!(ARG_pp) || !(ARG_pp)->objbind_table) {\
-    break;\
-  }\
-  hash_iterate((ARG_pp)->objbind_table, MY_dummy, MY_value) {\
-    NAME_ob = MY_value;
+#define property_page_objprop_iterate(ARG_pp, NAME_op)\
+  hash_values_iterate((ARG_pp)->objprop_table, NAME_op)
+#define property_page_objprop_iterate_end hash_values_iterate_end
 
-#define property_page_objbind_iterate_end \
-  } hash_iterate_end;\
-} while (0)
+#define property_page_objbind_iterate(ARG_pp, NAME_ob)\
+  hash_values_iterate((ARG_pp)->objbind_table, NAME_ob)
+#define property_page_objbind_iterate_end hash_values_iterate_end
 
 
 /****************************************************************************
diff --git a/server/edithand.c b/server/edithand.c
index 04ca03e..64dff4a 100644
--- a/server/edithand.c
+++ b/server/edithand.c
@@ -98,9 +98,9 @@ static void check_edited_tile_terrains(void)
     return;
   }
 
-  hash_iterate(unfixed_tile_table, ptile, dummy) {
+  hash_keys_iterate(unfixed_tile_table, ptile) {
     fix_tile_on_terrain_change(ptile, FALSE);
-  } hash_iterate_end;
+  } hash_keys_iterate_end;
   hash_delete_all_entries(unfixed_tile_table);
 
   assign_continent_numbers();
diff --git a/utility/hash.c b/utility/hash.c
index e212b2d..a581b91 100644
--- a/utility/hash.c
+++ b/utility/hash.c
@@ -133,6 +133,13 @@ struct hash_table {
   bool no_shrink;		/* do not auto-shrink when set */
 };
 
+struct hash_iter {
+  struct iterator vtable;
+  const struct hash_bucket *b, *end;
+};
+
+#define HASH_ITER(p) ((struct hash_iter *)(p))
+
 /* Calculate hash value given hash_table ptr and key: */
 #define HASH_VAL(h,k) (((h)->fval)((k), ((h)->num_buckets)))
 
@@ -785,82 +792,110 @@ const void *hash_value_by_number(const struct hash_table *h,
 }
 
 /**************************************************************************
-  If the hash table is not empty, sets 'iter' to point to the start of the
-  hash table and returns TRUE. Otherwise returns FALSE.
+  Prevent or allow the hash table automatically shrinking. Returns
+  the old value of the setting.
 **************************************************************************/
-bool hash_get_start_iter(const struct hash_table *h,
-                         struct hash_iter *iter)
+bool hash_set_no_shrink(struct hash_table *h, bool no_shrink)
 {
-  if (!h || !iter || hash_num_entries(h) < 1) {
-    return FALSE;
-  }
-
-  iter->table = h;
-  iter->index = -1;
-  return hash_iter_next(iter);
+  bool old = h->no_shrink;
+  h->no_shrink = no_shrink;
+  return old;
 }
 
 /**************************************************************************
-  Set the iterator 'iter' to the next item in the hash table. Returns
-  FALSE if there are no more items.
+  "Sizeof" function implementation for generic_iterate hash iterators.
 **************************************************************************/
-bool hash_iter_next(struct hash_iter *iter)
+size_t hash_iter_sizeof(void)
 {
-  const struct hash_table *h;
-  struct hash_bucket *bucket;
-
-  if (!iter || !iter->table) {
-    return FALSE;
-  }
+  return sizeof(struct hash_iter);
+}
 
-  h = iter->table;
-  iter->index++;
+/**************************************************************************
+  Helper function for hash (key, value) pair iteration.
+**************************************************************************/
+void *hash_iter_get_key(const struct iterator *hash_iter)
+{
+  struct hash_iter *it = HASH_ITER(hash_iter);
+  return (void *) it->b->key;
+}
 
-  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++;
-  }
+/**************************************************************************
+  Helper function for hash (key, value) pair iteration.
+**************************************************************************/
+void *hash_iter_get_value(const struct iterator *hash_iter)
+{
+  struct hash_iter *it = HASH_ITER(hash_iter);
+  return (void *) it->b->data;
+}
 
-  return FALSE;
+/**************************************************************************
+  Iterator interface 'next' function implementation.
+**************************************************************************/
+static void hash_iter_next(struct iterator *iter)
+{
+  struct hash_iter *it = HASH_ITER(iter);
+  do {
+    it->b++;
+  } while (it->b < it->end && it->b->used != BUCKET_USED);
 }
 
 /**************************************************************************
-  Returns the key of the hash table item pointed to by this iterator.
+  Iterator interface 'get' function implementation. This just returns the
+  iterator itself, so you would need to use hash_iter_get_key/value to
+  get the actual keys and values.
 **************************************************************************/
-void *hash_iter_get_key(struct hash_iter *iter)
+static void *hash_iter_get(const struct iterator *iter)
 {
-  if (!iter) {
-    return NULL;
-  }
-  return (void *) iter->key;
+  return (void *) iter;
 }
 
 /**************************************************************************
-  Returns the value (or "data") of the hash table item pointed to by this
-  iterator.
+  Iterator interface 'valid' function implementation.
 **************************************************************************/
-void *hash_iter_get_value(struct hash_iter *iter)
+static bool hash_iter_valid(const struct iterator *iter)
 {
-  if (!iter) {
-    return NULL;
-  }
-  return (void *) iter->value;
+  struct hash_iter *it = HASH_ITER(iter);
+  return it->b < it->end;
 }
 
 /**************************************************************************
-  Prevent or allow the hash table automatically shrinking. Returns
-  the old value of the setting.
+  Returns an iterator that iterates over both keys and values of the hash
+  table. NB: iterator_get() returns an iterator pointer, so use the helper
+  functions hash_iter_get_{key,value} to access the key and value.
 **************************************************************************/
-bool hash_set_no_shrink(struct hash_table *h, bool no_shrink)
+struct iterator *hash_iter_init(struct hash_iter *it,
+                                const struct hash_table *h)
 {
-  bool old = h->no_shrink;
+  it->vtable.next = hash_iter_next;
+  it->vtable.get = hash_iter_get;
+  it->vtable.valid = hash_iter_valid;
+  it->b = h->buckets - 1;
+  it->end = h->buckets + h->num_buckets + 1;
 
-  h->no_shrink = no_shrink;
+  /* Seek to the first used bucket. */
+  hash_iter_next(ITERATOR(it));
 
-  return old;
+  return ITERATOR(it);
+}
+
+/**************************************************************************
+  Returns an iterator over the hash table's keys.
+**************************************************************************/
+struct iterator *hash_key_iter_init(struct hash_iter *it,
+                                    const struct hash_table *h)
+{
+  struct iterator *ret = hash_iter_init(it, h);
+  it->vtable.get = hash_iter_get_key;
+  return ret;
+}
+
+/**************************************************************************
+  Returns an iterator over the hash table's values.
+**************************************************************************/
+struct iterator *hash_value_iter_init(struct hash_iter *it,
+                                      const struct hash_table *h)
+{
+  struct iterator *ret = hash_iter_init(it, h);
+  it->vtable.get = hash_iter_get_value;
+  return ret;
 }
diff --git a/utility/hash.h b/utility/hash.h
index d23f6f5..4200d5c 100644
--- a/utility/hash.h
+++ b/utility/hash.h
@@ -82,29 +82,32 @@ 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 } } }
+#include "iterator.h"
+
+struct hash_iter;
+size_t hash_iter_sizeof(void);
+
+struct iterator *hash_key_iter_init(struct hash_iter *it,
+                                    const struct hash_table *h);
+#define hash_keys_iterate(ARG_ht, NAME_key)\
+  generic_iterate(struct hash_iter, void *, NAME_key,\
+                  hash_iter_sizeof, hash_key_iter_init, (ARG_ht))
+#define hash_keys_iterate_end generic_iterate_end
+
+struct iterator *hash_value_iter_init(struct hash_iter *it,
+                                      const struct hash_table *h);
+#define hash_values_iterate(ARG_ht, NAME_value)\
+  generic_iterate(struct hash_iter, void *, NAME_value,\
+                  hash_iter_sizeof, hash_value_iter_init, (ARG_ht))
+#define hash_values_iterate_end generic_iterate_end
+
+struct iterator *hash_iter_init(struct hash_iter *it,
+                                const struct hash_table *h);
+void *hash_iter_get_key(const struct iterator *hash_iter);
+void *hash_iter_get_value(const struct iterator *hash_iter);
+#define hash_iterate(ARG_ht, NAME_iter)\
+  generic_iterate(struct hash_iter, struct iterator *, NAME_iter,\
+                  hash_iter_sizeof, hash_iter_init, (ARG_ht))
+#define hash_iterate_end generic_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