+ *tuning = default_tuning;
+}
+
+/* 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, 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
+check_tuning (Hash_table *table)
+{
+ const Hash_tuning *tuning = table->tuning;
+
+ if (tuning->growth_threshold > 0.0
+ && tuning->growth_threshold < 1.0
+ && tuning->growth_factor > 1.0
+ && tuning->shrink_threshold >= 0.0
+ && tuning->shrink_threshold < 1.0
+ && tuning->shrink_factor > tuning->shrink_threshold
+ && tuning->shrink_factor <= 1.0
+ && tuning->shrink_threshold < tuning->growth_threshold)
+ return true;
+
+ table->tuning = &default_tuning;
+ 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.
+
+ 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
+ NULL, the default tuning parameters are used instead.
+
+ The user-supplied HASHER function should be provided. It accepts two
+ arguments ENTRY and TABLE_SIZE. It computes, by hashing ENTRY contents, a
+ slot number for that entry which should be in the range 0..TABLE_SIZE-1.
+ This slot number is then returned.
+
+ The user-supplied COMPARATOR function should be provided. It accepts two
+ arguments pointing to user data, it then returns true for a pair of entries
+ that compare equal, or false otherwise. This function is internally called
+ on entries which are already known to hash to the same bucket index.
+
+ The user-supplied DATA_FREER function, when not NULL, may be later called
+ with the user data as an argument, just before the entry containing the
+ data gets freed. This happens from within `hash_free' or `hash_clear'.
+ You should specify this function only if you want these functions to free
+ all of your `data' data. This is typically the case when your data is
+ simply an auxiliary struct that you have malloc'd to aggregate several
+ values. */
+
+Hash_table *
+hash_initialize (unsigned candidate, const Hash_tuning *tuning,
+ Hash_hasher hasher, Hash_comparator comparator,
+ Hash_data_freer data_freer)
+{
+ Hash_table *table;
+ struct hash_entry *bucket;
+
+ if (hasher == NULL || comparator == NULL)
+ return NULL;
+
+ table = (Hash_table *) malloc (sizeof (Hash_table));
+ if (table == NULL)
+ return NULL;
+
+ if (!tuning)
+ tuning = &default_tuning;
+ table->tuning = tuning;
+ if (!check_tuning (table))
+ {
+ /* Fail if the tuning options are invalid. This is the only occasion
+ when the user gets some feedback about it. Once the table is created,
+ if the user provides invalid tuning options, we silently revert to
+ using the defaults, and ignore further request to change the tuning
+ options. */
+ free (table);
+ return NULL;
+ }
+
+ table->n_buckets
+ = next_prime (tuning->is_n_buckets ? candidate
+ : (unsigned) (candidate / tuning->growth_threshold));
+
+ table->bucket = (struct hash_entry *)
+ malloc (table->n_buckets * sizeof (struct hash_entry));
+ if (table->bucket == NULL)
+ {
+ free (table);
+ return NULL;
+ }
+ table->bucket_limit = table->bucket + table->n_buckets;
+
+ for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
projects / bison.git / blobdiff