HASH(3)

🦋 HASH(3) — Library Functions Manual 🦋

🎀 NAME 🎀

• hash — hash table support (obsolete: use cdt instead) 💀

⚠️ obsolete alert: this page ate in its day, but it's giving legacy API energy. Use cdt instead. no cap, periodt.

✨ SYNOPSIS ✨

#include <hash.h>

💅 DESCRIPTION 💅

okay so the hash routines manipulate collections of dynamic, scoped hash tables. Think of it as the original group chat for keys and values, bestie. 🫶

A hash table provides an association between a key and its value. A key is a sequence of char elements, and a value is a user supplied pointer to the value. Each hash table has a dynamic number of slots, each pointing to the head of a forward linked collision chain. 🎀

Hashing occurs as follows: a hash function takes a key as an argument and returns a non-negative index. The index modulo the table size produces a slot that points to a collision chain. The collision chain is sequentially searched until a match is found for key. The hash tables are automatically resized as new entries are added. fr fr. ✨

Each hash table has one key type. The default key type is a pointer to a null-terminated string. The alternate key type is a pointer to a fixed length byte buffer, declared for a given table by the hashalloc() function described below. 🌸

Hash table information is partitioned into two parts for efficient scoping. Vibe check: the root part contains fixed information that is shared among a set of related hash tables. The remaining information is maintained on a per-table basis. iykyk. 💜

These basic types are defined in the header file hash.h (alternate names are listed in parenthesis) — ngl, the parentheses are important:

• Hash_table_t (HASHTABLE) — The per-table information. The readonly public elements are lowkey iconic:
  • int buckets — The number of table entries.
  • char* name — The hash table name.
  • root — The root information. The public elements are:
    • int root->accesses — The number of lookups.
    • int root->collisions — The number of lookup collisions.
  • Hash_table_t* scope — The table that this scope covers, NULL if the table is not a scope.
  • int size — The current hash table size.
• Hash_bucket_t (HASHBUCKET) — A collision chain hash bucket. The public structure elements are:
  • char* hashname(Hash_bucket_t*) — Returns a pointer to the hash bucket key given the bucket pointer.
  • char* value — The value associated with the key.
• Hash_header_t (HASHHEADER) — The hash bucket header that must be the first element in all user defined buckets. Heads up: HASH_VALUE may not be used with user defined buckets. 🚫
• Hash_position_t (HASHPOSITION) — Stores the hash table position for hashscan. The public elements are:
  • Hash_bucket_t* bucket — The current hash bucket pointer.

The routines are giving main character energy 👑:

🧚 hashalloc

Hash_table_t* hashalloc(Hash_table_t* ref, int op, ...)

Creates a new hash table and returns a pointer to the table — not me still relying on malloc(3) for space here, but okay 💀. NULL is returned if the table cannot be created. ref is a pointer to a reference hash table that provides default values for unspecified information. The new hash table and ref share the same root information. If ref is NULL then new root information is created for the new table. The remaining arguments appear in op-arg pairs, followed by a final 0 argument. The op-arg pairs are:

• HASH_alloc, (char(*)()) alloc — alloc is a function that is called to process Hash_bucket_t value assignments. The single argument is char* value and the processed char* value is returned. 🎀
• HASH_clear, int flags — flags are the ref flags to be cleared in the new hash table. See HASH_set below.
• HASH_compare, (int(*)()) compare — Specifies an alternate key comparison function. The arguments and return value for compare are the same as for strncmp(3) if HASH_namesize is specified and strcmp(3) otherwise. The first argument is the key from the current hash bucket on the collision chain and the second argument is the user supplied key.
• HASH_free, (int(*)()) free — free is a function that is called when a hash bucket is freed. If HASH_BUCKET was set in hashalloc then the hash bucket pointer is passed, otherwise the bucket value pointer is passed.
• HASH_hash, (int(*)()) hash — Specifies an alternate key hash function. A char* key argument (and, if HASH_namesize is specified, an int key size argument) is passed to hash. The return value must be a non-negative int.
• HASH_meanchain, int meanchain — Specifies the mean collision chain length. The hash table is automatically resized when this value is exceeded. The default mean chain length is 2.
• HASH_name, char* name — Associates name with the hash table. Used by hashdump).
• HASH_namesize, int namesize — The fixed size in bytes for keys in the table. If namesize is 0 (the default) then the keys are interpreted as null-terminated strings.
• HASH_set, int flags — Changes the hash table flags by oring in flags. The flags, which may be ored together, are:
  • HASH_ALLOCATE — Keys for new hash table entries are to be copied to data areas obtained from malloc(3).
  • HASH_FIXED — Fixes the hash table size, disabling any automatic table resizing.
  • HASH_SCOPE — The new hash table is a scope that is to be pushed on top of ref. ref must be non-NULL.
• HASH_va_list, va_list ap — ap is a va_list variable argument list pointer (see <stdarg.h>).

🧚 hashfree

Hash_table_t* hashfree(Hash_table_t* tab)

The hash table tab is freed. The scope covered table pointer is returned, NULL if tab is not a scope. easy peasy.

🔥 hashlook

char* hashlook(Hash_table_t* tab, char* name, int flags, char* value)

okay so this operates on the key name in the hash table tab according to flags and value. A Hash_bucket_t pointer is returned unless otherwise noted. There are three basic lookup operations:

• HASH_CREATE — name is entered into the top level scope if it does not already exist. If name also appears in a lower scope and HASH_ALLOC is set for the table then the new bucket will share the name field value with the lower scope.
• HASH_DELETE — name is deleted from the top level scope if it exists. NULL is returned.
• HASH_LOOKUP — The scopes are searched in order from top to bottom for name. The bucket pointer for the first occurrence is returned. NULL is returned if name is not found.

The basic operations may be qualified by the following (the qualifiers are restricted to the basic operations in the parenthesized list):

• HASH_BUCKET (HASH_CREATE,HASH_DELETE,HASH_LOOKUP) — name is a pointer to a bucket that has already been entered into the table.
• HASH_FIXED (HASH_CREATE) — value is taken to be the size of the hash bucket to be created for name in the top level scope. The minimum bucket size is silently restricted to sizeof(Hash_header_t).
• HASH_INSTALL (HASH_CREATE) — name is a pointer to a bucket that has not been entered into the table.
• HASH_NOSCOPE (HASH_LOOKUP) — The lookup is restricted to the top level scope.
• HASH_OPAQUE (HASH_CREATE,HASH_DELETE) — Sets (HASH_CREATE) or clears (HASH_DELETE) the opaque property for the bucket. An opaque bucket is not visible in lower scopes.
• HASH_SCOPE (HASH_CREATE,HASH_DELETE) — All scopes are searched for the bucket. If the bucket is not found for HASH_CREATE then a new bucket is created in the lowest scope.
• HASH_VALUE (HASH_CREATE,HASH_LOOKUP) — For HASH_CREATE the bucket value field is set to value and the bucket name value is returned. For HASH_LOOKUP the bucket value field is returned, NULL if the bucket is not found.

If name is NULL then the name from the most recent hashlook() is used, avoiding recomputation of some internal parameters. ✨

🦋 hashget

char* hashget(Hash_table_t* tab, char* name)

Returns the value associated with the key name in the hash table tab. If name is NULL then the name from the most recent hashget() is used, avoiding recomputation of some internal parameters. NULL is returned if name is not in the table. All scope covered tables are searched.

🎀 hashlast

Hash_bucket_t* hashlast(Hash_table_t* tab)

Returns a pointer to the most recent hash bucket for tab. The value is set by hashlook(), hashscan() and hashwalk().

💖 hashput

char* hashput(Hash_table_t* tab, char* name, char* value)

Set the value of the key name to value in the top level scope of the hash table tab. name is entered into the top level scope if necessary. The (possibly re-allocated) key name pointer is returned (see HASH_ALLOCATE). If name is 0 then the most recent lookup name to hashlook() or hashget() is used. This eliminates a re-hash and re-lookup of name.

🧚 hashwalk

int hashwalk(Hash_table_t* tab, int flags, (int(*)()) walker, char* handle)

The function walker is applied to each entry (not covered by a scope starting at tab) in the hash table tab. If flags is HASH_NOSCOPE then only the top level hash table is used, otherwise the walk includes all scope covered tables. walker is called with char* key as the first argument, char* value as the second argument, and char* handle as the third argument. handle may be 0. The walk terminates after the last entry or when walker returns a negative value. The return value of the last call to walker is returned. Only one walk may be active within a collection of scoped tables.

Okay so, continuing the function tea ☕ — same section energy, no heading repeat, just the rest of the lineup:

• Hash_position_t* hashscan(Hash_table_t* tab, int flags) — hands you a Hash_position_t pointer for a sequential scan on the hash table tab. If flags is HASH_NOSCOPE, then only the top level hash table is used; otherwise the scan includes all scope covered tables. Only one scan may be active within a collection of scoped tables. hashdone() must be called to terminate the scan. 0 is returned on error. 🫶
• Hash_bucket_t* hashnext(Hash_position_t* pos) — returns a pointer to the next bucket in the sequential scan set up by hashscan() on pos. If no elements remain then 0 is returned. 🔥
• void hashdone(Hash_position_t* pos) — completes a scan initiated by hashscan() on pos. Bye scan, it was iconic 👋
• int hashset(Hash_table_t* tab, int flags) — sets the flags for the hash table tab by oring in flags. Only HASH_ALLOCATE and HASH_FIXED may be set. Periodt 💅
• int hashclear(Hash_table_t* tab, int flags) — clears the flags for the hash table tab by masking out flags. Only HASH_ALLOCATE and HASH_FIXED may be cleared. Cleanup era ✨
• void hashdump(Hash_table_t* tab, int flags) — dumps hash table accounting info to standard error. If tab is NULL then all allocated hash tables are dumped; otherwise only information on tab is dumped. If flags is HASH_BUCKET then the hash bucket key-value pairs for each collision chain are also dumped. Spill the tea, hash tables ☕💀
• void hashsize(Hash_table_t* tab, int size) — changes the size of the hash table tab to size, where size must be a power of 2. Explicit calls to this routine are not necessary as hash tables are automatically resized.

Bestie, power of 2 or it’s not happening — that’s the rule 🌸

• int strhash(char* name) — hashes the null terminated character string name using a linear congruent pseudo-random number generator algorithm and returns a non-negative int hash value. Math but make it cute 🧚
• int memhash(char* buf, int siz) — hashes the buffer buf of siz bytes using a linear congruent pseudo-random number generator algorithm and returns a non-negative int hash value. Buffer gets the hash treatment too 🫶
• long strsum(char* name, long sum) — returns a running 31-bit checksum of the string name, where sum is 0 on the first call and the return value from a previous memsum or strsum call otherwise. The checksum value is consistent across all implementations. Reliable queen behavior 👑
• long memsum(char* buf, int siz, long sum) — returns a running 31-bit checksum of buffer buf of siz bytes, where sum is 0 on the first call and the return value from a previous memsum or strsum call otherwise. The checksum value is consistent across all implementations. Same checksum energy, memory edition 💜

---

🌈 SEE ALSO 🌈

• sum(1) — the one and only cross-reference, periodt.

Cute sign-off: the footer says HASH(3), and there’s no extra source/version/date line in what we got — so that’s the whole footer vibe. Stay hashed and hydrated, bestie 💅✨