1 files changed, 264 insertions, 0 deletions
diff --git a/lib/hash.h b/lib/hash.h
new file mode 100644
index 0000000..ebfc740
--- /dev/null
+++ b/lib/hash.h
@@ -0,0 +1,264 @@
+/* hash - hashing table processing.
+   Copyright (C) 1998-1999, 2001, 2003, 2009-2022 Free Software Foundation,
+   Inc.
+   Written by Jim Meyering <meyering@ascend.com>, 1998.
+
+   This file is free software: you can redistribute it and/or modify
+   it under the terms of the GNU Lesser General Public License as
+   published by the Free Software Foundation; either version 2.1 of the
+   License, or (at your option) any later version.
+
+   This file is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public License
+   along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
+
+/* A generic hash table package.  */
+
+/* Make sure USE_OBSTACK is defined to 1 if you want the allocator to use
+   obstacks instead of malloc, and recompile 'hash.c' with same setting.  */
+
+#ifndef HASH_H_
+# define HASH_H_
+
+# include <stdio.h>
+# include <stdbool.h>
+
+# ifdef __cplusplus
+extern "C" {
+# endif
+
+struct hash_tuning
+  {
+    /* This structure is mainly used for 'hash_initialize', see the block
+       documentation of 'hash_reset_tuning' for more complete comments.  */
+
+    float shrink_threshold;     /* ratio of used buckets to trigger a shrink */
+    float shrink_factor;        /* ratio of new smaller size to original size */
+    float growth_threshold;     /* ratio of used buckets to trigger a growth */
+    float growth_factor;        /* ratio of new bigger size to original size */
+    bool is_n_buckets;          /* if CANDIDATE really means table size */
+  };
+
+typedef struct hash_tuning Hash_tuning;
+
+struct hash_table;
+
+typedef struct hash_table Hash_table;
+
+/*
+ * Information and lookup.
+ */
+
+/* The following few functions provide information about the overall hash
+   table organization: the number of entries, number of buckets and maximum
+   length of buckets.  */
+
+/* Return the number of buckets in the hash table.  The table size, the total
+   number of buckets (used plus unused), or the maximum number of slots, are
+   the same quantity.  */
+extern size_t hash_get_n_buckets (const Hash_table *table)
+       _GL_ATTRIBUTE_PURE;
+
+/* Return the number of slots in use (non-empty buckets).  */
+extern size_t hash_get_n_buckets_used (const Hash_table *table)
+       _GL_ATTRIBUTE_PURE;
+
+/* Return the number of active entries.  */
+extern size_t hash_get_n_entries (const Hash_table *table)
+       _GL_ATTRIBUTE_PURE;
+
+/* Return the length of the longest chain (bucket).  */
+extern size_t hash_get_max_bucket_length (const Hash_table *table)
+       _GL_ATTRIBUTE_PURE;
+
+/* Do a mild validation of a hash table, by traversing it and checking two
+   statistics.  */
+extern bool hash_table_ok (const Hash_table *table)
+       _GL_ATTRIBUTE_PURE;
+
+extern void hash_print_statistics (const Hash_table *table, FILE *stream);
+
+/* If ENTRY matches an entry already in the hash table, return the
+   entry from the table.  Otherwise, return NULL.  */
+extern void *hash_lookup (const Hash_table *table, const void *entry);
+
+/*
+ * Walking.
+ */
+
+/* The functions in this page traverse the hash table and process the
+   contained entries.  For the traversal to work properly, the hash table
+   should not be resized nor modified while any particular entry is being
+   processed.  In particular, entries should not be added, and an entry
+   may be removed only if there is no shrink threshold and the entry being
+   removed has already been passed to hash_get_next.  */
+
+/* Return the first data in the table, or NULL if the table is empty.  */
+extern void *hash_get_first (const Hash_table *table)
+       _GL_ATTRIBUTE_PURE;
+
+/* 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 are no more entries.  */
+extern void *hash_get_next (const Hash_table *table, const void *entry);
+
+/* Fill BUFFER with pointers to active user entries in the hash table, then
+   return the number of pointers copied.  Do not copy more than BUFFER_SIZE
+   pointers.  */
+extern size_t hash_get_entries (const Hash_table *table, void **buffer,
+                                size_t buffer_size);
+
+typedef bool (*Hash_processor) (void *entry, void *processor_data);
+
+/* Call a PROCESSOR function for each entry of a hash table, and return the
+   number of entries for which the processor function returned success.  A
+   pointer to some PROCESSOR_DATA which will be made available to each call to
+   the processor function.  The PROCESSOR accepts two arguments: the first is
+   the user entry being walked into, the second is the value of PROCESSOR_DATA
+   as received.  The walking continue for as long as the PROCESSOR function
+   returns nonzero.  When it returns zero, the walking is interrupted.  */
+extern size_t hash_do_for_each (const Hash_table *table,
+                                Hash_processor processor, void *processor_data);
+
+/*
+ * Allocation and clean-up.
+ */
+
+/* Return a hash index for a NUL-terminated STRING between 0 and N_BUCKETS-1.
+   This is a convenience routine for constructing other hashing functions.  */
+extern size_t hash_string (const char *string, size_t n_buckets)
+       _GL_ATTRIBUTE_PURE;
+
+extern void hash_reset_tuning (Hash_tuning *tuning);
+
+typedef size_t (*Hash_hasher) (const void *entry, size_t table_size);
+typedef bool (*Hash_comparator) (const void *entry1, const void *entry2);
+typedef void (*Hash_data_freer) (void *entry);
+
+/* Reclaim all storage associated with a hash table.  If a data_freer
+   function has been supplied by the user when the hash table was created,
+   this function applies it to the data of each entry before freeing that
+   entry.  */
+extern void hash_free (Hash_table *table);
+
+/* 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.  If TUNING is
+   provided but the values requested are out of bounds or might cause
+   rounding errors, return NULL.
+
+   The user-supplied HASHER function, when not NULL, 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, when not NULL, 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,
+   but which are distinct pointers.
+
+   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.  */
+_GL_ATTRIBUTE_NODISCARD
+extern Hash_table *hash_initialize (size_t candidate,
+                                    const Hash_tuning *tuning,
+                                    Hash_hasher hasher,
+                                    Hash_comparator comparator,
+                                    Hash_data_freer data_freer)
+  _GL_ATTRIBUTE_MALLOC _GL_ATTRIBUTE_DEALLOC (hash_free, 1);
+
+/* Same as hash_initialize, but invokes xalloc_die on memory exhaustion.  */
+/* This function is defined by module 'xhash'.  */
+_GL_ATTRIBUTE_NODISCARD
+extern Hash_table *hash_xinitialize (size_t candidate,
+                                     const Hash_tuning *tuning,
+                                     Hash_hasher hasher,
+                                     Hash_comparator comparator,
+                                     Hash_data_freer data_freer)
+  _GL_ATTRIBUTE_MALLOC _GL_ATTRIBUTE_DEALLOC (hash_free, 1)
+  _GL_ATTRIBUTE_RETURNS_NONNULL;
+
+/* Make all buckets empty, placing any chained entries on the free list.
+   Apply the user-specified function data_freer (if any) to the datas of any
+   affected entries.  */
+extern void hash_clear (Hash_table *table);
+
+/*
+ * Insertion and deletion.
+ */
+
+/* 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
+   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.  Return true iff the rehash succeeded.  */
+_GL_ATTRIBUTE_NODISCARD
+extern bool hash_rehash (Hash_table *table, size_t candidate);
+
+/* If ENTRY matches an entry already in the hash table, return the pointer
+   to the entry from the table.  Otherwise, insert ENTRY and return ENTRY.
+   Return NULL if the storage required for insertion cannot be allocated.
+   This implementation does not support duplicate entries or insertion of
+   NULL.  */
+_GL_ATTRIBUTE_NODISCARD
+extern void *hash_insert (Hash_table *table, const void *entry);
+
+/* Same as hash_insert, but invokes xalloc_die on memory exhaustion.  */
+/* This function is defined by module 'xhash'.  */
+extern void *hash_xinsert (Hash_table *table, const void *entry);
+
+/* Insert ENTRY into hash TABLE if there is not already a matching entry.
+
+   Return -1 upon memory allocation failure.
+   Return 1 if insertion succeeded.
+   Return 0 if there is already a matching entry in the table,
+   and in that case, if MATCHED_ENT is non-NULL, set *MATCHED_ENT
+   to that entry.
+
+   This interface is easier to use than hash_insert when you must
+   distinguish between the latter two cases.  More importantly,
+   hash_insert is unusable for some types of ENTRY values.  When using
+   hash_insert, the only way to distinguish those cases is to compare
+   the return value and ENTRY.  That works only when you can have two
+   different ENTRY values that point to data that compares "equal".  Thus,
+   when the ENTRY value is a simple scalar, you must use
+   hash_insert_if_absent.  ENTRY must not be NULL.  */
+extern int hash_insert_if_absent (Hash_table *table, const void *entry,
+                                  const void **matched_ent);
+
+/* If ENTRY is already in the table, remove it and return the just-deleted
+   data (the user may want to deallocate its storage).  If ENTRY is not in the
+   table, don't modify the table and return NULL.  */
+extern void *hash_remove (Hash_table *table, const void *entry);
+
+/* Same as hash_remove.  This interface is deprecated.
+   FIXME: Remove in 2022.  */
+_GL_ATTRIBUTE_DEPRECATED
+extern void *hash_delete (Hash_table *table, const void *entry);
+
+# ifdef __cplusplus
+}
+# endif
+
+#endif