X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flibpspp%2Fhash.c;h=9da3deb120a92ba0ee3423f78441ad85dd9ab22f;hb=f404544337964f80bb2d1fee5acb147f7023bc08;hp=9a6c3cae89b2e9499f450a72601de78c3228d464;hpb=a1a4228b112a6aca97fef5aaaf9ffa21271a1f72;p=pspp-builds.git diff --git a/src/libpspp/hash.c b/src/libpspp/hash.c index 9a6c3cae..9da3deb1 100644 --- a/src/libpspp/hash.c +++ b/src/libpspp/hash.c @@ -1,21 +1,18 @@ -/* PSPP - computes sample statistics. +/* PSPP - a program for statistical analysis. Copyright (C) 1997-9, 2000 Free Software Foundation, Inc. - Written by Ben Pfaff . - 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 @@ -27,12 +24,12 @@ #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) @@ -55,11 +52,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); @@ -91,11 +88,11 @@ hsh_hash_bytes (const void *buf_, size_t size) hash = (hash * FNV_32_PRIME) ^ *buf++; return hash; -} +} /* Fowler-Noll-Vo 32-bit hash, for strings. */ unsigned -hsh_hash_string (const char *s_) +hsh_hash_string (const char *s_) { const unsigned char *s = (const unsigned char *) s_; unsigned hash; @@ -111,7 +108,7 @@ hsh_hash_string (const char *s_) /* Fowler-Noll-Vo 32-bit hash, for case-insensitive strings. */ unsigned -hsh_hash_case_string (const char *s_) +hsh_hash_case_string (const char *s_) { const unsigned char *s = (const unsigned char *) s_; unsigned hash; @@ -127,14 +124,14 @@ hsh_hash_case_string (const char *s_) /* Hash for ints. */ unsigned -hsh_hash_int (int i) +hsh_hash_int (int i) { return hsh_hash_bytes (&i, sizeof i); } /* Hash for double. */ unsigned -hsh_hash_double (double d) +hsh_hash_double (double d) { if (!isnan (d)) return hsh_hash_bytes (&d, sizeof d); @@ -155,7 +152,7 @@ struct hsh_table 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. */ @@ -167,7 +164,7 @@ struct hsh_table struct hsh_table * hsh_create (int size, hsh_compare_func *compare, hsh_hash_func *hash, - hsh_free_func *free, void *aux) + hsh_free_func *free, const void *aux) { return hsh_create_pool (NULL, size, compare, hash, free, aux); } @@ -179,16 +176,16 @@ hsh_create (int size, hsh_compare_func *compare, hsh_hash_func *hash, identical, nonzero otherwise; HASH returns a nonnegative hash value for an entry; FREE destroys an entry. */ struct hsh_table * -hsh_create_pool (struct pool *pool, int size, +hsh_create_pool (struct pool *pool, int size, hsh_compare_func *compare, hsh_hash_func *hash, - hsh_free_func *free, void *aux) + hsh_free_func *free, const void *aux) { struct hsh_table *h; int i; assert (compare != NULL); assert (hash != NULL); - + h = pool_malloc (pool, sizeof *h); h->pool = pool; h->used = 0; @@ -236,7 +233,7 @@ hsh_destroy (struct hsh_table *h) { int i; - if (h != NULL) + if (h != NULL) { if (h->free) for (i = 0; i < h->size; i++) @@ -251,7 +248,7 @@ hsh_destroy (struct hsh_table *h) 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); @@ -271,7 +268,7 @@ locate_matching_entry (struct hsh_table *h, const void *target) 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) +locate_empty_entry (struct hsh_table *h, const void *target) { unsigned i = h->hash (target, h->aux); @@ -307,7 +304,7 @@ rehash (struct hsh_table *h, size_t new_size) 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) @@ -323,7 +320,7 @@ rehash (struct hsh_table *h, size_t new_size) /* A "algo_predicate_func" that returns true if DATA points to a non-null void. */ static bool -not_null (const void *data_, void *aux UNUSED) +not_null (const void *data_, const void *aux UNUSED) { void *const *data = data_; @@ -349,7 +346,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; @@ -365,7 +362,7 @@ 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_, const void *h_) +comparison_helper (const void *a_, const void *b_, const void *h_) { void *const *a = a_; void *const *b = b_; @@ -416,7 +413,7 @@ 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; @@ -436,7 +433,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; @@ -452,11 +449,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); @@ -473,7 +470,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; @@ -481,7 +478,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; @@ -494,7 +491,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; @@ -518,32 +515,32 @@ hsh_find (struct hsh_table *h, const void *target) moves that this algorithm makes should be at most 2 - ln 2 ~= 1.65. */ bool -hsh_delete (struct hsh_table *h, const void *target) +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 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 @@ -556,7 +553,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); @@ -592,11 +589,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; }