Design notes and plan

[ElectricRCAircraftGuy]

Notes to self from 20 Feb. 2022

https://stackoverflow.com/questions/7666509/hash-function-for-string#45641002

Write unordered_map or hash_table "class" for C!

Have it support multiple objects and track collision and usage stats for each object. Make it deterministic and use static memory allocation for use in real-time safety-critical applications. Write a shell for basic unit tests. Begin with the murmur hash 3 from the link above.

Learn CMake and integrate it with gtest.

Notes to self from 21 Feb. 2022

https://benhoyt.com/writings/hash-table-in-c/

Start new GitHub project:
eRCaGuy_hash_table

An unordered map in C. No malloc ever. Safety critical. Real time. User sets max container size at start. Recommended is to use container size 2x the number of elements you plan to ever store.

Keep stats.

Use linked list iterator to iterate through them all (yes). OR use array iteration and linear search (no).

NB: when hashing into an index, if index is taken, do NOT use linked list there. Instead, use the next empty slot in the array.

For key:value pairs, use a struct which can store ANY data type as a key and ANY data type as a value. Essentially I think I just need to make each be a uint8_t array long enough to store a long double OR ptr, so that one can either store real values OR a ptr to some bigger object.

Write helper macros to convert to/from byte arrays. Ex:

BYTE_ARRAY_TO_DOUBLE()
DOUBLE_TO_BYTE_ARRAY()

BYTE_ARRAY_TO_PTR() // to `void*`
PTR_TO_BYTE_ARRAY() // any ptr type to uint8_t[]

23 Feb. 2022

In order to have variable-sized objects, yet still with static memory allocation, you can do something like this:

// =============================================================================
// eRCaGuy_hash_table_private.h
// =============================================================================

/// A key:value element struct for a single key:value pair plus 
/// ptr to next element for iterating, plus bool to indicate whether
/// or not this element is taken.
typedef struct hash_table_s
{
    // fill me in
} hash_table_t;

// =============================================================================
// eRCaGuy_hash_table.h
// =============================================================================

#include "eRCaGuy_hash_table_private.h"

// other public functions here
// See here for inspiration on the API: 
// https://en.cppreference.com/w/cpp/container/unordered_map
// Ex:

// See here for inspiration: 
// https://stackoverflow.com/questions/3965279/opaque-c-structs-various-ways-to-declare-them/54488289#54488289

#define KEY_AND_VALUE_SIZE (MAX(sizeof(long double), sizeof(void*)))

//////////// todo
#define C_STR_TO_BYTE_ARRAY(c_str) (uint8_t*)(c_str)

typedef enum hash_table_error_e
{
    /// No error
    HASH_TABLE_ERROR_OK = 0,

    // other errors
} hash_table_error_t;

// INCOMPLETE DEFINITIONS (quickly written more like usage examples for now
// just to get my ideas jotted down)
hash_table_error_t hash_table_open(hash_table);
hash_table_error_t hash_table_write(hash_table, const key, const value);
hash_table_error_t hash_table_read(hash_table, const key, &value);
hash_table_error_t hash_table_erase(hash_table, const key);

// =============================================================================
// eRCaGuy_hash_table.c
// =============================================================================

// implementation of all public and private functions here

// =============================================================================
// user_code.c
// =============================================================================

#include "eRCaGuy_hash_table.h"

// From: 
// https://github.com/ElectricRCAircraftGuy/eRCaGuy_hello_world/blob/master/c/utilities.h
#define ARRAY_LEN(array) (sizeof(array) / sizeof(array[0]))

// Notice that multiple hash tables of different sizes are allowed, even when 
// *statically* allocated!

uint8_t key_bytes[KEY_AND_VALUE_SIZE];
uint8_t value_bytes[KEY_AND_VALUE_SIZE];

// hash table 1 (some size)

#define MAX_EXPECTED_ELEMENTS (100UL)
#define HASH_TABLE_SIZE (2UL*MAX_EXPECTED_ELEMENTS)
static hash_table_t hash_table1[HASH_TABLE_SIZE];
hash_table_open(hash_table1, ARRAY_LEN(hash_table1));

C_STR_TO_BYTE_ARRAY(key_bytes, "hello");
UINT32_TO_BYTE_ARRAY(value_bytes, 7);
hash_table_write(hash_table1, key_bytes, value_bytes);
hash_table_read(hash_table1, key_bytes, value_bytes);
uint32_t value = BYTE_ARRAY_TO_UINT32(value_bytes);

// hash table 2 (some other size)

static hash_table_t hash_table2[2UL*200UL];
hash_table_open(hash_table2, ARRAY_LEN(hash_table2));

Also add speed profiling to see how different hash algorithms compare against each other. See: https://stackoverflow.com/questions/7666509/hash-function-for-string/45641002#45641002

[ElectricRCAircraftGuy]

Other hash table algorithms to try out and test: http://www.cse.yorku.ca/~oz/hash.html

Hash algorithms mentioned there:

1. djb2
2. sdbm
3. lose lose (K&R 1st edition)

[ElectricRCAircraftGuy]

• https://stackoverflow.com/questions/10953958/can-crc32-be-used-as-a-hash-function
• https://stackoverflow.com/questions/7666509/hash-function-for-string/45641002#45641002
• https://benhoyt.com/writings/hash-table-in-c/