hashtable - CTL - C Container Template library

Defined in header <ctl/hashtable.h>, CTL prefix htbl, parent of unordered_map

No implementation yet.

SYNOPSIS

typedef struct {
  char *key;
  int value;
} charint;

static inline size_t
charint_hash(charint *a) { return FNV1a(a->key); }

static inline int
charint_equal(charint *a, charint *b) { return strcmp(a->key, b->key) == 0; }

static inline void
charint_free(charint *a) { free(a->key); }

static inline charint
charint_copy(charint *self) {
  char *copy_key = (char*) malloc(strlen(self->key) + 1);
  strcpy (copy_key, self->key);
  charint copy = {
    copy_key,
    self->value,
  };
  return copy;
}

#define T charint
#include <ctl/hashtable.h>

htbl_charint a = htbl_charint_init(1000, charint_hash, charint_equal);

char c_char[36];
for (int i=0; i<1000; i++) {
    snprintf(c_char, 36, "%c%d", 48 + (rand() % 74), rand());
    //str s = (str){.value = c_char};
    htbl_charint_insert(&a, charint_copy(&(charint){ c_char, i }));
}
foreach(htbl_charint, &a, it) { strcpy (c_char, it.ref->key); }
printf("last key \"%s\", ", c_char);
foreach(htbl_charint, &a, it) { htbl_charint_bucket_size(it.node); }
printf("htbl_charint load_factor: %f\n", htbl_charint_load_factor(&a));
htbl_charint_free(&a);

DESCRIPTION

hashtable is an optimized associative container (open-addressing hash table) that contains a set of unique objects of type Key. Search, insertion, and removal have average constant-time complexity.

The function names are composed of the prefix htbl_, the user-defined type T and the method name. E.g htbl_charint with #define T charint. The type must be a custom struct.

Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its value. This allows fast access to individual elements, since once a hash is computed, it refers to the exact bucket the element is placed into.

This hash table, in opposition to unordered_map, does not to guarantee that pointers into nodes and values stay the same. Container elements may not be modified since modification could change an element’s hash and corrupt the container.

It has the same API as unordered_map, just no Bucket interface.

Member types

T value type

A being uset_T container type

B being uset_T_node node type

I being uset_T_it iterator type

Member functions

init (bucket_count, T_hash(T*), T_equal(T*, T*))

constructs the hash table.

free (A* self)

destructs the hash table.

assign (A* self, A* other)

replaces the contents of the container.

copy (A* self)

returns a copy of the container.

Iterators

I begin (A* self)

Constructs an iterator to the begin.

I end (A* self)

constructs an iterator to the end.

I* next (I* iter)

Advances the iterator by 1 forwards. There’s no prev yet.

I* advance (I* iter, long i)

All our variants accepts negative i to move back. The return value may be ignored.

See iterators for more.

Capacity

empty (A* self)

checks whether the container is empty

size (A* self)

returns the number of non-empty and non-deleted elements

capacity (A* self)

returns the size of the array

size_t max_size ()

returns the maximum possible number of elements

Modifiers

clear (A* self)

clears the contents

insert (A* self, T value)

inserts the element (C++17)

emplace (A* self, T values...)

constructs elements in-place. (NYI)

emplace_hint (A* self, I* pos, T values...)

constructs elements in-place at position. (NYI)

erase (A* self, T key)

erases the element by key

erase_it (A* self, I* pos)

erases the element at pos

erase_range (A* self, I* first, I* last)

erases elements

swap (A* self, A* other)

swaps the contents

extract (A* self, T key) extract_it (A* self, I* pos)

extracts a node from the container. NYI

merge (A* self)

splices nodes from another container

Lookup

count (A* self)

returns the number of elements matching specific key

find (A* self, T key)

finds element with specific key

contains (A* self, T key)

checks if the container contains element with specific key. (C++20)

equal_range (A* self)

returns range of elements matching a specific key. (NYI)

Hash policy

load_factor (A* self)

returns average number of elements per bucket

max_load_factor () set_max_load_factor (A* self, float factor)

manages maximum average number of elements per bucket. defaults to 0.70

rehash (A* self, size_t bucket_count)

reserves at least the specified number of buckets. This regenerates the hash table.

reserve (A* self, size_t desired_size)

reserves space for at least the specified number of elements. This regenerates the hash table.

Non-member functions

swap (A* self)

specializes the swap algorithm

remove_if (A* self, int T_match(T*))

Removes all elements satisfying specific criteria.

erase_if (A* self, int T_match(T*))

erases all elements satisfying specific criteria (C++20)

intersection (A* self, A* other)

union (A* self, A* other)

difference (A* self, A* other)

symmetric_difference (A* self, A* other)