<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