<URL: http://bugs.freeciv.org/Ticket/Display.html?id=40716 >
The improved hash tables in trunk are a useful thing to have
for fixing and cleaning up some inefficient data structure use
in S2_1 (e.g. unit_list use in request_unit_select_same_type()).
-----------------------------------------------------------------------
私もハッシュブラウンにします。
commit b754520b376a95300c0dee5d4d4a3314974d9bd1
Author: Madeline Book <madeline.b...@gmail.com>
Date: Fri Feb 13 16:38:05 2009 -0500
Hash iteration from trunk.
diff --git a/utility/Makefile.am b/utility/Makefile.am
index 3fa02cc..154b313 100644
--- a/utility/Makefile.am
+++ b/utility/Makefile.am
@@ -27,6 +27,7 @@ libcivutility_a_SOURCES = \
inputfile.h \
ioz.c \
ioz.h \
+ iterator.h \
log.c \
log.h \
netintf.c \
diff --git a/utility/hash.c b/utility/hash.c
index e2e7dc2..a405edf 100644
--- a/utility/hash.c
+++ b/utility/hash.c
@@ -130,8 +130,16 @@ 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 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)))
@@ -158,6 +166,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 +447,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 +675,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 +790,112 @@ const void *hash_value_by_number(const struct hash_table *h,
{
return hash_lookup_data(h, hash_key_by_number(h, entry_number));
}
+
+/**************************************************************************
+ 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;
+}
+
+/**************************************************************************
+ "Sizeof" function implementation for generic_iterate hash iterators.
+**************************************************************************/
+size_t hash_iter_sizeof(void)
+{
+ return sizeof(struct hash_iter);
+}
+
+/**************************************************************************
+ 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;
+}
+
+/**************************************************************************
+ 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;
+}
+
+/**************************************************************************
+ 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);
+}
+
+/**************************************************************************
+ 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.
+**************************************************************************/
+static void *hash_iter_get(const struct iterator *iter)
+{
+ return (void *) iter;
+}
+
+/**************************************************************************
+ Iterator interface 'valid' function implementation.
+**************************************************************************/
+static bool hash_iter_valid(const struct iterator *iter)
+{
+ struct hash_iter *it = HASH_ITER(iter);
+ return it->b < it->end;
+}
+
+/**************************************************************************
+ 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.
+**************************************************************************/
+struct iterator *hash_iter_init(struct hash_iter *it,
+ const struct hash_table *h)
+{
+ 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;
+
+ /* Seek to the first used bucket. */
+ hash_iter_next(ITERATOR(it));
+
+ 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 9dc6e1d..4200d5c 100644
--- a/utility/hash.h
+++ b/utility/hash.h
@@ -79,4 +79,35 @@ 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);
+
+#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 */
diff --git a/utility/iterator.h b/utility/iterator.h
new file mode 100644
index 0000000..738d019
--- /dev/null
+++ b/utility/iterator.h
@@ -0,0 +1,88 @@
+/***********************************************************************
+ Freeciv - Copyright (C) 1996 - A Kjeldberg, L Gregersen, P Unold
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2, or (at your option)
+ any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+***********************************************************************/
+#ifndef FC__ITERATOR_H
+#define FC__ITERATOR_H
+
+/***********************************************************************
+ Iterator base class. "Derived" iterators must have this struct as
+ their first member (as a "vtable") and provide implementations of the
+ "pure virtual" member functions. See the function comment headers
+ below for the expected behaviour of these functions.
+***********************************************************************/
+struct iterator {
+ void (*next)(struct iterator *it);
+ void *(*get)(const struct iterator *it);
+ bool (*valid)(const struct iterator *it);
+};
+
+#define ITERATOR(p) ((struct iterator *)(p))
+
+/***********************************************************************
+ Advances the iterator to point to the next item in the sequence.
+***********************************************************************/
+static inline void iterator_next(struct iterator *it) {
+ it->next(it);
+}
+
+/***********************************************************************
+ Returns the item currently pointed to by the iterator. Note that the
+ iterator could point to an item whose value is NULL; to actually test
+ whether the iterator is still valid (e.g. has not gone past the
+ end of the sequence), use iterator_valid().
+***********************************************************************/
+static inline void *iterator_get(const struct iterator *it) {
+ return it->get(it);
+}
+
+/***********************************************************************
+ Returns TRUE if the iterator points to an item in the sequence.
+***********************************************************************/
+static inline bool iterator_valid(const struct iterator *it) {
+ return it->valid(it);
+}
+
+/***************************************************************************
+ Iteration macro for iterators derived from the 'iterator' base class.
+ Usually you would define a specific iteration macro for each derived
+ iterator type. The meaning of the arguments is as follows:
+
+ TYPE_it - The type of the derived iterator. E.g. 'struct foo_iter'.
+ TYPE_a - The real type of the items in the list. The variable with name
+ 'NAME_a' will be cast to this.
+ NAME_a - The name of the variable that will be assigned the current item
+ in each iteration. It will be declared for you within the scope
+ of the iteration loop.
+ FUNC_size - A function that returns the total size in bytes of a
+ 'TYPE_it'.
+ FUNC_init - A "construtor" for 'TYPE_it' objects. It returns a pointer to
+ a 'struct iterator' and takes as its first argument a pointer
+ to memory large enough to hold a 'TYPE_it' (this amount must
+ match the result of FUNC_size()). NB: This function must not
+ return NULL; it must return a valid iterator pointing to the
+ first element in the sequence, or an invalid iterator.
+ ... - Zero or more extra arguments that 'FUNC_init' expects.
+***************************************************************************/
+#define generic_iterate(TYPE_it, TYPE_a, NAME_a, FUNC_size, FUNC_init, ...)\
+do {\
+ char MY_mem_##NAME_a[FUNC_size()];\
+ struct iterator *MY_it_##NAME_a;\
+ TYPE_a NAME_a;\
+ MY_it_##NAME_a = FUNC_init((TYPE_it *) MY_mem_##NAME_a , ## __VA_ARGS__);\
+ for (; iterator_valid(MY_it_##NAME_a); iterator_next(MY_it_##NAME_a)) {\
+ NAME_a = (TYPE_a) iterator_get(MY_it_##NAME_a);\
+
+#define generic_iterate_end\
+ }\
+} while (FALSE)
+
+#endif /* FC__ITERATOR_H */
_______________________________________________
Freeciv-dev mailing list
Freeciv-dev@gna.org
https://mail.gna.org/listinfo/freeciv-dev
