-/* Global assumptions:
- - ANSI C
- - a certain amount of library support, at least <stdlib.h>
- - C ints are at least 32-bits long
- */
-
-/* Things to do:
- - add a sample do_all function for listing the hash table.
- */
+/* A generic hash table package. */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
-#include "near-prime.h"
#include "hash.h"
#ifdef USE_OBSTACK
-/* This macro assumes that there is an HT with an initialized
- HT_OBSTACK in scope. */
-# define ZALLOC(n) obstack_alloc (&(ht->ht_obstack), (n))
+# define ZALLOC(Ht, N) obstack_alloc (&(ht->ht_obstack), (N))
#else
-# define ZALLOC(n) malloc ((n))
+# define ZALLOC(Ht, N) malloc ((N))
#endif
#define BUCKET_HEAD(ht, idx) ((ht)->hash_table[(idx)])
-static void hash_free_0 (HT *, int);
+static int
+is_prime (candidate)
+ unsigned long candidate;
+{
+ /* No even number and none less than 10 will be passed here. */
+ unsigned long divn = 3;
+ unsigned long sq = divn * divn;
+
+ while (sq < candidate && (candidate % divn))
+ {
+ divn++;
+ sq += 4 * divn;
+ divn++;
+ }
+
+ return (candidate % divn);
+}
+
+/* Round a given number up to the nearest prime. */
+
+static unsigned long
+next_prime (candidate)
+ unsigned long candidate;
+{
+ /* Make it definitely odd. */
+ candidate |= 1;
+
+ while (!is_prime (candidate))
+ candidate += 2;
+
+ return candidate;
+}
static void
hash_free_entry (HT *ht, HASH_ENT *e)
}
else
{
- new = (HASH_ENT *) ZALLOC (sizeof (HASH_ENT));
+ new = (HASH_ENT *) ZALLOC (ht, sizeof (HASH_ENT));
}
return new;
}
return ht->hash_n_slots_used;
}
+/* Free all storage associated with HT that functions in this package
+ have allocated. If a key_freer function has been supplied (when HT
+ was created), this function applies it to the key of each entry before
+ freeing that entry. */
+
+static void
+hash_free_0 (HT *ht, int free_user_data)
+{
+ if (free_user_data && ht->hash_key_freer != NULL)
+ {
+ unsigned int i;
+
+ for (i = 0; i < ht->hash_table_size; i++)
+ {
+ HASH_ENT *p;
+ HASH_ENT *next;
+
+ for (p = BUCKET_HEAD (ht, i); p; p = next)
+ {
+ next = p->next;
+ ht->hash_key_freer (p->key);
+ }
+ }
+ }
+
+#ifdef USE_OBSTACK
+ obstack_free (&(ht->ht_obstack), NULL);
+#else
+ {
+ unsigned int i;
+ for (i = 0; i < ht->hash_table_size; i++)
+ {
+ HASH_ENT *p;
+ HASH_ENT *next;
+
+ for (p = BUCKET_HEAD (ht, i); p; p = next)
+ {
+ next = p->next;
+ free (p);
+ }
+ }
+ }
+#endif
+ ht->hash_free_entry_list = NULL;
+ free (ht->hash_table);
+}
+
/* FIXME-comment */
int
return ht->hash_table_size;
}
-/* TABLE_SIZE should be prime. If WHEN_TO_REHASH is positive, when
- that percentage of table entries have been used, the table is
- deemed too small; then a new, larger table (GROW_FACTOR times
- larger than the previous size) is allocated and all entries in
- the old table are rehashed into the new, larger one. The old
- table is freed. If WHEN_TO_REHASH is zero or negative, the
- table is never resized.
+/* CANDIDATE_TABLE_SIZE need not be prime. If WHEN_TO_REHASH (FIXME: add
+ this parameter) is positive, when that percentage of table entries have
+ been used, the table size is increased; then a new, larger table
+ (GROW_FACTOR (FIXME: maybe add this parameter) times larger than the previous
+ size) is allocated and all entries in the old table are rehashed into
+ the new, larger one. The old table is freed. If WHEN_TO_REHASH is zero
+ or negative, the table is never resized.
The function returns non-zero
- - if TABLE_SIZE is zero or negative
- - if EQUALITY_TESTER or HASH is null
+ - if CANDIDATE_TABLE_SIZE is zero or negative
+ - if KEY_COMPARATOR or HASH is null
- if it was unable to allocate sufficient storage for the hash table
- if WHEN_TO_REHASH is zero or negative
- Otherwise it returns zero.
-
- FIXME: tell what happens to any existing hash table when this
- function is called (e.g. a second time). */
+ Otherwise it returns zero. */
HT *
-hash_initialize (unsigned int table_size,
+hash_initialize (unsigned int candidate_table_size,
Hash_key_freer_type key_freer,
unsigned int (*hash) (const void *, unsigned int),
int (*key_comparator) (const void *, const void *))
{
HT *ht;
unsigned int i;
+ unsigned int table_size;
- if (table_size <= 0)
+ if (candidate_table_size <= 0)
return NULL;
if (hash == NULL || key_comparator == NULL)
if (ht == NULL)
return NULL;
+ table_size = next_prime (candidate_table_size);
ht->hash_table = (HASH_ENT **) malloc (table_size * sizeof (HASH_ENT *));
if (ht->hash_table == NULL)
return NULL;
if ((double) ht->hash_n_keys / ht->hash_table_size > 0.80)
{
unsigned int new_size;
- new_size = near_prime (2 * ht->hash_table_size);
+ new_size = next_prime (2 * ht->hash_table_size + 1);
*failed = hash_rehash (ht, new_size);
}
ht->hash_dirty_max_chain_length = 0;
}
-/* Free all storage associated with HT that functions in this package
- have allocated. If a key_freer function has been supplied (when HT
- was created), this function applies it to the key of each entry before
- freeing that entry. */
-
-static void
-hash_free_0 (HT *ht, int free_user_data)
-{
- if (free_user_data && ht->hash_key_freer != NULL)
- {
- unsigned int i;
-
- for (i = 0; i < ht->hash_table_size; i++)
- {
- HASH_ENT *p;
- HASH_ENT *next;
-
- for (p = BUCKET_HEAD (ht, i); p; p = next)
- {
- next = p->next;
- ht->hash_key_freer (p->key);
- }
- }
- }
-
-#ifdef USE_OBSTACK
- obstack_free (&(ht->ht_obstack), NULL);
-#else
- {
- unsigned int i;
- for (i = 0; i < ht->hash_table_size; i++)
- {
- HASH_ENT *p;
- HASH_ENT *next;
-
- for (p = BUCKET_HEAD (ht, i); p; p = next)
- {
- next = p->next;
- free (p);
- }
- }
- }
-#endif
- ht->hash_free_entry_list = NULL;
- free (ht->hash_table);
-}
-
void
hash_free (HT *ht)
{
projects / gnulib.git / blobdiff