X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flibpspp%2Fhash.c;h=9d88d6f7d568c221f5496a60bfef585a99f873fe;hb=0a20082e28caaaf1122510d992e1c6dce755ad0e;hp=76503664f016816cdd0ac49e9b5bd31ebb8eeed8;hpb=dcf9b154cbcaa35c3d8459a201b77eec8bcb30bd;p=pspp diff --git a/src/libpspp/hash.c b/src/libpspp/hash.c index 76503664f0..9d88d6f7d5 100644 --- a/src/libpspp/hash.c +++ b/src/libpspp/hash.c @@ -1,6 +1,5 @@ /* PSPP - computes sample statistics. 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 @@ -18,17 +17,21 @@ 02110-1301, USA. */ #include +#include #include "hash.h" #include "message.h" #include #include #include +#include #include #include "array.h" #include "alloc.h" -#include +#include "compiler.h" #include "misc.h" #include "str.h" +#include "pool.h" + #include "gettext.h" #define _(msgid) gettext (msgid) @@ -147,7 +150,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; @@ -157,15 +160,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; @@ -173,12 +188,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; @@ -225,13 +241,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) { @@ -249,6 +266,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. */ @@ -268,26 +303,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_; @@ -329,11 +364,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); @@ -385,7 +420,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; @@ -475,13 +510,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); @@ -502,7 +537,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); } @@ -511,7 +546,7 @@ hsh_delete (struct hsh_table *h, const void *target) } } else - return 0; + return false; } /* Iteration. */ @@ -566,7 +601,7 @@ hsh_count (struct hsh_table *h) /* Debug helpers. */ -#if GLOBAL_DEBUGGING +#if DEBUGGING #undef NDEBUG #include "message.h" #include