X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Fhash.c;h=bcf5244f049ca64be73130476386a7e95e6cf586;hb=17896e38991000673747aa115b3f7aeb9a57a40f;hp=050b3857338ac5a895305070ed1c92242e248940;hpb=1339492699ce7e12c9bf9fa17f9d60a66024cbd1;p=pspp-builds.git diff --git a/src/hash.c b/src/hash.c index 050b3857..bcf5244f 100644 --- a/src/hash.c +++ b/src/hash.c @@ -20,14 +20,19 @@ #include #include "hash.h" #include "error.h" +#include #include #include #include #include "algorithm.h" #include "alloc.h" +#include #include "misc.h" #include "str.h" +#include "gettext.h" +#define _(msgid) gettext (msgid) + /* Note for constructing hash functions: You can store the hash values in the records, then compare hash @@ -72,7 +77,7 @@ next_power_of_2 (size_t x) unsigned hsh_hash_bytes (const void *buf_, size_t size) { - const unsigned char *buf = buf_; + const unsigned char *buf = (const unsigned char *) buf_; unsigned hash; assert (buf != NULL); @@ -88,7 +93,7 @@ hsh_hash_bytes (const void *buf_, size_t size) unsigned hsh_hash_string (const char *s_) { - const unsigned char *s = s_; + const unsigned char *s = (const unsigned char *) s_; unsigned hash; assert (s != NULL); @@ -104,7 +109,7 @@ hsh_hash_string (const char *s_) unsigned hsh_hash_case_string (const char *s_) { - const unsigned char *s = s_; + const unsigned char *s = (const unsigned char *) s_; unsigned hash; assert (s != NULL); @@ -146,6 +151,12 @@ 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. */ + bool hash_ordered; +#endif }; /* Creates a hash table with at least M entries. COMPARE is a @@ -159,9 +170,6 @@ hsh_create (int size, hsh_compare_func *compare, hsh_hash_func *hash, struct hsh_table *h; int i; - if ( size == 0 ) - return NULL; - assert (compare != NULL); assert (hash != NULL); @@ -170,13 +178,16 @@ hsh_create (int size, hsh_compare_func *compare, hsh_hash_func *hash, if (size < 4) size = 4; h->size = next_power_of_2 (size); - h->entries = xmalloc (sizeof *h->entries * h->size); + h->entries = xnmalloc (h->size, sizeof *h->entries); for (i = 0; i < h->size; i++) h->entries[i] = NULL; h->aux = aux; h->compare = compare; h->hash = hash; h->free = free; +#ifndef NDEBUG + h->hash_ordered = true; +#endif return h; } @@ -196,6 +207,10 @@ hsh_clear (struct hsh_table *h) h->entries[i] = NULL; h->used = 0; + +#ifndef NDEBUG + h->hash_ordered = true; +#endif } /* Destroys table H and all its contents. */ @@ -222,6 +237,7 @@ locate_matching_entry (struct hsh_table *h, const void *target) { unsigned i = h->hash (target, h->aux); + assert (h->hash_ordered); for (;;) { void *entry; @@ -233,9 +249,11 @@ locate_matching_entry (struct hsh_table *h, const void *target) } } -/* Changes the capacity of H to NEW_SIZE. */ +/* 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. */ static void -hsh_rehash (struct hsh_table *h, size_t new_size) +rehash (struct hsh_table *h, size_t new_size) { void **begin, **end, **table_p; int i; @@ -243,11 +261,14 @@ hsh_rehash (struct hsh_table *h, size_t new_size) assert (h != NULL); assert (new_size >= h->used); + /* Verify that NEW_SIZE is a positive power of 2. */ + assert (new_size > 0 && (new_size & (new_size - 1)) == 0); + begin = h->entries; end = begin + h->size; h->size = new_size; - h->entries = xmalloc (sizeof *h->entries * h->size); + h->entries = xnmalloc (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++) @@ -257,6 +278,10 @@ hsh_rehash (struct hsh_table *h, size_t new_size) h->entries[locate_matching_entry (h, entry)] = entry; } free (begin); + +#ifndef NDEBUG + h->hash_ordered = true; +#endif } /* A "algo_predicate_func" that returns nonzero if DATA points @@ -271,18 +296,33 @@ not_null (const void *data_, void *aux UNUSED) /* Compacts hash table H and returns a pointer to its data. The returned data consists of hsh_count(H) non-null pointers, in - no particular order, followed by a null pointer. After - calling this function, only hsh_destroy() and hsh_count() may - be applied to H. */ -void ** + no particular order, followed by a null pointer. + + After calling this function, only hsh_destroy() and + hsh_count() should be applied to H. hsh_first() and + hsh_next() could also be used, but you're better off just + iterating through the returned array. + + This function is intended for use in situations where data + processing occurs in two phases. In the first phase, data is + added, removed, and searched for within a hash table. In the + second phase, the contents of the hash table are output and + the hash property itself is no longer of interest. + + Use hsh_sort() instead, if the second phase wants data in + 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) { size_t n; assert (h != NULL); - n = partition (h->entries, h->size, sizeof *h->entries, - not_null, NULL); + n = partition (h->entries, h->size, sizeof *h->entries, not_null, NULL); assert (n == h->used); +#ifndef NDEBUG + h->hash_ordered = false; +#endif return h->entries; } @@ -304,9 +344,24 @@ comparison_helper (const void *a_, const void *b_, void *h_) /* Sorts hash table H based on hash comparison function. The returned data consists of hsh_count(H) non-null pointers, sorted in order of the hash comparison function, followed by a - null pointer. After calling this function, only hsh_destroy() - and hsh_count() may be applied to H. */ -void ** + null pointer. + + After calling this function, only hsh_destroy() and + hsh_count() should be applied to H. hsh_first() and + hsh_next() could also be used, but you're better off just + iterating through the returned array. + + This function is intended for use in situations where data + processing occurs in two phases. In the first phase, data is + added, removed, and searched for within a hash table. In the + second phase, the contents of the hash table are output and + the hash property itself is no longer of interest. + + Use hsh_data() instead, if the second phase doesn't need the + data in any particular order. Use hsh_data_copy() or + hsh_sort_copy() instead, if the second phase still needs to + search the hash table. */ +void *const * hsh_sort (struct hsh_table *h) { assert (h != NULL); @@ -320,16 +375,18 @@ hsh_sort (struct hsh_table *h) The returned data consists of hsh_count(H) non-null pointers, in no particular order, followed by a null pointer. The hash table is not modified. The caller is responsible for freeing - the allocated data. */ + the allocated data. + + 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) { void **copy; assert (h != NULL); - copy = xmalloc ((h->used + 1) * sizeof *copy); - copy_if (h->entries, h->size, sizeof *h->entries, copy, - not_null, NULL); + copy = xnmalloc ((h->used + 1), sizeof *copy); + copy_if (h->entries, h->size, sizeof *h->entries, copy, not_null, NULL); copy[h->used] = NULL; return copy; } @@ -338,7 +395,10 @@ hsh_data_copy (struct hsh_table *h) The returned data consists of hsh_count(H) non-null pointers, sorted in order of the hash comparison function, followed by a null pointer. The hash table is not modified. The caller is - responsible for freeing the allocated data. */ + responsible for freeing the allocated data. + + 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) { @@ -363,9 +423,10 @@ hsh_probe (struct hsh_table *h, const void *target) assert (h != NULL); assert (target != NULL); + assert (h->hash_ordered); if (h->used > h->size / 2) - hsh_rehash (h, h->size * 2); + rehash (h, h->size * 2); i = locate_matching_entry (h, target); if (h->entries[i] == NULL) h->used++;