This file contains the hash_set, hash_map, and array_map data structures. It also defines the default_hash function, which provides a default hash algorithm (currently implemented using xxhash).

Classes, functions, and variables in this file
#defineRESIZE_THRESHOLD
#defineRESIZE_THRESHOLD_INVERSE
#defineRESIZE_FACTOR
typedefvoid *(alloc_keys_func)(size_t, size_t)
unsigned intdefault_hash (const K & key)
unsigned intdefault_hash (const K * keys, unsigned int length)
structhash_set_iterator
structhash_map_iterator
structarray_map_iterator
boolindex_between (unsigned int probe, unsigned int start, unsigned int end)
structhash_set
boolhash_set_init (hash_set< T > & set, unsigned int capacity, alloc_keys_func alloc_keys = calloc)
voidswap (hash_set< T > & first, hash_set< T > & second)
structhash_map
boolhash_map_init (hash_map< K, V > & map, unsigned int capacity, alloc_keys_func alloc_keys = calloc)
voidswap (hash_map< K, V > & first, hash_map< K, V > & second)
structarray_map
boolarray_map_init (array_map< K, V > & map, unsigned int initial_capacity)
unsigned intsize (const hash_set< T > & set)
unsigned intsize (const hash_map< K, V > & map)
unsigned intsize (const array_map< K, V > & map)
const MapType::key_type **invert (const MapType & map)
#define RESIZE_THRESHOLD 1 / 2

For hash_set and hash_map, capacity is the size of the underlying array (i.e. the number of buckets), whereas size is the number of elements (i.e. number of non-empty buckets). The functions hash_set::check_size and hash_map::check_size compute the load factor size / capacity and compare it to RESIZE_THRESHOLD. If the load factor is too large, the hashtable is resized and the capacity is increased.

#define RESIZE_THRESHOLD_INVERSE 2 / 1

The multiplicative inverse of RESIZE_THRESHOLD.

#define RESIZE_FACTOR 2

The multiplicative factor by which hash_set, hash_map, and array_map capacity is changed.

typedef void *(alloc_keys_func)(size_t, size_t)

A function pointer type describing a function that returns a pointer to allocated memory. The first argument is the number of elements to allocate, and the second argument is the number of bytes for each element. calloc is an example of a function with this type.

template<typename K>
unsigned int default_hash(
const K &key)

Evaluates the hash function of the given value key using the default implementation.

template<typename K>
unsigned int default_hash(
const K *keys,
unsigned intlength)

Evaluates the hash function of the given native array of values keys using the default implementation.

struct hash_set_iterator

template<typename T, bool IsConst>

An iterator implementation, similar to those in the Standard Template Library, to enable iteration of elements in a hash_set. This iterator is typically initialized using hash_set::begin.

This definition enables the use of range-based for loops.

Public members
booloperator != (const hash_set_iterator< T, IsConst > & other) const
value_typeoperator * ()
const hash_set_iterator< T, IsConst > &operator ++ ()
typedefstd::conditional< IsConst, const T &, T & >::type value_type
bool hash_set_iterator::operator != (
const hash_set_iterator< T, IsConst > &other) const

Returns whether this iterator is in the same position as other. This function assumes the two iterators were created from the same hash_set, and that it was not modified.

value_type hash_set_iterator::operator * ()

Returns the element in the hash_set at the current iterator position. This function assumes the hash_set was not resized and no element was removed since the last call to either the operator ++ or the constructor of this iterator, whichever came later.

const hash_set_iterator< T, IsConst > & hash_set_iterator::operator ++ ()

Advances the position of the iterator to the next element in the hash_set.

typedef std::conditional< IsConst, const T &, T & >::type hash_set_iterator::value_type

The type of the entries returned by this iterator. If this is a const iterator, value_type is const T&. Otherwise, value_type is T&.

struct hash_map_iterator

template<typename K, typename V, bool IsConst>

An iterator implementation, similar to those in the Standard Template Library, to enable iteration of elements in a hash_map. This iterator is typically initialized using hash_map::begin.

This definition enables the use of range-based for loops.

Public members
booloperator != (const hash_map_iterator< K, V, IsConst > & other) const
value_typeoperator * ()
const hash_map_iterator< K, V, IsConst > &operator ++ ()
typedefstd::conditional< IsConst, pair< const K &, const V & >, pair< K &, V & > >::type value_type
bool hash_map_iterator::operator != (
const hash_map_iterator< K, V, IsConst > &other) const

Returns whether this iterator is in the same position as other. This function assumes the two iterators were created from the same hash_map, and that it was not modified.

value_type hash_map_iterator::operator * ()

Returns the entry in the hash_map at the current iterator position. This function assumes the hash_map was not resized and no element was removed since the last call to either the operator ++ or the constructor of this iterator, whichever came later.

const hash_map_iterator< K, V, IsConst > & hash_map_iterator::operator ++ ()

Advances the position of the iterator to the next entry in the hash_map.

typedef std::conditional< IsConst, pair< const K &, const V & >, pair< K &, V & > >::type hash_map_iterator::value_type

The type of the entries returned by this iterator. If this is a const iterator, value_type is core::pair<const K&, constV&>. Otherwise, value_type is core::pair<K&, V&>.

struct array_map_iterator

template<typename K, typename V, bool IsConst>

An iterator implementation, similar to those in the Standard Template Library, to enable iteration of elements in an array_map. This iterator is typically initialized using array_map::begin.

This definition enables the use of range-based for loops.

Public members
booloperator != (const array_map_iterator< K, V, IsConst > & other) const
value_typeoperator * ()
const array_map_iterator< K, V, IsConst > &operator ++ ()
typedefstd::conditional< IsConst, pair< const K &, const V & >, pair< K &, V & > >::type value_type
bool array_map_iterator::operator != (
const array_map_iterator< K, V, IsConst > &other) const

Returns whether this iterator is in the same position as other. This function assumes the two iterators were created from the same array_map, and that it was not modified.

value_type array_map_iterator::operator * ()

Returns the entry in the array_map at the current iterator position. This function assumes the array_map was not resized and no element was removed since the last call to either the operator ++ or the constructor of this iterator, whichever came later.

const array_map_iterator< K, V, IsConst > & array_map_iterator::operator ++ ()

Advances the position of the iterator to the next entry in the array_map.

typedef std::conditional< IsConst, pair< const K &, const V & >, pair< K &, V & > >::type array_map_iterator::value_type

The type of the entries returned by this iterator. If this is a const iterator, value_type is core::pair<const K&, constV&>. Otherwise, value_type is core::pair<K&, V&>.

bool index_between(
unsigned intprobe,
unsigned intstart,
unsigned intend)

Returns true only if probe > start and probe <= end where probe, start, and end are in the additive group of integers modulo the capacity of this set.

struct hash_set

template<typename T>

An unordered associative container that contains a set of unique elements, each of type T. The elements are stored in the native array hash_set::keys, which has capacity hash_set::capacity. To compute the index of an element in hash_set::keys, we first compute its hash. To do so:

  1. If T is_pointer, is_fundamental, or is_enum, core::default_hash() provides the hash.

  2. For all other types, the T::hash function provides the hash. Once the hash is computed, the index into hash_set::keys is computed using hash % hash_set::capacity (modular division by the capacity).

The above approach could produce the same index for distinct elements. This event is known as a collision. We use linear probing to resolve collisions: When adding an element to the hash_set, we compute its index using the above procedure, then we inspect hash_set::keys[index] and use core::is_empty() to determine if another element already occupies that position. If so, we try the next position (index + 1) % hash_set::capacity. We continue until we find an empty index, and the element is inserted there.

Thus, the function core::is_empty() is used to determine if a position in hash_set::keys is occupied or empty. The total number of occupied positions is given by hash_set::size. WARNING: If hash_set::keys becomes full, the above linear probing mechanism could lead to an infinite loop. The function hash_set::check_size should be used whenever adding new elements to avoid this scenario.

Performance: This data structure provides constant-time access and modification, given that the load factor (size / capacity) is not too large.

Below is an example of a simple use-case of hash_set, where the expected output is a.contains(2): false, a.contains(3): true, -4 9 3.

#include <core/map.h>
#include <stdio.h>
using namespace core;

int main() {
    hash_set<int> a = hash_set<int>(8);
    a.add(-1); a.add(-4);
    a.add(3); a.add(9);
    a.remove(-1);

    printf("a.contains(2): %s, ", a.contains(2) ? "true" : "false");
    printf("a.contains(3): %s, ", a.contains(3) ? "true" : "false");
    for (int element : a)
        printf("%d ", element);
}

However, if a is not allocated on the stack, the destructor will not be automatically called, and so it must be freed manually using core::free or hash_set::free. In the example below, the expected output is the same as that of the program above: a.contains(2): false, a.contains(3): true, -4 9 3.

#include <core/map.h>
#include <stdio.h>
using namespace core;

int main() {
    hash_set<int>& a = *((hash_set<int>*) alloca(sizeof(hash_set<int>)));
    hash_set_init(a, 8);
    a.add(-1); a.add(-4);
    a.add(3); a.add(9);
    a.remove(-1);

    printf("a.contains(2): %s, ", a.contains(2) ? "true" : "false");
    printf("a.contains(3): %s, ", a.contains(3) ? "true" : "false");
    for (int element : a)
        printf("%d ", element);
    free(a);
}

A number of member functions require T to be CopyAssignable. If this is not the case, those operations can be performed directly on the public fields, as in the following example. In addition, when using a custom struct/class with hash_set, it must implement public static functions, like hash, is_empty, and move, as well as the operator ==. The expected output of the following example is first second.

#include <core/map.h>
#include <stdio.h>
#include <string.h>
using namespace core;

struct custom_string {
    char* buffer;

    static unsigned int hash(const custom_string& s) {
        return default_hash(s.buffer, strlen(s.buffer));
    }

    static bool is_empty(const custom_string& s) {
        return s.buffer == NULL;
    }

    static void move(const custom_string& src, custom_string& dst) {
        dst.buffer = src.buffer;
    }

    static void free(custom_string& s) {
        core::free(s.buffer);
    }
};

inline bool operator == (const custom_string& first, const custom_string& second) {
    if (first.buffer == NULL)
        return second.buffer == NULL;
    return strcmp(first.buffer, second.buffer) == 0;
}

bool init(custom_string& s, const char* src) {
    s.buffer = (char*) malloc(sizeof(char) * (strlen(src) + 1));
    if (s.buffer == NULL)
        return false;
    memcpy(s.buffer, src, sizeof(char) * (strlen(src) + 1));
    return true;
}

int main() {
    custom_string first, second;
    init(first, "first");
    init(second, "second");

    hash_set<custom_string> a = hash_set<custom_string>(8);
    a.check_size(a.size + 2);

    bool contains; unsigned int index;
    index = a.index_of(first, contains);
    if (!contains) {
        core::move(first, a.keys[index]);
        a.size++;
    }

    index = a.index_of(second, contains);
    if (!contains) {
        core::move(second, a.keys[index]);
        a.size++;
    }

    for (const custom_string& s : a)
        printf("%s ", s.buffer);
    for (custom_string& s : a)
        free(s);
}

Template parameters
T

the generic type of the elements in the set. T must satisfy either:

  1. is_fundamental,

  2. is_enum,

  3. is_pointer,

  4. implements the public static method unsigned int hash(const T&), the public static method void is_empty(const T&), implements the operators ==, and satisfies is_moveable. Some operations also require the operator !=, and public static methods void set_empty(T&) and void set_empty(T*, unsigned int). NOTE: The first argument to the == and != operators may be empty.

Public members
T *keys
unsigned intcapacity
unsigned intsize
hash_set (unsigned int initial_capacity, alloc_keys_func alloc_keys = calloc)
hash_set (const T * set, unsigned int length, alloc_keys_func alloc_keys = calloc)
hash_set (const std::initializer_list< T > & list, alloc_keys_func alloc_keys = calloc)
boolresize (unsigned int new_capacity, alloc_keys_func alloc_keys = calloc)
boolcheck_size (alloc_keys_func alloc_keys = calloc)
boolcheck_size (unsigned int new_size, alloc_keys_func alloc_keys = calloc)
booladd (const T & element, alloc_keys_func alloc_keys = calloc)
booladd_all (const hash_set< T > & elements, alloc_keys_func alloc_keys = calloc)
booladd_all (const T * elements, unsigned int count, alloc_keys_func alloc_keys = calloc)
boolremove (const T & element)
voidremove_at (unsigned int index, unsigned int hash_value)
boolcontains (const T & element) const
unsigned intindex_of (const T & element) const
unsigned intindex_of (const T & element, bool & contains) const
unsigned intindex_of (const T & element, bool & contains, unsigned int & hash_value) const
unsigned intindex_to_insert (const T & element)
voidclear ()
boolis_subset (const hash_set< T > & other) const
hash_set_iterator< T, false >begin ()
hash_set_iterator< T, false >end ()
hash_set_iterator< T, true >begin () const
hash_set_iterator< T, true >end () const
static voidswap (hash_set< T > & first, hash_set< T > & second)
static voidmove (const hash_set< T > & src, hash_set< T > & dst)
static boolcopy (const hash_set< T > & src, hash_set< T > & dst, alloc_keys_func alloc_keys = calloc)
static voidfree (hash_set< T > & set)
T * hash_set::keys

The native array of keys underlying the hashtable.

unsigned int hash_set::capacity

The capacity of hash_set::keys.

unsigned int hash_set::size

The number of elements in the hashtable (i.e. the number of non-empty buckets).

hash_set::hash_set(
unsigned intinitial_capacity,
alloc_keys_funcalloc_keys = calloc)

Constructs the hash_set with the given initial_capacity.

Parameters
alloc_keys

a memory allocation function with prototype void* alloc_keys(size_t count, size_t size) that allocates space for count items, each with size size, and initializes them such that core::is_empty() returns true for each element.

hash_set::hash_set(
const T *set,
unsigned intlength,
alloc_keys_funcalloc_keys = calloc)

Constructs the hash_set and inserts the given native array of elements set with given length.

Parameters
alloc_keys

a memory allocation function with prototype void* alloc_keys(size_t count, size_t size) that allocates space for count items, each with size size, and initializes them such that core::is_empty() returns true for each element.

hash_set::hash_set(
const std::initializer_list< T > &list,
alloc_keys_funcalloc_keys = calloc)

Constructs the hash_set and inserts the given initializer_list of elements list.

Parameters
alloc_keys

a memory allocation function with prototype void* alloc_keys(size_t count, size_t size) that allocates space for count items, each with size size, and initializes them such that core::is_empty() returns true for each element.

bool hash_set::resize(
unsigned intnew_capacity,
alloc_keys_funcalloc_keys = calloc)

Forces the underlying hash_set::keys to be resized to the requested capacity.

WARNING: If new_capacity <= hash_set::size, the hashtable could become full during the resize process, leading to an infinite loop due to the linear probing collision resolution mechanism.

Parameters
alloc_keys

a memory allocation function with prototype void* alloc_keys(size_t count, size_t size) that allocates space for count items, each with size size, and initializes them such that core::is_empty() returns true for each element.

bool hash_set::check_size(
alloc_keys_funcalloc_keys = calloc)

This function first determines whether hash_set::size < hash_set::capacity * RESIZE_THRESHOLD. If not, the capacity of the underlying hash_set::keys is increased by RESIZE_FACTOR until the condition is satisfied. This is useful to ensure the hashtable is sufficiently large when preparing to add new elements.

Parameters
alloc_keys

a memory allocation function with prototype void* alloc_keys(size_t count, size_t size) that allocates space for count items, each with size size, and initializes them such that core::is_empty() returns true for each element.

Returns

true if the resize was successful, and false if there is insufficient memory.

bool hash_set::check_size(
unsigned intnew_size,
alloc_keys_funcalloc_keys = calloc)

For a requested number of elements new_size, this function first determines whether new_size < hash_set::capacity * RESIZE_THRESHOLD. If not, the capacity of the underlying hashtable is increased by RESIZE_FACTOR until the condition is satisfied. This is useful to ensure the hashtable is sufficiently large when preparing to add new elements.

Parameters
alloc_keys

a memory allocation function with prototype void* alloc_keys(size_t count, size_t size) that allocates space for count items, each with size size, and initializes them such that core::is_empty() returns true for each element.

Returns

true if the resize was successful, and false if there is insufficient memory.

bool hash_set::add(
const T &element,
alloc_keys_funcalloc_keys = calloc)

Add the given element to this set. The assignment operator is used to insert each element, and so this function should not be used if T is not CopyAssignable. In such a case, insertion should be performed manually using hash_set::index_of to find the appropriate index and directly modifying hash_set::keys and hash_set::size. See the example in the hash_set description.

Parameters
alloc_keys

a memory allocation function with prototype void* alloc_keys(size_t count, size_t size) that allocates space for count items, each with size size, and initializes them such that core::is_empty() returns true for each element.

Template parameters
T

is CopyAssignable.

bool hash_set::add_all(
const hash_set< T > &elements,
alloc_keys_funcalloc_keys = calloc)

Adds all the elements in the hash_set elements to this set. The assignment operator is used to insert each element, and so this function should not be used if T is not CopyAssignable. In such a case, insertion should be performed manually using hash_set::index_of or hash_set::index_to_insert to find the appropriate index and directly modifying hash_set::keys and hash_set::size. See the example in the hash_set description.

Parameters
alloc_keys

a memory allocation function with prototype void* alloc_keys(size_t count, size_t size) that allocates space for count items, each with size size, and initializes them such that core::is_empty() returns true for each element.

Template parameters
T

is CopyAssignable.

bool hash_set::add_all(
const T *elements,
unsigned intcount,
alloc_keys_funcalloc_keys = calloc)

Adds all the elements in the native array elements with length count to this set. The assignment operator is used to insert each element, and so this function should not be used if T is not CopyAssignable. In such a case, insertion should be performed manually using hash_set::index_of or hash_set::index_to_insert and direct modification of the public fields.

Parameters
alloc_keys

a memory allocation function with prototype void* alloc_keys(size_t count, size_t size) that allocates space for count items, each with size size, and initializes them such that core::is_empty() returns true for each element.

Template parameters
T

is CopyAssignable.

bool hash_set::remove(
const T &element)

This function removes the given element from the set. This function does not free the removed element.

Returns

true if the element is removed, and false if the set does not contain element.

void hash_set::remove_at(
unsigned intindex,
unsigned inthash_value)

This function removes the element at the bucket given by index whose hash value is hash_value. This function assumes that an element is located at the given bucket with the correct provided hash value. This function does not free the removed element.

bool hash_set::contains(
const T &element) const

Returns true if element exists in the set, and false otherwise.

unsigned int hash_set::index_of(
const T &element) const

If the given element exists in this set, this function returns the index of the bucket that contains it. If not, this function returns the index where the key would be located, if it had existed in the set.

unsigned int hash_set::index_of(
const T &element,
bool &contains) const

If the given element exists in this set, this function returns the index of the bucket that contains it, and sets contains to true. If element is not in the set, contains is set to false, and this function returns the index where the key would be located, if it had existed in the set.

unsigned int hash_set::index_of(
const T &element,
bool &contains,
unsigned int &hash_value) const

If the given element exists in this set, this function returns the index of the bucket that contains it, and sets contains to true. If element is not in the set, contains is set to false, and this function returns the index where the key would be located, if it had existed in the set. In any case, the evaluated hash function of element is stored in hash_value.

unsigned int hash_set::index_to_insert(
const T &element)

For a given element, this function computes and returns the index of the bucket where the element would be inserted, for example by a call to hash_set::add, assuming element does not already exist in the set.

void hash_set::clear()

Removes all elements from this hash_set. Note that this function does not free each element beforehand.

bool hash_set::is_subset(
const hash_set< T > &other) const

Returns true if this hash_set is a subset of other.

hash_set_iterator< T, false > hash_set::begin()

Returns a hash_set_iterator pointing to the first element in this container.

NOTE: Unlike the libstdc++ unordered_set and unordered_map iterators, we do not keep a linked list among the elements, so if rapid iteration over elements is more critical than rapid queries, consider using an array_map.

hash_set_iterator< T, false > hash_set::end()

Returns a hash_set_iterator pointing to the end of this container.

NOTE: Unlike the libstdc++ unordered_set and unordered_map iterators, we do not keep a linked list among the elements, so if rapid iteration over elements is more critical than rapid queries, consider using an array_map.

hash_set_iterator< T, true > hash_set::begin()

Returns a const hash_set_iterator pointing to the first element in this container.

NOTE: Unlike the libstdc++ unordered_set and unordered_map iterators, we do not keep a linked list among the elements, so if rapid iteration over elements is more critical than rapid queries, consider using an array_map.

hash_set_iterator< T, true > hash_set::end()

Returns a const hash_set_iterator pointing to the end of this container.

NOTE: Unlike the libstdc++ unordered_set and unordered_map iterators, we do not keep a linked list among the elements, so if rapid iteration over elements is more critical than rapid queries, consider using an array_map.

static void hash_set::swap(
hash_set< T > &first,
hash_set< T > &second)

Swaps the contents of the hash_set first with that of second.

static void hash_set::move(
const hash_set< T > &src,
hash_set< T > &dst)

Moves the contents of the hash_set src into dst. Note this function does not copy the contents of the underlying hash_set::keys, it merely copies the pointer.

static bool hash_set::copy(
const hash_set< T > &src,
hash_set< T > &dst,
alloc_keys_funcalloc_keys = calloc)

Copies the contents of the hash_set src into dst.

Parameters
alloc_keys

a memory allocation function with prototype void* alloc_keys(size_t count, size_t size) that allocates space for count items, each with size size, and initializes them such that core::is_empty() returns true for each element.

static void hash_set::free(
hash_set< T > &set)

Frees hash_set::keys. This should not be used if set was constructed on the stack, as the destructor will automatically free hash_set::data. The elements of set are not freed.

template<typename T>
bool hash_set_init(
hash_set< T > &set,
unsigned intcapacity,
alloc_keys_funcalloc_keys = calloc)

Initializes the hash_set set with the given initial capacity.

Parameters
alloc_keys

a memory allocation function with prototype void* alloc_keys(size_t count, size_t size) that allocates space for count items, each with size size, and initializes them such that core::is_empty() returns true for each element.

template<typename T>
void swap(
hash_set< T > &first,
hash_set< T > &second)

Swaps the underlying buffers of the given hash_sets first and second.

struct hash_map

template<typename K, typename V>

An unordered associative container that contains a set of key-value pairs, where the keys are unique and have type K and the values have type V. The keys are stored in a hash_set structure, and the values are stored in hash_map::values, which is a native array parallel to the key array in hash_set::keys. To compute the index of a key-value pair, we compute the index of the key using the algorithm described in hash_set. The value has the same index in hash_map::values. This structure uses the same linear probing approach to resolve collisions (i.e. when two distinct keys are computed to have the same index).

WARNING: As with hash_set, if the map becomes full, the linear probing mechanism could lead to an infinite loop in many hash_map operations. The function hash_map::check_size should be used whenever adding new elements to avoid this scenario.

Performance: This data structure provides constant-time access and modification, given that the load factor (size / capacity) is not too large.

Below is a simple example using a hash_map, where the expected output is a.get(3): c, a.get(4): d, 1:a 4:d 3:c.

#include <core/map.h>
#include <stdio.h>
using namespace core;

int main() {
    hash_map<int, char> a = hash_map<int, char>(8);
    a.put(1, 'a'); a.put(2, 'b');
    a.put(3, 'c'); a.put(4, 'd');
    a.remove(2);

    printf("a.get(3): %c, ", a.get(3));
    printf("a.get(4): %c,  ", a.get(4));
    for (const auto& entry : a)
        printf("%d:%c ", entry.key, entry.value);
}

However, if a is not allocated on the stack, the destructor will not be automatically called, and so it must be freed manually using core::free or hash_map::free. In the example below, the expected output is the same as that of the program above: a.get(3): c, a.get(4): d, 1:a 4:d 3:c.

#include <core/map.h>
#include <stdio.h>
using namespace core;

int main() {
    hash_map<int, char>& a = *((hash_map<int, char>*) malloc(sizeof(hash_map<int, char>)));
    hash_map_init(a, 8);
    a.put(1, 'a'); a.put(2, 'b');
    a.put(3, 'c'); a.put(4, 'd');
    a.remove(2);

    printf("a.get(3): %c, ", a.get(3));
    printf("a.get(4): %c,  ", a.get(4));
    for (const auto& entry : a)
        printf("%d:%c ", entry.key, entry.value);
    free(a);
}

A number of member functions require K and V to be CopyAssignable. If this is not the case, those operations can be performed directly on the public fields, as in the following example. In addition, when using a custom struct/class as the key type in hash_map, it must implement public static functions, like hash, is_empty, and move, as well as the operator ==. The expected output of the following example is first:1 second:2.

#include <core/map.h>
#include <stdio.h>
#include <string.h>
using namespace core;

struct custom_string {
    char* buffer;

    static unsigned int hash(const custom_string& s) {
        return default_hash(s.buffer, strlen(s.buffer));
    }

    static bool is_empty(const custom_string& s) {
        return s.buffer == NULL;
    }

    static void move(const custom_string& src, custom_string& dst) {
        dst.buffer = src.buffer;
    }

    static void free(custom_string& s) {
        core::free(s.buffer);
    }
};

inline bool operator == (const custom_string& first, const custom_string& second) {
    if (first.buffer == NULL)
        return second.buffer == NULL;
    return strcmp(first.buffer, second.buffer) == 0;
}

bool init(custom_string& s, const char* src) {
    s.buffer = (char*) malloc(sizeof(char) * (strlen(src) + 1));
    if (s.buffer == NULL)
        return false;
    memcpy(s.buffer, src, sizeof(char) * (strlen(src) + 1));
    return true;
}

int main() {
    custom_string key_one, key_two;
    int value_one = 1, value_two = 2;
    init(key_one, "first");
    init(key_two, "second");

    hash_map<custom_string, int> a = hash_map<custom_string, int>(8);
    a.check_size(a.table.size + 2);

    bool contains; unsigned int index;
    a.get(key_one, contains, index);
    if (!contains) {
        core::move(key_one, a.table.keys[index]);
        a.values[index] = value_one;
        a.table.size++;
    }

    a.get(key_two, contains, index);
    if (!contains) {
        core::move(key_two, a.table.keys[index]);
        a.values[index] = value_two;
        a.table.size++;
    }

    for (const auto& entry : a)
        printf("%s:%d ", entry.key.buffer, entry.value);
    for (auto entry : a)
        free(entry.key);
}

Template parameters
K

the generic type of the keys in the map. K must satisfy either:

  1. is_fundamental,

  2. is_enum,

  3. is_pointer,

  4. implements the public static method unsigned int hash(const T&), the public static method void is_empty(const T&), implements the operators ==, and satisfies is_moveable. Some operations also require the operator !=, and public static methods void set_empty(T&) and void set_empty(T*, unsigned int). NOTE: The first argument to the == and != operators may be empty.

V

the generic type of the values in the map. V must satisfy is_moveable.

Public members
hash_set< K >table
V *values
hash_map (unsigned int capacity, alloc_keys_func alloc_keys = calloc)
hash_map (const K * map, unsigned int length, alloc_keys_func alloc_keys = calloc)
hash_map (const K * keys, const V * values, unsigned int length, alloc_keys_func alloc_keys = calloc)
hash_map (const std::initializer_list< pair< K, V >> & list, alloc_keys_func alloc_keys = calloc)
boolresize (unsigned int new_capacity, alloc_keys_func alloc_keys = calloc)
boolcheck_size (alloc_keys_func alloc_keys = calloc)
boolcheck_size (unsigned int new_size, alloc_keys_func alloc_keys = calloc)
boolput (const K & key, const V & value, alloc_keys_func alloc_keys = calloc)
boolput_all (const hash_map< K, V > & elements, alloc_keys_func alloc_keys = calloc)
boolremove (const K & key)
voidremove_at (unsigned int index, unsigned int hash_value)
V &get (const K & key) const
V &get (const K & key, bool & contains) const
V &get (const K & key, bool & contains, unsigned int & index) const
V &get (const K & key, bool & contains, unsigned int & index, unsigned int & hash_value) const
voidclear ()
hash_map_iterator< K, V, false >begin ()
hash_map_iterator< K, V, false >end ()
hash_map_iterator< K, V, true >begin () const
hash_map_iterator< K, V, true >end () const
static voidswap (hash_map< K, V > & first, hash_map< K, V > & second)
static voidmove (const hash_map< K, V > & src, hash_map< K, V > & dst)
static boolcopy (const hash_map< K, V > & src, hash_map< K, V > & dst, alloc_keys_func alloc_keys = calloc)
static voidfree (hash_map< K, V > & map)
typedefK key_type
typedefV value_type
hash_set< K > hash_map::table

The underlying hashtable containing the keys.

V * hash_map::values

An array parallel to hash_set::keys in hash_map::table, containing a value at every non-empty bucket index.

hash_map::hash_map(
unsigned intcapacity,
alloc_keys_funcalloc_keys = calloc)

Constructs the hash_map with the given initial capacity.

Parameters
alloc_keys

a memory allocation function with prototype void* alloc_keys(size_t count, size_t size) that allocates space for count items, each with size size, and initializes them such that core::is_empty() returns true for each key.

hash_map::hash_map(
const K *map,
unsigned intlength,
alloc_keys_funcalloc_keys = calloc)

Constructs the hash_map and inserts the array of keys map, where each element in map is interpreted as a key, and its corresponding value is the index of the element.

Parameters
alloc_keys

a memory allocation function with prototype void* alloc_keys(size_t count, size_t size) that allocates space for count items, each with size size, and initializes them such that core::is_empty() returns true for each key.

Template parameters
V

satisfies is_integral.

hash_map::hash_map(
const K *keys,
const V *values,
unsigned intlength,
alloc_keys_funcalloc_keys = calloc)

Constructs the hash_map and inserts the list of key-value pairs given by the native arrays keys and values.

Parameters
alloc_keys

a memory allocation function with prototype void* alloc_keys(size_t count, size_t size) that allocates space for count items, each with size size, and initializes them such that core::is_empty() returns true for each key.

hash_map::hash_map(
const std::initializer_list< pair< K, V >> &list,
alloc_keys_funcalloc_keys = calloc)

Constructs the hash_map and inserts the given initializer_list of core::pair entries.

Parameters
alloc_keys

a memory allocation function with prototype void* alloc_keys(size_t count, size_t size) that allocates space for count items, each with size size, and initializes them such that core::is_empty() returns true for each key.

bool hash_map::resize(
unsigned intnew_capacity,
alloc_keys_funcalloc_keys = calloc)

Forces the underlying hash_map::table.keys and hash_map::values to be resized to the requested capacity.

WARNING: If new_capacity <= hash_map::table.size, the hashtable could become full during the resize process, leading to an infinite loop due to the linear probing collision resolution mechanism.

Parameters
alloc_keys

a memory allocation function with prototype void* alloc_keys(size_t count, size_t size) that allocates space for count items, each with size size, and initializes them such that core::is_empty() returns true for each key.

bool hash_map::check_size(
alloc_keys_funcalloc_keys = calloc)

This function first determines whether hash_map::table.size < hash_map::table.capacity * RESIZE_THRESHOLD. If not, the capacities of the underlying hash_map::table and hash_map::values is increased by RESIZE_FACTOR until the condition is satisfied. This is useful to ensure the hashtable is sufficiently large when preparing to add new elements.

Parameters
alloc_keys

a memory allocation function with prototype void* alloc_keys(size_t count, size_t size) that allocates space for count items, each with size size, and initializes them such that core::is_empty() returns true for each key.

Returns

true if the resize was successful, and false if there is insufficient memory.

bool hash_map::check_size(
unsigned intnew_size,
alloc_keys_funcalloc_keys = calloc)

For a requested number of elements new_size, this function first determines whether new_size < hash_map::table.capacity * RESIZE_THRESHOLD. If not, the capacities of the underlying hash_map::table and hash_map::values is increased by RESIZE_FACTOR until the condition is satisfied. This is useful to ensure the hashtable is sufficiently large when preparing to add new elements.

Parameters
alloc_keys

a memory allocation function with prototype void* alloc_keys(size_t count, size_t size) that allocates space for count items, each with size size, and initializes them such that core::is_empty() returns true for each key.

Returns

true if the resize was successful, and false if there is insufficient memory.

bool hash_map::put(
const K &key,
const V &value,
alloc_keys_funcalloc_keys = calloc)

Adds the given key-value pair to this map. The assignment operator is used insert the entry, and so this function should not be used if K and V are not CopyAssignable. In such a case, insertion should be performed manually by using hash_map::get or hash_set::index_to_insert to find the appropriate index and directly modifying hash_map::table.keys, hash_map::table.size, and hash_map::values. See the example in the hash_map description.

Parameters
alloc_keys

a memory allocation function with prototype void* alloc_keys(size_t count, size_t size) that allocates space for count items, each with size size, and initializes them such that core::is_empty() returns true for each key.

Template parameters
K

is CopyAssignable.

V

is CopyAssignable.

bool hash_map::put_all(
const hash_map< K, V > &elements,
alloc_keys_funcalloc_keys = calloc)

Adds the given key-value pairs in elements to this map. The assignment operator is used insert each entry, and so this function should not be used if K and V are not CopyAssignable. In such a case, insertion should be performed manually by using hash_map::get or hash_map::index_to_insert to find the appropriate index and directly modifying hash_map::table.keys, hash_map::table.size, and hash_map::values. See the example in the hash_map description.

Parameters
alloc_keys

a memory allocation function with prototype void* alloc_keys(size_t count, size_t size) that allocates space for count items, each with size size, and initializes them such that core::is_empty() returns true for each key.

Template parameters
K

is CopyAssignable.

V

is CopyAssignable.

bool hash_map::remove(
const K &key)

This function removes key and associated value from the map. This function does not free the removed element.

Returns

true if the element is removed, and false if the set does not contain element.

void hash_map::remove_at(
unsigned intindex,
unsigned inthash_value)

This function removes the entry at the bucket given by index whose hash value is hash_value. This function assumes that an entry is located at the given bucket with the correct provided hash value. This function does not free the removed key or value.

V & hash_map::get(
const K &key) const

Retrieves the value associated with the given key. This function assumes the given key exists in the map.

V & hash_map::get(
const K &key,
bool &contains) const

If the given key exists in this map, this function returns the value associated with the key, and sets contains to true. If key is not in the map, contains is set to false.

V & hash_map::get(
const K &key,
bool &contains,
unsigned int &index) const

If the given key exists in this map, this function returns the value associated with the key, sets contains to true, and sets index to the bucket containing the key. If key is not in the map, contains is set to false, and index is set to the index where the key would be located, if it had existed in the map.

V & hash_map::get(
const K &key,
bool &contains,
unsigned int &index,
unsigned int &hash_value) const

If the given key exists in this map, this function returns the value associated with the key, sets contains to true, and sets index to the bucket containing the key. If key is not in the map, contains is set to false, and index is set to the index where the key would be located, if it had existed in the map. In any case, the evaluated hash function of key is stored in hash_value.

void hash_map::clear()

Removes all entries from this hash_map. Note that this function does not free each entry beforehand.

hash_map_iterator< K, V, false > hash_map::begin()

Returns a hash_map_iterator pointing to the first entry in this container.

NOTE: Unlike the libstdc++ unordered_set and unordered_map iterators, we do not keep a linked list among the elements, so if rapid iteration over elements is more critical than rapid queries, consider using an array_map.

hash_map_iterator< K, V, false > hash_map::end()

Returns a hash_map_iterator pointing to the end of this container.

NOTE: Unlike the libstdc++ unordered_set and unordered_map iterators, we do not keep a linked list among the elements, so if rapid iteration over elements is more critical than rapid queries, consider using an array_map.

hash_map_iterator< K, V, true > hash_map::begin()

Returns a const hash_map_iterator pointing to the first entry in this container.

NOTE: Unlike the libstdc++ unordered_set and unordered_map iterators, we do not keep a linked list among the elements, so if rapid iteration over elements is more critical than rapid queries, consider using an array_map.

hash_map_iterator< K, V, true > hash_map::end()

Returns a const hash_map_iterator pointing to the end of this container.

NOTE: Unlike the libstdc++ unordered_set and unordered_map iterators, we do not keep a linked list among the elements, so if rapid iteration over elements is more critical than rapid queries, consider using an array_map.

static void hash_map::swap(
hash_map< K, V > &first,
hash_map< K, V > &second)

Swaps the contents of the hash_map first with that of second.

static void hash_map::move(
const hash_map< K, V > &src,
hash_map< K, V > &dst)

Moves the contents of the hash_map src into dst. Note this function does not copy the contents of the underlying hash_map::table or hash_map::values, it merely copies the pointers.

static bool hash_map::copy(
const hash_map< K, V > &src,
hash_map< K, V > &dst,
alloc_keys_funcalloc_keys = calloc)

Copies the contents of the hash_map src into dst.

Parameters
alloc_keys

a memory allocation function with prototype void* alloc_keys(size_t count, size_t size) that allocates space for count items, each with size size, and initializes them such that core::is_empty() returns true for each key.

static void hash_map::free(
hash_map< K, V > &map)

Frees hash_map::table and hash_map::values. This should not be used if map was constructed on the stack, as the destructor will automatically free hash_map::table and hash_map::values. The existing entries of map are not freed.

typedef K hash_map::key_type

The type of the keys in this hash_map.

typedef V hash_map::value_type

The type of the values in this hash_map.

template<typename K, typename V>
bool hash_map_init(
hash_map< K, V > &map,
unsigned intcapacity,
alloc_keys_funcalloc_keys = calloc)

Initializes the hash_map map with the given initial capacity.

Parameters
alloc_keys

a memory allocation function with prototype void* alloc_keys(size_t count, size_t size) that allocates space for count items, each with size size, and initializes them such that core::is_empty() returns true for each key.

template<typename K, typename V>
void swap(
hash_map< K, V > &first,
hash_map< K, V > &second)

Swaps the underlying buffers of the given hash_maps first and second.

struct array_map

template<typename K, typename V>

A sequentially-ordered associative container that contains a set of key-value pairs, where the keys are unique and have type K and the values have type V. The keys are stored sequentially in a native array array_map::keys, and the values are stored sequentially in a parallel native array array_map::values.

When inserting a key-value pair into an array_map, a linear search is performed to determine if the key already exists in the map. If so, its corresponding value is replaced by the new value. If not, the new key and value are inserted at the ends of their respective arrays, and array_map::size is incremented.

Performance: This data structure provides linear-time access and modification. However, due to locality of reference, this data structure may perform operations more quickly than hash_map if the size of the map is small.

A simple example of the use of array_map is given below, where the expected output is a.get(3): c, a.get(4): d, 1:a 4:d 3:c.

#include <core/map.h>
#include <stdio.h>
using namespace core;

int main() {
    array_map<int, char> a = array_map<int, char>(8);
    a.put(1, 'a'); a.put(2, 'b');
    a.put(3, 'c'); a.put(4, 'd');
    a.remove(2);

    printf("a.get(3): %c, ", a.get(3));
    printf("a.get(4): %c,  ", a.get(4));
    for (const auto& entry : a)
        printf("%d:%c ", entry.key, entry.value);
}

However, if a is not allocated on the stack, the destructor will not be automatically called, and so it must be freed using core::free or hash_map::free. In the example below, the expected output is the same as that of the program above: a.get(3): c, a.get(4): d, 1:a 4:d 3:c.

#include <core/map.h>
#include <stdio.h>
using namespace core;

int main() {
    array_map<int, char>& a = *((array_map<int, char>*) alloca(sizeof(array_map<int, char>)));
    array_map_init(a, 8);
    a.put(1, 'a'); a.put(2, 'b');
    a.put(3, 'c'); a.put(4, 'd');
    a.remove(2);

    printf("a.get(3): %c, ", a.get(3));
    printf("a.get(4): %c,  ", a.get(4));
    for (const auto& entry : a)
        printf("%d:%c ", entry.key, entry.value);
    free(a);
}

A number of member functions require K and V to be CopyAssignable. If this is not the case, those operations can be performed directly on the public fields, as in the following example. The expected output is first:1 second:2.

#include <core/map.h>
#include <stdio.h>
#include <string.h>
using namespace core;

struct custom_string {
    char* buffer;

    static void move(const custom_string& src, custom_string& dst) {
        dst.buffer = src.buffer;
    }

    static void free(custom_string& s) {
        core::free(s.buffer);
    }
};

inline bool operator == (const custom_string& first, const custom_string& second) {
    if (first.buffer == NULL)
        return second.buffer == NULL;
    return strcmp(first.buffer, second.buffer) == 0;
}

bool init(custom_string& s, const char* src) {
    s.buffer = (char*) malloc(sizeof(char) * (strlen(src) + 1));
    if (s.buffer == NULL)
        return false;
    memcpy(s.buffer, src, sizeof(char) * (strlen(src) + 1));
    return true;
}

int main() {
    custom_string key_one, key_two;
    int value_one = 1, value_two = 2;
    init(key_one, "first");
    init(key_two, "second");

    array_map<custom_string, int> a = array_map<custom_string, int>(8);
    a.ensure_capacity(2);

    unsigned int index;
    a.get(key_one, index);
    if (index == a.size) {
        core::move(key_one, a.keys[index]);
        a.values[index] = value_one;
        a.size++;
    }

    a.get(key_two, index);
    if (index == a.size) {
        core::move(key_two, a.keys[index]);
        a.values[index] = value_two;
        a.size++;
    }

    for (const auto& entry : a)
        printf("%s:%d ", entry.key.buffer, entry.value);
    for (auto entry : a)
        free(entry.key);
}

Public members
K *keys
V *values
size_tcapacity
size_tsize
array_map (unsigned int initial_capacity)
boolensure_capacity (unsigned int new_length)
boolput (const K & key, const V & value)
unsigned intindex_of (const K & key) const
unsigned intindex_of (const K & key, unsigned int start) const
unsigned intlast_index_of (const K & key) const
boolcontains (const K & key) const
V &get (const K & key)
const V &get (const K & key) const
V &get (const K & key, unsigned int & index)
V &get (const K & key, bool & contains)
const V &get (const K & key, bool & contains) const
boolremove (const K & key)
voidremove_at (unsigned int index)
voidclear ()
array_map_iterator< K, V, false >begin ()
array_map_iterator< K, V, false >end ()
array_map_iterator< K, V, true >begin () const
array_map_iterator< K, V, true >end () const
static voidswap (array_map< K, V > & first, array_map< K, V > & second)
static voidmove (const array_map< K, V > & src, array_map< K, V > & dst)
static voidfree (array_map< K, V > & map)
typedefK key_type
typedefV value_type
K * array_map::keys

The native array of keys.

V * array_map::values

The native array of values parallel to array_map::keys.

size_t array_map::capacity

The capacity of array_map::keys and array_map::values.

size_t array_map::size

The number of entries in the array_map.

array_map::array_map(
unsigned intinitial_capacity)

Constructs the hash_map with the given initial_capacity.

bool array_map::ensure_capacity(
unsigned intnew_length)

Given the requested number of elements new_length, this function determines whether array_map::capacity is sufficient. If not, it attempts to increase its capacity by factors of RESIZE_FACTOR.

Returns

true if the resize was successful, and false if there is insufficient memory.

bool array_map::put(
const K &key,
const V &value)

Adds the given key-value pair to this map. The assignment operator is used insert the entry, and so this function should not be used if K and V are not CopyAssignable. In such a case, insertion should be performed manually by using array_map::get to compute the appropriate index and directly modifying the the public fields. See the example in the description of array_map.

Template parameters
K

is CopyAssignable.

V

is CopyAssignable.

unsigned int array_map::index_of(
const K &key) const

Performs a linear search to find the index of the given key. If the key is not in this map, array_map::size is returned.

unsigned int array_map::index_of(
const K &key,
unsigned intstart) const

Performs a linear search to find the index of the given key, with the search beginning at the index start. If the key is not in this map, array_map::size is returned.

unsigned int array_map::last_index_of(
const K &key) const

Performs a reverse linear search to find the index of the given key. If the key is not in this map, static_cast<unsigned int>(-1) is returned.

bool array_map::contains(
const K &key) const

Returns true if the given key exists in the map, and false otherwise.

V & array_map::get(
const K &key)

Retrieves the value associated with the given key. This function assumes the given key exists in the map.

const V & array_map::get(
const K &key) const

Retrieves the const value associated with the given key. This function assumes the given key exists in the map.

V & array_map::get(
const K &key,
unsigned int &index)

If the given key exists in the map, this function returns the value associated with the key, and sets index to the index of array_map::keys where the key is located. If key does not exist in the map, index is set to array_map::size.

V & array_map::get(
const K &key,
bool &contains)

If the given key exists in the map, this function returns the value associated with the key, and sets contains to true. If key does not exist in the map, contains is set to false.

const V & array_map::get(
const K &key,
bool &contains) const

If the given key exists in the map, this function returns the const value associated with the key, and sets contains to true. If key does not exist in the map, contains is set to false.

bool array_map::remove(
const K &key)

This function removes key and associated value from the map. This function does not free the removed element.

Returns

true if the element is removed, and false if the set does not contain element.

void array_map::remove_at(
unsigned intindex)

This function removes the key-value pair located at the given index in the map. This function does not free the removed element. This function assumes 0 <= index < array_map::size.

Template parameters
K

satisfies is_moveable.

V

satisfies is_moveable.

void array_map::clear()

Removes all entries from this array_map. Note that this function does not free each entry beforehand.

array_map_iterator< K, V, false > array_map::begin()

Returns an array_map_iterator pointing to the first entry in this container.

array_map_iterator< K, V, false > array_map::end()

Returns an array_map_iterator pointing to the end of this container.

array_map_iterator< K, V, true > array_map::begin()

Returns a const array_map_iterator pointing to the first entry in this container.

array_map_iterator< K, V, true > array_map::end()

Returns a const array_map_iterator pointing to the end of this container.

static void array_map::swap(
array_map< K, V > &first,
array_map< K, V > &second)

Swaps the contents of the array_map first with that of second.

static void array_map::move(
const array_map< K, V > &src,
array_map< K, V > &dst)

Moves the contents of the array_map src into dst. Note this function does not copy the contents of the underlying array_map::keys or array_map::values, it merely copies the pointers.

static void array_map::free(
array_map< K, V > &map)

Frees array_map::keys and array_map::values. This should not be used if map was constructed on the stack, as the destructor will automatically free array_map::keys and array_map::values. The existing entries of map are not freed.

typedef K array_map::key_type

The type of the keys in this array_map.

typedef V array_map::value_type

The type of the values in this array_map.

template<typename K, typename V>
bool array_map_init(
array_map< K, V > &map,
unsigned intinitial_capacity)

Initializes the array_map map with the given initial_capacity.

template<typename T>
unsigned int size(
const hash_set< T > &set)

Returns the number of elements in the given hash_set set.

template<typename K, typename V>
unsigned int size(
const hash_map< K, V > &map)

Returns the number of elements in the given hash_map map.

template<typename K, typename V>
unsigned int size(
const array_map< K, V > &map)

Returns the number of elements in the given array_map map.

template<typename MapType>
const MapType::key_type ** invert(
const MapType &map)

Assuming the given map has value type that satisfies is_integral, and the values in the map are unique and no larger than size(map), this function returns an array of pointers to the keys in map, where the pointer at index i references the key in map that corresponds to the value i. The caller of this function is responsible for the memory of the returned native array, and must call free to release it.

Template parameters
MapType

a map type that allows range-based for iteration, and for which the function unsigned int size(const MapType&) is defined.