X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flibpspp%2Fhash.c;h=eb43b54e7fedf24d7db0dd569cc34d885bb91dd4;hb=b5c82cc9aabe7e641011130240ae1b2e84348e23;hp=c3a7eb7e59d7c82d5ec2feeda287cdc014b4befb;hpb=5fd22ca7771c8175ef05e91e1194c3c4096337f4;p=pspp-builds.git diff --git a/src/libpspp/hash.c b/src/libpspp/hash.c index c3a7eb7e..eb43b54e 100644 --- a/src/libpspp/hash.c +++ b/src/libpspp/hash.c @@ -1,35 +1,34 @@ -/* PSPP - computes sample statistics. - Copyright (C) 1997-9, 2000 Free Software Foundation, Inc. - Written by Ben Pfaff . +/* PSPP - a program for statistical analysis. + Copyright (C) 1997-9, 2000, 2008 Free Software Foundation, Inc. - 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 of the - License, or (at your option) any later version. + 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 3 of the License, 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. + 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. You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA - 02110-1301, USA. */ + along with this program. If not, see . */ #include +#include #include "hash.h" #include "message.h" #include -#include #include #include #include #include "array.h" -#include "alloc.h" #include "compiler.h" #include "misc.h" #include "str.h" +#include "pool.h" + +#include "xalloc.h" #include "gettext.h" #define _(msgid) gettext (msgid) @@ -52,11 +51,11 @@ /* Returns smallest power of 2 greater than X. */ static size_t -next_power_of_2 (size_t x) +next_power_of_2 (size_t x) { assert (x != 0); - for (;;) + for (;;) { /* Turn off rightmost 1-bit in x. */ size_t y = x & (x - 1); @@ -70,74 +69,6 @@ next_power_of_2 (size_t x) } } -/* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */ -#define FNV_32_PRIME 16777619u -#define FNV_32_BASIS 2166136261u - -/* Fowler-Noll-Vo 32-bit hash, for bytes. */ -unsigned -hsh_hash_bytes (const void *buf_, size_t size) -{ - const unsigned char *buf = (const unsigned char *) buf_; - unsigned hash; - - assert (buf != NULL); - - hash = FNV_32_BASIS; - while (size-- > 0) - hash = (hash * FNV_32_PRIME) ^ *buf++; - - return hash; -} - -/* Fowler-Noll-Vo 32-bit hash, for strings. */ -unsigned -hsh_hash_string (const char *s_) -{ - const unsigned char *s = (const unsigned char *) s_; - unsigned hash; - - assert (s != NULL); - - hash = FNV_32_BASIS; - while (*s != '\0') - hash = (hash * FNV_32_PRIME) ^ *s++; - - return hash; -} - -/* Fowler-Noll-Vo 32-bit hash, for case-insensitive strings. */ -unsigned -hsh_hash_case_string (const char *s_) -{ - const unsigned char *s = (const unsigned char *) s_; - unsigned hash; - - assert (s != NULL); - - hash = FNV_32_BASIS; - while (*s != '\0') - hash = (hash * FNV_32_PRIME) ^ toupper (*s++); - - return hash; -} - -/* Hash for ints. */ -unsigned -hsh_hash_int (int i) -{ - return hsh_hash_bytes (&i, sizeof i); -} - -/* Hash for double. */ -unsigned -hsh_hash_double (double d) -{ - if (!isnan (d)) - return hsh_hash_bytes (&d, sizeof d); - else - return 0; -} /* Hash tables. */ @@ -148,38 +79,51 @@ 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; - + #ifndef NDEBUG /* Set to false if hsh_data() or hsh_sort() has been called, 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; 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; @@ -220,21 +164,22 @@ hsh_destroy (struct hsh_table *h) { int i; - if (h != NULL) + if (h != NULL) { if (h->free) 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) +locate_matching_entry (struct hsh_table *h, const void *target) { unsigned i = h->hash (target, h->aux); @@ -250,6 +195,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 +232,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++) + 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_; @@ -314,7 +277,7 @@ not_null (const void *data_, void *aux UNUSED) sorted order. Use hsh_data_copy() or hsh_sort_copy() instead, if the second phase still needs to search the hash table. */ void *const * -hsh_data (struct hsh_table *h) +hsh_data (struct hsh_table *h) { size_t n; @@ -330,11 +293,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); @@ -381,12 +344,12 @@ hsh_sort (struct hsh_table *h) If you don't need to search or modify the hash table, then hsh_data() is a more efficient choice. */ void ** -hsh_data_copy (struct hsh_table *h) +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; @@ -401,7 +364,7 @@ hsh_data_copy (struct hsh_table *h) If you don't need to search or modify the hash table, then hsh_sort() is a more efficient choice. */ void ** -hsh_sort_copy (struct hsh_table *h) +hsh_sort_copy (struct hsh_table *h) { void **copy; @@ -417,11 +380,11 @@ hsh_sort_copy (struct hsh_table *h) to a pointer to that entry; otherwise returns a pointer to a NULL entry which *must* be used to insert a new entry having the same key data. */ -inline void ** +void ** hsh_probe (struct hsh_table *h, const void *target) { unsigned i; - + assert (h != NULL); assert (target != NULL); assert (h->hash_ordered); @@ -438,7 +401,7 @@ hsh_probe (struct hsh_table *h, const void *target) TARGET and returns a null pointer. If found, returns the match, without replacing it in the table. */ void * -hsh_insert (struct hsh_table *h, void *target) +hsh_insert (struct hsh_table *h, void *target) { void **entry; @@ -446,7 +409,7 @@ hsh_insert (struct hsh_table *h, void *target) assert (target != NULL); entry = hsh_probe (h, target); - if (*entry == NULL) + if (*entry == NULL) { *entry = target; return NULL; @@ -459,7 +422,7 @@ hsh_insert (struct hsh_table *h, void *target) TARGET and returns a null pointer. If found, returns the match, after replacing it in the table by TARGET. */ void * -hsh_replace (struct hsh_table *h, void *target) +hsh_replace (struct hsh_table *h, void *target) { void **entry = hsh_probe (h, target); void *old = *entry; @@ -476,43 +439,43 @@ 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 -hsh_delete (struct hsh_table *h, const void *target) +bool +hsh_delete (struct hsh_table *h, const void *target) { unsigned i = locate_matching_entry (h, target); - if (h->entries[i] != NULL) + if (h->entries[i] != NULL) { h->used--; if (h->free != NULL) h->free (h->entries[i], h->aux); - for (;;) + for (;;) { unsigned r; ptrdiff_t j; h->entries[i] = NULL; j = i; - do + do { 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); } while ((i <= r && r < j) || (r < j && j < i) || (j < i && i <= r)); - h->entries[j] = h->entries[i]; + h->entries[j] = h->entries[i]; } } else - return 0; + return false; } /* Iteration. */ @@ -521,7 +484,7 @@ hsh_delete (struct hsh_table *h, const void *target) use with hsh_next(). If TABLE is empty, returns a null pointer. */ void * -hsh_first (struct hsh_table *h, struct hsh_iterator *iter) +hsh_first (struct hsh_table *h, struct hsh_iterator *iter) { assert (h != NULL); assert (iter != NULL); @@ -557,11 +520,11 @@ hsh_next (struct hsh_table *h, struct hsh_iterator *iter) } /* Returns the number of items in H. */ -size_t -hsh_count (struct hsh_table *h) +size_t +hsh_count (struct hsh_table *h) { assert (h != NULL); - + return h->used; }