/* hash - hashing table processing.
- Copyright (C) 1998, 1999 Free Software Foundation, Inc.
+ Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
Written by Jim Meyering, 1992.
This program is free software; you can redistribute it and/or modify
#include <stdio.h>
#include <assert.h>
+#ifndef HAVE_DECL_FREE
+"this configure-time declaration test was not run"
+#endif
#if !HAVE_DECL_FREE
void free ();
#endif
+
+#ifndef HAVE_DECL_MALLOC
+"this configure-time declaration test was not run"
+#endif
#if !HAVE_DECL_MALLOC
char *malloc ();
#endif
#include "hash.h"
+struct hash_table
+ {
+ /* The array of buckets starts at BUCKET and extends to BUCKET_LIMIT-1,
+ for a possibility of N_BUCKETS. Among those, N_BUCKETS_USED buckets
+ are not empty, there are N_ENTRIES active entries in the table. */
+ struct hash_entry *bucket;
+ struct hash_entry *bucket_limit;
+ unsigned n_buckets;
+ unsigned n_buckets_used;
+ unsigned n_entries;
+
+ /* Tuning arguments, kept in a physicaly separate structure. */
+ const Hash_tuning *tuning;
+
+ /* Three functions are given to `hash_initialize', see the documentation
+ block for this function. In a word, HASHER randomizes a user entry
+ into a number up from 0 up to some maximum minus 1; COMPARATOR returns
+ true if two user entries compare equally; and DATA_FREER is the cleanup
+ function for a user entry. */
+ Hash_hasher hasher;
+ Hash_comparator comparator;
+ Hash_data_freer data_freer;
+
+ /* A linked list of freed struct hash_entry structs. */
+ struct hash_entry *free_entry_list;
+
+#if USE_OBSTACK
+ /* Whenever obstacks are used, it is possible to allocate all overflowed
+ entries into a single stack, so they all can be freed in a single
+ operation. It is not clear if the speedup is worth the trouble. */
+ struct obstack entry_stack;
+#endif
+ };
+
/* A hash table contains many internal entries, each holding a pointer to
some user provided data (also called a user entry). An entry indistinctly
refers to both the internal entry and its associated user entry. A user
return bucket->data;
assert (0);
+ return NULL;
}
/* Return the user data for the entry following ENTRY, where ENTRY has been
returned by a previous call to either `hash_get_first' or `hash_get_next'.
- Return NULL if there is no more entries. */
+ Return NULL if there are no more entries. */
void *
hash_get_next (const Hash_table *table, const void *entry)
return cursor->next->data;
/* Find first entry in any subsequent bucket. */
- for (; bucket < table->bucket_limit; bucket++)
+ while (++bucket < table->bucket_limit)
if (bucket->data)
return bucket->data;
divisor++;
}
- return candidate % divisor != 0;
+ return (candidate % divisor ? true : false);
}
/* Round a given CANDIDATE number up to the nearest prime, and return that
/* For the given hash TABLE, check the user supplied tuning structure for
reasonable values, and return true if there is no gross error with it.
- Otherwise, definitvely reset the TUNING field to some acceptable default in
- the hash table (that is, the user loses the right of further modifying
+ Otherwise, definitively reset the TUNING field to some acceptable default
+ in the hash table (that is, the user loses the right of further modifying
tuning arguments), and return false. */
static bool
return false;
}
-/* Allocate and return a new hash table, or NULL upon failure. The
- initial number of buckets is automatically selected so as to _guarantee_ that
- you may insert at least CANDIDATE different user entries before any growth
- of the hash table size occurs. So, if have a reasonably tight a-priori
- upper bound on the
- number of entries you intend to insert in the hash table, you may save some
- table memory and insertion time, by specifying it here. If the
- IS_N_BUCKETS field of the TUNING structure is true, the CANDIDATE argument
- has its meaning changed to the wanted number of buckets.
+/* Allocate and return a new hash table, or NULL upon failure. The initial
+ number of buckets is automatically selected so as to _guarantee_ that you
+ may insert at least CANDIDATE different user entries before any growth of
+ the hash table size occurs. So, if have a reasonably tight a-priori upper
+ bound on the number of entries you intend to insert in the hash table, you
+ may save some table memory and insertion time, by specifying it here. If
+ the IS_N_BUCKETS field of the TUNING structure is true, the CANDIDATE
+ argument has its meaning changed to the wanted number of buckets.
TUNING points to a structure of user-supplied values, in case some fine
tuning is wanted over the default behavior of the hasher. If TUNING is
hash_clear (Hash_table *table)
{
struct hash_entry *bucket;
- struct hash_entry *cursor;
for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
{
if (bucket->data)
{
+ struct hash_entry *cursor;
+ struct hash_entry *next;
+
/* Free the bucket overflow. */
- for (cursor = bucket->next; cursor; cursor = cursor->next)
+ for (cursor = bucket->next; cursor; cursor = next)
{
if (table->data_freer)
(*table->data_freer) (cursor->data);
cursor->data = NULL;
+ next = cursor->next;
/* Relinking is done one entry at a time, as it is to be expected
that overflows are either rare or short. */
cursor->next = table->free_entry_list;
if (bucket->data == NULL)
return NULL;
- /* Check if then entry is found as the bucket head. */
+ /* See if the entry is the first in the bucket. */
if ((*table->comparator) (entry, bucket->data))
{
void *data = bucket->data;
/* For an already existing hash table, change the number of buckets through
specifying CANDIDATE. The contents of the hash table are preserved. The
- new number of buckets is automatically selected so as to _guarantee_ that the
- table may receive at least CANDIDATE different user entries, including
+ new number of buckets is automatically selected so as to _guarantee_ that
+ the table may receive at least CANDIDATE different user entries, including
those already in the table, before any other growth of the hash table size
occurs. If TUNING->IS_N_BUCKETS is true, then CANDIDATE specifies the
exact number of buckets desired. */
table->bucket_limit = new_table->bucket_limit;
table->n_buckets = new_table->n_buckets;
table->n_buckets_used = new_table->n_buckets_used;
+ table->free_entry_list = new_table->free_entry_list;
/* table->n_entries already holds its value. */
#if USE_OBSTACK
table->entry_stack = new_table->entry_stack;
void *data;
struct hash_entry *bucket;
- if (data = hash_find_entry (table, entry, &bucket, true), !data)
+ data = hash_find_entry (table, entry, &bucket, true);
+ if (!data)
return NULL;
table->n_entries--;
struct hash_entry *cursor;
if (bucket)
- printf ("%d:\n", slot);
+ printf ("%d:\n", bucket - table->bucket);
for (cursor = bucket; cursor; cursor = cursor->next)
{
char *s = (char *) cursor->data;
/* FIXME */
- printf (" %s\n", s);
+ if (s)
+ printf (" %s\n", s);
}
}
}
projects / gnulib.git / blobdiff