<URL: http://bugs.freeciv.org/Ticket/Display.html?id=40597 >
Attached patch improves hash key/value iteration using
the iterator interface in 40596.
- For convenience three iterate macros are provided for
hash tables: for iterating over keys, values, or both.
- The implementation of the iterator and hash table is
kept in the hash.c module and out of the header.
- Code making its own iteration macros based on internal
hash tables is simplified.
-----------------------------------------------------------------------
あなたの凄い運命をこよなく愛するようになる。
client/editor.c | 12 ++--
client/gui-gtk-2.0/editprop.c | 59 +++++++++------
server/edithand.c | 4 +-
utility/hash.c | 167 +++++++++++++++++++++++++++++++----------
utility/hash.h | 42 +++++------
5 files changed, 189 insertions(+), 95 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..26696f1 100644
--- a/client/gui-gtk-2.0/editprop.c
+++ b/client/gui-gtk-2.0/editprop.c
@@ -22,6 +22,7 @@
#include "fcintl.h"
#include "hash.h"
+#include "iterator.h"
#include "log.h"
#include "mem.h"
@@ -539,29 +540,19 @@ 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;
+static struct iterator *
+property_page_get_objprop_iter(const struct property_page *pp);
+#define property_page_objprop_iterate(ARG_pp, NAME_op)\
+ generic_iterate(property_page_get_objprop_iter(ARG_pp),\
+ struct objprop *, NAME_op)
+#define property_page_objprop_iterate_end generic_iterate_end
-#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_objbind_iterate_end \
- } hash_iterate_end;\
-} while (0)
+static struct iterator *
+property_page_get_objbind_iter(const struct property_page *pp);
+#define property_page_objbind_iterate(ARG_pp, NAME_ob)\
+ generic_iterate(property_page_get_objbind_iter(ARG_pp),\
+ struct objbind *, NAME_ob)
+#define property_page_objbind_iterate_end generic_iterate_end
/****************************************************************************
@@ -3685,6 +3676,30 @@ static void property_page_setup_objprops(struct property_page *pp)
}
/****************************************************************************
+ Return an iterator over the object properties in the property page.
+****************************************************************************/
+static struct iterator *
+property_page_get_objprop_iter(const struct property_page *pp)
+{
+ if (!pp || !pp->objprop_table) {
+ return NULL;
+ }
+ return hash_get_value_iter(pp->objprop_table);
+}
+
+/****************************************************************************
+ Return an iterator over the bound objects in the property page.
+****************************************************************************/
+static struct iterator *
+property_page_get_objbind_iter(const struct property_page *pp)
+{
+ if (!pp || !pp->objbind_table) {
+ return NULL;
+ }
+ return hash_get_value_iter(pp->objbind_table);
+}
+
+/****************************************************************************
Callback for when a property page's listview's selection changes.
****************************************************************************/
static void property_page_selection_changed(GtkTreeSelection *sel,
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..b8353f5 100644
--- a/utility/hash.c
+++ b/utility/hash.c
@@ -133,6 +133,15 @@ struct hash_table {
bool no_shrink; /* do not auto-shrink when set */
};
+struct hash_iterator {
+ struct iterator vtable;
+ const struct hash_table *table;
+ int index;
+ const void *key;
+ const void *value;
+};
+#define HASH_ITERATOR(p) ((struct hash_iterator *)(p))
+
/* Calculate hash value given hash_table ptr and key: */
#define HASH_VAL(h,k) (((h)->fval)((k), ((h)->num_buckets)))
@@ -785,82 +794,158 @@ 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;
+ bool old = h->no_shrink;
+ h->no_shrink = no_shrink;
+ return old;
+}
+
+/**************************************************************************
+ Helper function for hash (key, value) pair iteration.
+**************************************************************************/
+void *hash_iter_get_key(const struct iterator *hash_iter)
+{
+ if (!hash_iter) {
+ return NULL;
}
+ return (void *)(HASH_ITERATOR(hash_iter)->key);
+}
- iter->table = h;
- iter->index = -1;
- return hash_iter_next(iter);
+/**************************************************************************
+ Helper function for hash (key, value) pair iteration.
+**************************************************************************/
+void *hash_iter_get_value(const struct iterator *hash_iter)
+{
+ if (!hash_iter) {
+ return NULL;
+ }
+ return (void *)(HASH_ITERATOR(hash_iter)->value);
}
/**************************************************************************
- Set the iterator 'iter' to the next item in the hash table. Returns
- FALSE if there are no more items.
+ Iterator interface 'next' function implementation.
**************************************************************************/
-bool hash_iter_next(struct hash_iter *iter)
+static void hash_iter_next(struct iterator *iter)
{
+ struct hash_iterator *it;
const struct hash_table *h;
- struct hash_bucket *bucket;
+ const struct hash_bucket *bucket;
- if (!iter || !iter->table) {
- return FALSE;
+ it = HASH_ITERATOR(iter);
+ if (!it || !it->table) {
+ return;
}
- h = iter->table;
- iter->index++;
+ h = it->table;
+ it->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;
+ while (it->index < hash_num_buckets(h)) {
+ bucket = h->buckets + it->index;
+ if (bucket->used == BUCKET_USED) {
+ it->key = bucket->key;
+ it->value = bucket->data;
+ return;
}
- iter->index++;
+ it->index++;
}
- return FALSE;
+ it->key = NULL;
+ it->value = NULL;
}
/**************************************************************************
- Returns the key of the hash table item pointed to by this iterator.
+ Iterator interface 'free' function implementation.
**************************************************************************/
-void *hash_iter_get_key(struct hash_iter *iter)
+static void hash_iter_free(struct iterator *iter)
{
- if (!iter) {
- return NULL;
+ struct hash_iterator *it;
+ it = HASH_ITERATOR(iter);
+ if (it) {
+ it->table = NULL;
+ free(it);
}
- return (void *) iter->key;
}
/**************************************************************************
- Returns the value (or "data") 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_value(struct hash_iter *iter)
+static void *hash_iter_get(const struct iterator *iter)
{
- if (!iter) {
+ return (void *) iter;
+}
+
+/**************************************************************************
+ Iterator interface 'valid' function implementation.
+**************************************************************************/
+static bool hash_iter_valid(const struct iterator *iter)
+{
+ struct hash_iterator *it;
+ it = HASH_ITERATOR(iter);
+ if (!it || !it->table) {
+ return FALSE;
+ }
+ return 0 <= it->index && it->index < hash_num_buckets(it->table);
+}
+
+/**************************************************************************
+ Returns an iterator that iterates over both keys and values of the hash
+ table. NB: iterator_next() returns an iterator pointer, so use the helper
+ functions hash_iter_get_{key,value} to access the key and value.
+**************************************************************************/
+struct iterator *hash_get_iter(const struct hash_table *h)
+{
+ struct hash_iterator *it;
+
+ if (!h || hash_num_entries(h) < 1) {
return NULL;
}
- return (void *) iter->value;
+
+ it = fc_calloc(1, sizeof(*it));
+ it->vtable.next = hash_iter_next;
+ it->vtable.free = hash_iter_free;
+ it->vtable.get = hash_iter_get;
+ it->vtable.valid = hash_iter_valid;
+ it->table = h;
+ it->index = -1;
+
+ /* Seek to first used bucket. */
+ hash_iter_next(ITERATOR(it));
+
+ return ITERATOR(it);
}
/**************************************************************************
- Prevent or allow the hash table automatically shrinking. Returns
- the old value of the setting.
+ Returns an iterator over the hash table's keys.
**************************************************************************/
-bool hash_set_no_shrink(struct hash_table *h, bool no_shrink)
+struct iterator *hash_get_key_iter(const struct hash_table *h)
{
- bool old = h->no_shrink;
+ struct hash_iterator *it;
- h->no_shrink = no_shrink;
+ it = HASH_ITERATOR(hash_get_iter(h));
+ if (it) {
+ it->vtable.get = hash_iter_get_key;
+ }
- return old;
+ return ITERATOR(it);
+}
+
+/**************************************************************************
+ Returns an iterator over the hash table's values.
+**************************************************************************/
+struct iterator *hash_get_value_iter(const struct hash_table *h)
+{
+ struct hash_iterator *it;
+
+ it = HASH_ITERATOR(hash_get_iter(h));
+ if (it) {
+ it->vtable.get = hash_iter_get_value;
+ }
+
+ return ITERATOR(it);
}
diff --git a/utility/hash.h b/utility/hash.h
index d23f6f5..de9227e 100644
--- a/utility/hash.h
+++ b/utility/hash.h
@@ -82,29 +82,23 @@ 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 iterator *hash_get_key_iter(const struct hash_table *h);
+#define hash_keys_iterate(ARG_ht, NAME_key)\
+ generic_iterate(hash_get_key_iter(ARG_ht), void *, NAME_key)
+#define hash_keys_iterate_end generic_iterate_end
+
+struct iterator *hash_get_value_iter(const struct hash_table *h);
+#define hash_values_iterate(ARG_ht, NAME_value)\
+ generic_iterate(hash_get_value_iter(ARG_ht), void *, NAME_value)
+#define hash_values_iterate_end generic_iterate_end
+
+struct iterator *hash_get_iter(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(hash_get_iter(ARG_ht), struct iterator *, NAME_iter)
+#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
