X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flibpspp%2Fhash.c;h=71bcd0f14f331f8eb1c07d5478bc46c029ee71de;hb=136d243060f851e01ef46e72b9b554059b5ae544;hp=fcf2b1f9634452c7c079948b21e0b77d3a7df0ba;hpb=2322678e8fddbbf158b01b2720db2636404bba3b;p=pspp diff --git a/src/libpspp/hash.c b/src/libpspp/hash.c index fcf2b1f963..71bcd0f14f 100644 --- a/src/libpspp/hash.c +++ b/src/libpspp/hash.c @@ -18,6 +18,7 @@ 02110-1301, USA. */ #include +#include #include "hash.h" #include "message.h" #include @@ -30,6 +31,8 @@ #include "compiler.h" #include "misc.h" #include "str.h" +#include "pool.h" + #include "gettext.h" #define _(msgid) gettext (msgid) @@ -148,7 +151,7 @@ struct hsh_table size_t size; /* Number of entries (a power of 2). */ void **entries; /* Hash table proper. */ - void *aux; /* Auxiliary data for comparison functions. */ + const void *aux; /* Auxiliary data for comparison functions. */ hsh_compare_func *compare; hsh_hash_func *hash; hsh_free_func *free; @@ -158,15 +161,27 @@ struct hsh_table so that most hsh_*() functions may no longer be called. */ bool hash_ordered; #endif + + struct pool *pool; /* The pool used for this hash table */ }; +struct hsh_table * +hsh_create (int size, hsh_compare_func *compare, hsh_hash_func *hash, + hsh_free_func *free, const void *aux) +{ + return hsh_create_pool (NULL, size, compare, hash, free, aux); +} + + + /* Creates a hash table with at least M entries. COMPARE is a function that compares two entries and returns 0 if they are identical, nonzero otherwise; HASH returns a nonnegative hash value for an entry; FREE destroys an entry. */ struct hsh_table * -hsh_create (int size, hsh_compare_func *compare, hsh_hash_func *hash, - hsh_free_func *free, void *aux) +hsh_create_pool (struct pool *pool, int size, + hsh_compare_func *compare, hsh_hash_func *hash, + hsh_free_func *free, const void *aux) { struct hsh_table *h; int i; @@ -174,12 +189,13 @@ hsh_create (int size, hsh_compare_func *compare, hsh_hash_func *hash, assert (compare != NULL); assert (hash != NULL); - h = xmalloc (sizeof *h); + h = pool_malloc (pool, sizeof *h); + h->pool = pool; h->used = 0; if (size < 4) size = 4; h->size = next_power_of_2 (size); - h->entries = xnmalloc (h->size, sizeof *h->entries); + h->entries = pool_nmalloc (pool, h->size, sizeof *h->entries); for (i = 0; i < h->size; i++) h->entries[i] = NULL; h->aux = aux; @@ -226,13 +242,14 @@ hsh_destroy (struct hsh_table *h) for (i = 0; i < h->size; i++) if (h->entries[i] != NULL) h->free (h->entries[i], h->aux); - free (h->entries); - free (h); + pool_free (h->pool, h->entries); + pool_free (h->pool, h); } } -/* Locates an entry matching TARGET. Returns a pointer to the - entry, or a null pointer on failure. */ +/* Locates an entry matching TARGET. Returns the index for the + entry, if found, or the index of an empty entry that indicates + where TARGET should go, otherwise. */ static inline unsigned locate_matching_entry (struct hsh_table *h, const void *target) { @@ -250,6 +267,24 @@ locate_matching_entry (struct hsh_table *h, const void *target) } } +/* Returns the index of an empty entry that indicates + where TARGET should go, assuming that TARGET is not equal to + any item already in the hash table. */ +static inline unsigned +locate_empty_entry (struct hsh_table *h, const void *target) +{ + unsigned i = h->hash (target, h->aux); + + assert (h->hash_ordered); + for (;;) + { + i &= h->size - 1; + if (h->entries[i] == NULL) + return i; + i--; + } +} + /* Changes the capacity of H to NEW_SIZE, which must be a positive power of 2 at least as large as the number of elements in H. */ @@ -269,26 +304,26 @@ rehash (struct hsh_table *h, size_t new_size) end = begin + h->size; h->size = new_size; - h->entries = xnmalloc (h->size, sizeof *h->entries); + h->entries = pool_nmalloc (h->pool, h->size, sizeof *h->entries); for (i = 0; i < h->size; i++) h->entries[i] = NULL; for (table_p = begin; table_p < end; table_p++) { void *entry = *table_p; if (entry != NULL) - h->entries[locate_matching_entry (h, entry)] = entry; + h->entries[locate_empty_entry (h, entry)] = entry; } - free (begin); + pool_free (h->pool, begin); #ifndef NDEBUG h->hash_ordered = true; #endif } -/* A "algo_predicate_func" that returns nonzero if DATA points +/* A "algo_predicate_func" that returns true if DATA points to a non-null void. */ -static int -not_null (const void *data_, void *aux UNUSED) +static bool +not_null (const void *data_, const void *aux UNUSED) { void *const *data = data_; @@ -330,11 +365,11 @@ hsh_data (struct hsh_table *h) /* Dereferences void ** pointers and passes them to the hash comparison function. */ static int -comparison_helper (const void *a_, const void *b_, void *h_) +comparison_helper (const void *a_, const void *b_, const void *h_) { void *const *a = a_; void *const *b = b_; - struct hsh_table *h = h_; + const struct hsh_table *h = h_; assert(a); assert(b); @@ -386,7 +421,7 @@ hsh_data_copy (struct hsh_table *h) void **copy; assert (h != NULL); - copy = xnmalloc ((h->used + 1), sizeof *copy); + copy = pool_nmalloc (h->pool, (h->used + 1), sizeof *copy); copy_if (h->entries, h->size, sizeof *h->entries, copy, not_null, NULL); copy[h->used] = NULL; return copy; @@ -476,13 +511,13 @@ hsh_find (struct hsh_table *h, const void *target) } /* Deletes the entry in hash table H that matches TARGET. - Returns nonzero if an entry was deleted. + Returns true if an entry was deleted. Uses Knuth's Algorithm 6.4R (Deletion with linear probing). Because our load factor is at most 1/2, the average number of moves that this algorithm makes should be at most 2 - ln 2 ~= 1.65. */ -int +bool hsh_delete (struct hsh_table *h, const void *target) { unsigned i = locate_matching_entry (h, target); @@ -503,7 +538,7 @@ hsh_delete (struct hsh_table *h, const void *target) { i = (i - 1) & (h->size - 1); if (h->entries[i] == NULL) - return 1; + return true; r = h->hash (h->entries[i], h->aux) & (h->size - 1); } @@ -512,7 +547,7 @@ hsh_delete (struct hsh_table *h, const void *target) } } else - return 0; + return false; } /* Iteration. */ @@ -567,7 +602,7 @@ hsh_count (struct hsh_table *h) /* Debug helpers. */ -#if GLOBAL_DEBUGGING +#if DEBUGGING #undef NDEBUG #include "message.h" #include