table

table.h

Header ../../src/table.h; examples ../../test/test_table.c; article ../table/table.pdf.

Hash table

• Description
• Typedef Aliases: <pT>uint, <pT>key, <pT>hash_fn, <pT>unhash_fn, <pT>is_equal_fn, <pT>value, <pT>entry, <pT>policy_fn, <pT>action_fn, <pT>predicate_fn, <pT>to_string_fn
• Struct, Union, and Enum Definitions: table_result, <T>entry, <t>table, <T>cursor, table_stats
• Function Summary
• Function Definitions
• License

Description

<t>table implements a set or map of <pT>entry as an inline-chined hash-table. It must be supplied <pT>hash_fn <t>hash and, <pT>is_equal_fn <t>is_equal or <pT>unhash_fn <t>unhash. It is contiguous and not stable, and may rearrange elements.

• Parameter: TABLE_NAME, TABLE_KEY
  <t> that satisfies C naming conventions when mangled and a valid <pT>key associated therewith; required.
• Parameter: TABLE_UNHASH
  By default it assumes that <t>is_equal is supplied; with this, instead requires <t>unhash satisfying <pT>unhash_fn.
• Parameter: TABLE_VALUE
  An optional type that is the payload of the key, thus making this a map or associative array.
• Parameter: TABLE_UINT
  This is <pT>uint, the unsigned type of hash of the key given by <pT>hash_fn; defaults to size_t. Usually this can be set to the more sensible value uint32_t (or smaller) in C99's stdint.h.
• Parameter: TABLE_DEFAULT
  Default trait; a <pT>value used in <T>table<R>get.
• Parameter: TABLE_TO_STRING
  To string trait contained in ../../src/to_string.h. See <pT>to_string_fn.
• Parameter: TABLE_EXPECT_TRAIT, TABLE_TRAIT
  Named traits are obtained by including table.h multiple times with TABLE_EXPECT_TRAIT and then subsequently including the name in TABLE_TRAIT.
• Parameter: TABLE_DECLARE_ONLY
  For headers in different compilation units.
• Standard:
  C89
• Dependancies:
  box

Typedef Aliases

<pT>uint

typedef TABLE_UINT <pT>uint;

<pT>hash_fn returns this hash type by TABLE_UINT, which must be be an unsigned integer. Places a simplifying limit on the maximum number of elements of half the cardinality.

<pT>key

typedef TABLE_KEY <pT>key;

Valid tag type defined by TABLE_KEY used for keys. If TABLE_UNHASH is not defined, a copy of this value will be stored in the internal buckets.

<pT>hash_fn

typedef <pT>uint(*<pT>hash_fn)(const <pT>key);

A map from <pT>key onto <pT>uint, called <t>hash, that, ideally, should be easy to compute while minimizing duplicate addresses. Must be consistent for each value while in the table. If <pT>key is a pointer, one is permitted to have null in the domain.

<pT>unhash_fn

typedef <pT>key(*<pT>unhash_fn)(<pT>uint);

Defining TABLE_UNHASH says <pT>hash_fn forms a bijection between the range in <pT>key and the image in <pT>uint, and the inverse is called <t>unhash. In this case, keys are not stored in the hash table, rather they are generated using this inverse-mapping. (This provides a smaller and simpler hashing method where the information in the key being hashed is equal to the hash itself—such as numbers.)

<pT>is_equal_fn

typedef int(*<pT>is_equal_fn)(const <pT>key a, const <pT>key b);

Equivalence relation between <pT>key that satisfies <t>is_equal_fn(a, b) -> <t>hash(a) == <t>hash(b), called <t>is_equal. If TABLE_UNHASH is set, there is no need for this function because the comparison is done directly in hash space.

<pT>value

typedef TABLE_VALUE <pT>value;

Defining TABLE_VALUE produces an associative map, otherwise it is the same as <pT>key.

<pT>entry

typedef struct <T>entry <pT>entry;

If TABLE_VALUE, this is <T>entry; otherwise, it's the same as <pT>key.

<pT>policy_fn

typedef int(*<pT>policy_fn)(<pT>key original, <pT>key replace);

Returns true if the replace replaces the original. (fixme: Shouldn't it be entry?)

<pT>action_fn

typedef void(*<pT>action_fn)(<pT>type *);

../../src/iterate.h: Operates by side-effects.

<pT>predicate_fn

typedef int(*<pT>predicate_fn)(const <pT>type *);

../../src/iterate.h: Returns a boolean given read-only.

<pT>to_string_fn

typedef void(*<pT>to_string_fn)(const <pT>key, const <pT>value , char()[12]);

The type of the required <tr>to_string. Responsible for turning the read-only argument into a 12-max-char output string. <pT>value is omitted when it's a set.

Struct, Union, and Enum Definitions

table_result

enum table_result { TABLE_RESULT };

A result of modifying the table, of which TABLE_ERROR is false.

<T>entry

struct <T>entry { <pT>key key; <pT>value value; };

Defining TABLE_VALUE creates this map from <pT>key to <pT>value, as an interface with table.

<t>table

struct <t>table { struct <pT>bucket *buckets; <pT>uint log_capacity, size, top; };

To initialize, see <t>table, TABLE_IDLE, {0} (C99,) or being static. The fields should be treated as read-only; any modification is liable to cause the table to go into an invalid state.

<T>cursor

struct <T>cursor { struct <t>table *table; <pT>uint i; };

Adding, deleting, successfully looking up entries, or any modification of the table's topology invalidates the iterator. Iteration usually not in any particular order, but deterministic up to topology changes. The asymptotic runtime of iterating though the whole table is proportional to the capacity.

table_stats

struct table_stats { size_t n, max; double mean, ssdm; };

Welford1962Note: population variance: ssdm/n, sample variance: ssdm/(n-1).

Function Summary

Modifiers	Function Name	Argument List
struct <T>cursor	<T>begin	<t>table
int	<T>exists	<T>cursor
struct <pT>bucket *	<T>entry	<T>cursor
<pT>key	<T>key	<T>cursor
<pT>value *	<T>value	<T>cursor
void	<T>next	<T>cursor
int	<T>cursor_remove	<T>cursor
struct <t>table	<t>table
void	<t>table_	<t>table
int	<T>buffer	<t>table, <pT>uint
void	<T>clear	<t>table
int	<T>contains	<t>table, <pT>key
int	<T>query	<t>table, <pT>key, <pT>key, <pT>value
int	<T>query	<t>table, <pT>key, <pT>key
<pT>value	<T>get_or	<t>table, <pT>key, <pT>value
enum table_result	<T>try	<t>table, <pT>key
enum table_result	<T>assign	<t>table, <pT>key, <pT>value
enum table_result	<T>update	<t>table, <pT>key, <pT>key
enum table_result	<T>policy	<t>table, <pT>key, <pT>key, <pT>policy_fn
int	<T>remove	<t>table, <pT>key
static <pT>key	<T>key	cur
static <pT>value *	<T>value	cur
static int	<T>cursor_remove	cur
static struct <t>table	<t>table
static void	<t>table_	table
static int	<T>buffer	table, n
static void	<T>clear	table
static int	<T>contains	table, key
static int	<T>query	table, key, result, value
static <pT>value	<T>get_or	table, key, default_value
static enum table_result	<T>try	table, key
static enum table_result	<T>assign	table, key, content
static enum table_result	<T>update	table, key, eject
static enum table_result	<T>policy	table, key, eject, policy
static int	<T>remove	table, key
<pT>type *	<TR>any	<pT>box, <pTR>predicate_fn
void	<TR>each	<pT>box, <pTR>action_fn
void	<TR>if_each	<pT>box, <pTR>predicate_fn, <pTR>action_fn
int	<TR>copy_if	restrict, restrict, <pTR>predicate_fn
static <pT>type *	<TR>any	box, predicate
static void	<TR>each	box, action
static void	<TR>if_each	box, predicate, action
static int	<TR>copy_if	dst, src, copy
static void	<TR>keep_if	box, keep, destruct
static void	<TR>trim	box, predicate
const char *	<TR>to_string	box
static const char *	<TR>to_string	box
void	<T>graph	<pT>box
int	<T>graph_fn	<pT>box, char
static <pT>value	<T>table<R>get	table, key

Function Definitions

<T>begin

struct <T>cursor <T>begin(const struct <t>table *);

<T>exists

int <T>exists(struct <T>cursor *);

<T>entry

struct <pT>bucket *<T>entry(struct <T>cursor *);

<T>key

<pT>key <T>key(const struct <T>cursor *);

<T>value

<pT>value *<T>value(const struct <T>cursor *);

<T>next

void <T>next(struct <T>cursor *);

<T>cursor_remove

int <T>cursor_remove(struct <T>cursor *);

<t>table

struct <t>table <t>table(void);

<t>table_

void <t>table_(struct <t>table *);

<T>buffer

int <T>buffer(struct <t>table *, <pT>uint);

<T>clear

void <T>clear(struct <t>table *);

<T>contains

int <T>contains(struct <t>table *, <pT>key);

<T>query

int <T>query(struct <t>table *, <pT>key, <pT>key *, <pT>value *);

<T>query

int <T>query(struct <t>table *, <pT>key, <pT>key *);

<T>get_or

<pT>value <T>get_or(struct <t>table *, <pT>key, <pT>value);

<T>try

enum table_result <T>try(struct <t>table *, <pT>key);

<T>assign

enum table_result <T>assign(struct <t>table *, <pT>key, <pT>value **);

<T>update

enum table_result <T>update(struct <t>table *, <pT>key, <pT>key *);

<T>policy

enum table_result <T>policy(struct <t>table *, <pT>key, <pT>key *, <pT>policy_fn);

<T>remove

int <T>remove(struct <t>table *, <pT>key);

<T>key

static <pT>key <T>key(const struct <T>cursor *const cur)

• Return:
  If cur has an element, returns it's key.

<T>value

static <pT>value *<T>value(const struct <T>cursor *const cur)

• Return:
  If cur has an element, returns it's value, if TABLE_VALUE.

<T>cursor_remove

static int <T>cursor_remove(struct <T>cursor *const cur)

Removes the entry at cur. Whereas <T>remove invalidates the cursor, this corrects cur so <T>next is the next entry. To use the cursor after this, one must move to the next.

• Return:
  Success, or there was no entry at the iterator's position, (anymore.)

<t>table

static struct <t>table <t>table(void)

Zeroed data (not all-bits-zero) is initialized.

• Return:
  An idle array.
• Order:
  Θ(1)

<t>table_

static void <t>table_(struct <t>table *const table)

If table is not null, destroys and returns it to idle.

<T>buffer

static int <T>buffer(struct <t>table *const table, const <pT>uint n)

Reserve at least n more empty buckets in table. This may cause the capacity to increase and invalidates any pointers to data in the table.

• Return:
  Success.
• Exceptional return: ERANGE
  The request was unsatisfiable.
• Exceptional return: realloc

<T>clear

static void <T>clear(struct <t>table *const table)

Clears and removes all buckets from table. The capacity and memory of the table is preserved, but all previous values are un-associated. (The load factor will be less until it reaches it's previous size.)

• Order:
  Θ(table.capacity)

<T>contains

static int <T>contains(struct <t>table *const table, const <pT>key key)

• Return:
  Whether key is in table (which can be null.)

<T>query

static int <T>query(struct <t>table *const table, const <pT>key key, <pT>key *result, <pT>value *value)

If can be no default key, use this to separate a null—returns false—from a result. Otherwise, a more convenient function is <T>get_or.

• Parameter: result
  If null, behaves like <T>contains, otherwise, a <pT>key which gets filled on true.
• Parameter: value
  Only on a map with TABLE_VALUE. If not-null, stores the value.
• Return:
  Whether key is in table (which can be null.)

<T>get_or

static <pT>value <T>get_or(struct <t>table *const table, const <pT>key key, <pT>value default_value)

• Return:
  The value associated with key in table, (which can be null.) If no such value exists, default_value is returned.
• Order:
  Average Ο(1); worst Ο(n).

<T>try

static enum table_result <T>try(struct <t>table *const table, <pT>key key)

Only if TABLE_VALUE is not set; see <T>assign for a map. Puts key in set table only if absent.

• Return:
  One of: TABLE_ERROR, tried putting the entry in the table but failed, the table is not modified; TABLE_PRESENT, does nothing if there is another entry with the same key; TABLE_ABSENT, put an entry in the table.
• Exceptional return: realloc, ERANGE
  On TABLE_ERROR.
• Order:
  Average amortised Ο(1); worst Ο(n).

<T>assign

static enum table_result <T>assign(struct <t>table *const table, <pT>key key, <pT>value **const content)

Only if TABLE_VALUE is set; see <T>try for a set. Puts key in the map table and store the associated value in content.

• Return:
  TABLE_ERROR does not set content; TABLE_ABSENT, the content will be a pointer to uninitialized memory; TABLE_PRESENT, gets the current content, (does not alter the keys, if they are distinguishable.)
• Exceptional return: malloc, ERANGE
  On TABLE_ERROR.

<T>update

static enum table_result <T>update(struct <t>table *const table, <pT>key key, <pT>key *eject)

Puts key in table, replacing an equal-valued key. (If keys are indistinguishable, this function is not very useful, see <T>try or <T>assign.)

• Return:
  One of: TABLE_ERROR, the table is not modified; TABLE_ABSENT, the key is new; TABLE_PRESENT, the key displaces another, and if non-null, eject will be filled with the previous entry.
• Exceptional return: realloc, ERANGE
  On TABLE_ERROR.
• Order:
  Average amortised Ο(1); worst Ο(n).

<T>policy

static enum table_result <T>policy(struct <t>table *const table, <pT>key key, <pT>key *eject, const <pT>policy_fn policy)

Puts key in table only if absent or if calling policy returns true.

• Return:
  One of: TABLE_ERROR, the table is not modified; TABLE_ABSENT, the key is new; TABLE_PRESENT, key collides, if policy returns true, eject, if non-null, will be filled;
• Exceptional return: realloc, ERANGE
  On TABLE_ERROR.
• Order:
  Average amortised Ο(1); worst Ο(n).

<T>remove

static int <T>remove(struct <t>table *const table, const <pT>key key)

Removes key from table (which could be null.)

• Return:
  Whether that key was in table.
• Order:
  Average Ο(1), (hash distributes elements uniformly); worst Ο(n).

<TR>any

<pT>type *<TR>any(const <pT>box *, <pTR>predicate_fn);

<TR>each

void <TR>each(<pT>box *, <pTR>action_fn);

<TR>if_each

void <TR>if_each(<pT>box *, <pTR>predicate_fn, <pTR>action_fn);

<TR>copy_if

int <TR>copy_if(<pT>box *restrict, const <pTR>box *restrict, <pTR>predicate_fn);

<TR>any

static <pT>type *<TR>any(const <pT>box *const box, const <pTR>predicate_fn predicate)

../../src/iterate.h: Iterates through box and calls predicate until it returns true.

• Return:
  The first predicate that returned true, or, if the statement is false on all, null.
• Order:
  Ο(box.size) × Ο(predicate)

<TR>each

static void <TR>each(<pT>box *const box, const <pTR>action_fn action)

../../src/iterate.h: Iterates through box and calls action on all the elements. Differs calling action until the iterator is one-ahead, so can delete elements as long as it doesn't affect the next, (specifically, a linked-list.)

• Order:
  Ο(|box|) × Ο(action)

<TR>if_each

static void <TR>if_each(<pT>box *const box, const <pTR>predicate_fn predicate, const <pTR>action_fn action)

../../src/iterate.h: Iterates through box and calls action on all the elements for which predicate returns true.

• Order:
  Ο(box.size) × (Ο(predicate) + Ο(action))

<TR>copy_if

static int <TR>copy_if(<pT>box *restrict const dst, const <pTR>box *restrict const src, const <pTR>predicate_fn copy)

../../src/iterate.h, BOX_CONTIGUOUS: For all elements of src, calls copy, and if true, lazily copies the elements to dst. dst and src can not be the same but src can be null, (in which case, it does nothing.)

• Exceptional return: realloc
• Order:
  Ο(|src|) × Ο(copy)

<TR>keep_if

static void <TR>keep_if(<pT>box *const box, const <pTR>predicate_fn keep, const <pTR>action_fn destruct)

../../src/iterate.h BOX_CONTIGUOUS: For all elements of box, calls keep, and if false, if contiguous, lazy deletes that item, if not, eagerly. Calls destruct if not-null before deleting.

• Order:
  Ο(|box|) (× O(keep) + O(destruct))

<TR>trim

static void <TR>trim(<pT>box *const box, const <pTR>predicate_fn predicate)

../../src/iterate.h, BOX_CONTIGUOUS: Removes at either end of box the things that predicate, if it exists, returns true.

• Order:
  Ο(box.size) × Ο(predicate)

<TR>to_string

const char *<TR>to_string(const <pT>box *const box);

<TR>to_string

static const char *<TR>to_string(const <pT>box *const box)

../../src/to_string.h: print the contents of box in a static string buffer of 256 bytes, with limitations of only printing 4 things in a single sequence point.

• Return:
  Address of the static buffer.
• Order:
  Θ(1)

<T>graph

void <T>graph(const <pT>box *, FILE *);

<T>graph_fn

int <T>graph_fn(const <pT>box *, const char *);

<T>table<R>get

static <pT>value <T>table<R>get(struct <t>table *const table, const <pT>key key)

This is functionally identical to <T>get_or, but a with a trait specifying a constant default value. This is the most convenient access method, but it needs to have a TABLE_DEFAULT.

• Return:
  The value associated with key in table, (which can be null.) If no such value exists, the TABLE_DEFAULT for this trait is returned.
• Order:
  Average Ο(1); worst Ο(n).

License

2019 Neil Edelman, distributed under the terms of the MIT License.