[Freeciv-Dev] (PR#40324) [patch] Hash table iterators and fast clear
URL: http://bugs.freeciv.org/Ticket/Display.html?id=40324 Committed to S2_2 (r14932) and trunk (r14933). Shortly thereafter, also fixed a comment typo in the former two commits thus preventing the atrocity remaining there until the end of time. -_- -- 申し訳ございません ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
[Freeciv-Dev] (PR#40324) [patch] Hash table iterators and fast clear
URL: http://bugs.freeciv.org/Ticket/Display.html?id=40324
Fixed two typos in the hash_iterate macro.
-
月曜日は働く代わりに猫さんたちと月に飛んでいます。
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..d23f6f5 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,
+
[Freeciv-Dev] (PR#40324) [patch] Hash table iterators and fast clear
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
Re: [Freeciv-Dev] (PR#40324) [patch] Hash table iterators and fast clear
URL: http://bugs.freeciv.org/Ticket/Display.html?id=40324 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. -jason ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
[Freeciv-Dev] (PR#40324) [patch] Hash table iterators and fast clear
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
