<URL: http://bugs.freeciv.org/Ticket/Display.html?id=40324 >
The attached patch implements GtkTreeIter style
iterators for hash tables:
{
struct hash_iter iter;
if (!hash_get_start_iter(h, &iter)) {
/* Hash table 'h' is empty. */
}
do {
void *key = hash_iter_get_key(&iter);
void *value = hash_iter_get_value(&iter);
/* Use key and/or value. */
} while (hash_iter_next(&iter);
}
The point of the above interface is to avoid
the O(N^2) cost of using hash_{key,value}_by_number
to iterate over all items in a hash table (each call
to *_by_number being O(N), with N the number of items
in the table).
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.)
These hash table improvements are needed for my
improved implementation of editor tile selection
(much cleaner than the current one using bitvectors).
----------------------------------------------------------------------
水曜日は働く代わりにほかの惑星で水を探しています。
diff --git a/utility/hash.c b/utility/hash.c
index e2e7dc2..e915bd6 100644
--- a/utility/hash.c
+++ b/utility/hash.c
@@ -771,3 +771,94 @@ 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;
+}
+
+/**************************************************************************
+ Quickly erase all items in the hash table returning it to an empty
+ state.
+
+ NB: This function MUST NOT be used if you supplied a free_key_func
+ or free_data_func to hash_new_*. In that case you must use
+ hash_delete_all_entries instead.
+**************************************************************************/
+void hash_fast_clear(struct hash_table *h)
+{
+ if (!h) {
+ return;
+ }
+
+ assert(h->free_key_func == NULL);
+ assert(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;
+}
diff --git a/utility/hash.h b/utility/hash.h
index 9dc6e1d..b53f413 100644
--- a/utility/hash.h
+++ b/utility/hash.h
@@ -79,4 +79,19 @@ 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);
+void hash_fast_clear(struct hash_table *h);
+
+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);
+
#endif /* FC__HASH_H */
_______________________________________________
Freeciv-dev mailing list
Freeciv-dev@gna.org
https://mail.gna.org/listinfo/freeciv-dev
