From 9e41822d23f3c62349751e172a946e832c4a96eb Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Wed, 4 May 2005 05:28:27 +0000 Subject: [PATCH] Improve hash.c comments, error-checking. --- src/ChangeLog | 14 +++++++ src/autorecode.c | 2 +- src/frequencies.q | 2 +- src/hash.c | 95 +++++++++++++++++++++++++++++++++++++---------- src/hash.h | 4 +- src/oneway.q | 6 +-- 6 files changed, 97 insertions(+), 26 deletions(-) diff --git a/src/ChangeLog b/src/ChangeLog index 77928bca..57d7b856 100644 --- a/src/ChangeLog +++ b/src/ChangeLog @@ -1,3 +1,17 @@ +Tue May 3 22:25:17 2005 Ben Pfaff + + Improve hash.c comments, error-checking. + + * hash.c: (struct hsh_table) [NDEBUG] Add hash_ordered member. + (hsh_create) size == 0 should *not* return NULL! Set + hash_ordered. + (hsh_clear) Set hash_ordered. + (locate_matching_entry) Check hash_ordered. + (hsh_rehash) Rename rehash(). Add assertion. Set hash_ordered. + (hsh_data) Set hash_ordered. Add const-ness to return value and + update all callers. + (hsh_sort) Ditto. + Wed May 4 08:50:11 WST 2005 John Darrington * casefile.c: Removed unnecessary #include diff --git a/src/autorecode.c b/src/autorecode.c index 0b6857dd..7887d8a6 100644 --- a/src/autorecode.c +++ b/src/autorecode.c @@ -232,7 +232,7 @@ recode (const struct autorecode_pgm *arc) for (i = 0; i < arc->var_cnt; i++) { struct arc_spec *spec = &t->specs[i]; - void **p = hsh_sort (arc->src_values[i]); + void *const *p = hsh_sort (arc->src_values[i]); int count = hsh_count (arc->src_values[i]); int j; diff --git a/src/frequencies.q b/src/frequencies.q index d5e669e1..983f35da 100644 --- a/src/frequencies.q +++ b/src/frequencies.q @@ -702,7 +702,7 @@ postprocess_freq_tab (struct variable *v) hsh_compare_func *compare; struct freq_tab *ft; size_t count; - void **data; + void *const *data; struct freq *freqs, *f; size_t i; diff --git a/src/hash.c b/src/hash.c index 050b3857..1d9c2f5b 100644 --- a/src/hash.c +++ b/src/hash.c @@ -25,6 +25,7 @@ #include #include "algorithm.h" #include "alloc.h" +#include "bool.h" #include "misc.h" #include "str.h" @@ -146,6 +147,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 +166,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); @@ -177,6 +181,9 @@ hsh_create (int size, hsh_compare_func *compare, hsh_hash_func *hash, h->compare = compare; h->hash = hash; h->free = free; +#ifndef NDEBUG + h->hash_ordered = true; +#endif return h; } @@ -196,6 +203,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 +233,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 +245,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,6 +257,9 @@ 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; @@ -257,6 +274,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 +292,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 +340,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,7 +371,10 @@ 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) { @@ -328,8 +382,7 @@ hsh_data_copy (struct hsh_table *h) assert (h != NULL); copy = xmalloc ((h->used + 1) * sizeof *copy); - copy_if (h->entries, h->size, sizeof *h->entries, copy, - not_null, NULL); + copy_if (h->entries, h->size, sizeof *h->entries, copy, not_null, NULL); copy[h->used] = NULL; return copy; } @@ -338,7 +391,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 +419,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++; diff --git a/src/hash.h b/src/hash.h index ffacad8e..e426483a 100644 --- a/src/hash.h +++ b/src/hash.h @@ -45,8 +45,8 @@ struct hsh_table *hsh_create (int m, hsh_compare_func *, void *aux); void hsh_clear (struct hsh_table *); void hsh_destroy (struct hsh_table *); -void **hsh_sort (struct hsh_table *); -void **hsh_data (struct hsh_table *); +void *const *hsh_sort (struct hsh_table *); +void *const *hsh_data (struct hsh_table *); void **hsh_sort_copy (struct hsh_table *); void **hsh_data_copy (struct hsh_table *); diff --git a/src/oneway.q b/src/oneway.q index 27703055..aa45fbed 100644 --- a/src/oneway.q +++ b/src/oneway.q @@ -423,7 +423,7 @@ show_descriptives(void) const char *s = var_to_string(vars[v]); - struct group_statistics **gs_array = hsh_sort(gp->group_hash); + struct group_statistics *const *gs_array = hsh_sort(gp->group_hash); int count = 0; tab_text (t, 0, row, TAB_LEFT | TAT_TITLE, s); @@ -574,7 +574,7 @@ show_contrast_coeffs(short *bad_contrast) int n_rows = 2 + cmd.sbc_contrast; union value *group_value; int count = 0 ; - void **group_values ; + void *const *group_values ; struct tab_table *t; @@ -699,7 +699,7 @@ show_contrast_tests(short *bad_contrast) struct group_proc *grp_data = group_proc_get (vars[v]); struct hsh_table *group_hash = grp_data->group_hash; - void **group_stat_array; + void *const *group_stat_array; double T; double std_error_contrast ; -- 2.30.2