1
\$\begingroup\$

I tried implementing a general purpose hashtable in C99.

The basic structure is I have a huge array of hashtable entries and each entry is the entry point to a doubly linked list so that in case there are hash collisions due to a poor hash function the data is automatically appended to the linked list and then while retrieving I compare the actual keys.

Implementation:

from cgl.h:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
// ...
#define CGL_utils_clamp(x, minl, maxl) \
                       (x < minl ? minl : (x > maxl ? maxl : x))
// ...
#define CGL_malloc(size) malloc(size)
#define CGL_free(ptr) free(ptr)
// ...
#ifndef CGL_HASHTABLE_MAX_KEY_SIZE
#define CGL_HASHTABLE_MAX_KEY_SIZE 256
#endif

struct CGL_hashtable_entry;
typedef struct CGL_hashtable_entry CGL_hashtable_entry;

struct CGL_hashtable;
typedef struct CGL_hashtable CGL_hashtable;

struct CGL_hashtable_iterator;
typedef struct CGL_hashtable_iterator CGL_hashtable_iterator;

typedef uint32_t(*CGL_hash_function)(const void*, size_t);
// ...
// From : http://www.azillionmonkeys.com/qed/hash.html

#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
  || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
#define CGL_get16bits(d) (*((const uint16_t *) (d)))
#endif

#if !defined (CGL_get16bits)
#define CGL_get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
                       +(uint32_t)(((const uint8_t *)(d))[0]) )
#endif
// ...
uint32_t CGL_utils_super_fast_hash(const void* dat, size_t len)
{
    const uint8_t* data = (const uint8_t*)dat;
    uint32_t hash = (uint32_t)len;
    uint32_t tmp;
    int rem;
    
    if (len <= 0 || data == NULL) return 0;

    rem = len & 3;
    len >>= 2;

    /* Main loop */
    for (;len > 0; len--) {
        hash  += CGL_get16bits (data);
        tmp    = (CGL_get16bits (data+2) << 11) ^ hash;
        hash   = (hash << 16) ^ tmp;
        data  += 2*sizeof (uint16_t);
        hash  += hash >> 11;
    }

    /* Handle end cases */
    switch (rem) {
        case 3: hash += CGL_get16bits (data);
                hash ^= hash << 16;
                hash ^= ((signed char)data[sizeof (uint16_t)]) << 18;
                hash += hash >> 11;
                break;
        case 2: hash += CGL_get16bits (data);
                hash ^= hash << 11;
                hash += hash >> 17;
                break;
        case 1: hash += (signed char)*data;
                hash ^= hash << 10;
                hash += hash >> 1;
    }

    /* Force "avalanching" of final 127 bits */
    hash ^= hash << 3;
    hash += hash >> 5;
    hash ^= hash << 4;
    hash += hash >> 17;
    hash ^= hash << 25;
    hash += hash >> 6;

    return hash;
}

struct CGL_hashtable_entry
{
    bool set;
    uint8_t key[CGL_HASHTABLE_MAX_KEY_SIZE];
    void* value;
    size_t value_size;
    CGL_hashtable_entry* prev_entry; // prev entry in the linked list with same hash
    CGL_hashtable_entry* next_entry; // next entry in the linked list with same hash
};

struct CGL_hashtable
{
    CGL_hashtable_entry* entries;
    size_t table_size;
    size_t key_size;
    CGL_hash_function hash_function;
    size_t count;
};

struct CGL_hashtable_iterator
{
    CGL_hashtable* hashtable;
    CGL_hashtable_entry* current_entry;
    uint32_t current_index;
};

static void __CGL_hashtable_entry_destroy(CGL_hashtable_entry* entry, bool destory_current)
{
    if(entry == NULL) return;
    if(entry->next_entry != NULL) __CGL_hashtable_entry_destroy(entry->next_entry, true);
    if(entry->value) CGL_free(entry->value);
    if(destory_current) CGL_free(entry);
}

static void __CGL_hashtable_get_key_size_and_table_index(CGL_hashtable* table, size_t* key_size, size_t* hash_table_index, const void* key)
{
    *key_size = table->key_size;
    if(*key_size == 0) *key_size = strlen((const char*)key);
    *key_size = CGL_utils_clamp(*key_size, 1, CGL_HASHTABLE_MAX_KEY_SIZE);
    uint32_t hash = table->hash_function(key, *key_size);
    *hash_table_index = hash % table->table_size;
}

static CGL_hashtable_entry* __CGL_hashtable_get_entry_ptr(CGL_hashtable* table, const void* key)
{
    size_t key_size, hash_table_index;
    __CGL_hashtable_get_key_size_and_table_index(table, &key_size, &hash_table_index, key);
    CGL_hashtable_entry* current_entry = &table->entries[hash_table_index];
    while(current_entry != NULL)
    {
        if(memcmp(current_entry->key, key, key_size) == 0) return current_entry;
        current_entry = current_entry->next_entry;
    }
    return NULL;
}


CGL_hashtable* CGL_hashtable_create(size_t table_size, size_t key_size)
{
    CGL_hashtable* table = (CGL_hashtable*)CGL_malloc(sizeof(CGL_hashtable));
    table->count = 0;
    table->entries = (CGL_hashtable_entry*)CGL_malloc(sizeof(CGL_hashtable_entry) * table_size);
    memset(table->entries, 0, (sizeof(CGL_hashtable_entry) * table_size));
    table->key_size = key_size;
    table->table_size = table_size;
    table->hash_function = CGL_utils_super_fast_hash;
    return table;
}

void CGL_hashtable_destroy(CGL_hashtable* table)
{
    // destroy entries linked lists (if any) and data values
    CGL_hashtable_entry* entries = table->entries;
    for(size_t i = 0 ; i < table->table_size ; i++)
        __CGL_hashtable_entry_destroy(&entries[i], false);
    CGL_free(table->entries);
    CGL_free(table);
}

void CGL_hashtable_set(CGL_hashtable* table, const void* key, const void* value, size_t value_size)
{
    size_t key_size, hash_table_index;
    __CGL_hashtable_get_key_size_and_table_index(table, &key_size, &hash_table_index, key);
    CGL_hashtable_entry* entry_ptr = __CGL_hashtable_get_entry_ptr(table, key);
    if(entry_ptr)
    {
        entry_ptr->value_size = value_size;
        entry_ptr->value = NULL;    
        if(value_size > 0)
        {
            entry_ptr->value = CGL_malloc(value_size);
            memcpy(entry_ptr->value, value, value_size);
        }
    }
    else
    {
        CGL_hashtable_entry entry;
        entry.set = true;
        entry.next_entry = NULL;
        entry.prev_entry = NULL;
        memcpy(entry.key, key, key_size);
        entry.value_size = value_size;
        entry.value = NULL;    
        if(value_size > 0)
        {
            entry.value = CGL_malloc(value_size);
            memcpy(entry.value, value, value_size);
        }
        if(table->entries[hash_table_index].set)
        {
            CGL_hashtable_entry* entry_to_place = &table->entries[hash_table_index];
            while(entry_to_place->next_entry != NULL) entry_to_place = entry_to_place->next_entry;
            entry.prev_entry = entry_to_place;
            entry_to_place->next_entry = (CGL_hashtable_entry*)CGL_malloc(sizeof(CGL_hashtable_entry));
            memcpy(entry_to_place->next_entry, &entry, sizeof(CGL_hashtable_entry));
        }
        else
        {
            CGL_hashtable_entry* next_entry = table->entries[hash_table_index].next_entry;
            memcpy(&table->entries[hash_table_index], &entry, sizeof(CGL_hashtable_entry));
            table->entries[hash_table_index].next_entry = next_entry;
        }
    }
}

size_t CGL_hashtable_get(CGL_hashtable* table, const void* key, void* value)
{
    CGL_hashtable_entry* entry = __CGL_hashtable_get_entry_ptr(table, key);
    if(entry && value) memcpy(value, entry->value, entry->value_size);
    if(entry) return entry->value_size;
    return 0;
}

bool CGL_hashtable_exists(CGL_hashtable* table, const void* key)
{
    return __CGL_hashtable_get_entry_ptr(table, key) != NULL;
    // OR
    //return CGL_hashtable_get(table, key, NULL) != 0;
}

bool CGL_hashtable_remove(CGL_hashtable* table, const void* key)
{
    CGL_hashtable_entry* entry = __CGL_hashtable_get_entry_ptr(table, key);
    if(entry)
    {
        if(entry->value) CGL_free(entry->value);
        memset(entry->key, 0, CGL_HASHTABLE_MAX_KEY_SIZE);
        entry->set = false;
        if(entry->prev_entry)
        {
            entry->prev_entry->next_entry = entry->next_entry;
            CGL_free(entry);
        }
    }
    return entry != NULL;
}

Usage:

int main (void) {
    char buffer[1024];
    CGL_hashtable* table = CGL_hashtable_create(10000, 0);
    int idata = 0;
    float fdata = 0.0f;
    CGL_hashtable_set(table, "Name", "Jaysmito", 9);
    idata = 18;
    CGL_hashtable_set(table, "Age", &idata, sizeof(idata));
    fdata = 454.4854f;
    CGL_hashtable_set(table, "Float Data", &fdata, sizeof(fdata));

    // print 
    CGL_hashtable_get(table, "Age", buffer);
    printf("Age : %d\n", *(int*)buffer);
    CGL_hashtable_get(table, "Float Data", buffer);
    printf("Float Data : %f\n", *(float*)buffer);
    CGL_hashtable_get(table, "Name", buffer);
    printf("Name : %s\n", buffer);
    CGL_hashtable_set(table, "Name", "Jack", 5);
    CGL_hashtable_get(table, "Name", buffer);
    printf("Name 2 : %s\n", buffer);
    CGL_hashtable_destroy(table);
}
\$\endgroup\$
4
  • 2
    \$\begingroup\$ You keep prev… and next…, but CGL_hashtable_remove() doesn't do a full doubly linked list remove. I don't think this correct when removing the successor of a removed item (accesses a freed entry, doesn't link previous entry to next)). To test external collision resolution, use a table size of 1 or a hash function returning a constant. \$\endgroup\$
    – greybeard
    Oct 1, 2022 at 10:59
  • \$\begingroup\$ @greybeard as far as I tested it seems to work with table size 1. And as for why not doa. Full remove its as the first element of the linked list is inside the table array (where prev is NULL)and I cannot actually remove it so I just set it false(disabled) \$\endgroup\$ Oct 1, 2022 at 12:41
  • \$\begingroup\$ so I just set it false(disabled) which goes unchecked in __CGL_hashtable_get_entry_ptr(). \$\endgroup\$
    – greybeard
    Oct 1, 2022 at 14:43
  • \$\begingroup\$ @greybeardbut I don't think that's an issue as I am comparing the keys (keys of disabled entries are zeroed in remove) so it's just iterating 1 extra time if(memcmp(current_entry->key, key, key_size) == 0) \$\endgroup\$ Oct 1, 2022 at 15:37

2 Answers 2

3
\$\begingroup\$

Enable more warnings

Before you ask for a review, get your compiler to review your code for you. This can help identify any oversights. I got a quite detailed analysis from GCC:

gcc-12 -std=c17 -fPIC -gdwarf-4 -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Wconversion  -Wstrict-prototypes -fanalyzer  -Wconversion      280098.c    -o 280098
280098.c: In function ‘CGL_utils_super_fast_hash’:
280098.c:67:26: warning: conversion to ‘uint32_t’ {aka ‘unsigned int’} from ‘int’ may change the sign of the result [-Wsign-conversion]
   67 |                     hash ^= ((signed char)data[sizeof (uint16_t)]) << 18;
      |                          ^~
280098.c:74:26: warning: conversion to ‘uint32_t’ {aka ‘unsigned int’} from ‘int’ may change the sign of the result [-Wsign-conversion]
   74 |             case 1: hash += (signed char)*data;
      |                          ^~
280098.c: In function ‘CGL_hashtable_create’:
280098.c:151:18: warning: dereference of possibly-NULL ‘table’ [CWE-690] [-Wanalyzer-possible-null-dereference]
  151 |     table->count = 0;
      |     ~~~~~~~~~~~~~^~~
  ‘main’: events 1-2
    |
    |  250 | int main (void) {
    |      |     ^~~~
    |      |     |
    |      |     (1) entry to ‘main’
    |  251 |     char buffer[1024];
    |  252 |     CGL_hashtable* table = CGL_hashtable_create(10000, 0);
    |      |                            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    |      |                            |
    |      |                            (2) calling ‘CGL_hashtable_create’ from ‘main’
    |
    +--> ‘CGL_hashtable_create’: event 3
           |
           |  148 | CGL_hashtable* CGL_hashtable_create(size_t table_size, size_t key_size)
           |      |                ^~~~~~~~~~~~~~~~~~~~
           |      |                |
           |      |                (3) entry to ‘CGL_hashtable_create’
           |
         ‘CGL_hashtable_create’: event 4
           |
           |   12 |     #define CGL_malloc(size) malloc(size)
           |      |                              ^~~~~~~~~~~~
           |      |                              |
           |      |                              (4) this call could return NULL
280098.c:150:44: note: in expansion of macro ‘CGL_malloc’
           |  150 |     CGL_hashtable* table = (CGL_hashtable*)CGL_malloc(sizeof(CGL_hashtable));
           |      |                                            ^~~~~~~~~~
           |
         ‘CGL_hashtable_create’: event 5
           |
           |  151 |     table->count = 0;
           |      |     ~~~~~~~~~~~~~^~~
           |      |                  |
           |      |                  (5) ‘table’ could be NULL: unchecked value from (4)
           |
280098.c:153:5: warning: use of possibly-NULL ‘*table.entries’ where non-null expected [CWE-690] [-Wanalyzer-possible-null-argument]
  153 |     memset(table->entries, 0, (sizeof(CGL_hashtable_entry) * table_size));
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  ‘main’: events 1-2
    |
    |  250 | int main (void) {
    |      |     ^~~~
    |      |     |
    |      |     (1) entry to ‘main’
    |  251 |     char buffer[1024];
    |  252 |     CGL_hashtable* table = CGL_hashtable_create(10000, 0);
    |      |                            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    |      |                            |
    |      |                            (2) calling ‘CGL_hashtable_create’ from ‘main’
    |
    +--> ‘CGL_hashtable_create’: event 3
           |
           |  148 | CGL_hashtable* CGL_hashtable_create(size_t table_size, size_t key_size)
           |      |                ^~~~~~~~~~~~~~~~~~~~
           |      |                |
           |      |                (3) entry to ‘CGL_hashtable_create’
           |
         ‘CGL_hashtable_create’: event 4
           |
           |   12 |     #define CGL_malloc(size) malloc(size)
           |      |                              ^~~~~~~~~~~~
           |      |                              |
           |      |                              (4) this call could return NULL
280098.c:152:44: note: in expansion of macro ‘CGL_malloc’
           |  152 |     table->entries = (CGL_hashtable_entry*)CGL_malloc(sizeof(CGL_hashtable_entry) * table_size);
           |      |                                            ^~~~~~~~~~
           |
         ‘CGL_hashtable_create’: event 5
           |
           |  153 |     memset(table->entries, 0, (sizeof(CGL_hashtable_entry) * table_size));
           |      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           |      |     |
           |      |     (5) argument 1 (‘*table.entries’) from (4) could be NULL where non-null expected
           |
In file included from 280098.c:5:
/usr/include/string.h:61:14: note: argument 1 of ‘memset’ must be non-null
   61 | extern void *memset (void *__s, int __c, size_t __n) __THROW __nonnull ((1));
      |              ^~~~~~
280098.c: In function ‘CGL_hashtable_set’:
280098.c:182:13: warning: leak of ‘<unknown>’ [CWE-401] [-Wanalyzer-malloc-leak]
  182 |             memcpy(entry_ptr->value, value, value_size);
      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  ‘main’: events 1-2
    |
    |  250 | int main (void) {
    |      |     ^~~~
    |      |     |
    |      |     (1) entry to ‘main’
    |......
    |  255 |     CGL_hashtable_set(table, "Name", "Jaysmito", 9);
    |      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    |      |     |
    |      |     (2) calling ‘CGL_hashtable_set’ from ‘main’
    |
    +--> ‘CGL_hashtable_set’: events 3-4
           |
           |  170 | void CGL_hashtable_set(CGL_hashtable* table, const void* key, const void* value, size_t value_size)
           |      |      ^~~~~~~~~~~~~~~~~
           |      |      |
           |      |      (3) entry to ‘CGL_hashtable_set’
           |......
           |  173 |     __CGL_hashtable_get_key_size_and_table_index(table, &key_size, &hash_table_index, key);
           |      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           |      |     |
           |      |     (4) calling ‘__CGL_hashtable_get_key_size_and_table_index’ from ‘CGL_hashtable_set’
           |
           +--> ‘__CGL_hashtable_get_key_size_and_table_index’: events 5-7
                  |
                  |  125 | static void __CGL_hashtable_get_key_size_and_table_index(CGL_hashtable* table, size_t* key_size, size_t* hash_table_index, const void* key)
                  |      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                  |      |             |
                  |      |             (5) entry to ‘__CGL_hashtable_get_key_size_and_table_index’
                  |......
                  |  128 |     if(*key_size == 0) *key_size = strlen((const char*)key);
                  |      |       ~                            ~~~~~~~~~~~~~~~~~~~~~~~~
                  |      |       |                            |
                  |      |       |                            (7) ...to here
                  |      |       (6) following ‘true’ branch...
                  |
                ‘__CGL_hashtable_get_key_size_and_table_index’: event 8
                  |
                  |   10 |                            (x < minl ? minl : (x > maxl ? maxl : x))
                  |      |                            ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
                  |      |                                             |
                  |      |                                             (8) following ‘true’ branch...
280098.c:129:17: note: in expansion of macro ‘CGL_utils_clamp’
                  |  129 |     *key_size = CGL_utils_clamp(*key_size, 1, CGL_HASHTABLE_MAX_KEY_SIZE);
                  |      |                 ^~~~~~~~~~~~~~~
                  |
                ‘__CGL_hashtable_get_key_size_and_table_index’: event 9
                  |
                  |  129 |     *key_size = CGL_utils_clamp(*key_size, 1, CGL_HASHTABLE_MAX_KEY_SIZE);
                  |      |                                 ^~~~~~~~~
                  |      |                                 |
                  |      |                                 (9) ...to here
280098.c:10:48: note: in definition of macro ‘CGL_utils_clamp’
                  |   10 |                            (x < minl ? minl : (x > maxl ? maxl : x))
                  |      |                                                ^
                  |
                ‘__CGL_hashtable_get_key_size_and_table_index’: event 10
                  |
                  |  130 |     uint32_t hash = table->hash_function(key, *key_size);
                  |      |                     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                  |      |                     |
                  |      |                     (10) calling ‘CGL_utils_super_fast_hash’ from ‘__CGL_hashtable_get_key_size_and_table_index’
                  |
                  +--> ‘CGL_utils_super_fast_hash’: events 11-14
                         |
                         |   42 |     uint32_t CGL_utils_super_fast_hash(const void* dat, size_t len)
                         |      |              ^~~~~~~~~~~~~~~~~~~~~~~~~
                         |      |              |
                         |      |              (11) entry to ‘CGL_utils_super_fast_hash’
                         |......
                         |   49 |         if (len <= 0 || data == NULL) return 0;
                         |      |            ~  
                         |      |            |
                         |      |            (12) following ‘false’ branch...
                         |   50 | 
                         |   51 |         rem = len & 3;
                         |      |               ~~~~~~~
                         |      |                   |
                         |      |                   (13) ...to here
                         |......
                         |   55 |         for (;len > 0; len--) {
                         |      |               ~~~~~~~
                         |      |                   |
                         |      |                   (14) following ‘true’ branch (when ‘len != 0’)...
                         |
                       ‘CGL_utils_super_fast_hash’: event 15
                         |
                         |   38 |     #define CGL_get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
                         |      |                                                                  ^
                         |      |                                                                  |
                         |      |                                                                  (15) ...to here
280098.c:56:22: note: in expansion of macro ‘CGL_get16bits’
                         |   56 |             hash  += CGL_get16bits (data);
                         |      |                      ^~~~~~~~~~~~~
                         |
                       ‘CGL_utils_super_fast_hash’: events 16-17
                         |
                         |   64 |         switch (rem) {
                         |      |         ^~~~~~
                         |      |         |
                         |      |         (16) following ‘default:’ branch...
                         |......
                         |   80 |         hash ^= hash << 3;
                         |      |                 ~~~~~~~~~
                         |      |                      |
                         |      |                      (17) ...to here
                         |
                  <------+
                  |
                ‘__CGL_hashtable_get_key_size_and_table_index’: event 18
                  |
                  |  130 |     uint32_t hash = table->hash_function(key, *key_size);
                  |      |                     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                  |      |                     |
                  |      |                     (18) returning to ‘__CGL_hashtable_get_key_size_and_table_index’ from ‘CGL_utils_super_fast_hash’
                  |
           <------+
           |
         ‘CGL_hashtable_set’: events 19-20
           |
           |  173 |     __CGL_hashtable_get_key_size_and_table_index(table, &key_size, &hash_table_index, key);
           |      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           |      |     |
           |      |     (19) returning to ‘CGL_hashtable_set’ from ‘__CGL_hashtable_get_key_size_and_table_index’
           |  174 |     CGL_hashtable_entry* entry_ptr = __CGL_hashtable_get_entry_ptr(table, key);
           |      |                                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           |      |                                      |
           |      |                                      (20) calling ‘__CGL_hashtable_get_entry_ptr’ from ‘CGL_hashtable_set’
           |
           +--> ‘__CGL_hashtable_get_entry_ptr’: events 21-22
                  |
                  |  134 | static CGL_hashtable_entry* __CGL_hashtable_get_entry_ptr(CGL_hashtable* table, const void* key)
                  |      |                             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                  |      |                             |
                  |      |                             (21) entry to ‘__CGL_hashtable_get_entry_ptr’
                  |......
                  |  137 |     __CGL_hashtable_get_key_size_and_table_index(table, &key_size, &hash_table_index, key);
                  |      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                  |      |     |
                  |      |     (22) calling ‘__CGL_hashtable_get_key_size_and_table_index’ from ‘__CGL_hashtable_get_entry_ptr’
                  |
                  +--> ‘__CGL_hashtable_get_key_size_and_table_index’: events 23-25
                         |
                         |  125 | static void __CGL_hashtable_get_key_size_and_table_index(CGL_hashtable* table, size_t* key_size, size_t* hash_table_index, const void* key)
                         |      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                         |      |             |
                         |      |             (23) entry to ‘__CGL_hashtable_get_key_size_and_table_index’
                         |......
                         |  128 |     if(*key_size == 0) *key_size = strlen((const char*)key);
                         |      |       ~                            ~~~~~~~~~~~~~~~~~~~~~~~~
                         |      |       |                            |
                         |      |       |                            (25) ...to here
                         |      |       (24) following ‘true’ branch...
                         |
                       ‘__CGL_hashtable_get_key_size_and_table_index’: event 26
                         |
                         |   10 |                            (x < minl ? minl : (x > maxl ? maxl : x))
                         |      |                            ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
                         |      |                                             |
                         |      |                                             (26) following ‘true’ branch...
280098.c:129:17: note: in expansion of macro ‘CGL_utils_clamp’
                         |  129 |     *key_size = CGL_utils_clamp(*key_size, 1, CGL_HASHTABLE_MAX_KEY_SIZE);
                         |      |                 ^~~~~~~~~~~~~~~
                         |
                       ‘__CGL_hashtable_get_key_size_and_table_index’: event 27
                         |
                         |  129 |     *key_size = CGL_utils_clamp(*key_size, 1, CGL_HASHTABLE_MAX_KEY_SIZE);
                         |      |                                 ^~~~~~~~~
                         |      |                                 |
                         |      |                                 (27) ...to here
280098.c:10:48: note: in definition of macro ‘CGL_utils_clamp’
                         |   10 |                            (x < minl ? minl : (x > maxl ? maxl : x))
                         |      |                                                ^
                         |
                       ‘__CGL_hashtable_get_key_size_and_table_index’: event 28
                         |
                         |  130 |     uint32_t hash = table->hash_function(key, *key_size);
                         |      |                     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                         |      |                     |
                         |      |                     (28) calling ‘CGL_utils_super_fast_hash’ from ‘__CGL_hashtable_get_key_size_and_table_index’
                         |
                         +--> ‘CGL_utils_super_fast_hash’: events 29-32
                                |
                                |   42 |     uint32_t CGL_utils_super_fast_hash(const void* dat, size_t len)
                                |      |              ^~~~~~~~~~~~~~~~~~~~~~~~~
                                |      |              |
                                |      |              (29) entry to ‘CGL_utils_super_fast_hash’
                                |......
                                |   49 |         if (len <= 0 || data == NULL) return 0;
                                |      |            ~  
                                |      |            |
                                |      |            (30) following ‘false’ branch...
                                |   50 | 
                                |   51 |         rem = len & 3;
                                |      |               ~~~~~~~
                                |      |                   |
                                |      |                   (31) ...to here
                                |......
                                |   55 |         for (;len > 0; len--) {
                                |      |               ~~~~~~~
                                |      |                   |
                                |      |                   (32) following ‘true’ branch (when ‘len != 0’)...
                                |
                              ‘CGL_utils_super_fast_hash’: event 33
                                |
                                |   38 |     #define CGL_get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
                                |      |                                                                  ^
                                |      |                                                                  |
                                |      |                                                                  (33) ...to here
280098.c:56:22: note: in expansion of macro ‘CGL_get16bits’
                                |   56 |             hash  += CGL_get16bits (data);
                                |      |                      ^~~~~~~~~~~~~
                                |
                              ‘CGL_utils_super_fast_hash’: events 34-35
                                |
                                |   64 |         switch (rem) {
                                |      |         ^~~~~~
                                |      |         |
                                |      |         (34) following ‘default:’ branch...
                                |......
                                |   80 |         hash ^= hash << 3;
                                |      |                 ~~~~~~~~~
                                |      |                      |
                                |      |                      (35) ...to here
                                |
                         <------+
                         |
                       ‘__CGL_hashtable_get_key_size_and_table_index’: event 36
                         |
                         |  130 |     uint32_t hash = table->hash_function(key, *key_size);
                         |      |                     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                         |      |                     |
                         |      |                     (36) returning to ‘__CGL_hashtable_get_key_size_and_table_index’ from ‘CGL_utils_super_fast_hash’
                         |
                  <------+
                  |
                ‘__CGL_hashtable_get_entry_ptr’: event 37
                  |
                  |  137 |     __CGL_hashtable_get_key_size_and_table_index(table, &key_size, &hash_table_index, key);
                  |      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                  |      |     |
                  |      |     (37) returning to ‘__CGL_hashtable_get_entry_ptr’ from ‘__CGL_hashtable_get_key_size_and_table_index’
                  |
                ‘__CGL_hashtable_get_entry_ptr’: events 38-39
                  |
                  |  139 |     while(current_entry != NULL)
                  |      |                         ^
                  |      |                         |
                  |      |                         (38) following ‘true’ branch (when ‘current_entry’ is non-NULL)...
                  |  140 |     {
                  |  141 |         if(memcmp(current_entry->key, key, key_size) == 0) return current_entry;
                  |      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                  |      |            |
                  |      |            (39) ...to here
                  |
           <------+
           |
         ‘CGL_hashtable_set’: events 40-43
           |
           |  174 |     CGL_hashtable_entry* entry_ptr = __CGL_hashtable_get_entry_ptr(table, key);
           |      |                                      ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           |      |                                      |
           |      |                                      (40) returning to ‘CGL_hashtable_set’ from ‘__CGL_hashtable_get_entry_ptr’
           |  175 |     if(entry_ptr)
           |      |       ~                               
           |      |       |
           |      |       (41) following ‘true’ branch (when ‘entry_ptr’ is non-NULL)...
           |  176 |     {
           |  177 |         entry_ptr->value_size = value_size;
           |      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           |      |                               |
           |      |                               (42) ...to here
           |  178 |         entry_ptr->value = NULL;
           |  179 |         if(value_size > 0)
           |      |           ~                           
           |      |           |
           |      |           (43) following ‘true’ branch (when ‘value_size != 0’)...
           |
         ‘CGL_hashtable_set’: event 44
           |
           |   12 |     #define CGL_malloc(size) malloc(size)
           |      |                              ^~~~~~~~~~~~
           |      |                              |
           |      |                              (44) ...to here
280098.c:181:32: note: in expansion of macro ‘CGL_malloc’
           |  181 |             entry_ptr->value = CGL_malloc(value_size);
           |      |                                ^~~~~~~~~~
           |
         ‘CGL_hashtable_set’: event 45
           |
           |   12 |     #define CGL_malloc(size) malloc(size)
           |      |                              ^~~~~~~~~~~~
           |      |                              |
           |      |                              (45) allocated here
280098.c:181:32: note: in expansion of macro ‘CGL_malloc’
           |  181 |             entry_ptr->value = CGL_malloc(value_size);
           |      |                                ^~~~~~~~~~
           |
         ‘CGL_hashtable_set’: event 46
           |
           |  182 |             memcpy(entry_ptr->value, value, value_size);
           |      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           |      |             |
           |      |             (46) ‘<unknown>’ leaks here; was allocated at (45)
           |
280098.c:197:13: warning: use of possibly-NULL ‘entry.value’ where non-null expected [CWE-690] [-Wanalyzer-possible-null-argument]
  197 |             memcpy(entry.value, value, value_size);
      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  ‘main’: events 1-2
    |
    |  250 | int main (void) {
    |      |     ^~~~
    |      |     |
    |      |     (1) entry to ‘main’
    |......
    |  255 |     CGL_hashtable_set(table, "Name", "Jaysmito", 9);
    |      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    |      |     |
    |      |     (2) calling ‘CGL_hashtable_set’ from ‘main’
    |
    +--> ‘CGL_hashtable_set’: events 3-4
           |
           |  170 | void CGL_hashtable_set(CGL_hashtable* table, const void* key, const void* value, size_t value_size)
           |      |      ^~~~~~~~~~~~~~~~~
           |      |      |
           |      |      (3) entry to ‘CGL_hashtable_set’
           |......
           |  173 |     __CGL_hashtable_get_key_size_and_table_index(table, &key_size, &hash_table_index, key);
           |      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           |      |     |
           |      |     (4) calling ‘__CGL_hashtable_get_key_size_and_table_index’ from ‘CGL_hashtable_set’
           |
           +--> ‘__CGL_hashtable_get_key_size_and_table_index’: events 5-7
                  |
                  |  125 | static void __CGL_hashtable_get_key_size_and_table_index(CGL_hashtable* table, size_t* key_size, size_t* hash_table_index, const void* key)
                  |      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                  |      |             |
                  |      |             (5) entry to ‘__CGL_hashtable_get_key_size_and_table_index’
                  |......
                  |  128 |     if(*key_size == 0) *key_size = strlen((const char*)key);
                  |      |       ~                            ~~~~~~~~~~~~~~~~~~~~~~~~
                  |      |       |                            |
                  |      |       |                            (7) ...to here
                  |      |       (6) following ‘true’ branch...
                  |
                ‘__CGL_hashtable_get_key_size_and_table_index’: event 8
                  |
                  |   10 |                            (x < minl ? minl : (x > maxl ? maxl : x))
                  |      |                            ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
                  |      |                                             |
                  |      |                                             (8) following ‘true’ branch...
280098.c:129:17: note: in expansion of macro ‘CGL_utils_clamp’
                  |  129 |     *key_size = CGL_utils_clamp(*key_size, 1, CGL_HASHTABLE_MAX_KEY_SIZE);
                  |      |                 ^~~~~~~~~~~~~~~
                  |
                ‘__CGL_hashtable_get_key_size_and_table_index’: event 9
                  |
                  |  129 |     *key_size = CGL_utils_clamp(*key_size, 1, CGL_HASHTABLE_MAX_KEY_SIZE);
                  |      |                                 ^~~~~~~~~
                  |      |                                 |
                  |      |                                 (9) ...to here
280098.c:10:48: note: in definition of macro ‘CGL_utils_clamp’
                  |   10 |                            (x < minl ? minl : (x > maxl ? maxl : x))
                  |      |                                                ^
                  |
                ‘__CGL_hashtable_get_key_size_and_table_index’: event 10
                  |
                  |  130 |     uint32_t hash = table->hash_function(key, *key_size);
                  |      |                     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                  |      |                     |
                  |      |                     (10) calling ‘CGL_utils_super_fast_hash’ from ‘__CGL_hashtable_get_key_size_and_table_index’
                  |
                  +--> ‘CGL_utils_super_fast_hash’: events 11-14
                         |
                         |   42 |     uint32_t CGL_utils_super_fast_hash(const void* dat, size_t len)
                         |      |              ^~~~~~~~~~~~~~~~~~~~~~~~~
                         |      |              |
                         |      |              (11) entry to ‘CGL_utils_super_fast_hash’
                         |......
                         |   49 |         if (len <= 0 || data == NULL) return 0;
                         |      |            ~  
                         |      |            |
                         |      |            (12) following ‘false’ branch...
                         |   50 | 
                         |   51 |         rem = len & 3;
                         |      |               ~~~~~~~
                         |      |                   |
                         |      |                   (13) ...to here
                         |......
                         |   55 |         for (;len > 0; len--) {
                         |      |               ~~~~~~~
                         |      |                   |
                         |      |                   (14) following ‘true’ branch (when ‘len != 0’)...
                         |
                       ‘CGL_utils_super_fast_hash’: event 15
                         |
                         |   38 |     #define CGL_get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
                         |      |                                                                  ^
                         |      |                                                                  |
                         |      |                                                                  (15) ...to here
280098.c:56:22: note: in expansion of macro ‘CGL_get16bits’
                         |   56 |             hash  += CGL_get16bits (data);
                         |      |                      ^~~~~~~~~~~~~
                         |
                       ‘CGL_utils_super_fast_hash’: events 16-17
                         |
                         |   64 |         switch (rem) {
                         |      |         ^~~~~~
                         |      |         |
                         |      |         (16) following ‘default:’ branch...
                         |......
                         |   80 |         hash ^= hash << 3;
                         |      |                 ~~~~~~~~~
                         |      |                      |
                         |      |                      (17) ...to here
                         |
                  <------+
                  |
                ‘__CGL_hashtable_get_key_size_and_table_index’: event 18
                  |
                  |  130 |     uint32_t hash = table->hash_function(key, *key_size);
                  |      |                     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                  |      |                     |
                  |      |                     (18) returning to ‘__CGL_hashtable_get_key_size_and_table_index’ from ‘CGL_utils_super_fast_hash’
                  |
           <------+
           |
         ‘CGL_hashtable_set’: events 19-20
           |
           |  173 |     __CGL_hashtable_get_key_size_and_table_index(table, &key_size, &hash_table_index, key);
           |      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           |      |     |
           |      |     (19) returning to ‘CGL_hashtable_set’ from ‘__CGL_hashtable_get_key_size_and_table_index’
           |  174 |     CGL_hashtable_entry* entry_ptr = __CGL_hashtable_get_entry_ptr(table, key);
           |      |                                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           |      |                                      |
           |      |                                      (20) calling ‘__CGL_hashtable_get_entry_ptr’ from ‘CGL_hashtable_set’
           |
           +--> ‘__CGL_hashtable_get_entry_ptr’: events 21-22
                  |
                  |  134 | static CGL_hashtable_entry* __CGL_hashtable_get_entry_ptr(CGL_hashtable* table, const void* key)
                  |      |                             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                  |      |                             |
                  |      |                             (21) entry to ‘__CGL_hashtable_get_entry_ptr’
                  |......
                  |  137 |     __CGL_hashtable_get_key_size_and_table_index(table, &key_size, &hash_table_index, key);
                  |      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                  |      |     |
                  |      |     (22) calling ‘__CGL_hashtable_get_key_size_and_table_index’ from ‘__CGL_hashtable_get_entry_ptr’
                  |
                  +--> ‘__CGL_hashtable_get_key_size_and_table_index’: events 23-25
                         |
                         |  125 | static void __CGL_hashtable_get_key_size_and_table_index(CGL_hashtable* table, size_t* key_size, size_t* hash_table_index, const void* key)
                         |      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                         |      |             |
                         |      |             (23) entry to ‘__CGL_hashtable_get_key_size_and_table_index’
                         |......
                         |  128 |     if(*key_size == 0) *key_size = strlen((const char*)key);
                         |      |       ~                            ~~~~~~~~~~~~~~~~~~~~~~~~
                         |      |       |                            |
                         |      |       |                            (25) ...to here
                         |      |       (24) following ‘true’ branch...
                         |
                       ‘__CGL_hashtable_get_key_size_and_table_index’: event 26
                         |
                         |   10 |                            (x < minl ? minl : (x > maxl ? maxl : x))
                         |      |                            ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
                         |      |                                             |
                         |      |                                             (26) following ‘true’ branch...
280098.c:129:17: note: in expansion of macro ‘CGL_utils_clamp’
                         |  129 |     *key_size = CGL_utils_clamp(*key_size, 1, CGL_HASHTABLE_MAX_KEY_SIZE);
                         |      |                 ^~~~~~~~~~~~~~~
                         |
                       ‘__CGL_hashtable_get_key_size_and_table_index’: event 27
                         |
                         |  129 |     *key_size = CGL_utils_clamp(*key_size, 1, CGL_HASHTABLE_MAX_KEY_SIZE);
                         |      |                                 ^~~~~~~~~
                         |      |                                 |
                         |      |                                 (27) ...to here
280098.c:10:48: note: in definition of macro ‘CGL_utils_clamp’
                         |   10 |                            (x < minl ? minl : (x > maxl ? maxl : x))
                         |      |                                                ^
                         |
                       ‘__CGL_hashtable_get_key_size_and_table_index’: event 28
                         |
                         |  130 |     uint32_t hash = table->hash_function(key, *key_size);
                         |      |                     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                         |      |                     |
                         |      |                     (28) calling ‘CGL_utils_super_fast_hash’ from ‘__CGL_hashtable_get_key_size_and_table_index’
                         |
                         +--> ‘CGL_utils_super_fast_hash’: events 29-32
                                |
                                |   42 |     uint32_t CGL_utils_super_fast_hash(const void* dat, size_t len)
                                |      |              ^~~~~~~~~~~~~~~~~~~~~~~~~
                                |      |              |
                                |      |              (29) entry to ‘CGL_utils_super_fast_hash’
                                |......
                                |   49 |         if (len <= 0 || data == NULL) return 0;
                                |      |            ~  
                                |      |            |
                                |      |            (30) following ‘false’ branch...
                                |   50 | 
                                |   51 |         rem = len & 3;
                                |      |               ~~~~~~~
                                |      |                   |
                                |      |                   (31) ...to here
                                |......
                                |   55 |         for (;len > 0; len--) {
                                |      |               ~~~~~~~
                                |      |                   |
                                |      |                   (32) following ‘true’ branch (when ‘len != 0’)...
                                |
                              ‘CGL_utils_super_fast_hash’: event 33
                                |
                                |   38 |     #define CGL_get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
                                |      |                                                                  ^
                                |      |                                                                  |
                                |      |                                                                  (33) ...to here
280098.c:56:22: note: in expansion of macro ‘CGL_get16bits’
                                |   56 |             hash  += CGL_get16bits (data);
                                |      |                      ^~~~~~~~~~~~~
                                |
                              ‘CGL_utils_super_fast_hash’: events 34-35
                                |
                                |   64 |         switch (rem) {
                                |      |         ^~~~~~
                                |      |         |
                                |      |         (34) following ‘default:’ branch...
                                |......
                                |   80 |         hash ^= hash << 3;
                                |      |                 ~~~~~~~~~
                                |      |                      |
                                |      |                      (35) ...to here
                                |
                         <------+
                         |
                       ‘__CGL_hashtable_get_key_size_and_table_index’: event 36
                         |
                         |  130 |     uint32_t hash = table->hash_function(key, *key_size);
                         |      |                     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                         |      |                     |
                         |      |                     (36) returning to ‘__CGL_hashtable_get_key_size_and_table_index’ from ‘CGL_utils_super_fast_hash’
                         |
                  <------+
                  |
                ‘__CGL_hashtable_get_entry_ptr’: event 37
                  |
                  |  137 |     __CGL_hashtable_get_key_size_and_table_index(table, &key_size, &hash_table_index, key);
                  |      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                  |      |     |
                  |      |     (37) returning to ‘__CGL_hashtable_get_entry_ptr’ from ‘__CGL_hashtable_get_key_size_and_table_index’
                  |
           <------+
           |
         ‘CGL_hashtable_set’: events 38-39
           |
           |  174 |     CGL_hashtable_entry* entry_ptr = __CGL_hashtable_get_entry_ptr(table, key);
           |      |                                      ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           |      |                                      |
           |      |                                      (38) returning to ‘CGL_hashtable_set’ from ‘__CGL_hashtable_get_entry_ptr’
           |  175 |     if(entry_ptr)
           |      |       ~                               
           |      |       |
           |      |       (39) following ‘false’ branch (when ‘entry_ptr’ is NULL)...
           |
         ‘CGL_hashtable_set’: events 40-41
           |
           |  188 |         entry.set = true;
           |      |                   ^
           |      |                   |
           |      |                   (40) ...to here
           |......
           |  194 |         if(value_size > 0)
           |      |           ~        
           |      |           |
           |      |           (41) following ‘true’ branch (when ‘value_size != 0’)...
           |
         ‘CGL_hashtable_set’: event 42
           |
           |   12 |     #define CGL_malloc(size) malloc(size)
           |      |                              ^~~~~~~~~~~~
           |      |                              |
           |      |                              (42) ...to here
280098.c:196:27: note: in expansion of macro ‘CGL_malloc’
           |  196 |             entry.value = CGL_malloc(value_size);
           |      |                           ^~~~~~~~~~
           |
         ‘CGL_hashtable_set’: event 43
           |
           |   12 |     #define CGL_malloc(size) malloc(size)
           |      |                              ^~~~~~~~~~~~
           |      |                              |
           |      |                              (43) this call could return NULL
280098.c:196:27: note: in expansion of macro ‘CGL_malloc’
           |  196 |             entry.value = CGL_malloc(value_size);
           |      |                           ^~~~~~~~~~
           |
         ‘CGL_hashtable_set’: event 44
           |
           |  197 |             memcpy(entry.value, value, value_size);
           |      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           |      |             |
           |      |             (44) argument 1 (‘entry.value’) from (43) could be NULL where non-null expected
           |
/usr/include/string.h:43:14: note: argument 1 of ‘memcpy’ must be non-null
   43 | extern void *memcpy (void *__restrict __dest, const void *__restrict __src,
      |              ^~~~~~
280098.c:205:34: warning: leak of ‘<unknown>’ [CWE-401] [-Wanalyzer-malloc-leak]
  205 |             memcpy(entry_to_place->next_entry, &entry, sizeof(CGL_hashtable_entry));
      |                    ~~~~~~~~~~~~~~^~~~~~~~~~~~
  ‘main’: events 1-2
    |
    |  250 | int main (void) {
    |      |     ^~~~
    |      |     |
    |      |     (1) entry to ‘main’
    |......
    |  255 |     CGL_hashtable_set(table, "Name", "Jaysmito", 9);
    |      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    |      |     |
    |      |     (2) calling ‘CGL_hashtable_set’ from ‘main’
    |
    +--> ‘CGL_hashtable_set’: events 3-4
           |
           |  170 | void CGL_hashtable_set(CGL_hashtable* table, const void* key, const void* value, size_t value_size)
           |      |      ^~~~~~~~~~~~~~~~~
           |      |      |
           |      |      (3) entry to ‘CGL_hashtable_set’
           |......
           |  173 |     __CGL_hashtable_get_key_size_and_table_index(table, &key_size, &hash_table_index, key);
           |      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           |      |     |
           |      |     (4) calling ‘__CGL_hashtable_get_key_size_and_table_index’ from ‘CGL_hashtable_set’
           |
           +--> ‘__CGL_hashtable_get_key_size_and_table_index’: events 5-7
                  |
                  |  125 | static void __CGL_hashtable_get_key_size_and_table_index(CGL_hashtable* table, size_t* key_size, size_t* hash_table_index, const void* key)
                  |      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                  |      |             |
                  |      |             (5) entry to ‘__CGL_hashtable_get_key_size_and_table_index’
                  |......
                  |  128 |     if(*key_size == 0) *key_size = strlen((const char*)key);
                  |      |       ~                            ~~~~~~~~~~~~~~~~~~~~~~~~
                  |      |       |                            |
                  |      |       |                            (7) ...to here
                  |      |       (6) following ‘true’ branch...
                  |
                ‘__CGL_hashtable_get_key_size_and_table_index’: event 8
                  |
                  |   10 |                            (x < minl ? minl : (x > maxl ? maxl : x))
                  |      |                            ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
                  |      |                                             |
                  |      |                                             (8) following ‘true’ branch...
280098.c:129:17: note: in expansion of macro ‘CGL_utils_clamp’
                  |  129 |     *key_size = CGL_utils_clamp(*key_size, 1, CGL_HASHTABLE_MAX_KEY_SIZE);
                  |      |                 ^~~~~~~~~~~~~~~
                  |
                ‘__CGL_hashtable_get_key_size_and_table_index’: event 9
                  |
                  |  129 |     *key_size = CGL_utils_clamp(*key_size, 1, CGL_HASHTABLE_MAX_KEY_SIZE);
                  |      |                                 ^~~~~~~~~
                  |      |                                 |
                  |      |                                 (9) ...to here
280098.c:10:48: note: in definition of macro ‘CGL_utils_clamp’
                  |   10 |                            (x < minl ? minl : (x > maxl ? maxl : x))
                  |      |                                                ^
                  |
                ‘__CGL_hashtable_get_key_size_and_table_index’: event 10
                  |
                  |  130 |     uint32_t hash = table->hash_function(key, *key_size);
                  |      |                     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                  |      |                     |
                  |      |                     (10) calling ‘CGL_utils_super_fast_hash’ from ‘__CGL_hashtable_get_key_size_and_table_index’
                  |
                  +--> ‘CGL_utils_super_fast_hash’: events 11-14
                         |
                         |   42 |     uint32_t CGL_utils_super_fast_hash(const void* dat, size_t len)
                         |      |              ^~~~~~~~~~~~~~~~~~~~~~~~~
                         |      |              |
                         |      |              (11) entry to ‘CGL_utils_super_fast_hash’
                         |......
                         |   49 |         if (len <= 0 || data == NULL) return 0;
                         |      |            ~  
                         |      |            |
                         |      |            (12) following ‘false’ branch...
                         |   50 | 
                         |   51 |         rem = len & 3;
                         |      |               ~~~~~~~
                         |      |                   |
                         |      |                   (13) ...to here
                         |......
                         |   55 |         for (;len > 0; len--) {
                         |      |               ~~~~~~~
                         |      |                   |
                         |      |                   (14) following ‘true’ branch (when ‘len != 0’)...
                         |
                       ‘CGL_utils_super_fast_hash’: event 15
                         |
                         |   38 |     #define CGL_get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
                         |      |                                                                  ^
                         |      |                                                                  |
                         |      |                                                                  (15) ...to here
280098.c:56:22: note: in expansion of macro ‘CGL_get16bits’
                         |   56 |             hash  += CGL_get16bits (data);
                         |      |                      ^~~~~~~~~~~~~
                         |
                       ‘CGL_utils_super_fast_hash’: events 16-17
                         |
                         |   64 |         switch (rem) {
                         |      |         ^~~~~~
                         |      |         |
                         |      |         (16) following ‘default:’ branch...
                         |......
                         |   80 |         hash ^= hash << 3;
                         |      |                 ~~~~~~~~~
                         |      |                      |
                         |      |                      (17) ...to here
                         |
                  <------+
                  |
                ‘__CGL_hashtable_get_key_size_and_table_index’: event 18
                  |
                  |  130 |     uint32_t hash = table->hash_function(key, *key_size);
                  |      |                     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                  |      |                     |
                  |      |                     (18) returning to ‘__CGL_hashtable_get_key_size_and_table_index’ from ‘CGL_utils_super_fast_hash’
                  |
           <------+
           |
         ‘CGL_hashtable_set’: events 19-20
           |
           |  173 |     __CGL_hashtable_get_key_size_and_table_index(table, &key_size, &hash_table_index, key);
           |      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           |      |     |
           |      |     (19) returning to ‘CGL_hashtable_set’ from ‘__CGL_hashtable_get_key_size_and_table_index’
           |  174 |     CGL_hashtable_entry* entry_ptr = __CGL_hashtable_get_entry_ptr(table, key);
           |      |                                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           |      |                                      |
           |      |                                      (20) calling ‘__CGL_hashtable_get_entry_ptr’ from ‘CGL_hashtable_set’
           |
           +--> ‘__CGL_hashtable_get_entry_ptr’: events 21-22
                  |
                  |  134 | static CGL_hashtable_entry* __CGL_hashtable_get_entry_ptr(CGL_hashtable* table, const void* key)
                  |      |                             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                  |      |                             |
                  |      |                             (21) entry to ‘__CGL_hashtable_get_entry_ptr’
                  |......
                  |  137 |     __CGL_hashtable_get_key_size_and_table_index(table, &key_size, &hash_table_index, key);
                  |      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                  |      |     |
                  |      |     (22) calling ‘__CGL_hashtable_get_key_size_and_table_index’ from ‘__CGL_hashtable_get_entry_ptr’
                  |
                  +--> ‘__CGL_hashtable_get_key_size_and_table_index’: events 23-25
                         |
                         |  125 | static void __CGL_hashtable_get_key_size_and_table_index(CGL_hashtable* table, size_t* key_size, size_t* hash_table_index, const void* key)
                         |      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                         |      |             |
                         |      |             (23) entry to ‘__CGL_hashtable_get_key_size_and_table_index’
                         |......
                         |  128 |     if(*key_size == 0) *key_size = strlen((const char*)key);
                         |      |       ~                            ~~~~~~~~~~~~~~~~~~~~~~~~
                         |      |       |                            |
                         |      |       |                            (25) ...to here
                         |      |       (24) following ‘true’ branch...
                         |
                       ‘__CGL_hashtable_get_key_size_and_table_index’: event 26
                         |
                         |   10 |                            (x < minl ? minl : (x > maxl ? maxl : x))
                         |      |                            ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
                         |      |                                             |
                         |      |                                             (26) following ‘true’ branch...
280098.c:129:17: note: in expansion of macro ‘CGL_utils_clamp’
                         |  129 |     *key_size = CGL_utils_clamp(*key_size, 1, CGL_HASHTABLE_MAX_KEY_SIZE);
                         |      |                 ^~~~~~~~~~~~~~~
                         |
                       ‘__CGL_hashtable_get_key_size_and_table_index’: event 27
                         |
                         |  129 |     *key_size = CGL_utils_clamp(*key_size, 1, CGL_HASHTABLE_MAX_KEY_SIZE);
                         |      |                                 ^~~~~~~~~
                         |      |                                 |
                         |      |                                 (27) ...to here
280098.c:10:48: note: in definition of macro ‘CGL_utils_clamp’
                         |   10 |                            (x < minl ? minl : (x > maxl ? maxl : x))
                         |      |                                                ^
                         |
                       ‘__CGL_hashtable_get_key_size_and_table_index’: event 28
                         |
                         |  130 |     uint32_t hash = table->hash_function(key, *key_size);
                         |      |                     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                         |      |                     |
                         |      |                     (28) calling ‘CGL_utils_super_fast_hash’ from ‘__CGL_hashtable_get_key_size_and_table_index’
                         |
                         +--> ‘CGL_utils_super_fast_hash’: events 29-32
                                |
                                |   42 |     uint32_t CGL_utils_super_fast_hash(const void* dat, size_t len)
                                |      |              ^~~~~~~~~~~~~~~~~~~~~~~~~
                                |      |              |
                                |      |              (29) entry to ‘CGL_utils_super_fast_hash’
                                |......
                                |   49 |         if (len <= 0 || data == NULL) return 0;
                                |      |            ~  
                                |      |            |
                                |      |            (30) following ‘false’ branch...
                                |   50 | 
                                |   51 |         rem = len & 3;
                                |      |               ~~~~~~~
                                |      |                   |
                                |      |                   (31) ...to here
                                |......
                                |   55 |         for (;len > 0; len--) {
                                |      |               ~~~~~~~
                                |      |                   |
                                |      |                   (32) following ‘true’ branch (when ‘len != 0’)...
                                |
                              ‘CGL_utils_super_fast_hash’: event 33
                                |
                                |   38 |     #define CGL_get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
                                |      |                                                                  ^
                                |      |                                                                  |
                                |      |                                                                  (33) ...to here
280098.c:56:22: note: in expansion of macro ‘CGL_get16bits’
                                |   56 |             hash  += CGL_get16bits (data);
                                |      |                      ^~~~~~~~~~~~~
                                |
                              ‘CGL_utils_super_fast_hash’: events 34-35
                                |
                                |   64 |         switch (rem) {
                                |      |         ^~~~~~
                                |      |         |
                                |      |         (34) following ‘default:’ branch...
                                |......
                                |   80 |         hash ^= hash << 3;
                                |      |                 ~~~~~~~~~
                                |      |                      |
                                |      |                      (35) ...to here
                                |
                         <------+
                         |
                       ‘__CGL_hashtable_get_key_size_and_table_index’: event 36
                         |
                         |  130 |     uint32_t hash = table->hash_function(key, *key_size);
                         |      |                     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                         |      |                     |
                         |      |                     (36) returning to ‘__CGL_hashtable_get_key_size_and_table_index’ from ‘CGL_utils_super_fast_hash’
                         |
                  <------+
                  |
                ‘__CGL_hashtable_get_entry_ptr’: event 37
                  |
                  |  137 |     __CGL_hashtable_get_key_size_and_table_index(table, &key_size, &hash_table_index, key);
                  |      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                  |      |     |
                  |      |     (37) returning to ‘__CGL_hashtable_get_entry_ptr’ from ‘__CGL_hashtable_get_key_size_and_table_index’
                  |
           <------+
           |
         ‘CGL_hashtable_set’: events 38-39
           |
           |  174 |     CGL_hashtable_entry* entry_ptr = __CGL_hashtable_get_entry_ptr(table, key);
           |      |                                      ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           |      |                                      |
           |      |                                      (38) returning to ‘CGL_hashtable_set’ from ‘__CGL_hashtable_get_entry_ptr’
           |  175 |     if(entry_ptr)
           |      |       ~                               
           |      |       |
           |      |       (39) following ‘false’ branch (when ‘entry_ptr’ is NULL)...
           |
         ‘CGL_hashtable_set’: events 40-41
           |
           |  188 |         entry.set = true;
           |      |                   ^
           |      |                   |
           |      |                   (40) ...to here
           |......
           |  194 |         if(value_size > 0)
           |      |           ~        
           |      |           |
           |      |           (41) following ‘true’ branch (when ‘value_size != 0’)...
           |
         ‘CGL_hashtable_set’: event 42
           |
           |   12 |     #define CGL_malloc(size) malloc(size)
           |      |                              ^~~~~~~~~~~~
           |      |                              |
           |      |                              (42) ...to here
280098.c:196:27: note: in expansion of macro ‘CGL_malloc’
           |  196 |             entry.value = CGL_malloc(value_size);
           |      |                           ^~~~~~~~~~
           |
         ‘CGL_hashtable_set’: events 43-44
           |
           |  199 |         if(table->entries[hash_table_index].set)
           |      |           ^
           |      |           |
           |      |           (43) following ‘true’ branch...
           |  200 |         {
           |  201 |             CGL_hashtable_entry* entry_to_place = &table->entries[hash_table_index];
           |      |                                                    ~~~~~~~~~~~~~~
           |      |                                                         |
           |      |                                                         (44) ...to here
           |
         ‘CGL_hashtable_set’: event 45
           |
           |   12 |     #define CGL_malloc(size) malloc(size)
           |      |                              ^~~~~~~~~~~~
           |      |                              |
           |      |                              (45) allocated here
280098.c:204:64: note: in expansion of macro ‘CGL_malloc’
           |  204 |             entry_to_place->next_entry = (CGL_hashtable_entry*)CGL_malloc(sizeof(CGL_hashtable_entry));
           |      |                                                                ^~~~~~~~~~
           |
         ‘CGL_hashtable_set’: event 46
           |
           |  205 |             memcpy(entry_to_place->next_entry, &entry, sizeof(CGL_hashtable_entry));
           |      |                    ~~~~~~~~~~~~~~^~~~~~~~~~~~
           |      |                                  |
           |      |                                  (46) ‘<unknown>’ leaks here; was allocated at (45)
           |

Use Valgrind to help find memory errors

Valgrind is a useful tool to spot leaks, use-after-free, double-free and lots of other errors. With the provided main(), it reveals this leak:

valgrind --leak-check=full ./280098 
==129433== Memcheck, a memory error detector
==129433== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==129433== Using Valgrind-3.19.0 and LibVEX; rerun with -h for copyright info
==129433== Command: ./280098
==129433== 
Age : 18
Float Data : 454.485413
Name : Jaysmito
Name 2 : Jack
==129433== 
==129433== HEAP SUMMARY:
==129433==     in use at exit: 9 bytes in 1 blocks
==129433==   total heap usage: 7 allocs, 6 frees, 2,961,086 bytes allocated
==129433== 
==129433== 9 bytes in 1 blocks are definitely lost in loss record 1 of 1
==129433==    at 0x48437B4: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==129433==    by 0x10977F: CGL_hashtable_set (280098.c:196)
==129433==    by 0x109AB2: main (280098.c:255)
==129433== 
==129433== LEAK SUMMARY:
==129433==    definitely lost: 9 bytes in 1 blocks
==129433==    indirectly lost: 0 bytes in 0 blocks
==129433==      possibly lost: 0 bytes in 0 blocks
==129433==    still reachable: 0 bytes in 0 blocks
==129433==         suppressed: 0 bytes in 0 blocks
==129433== 
==129433== For lists of detected and suppressed errors, rerun with: -s
==129433== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

Consider a singly-linked list

We take the trouble to maintain prev_entry pointers in our list nodes, but never actually use them. We could make our nodes smaller, and our code faster, by using a simpler forward-list instead.

\$\endgroup\$
3
\$\begingroup\$

(Intending not to go into general pros and cons of hash table implementation.
Listing problems looks a bit like there isn't good (like declaring several parameters pointer to const) -
Consider anything not mentioned
Looking innocent enough, at least.)

  • What does specifying a table_size of 7 or 4711 in CGL_hashtable_create() mean? Does that limit the number of entries possible? Does the implementation go to lengths to keep a tolerable collision ratio for that many entries?
    Or as key_size? (Hint: It does not mean that many bytes will be compared.)
    Will key and/or value specified in CGL_hashtable_set() be copied, so the caller is free to subsequently change at least "the key"?
    → Document your code. In the code, preferably.
    I see an interface problem in CGL_hashtable_get() not getting an output buffer size, inviting overruns.

  • struct declarations:
    • old wisdom suggested to declare members in order of decreasing size to minimise alignment overhead.
    • C99 allows the last member to be an array of unknown size.
    This allows for keys not limited by any compile-time #define at some additional hassle.
    (Starting with table->entries no longer being an array of structs, but of pointers.
    Which may have general pros.)

  • __CGL_hashtable_entry_destroy():
    • Double underscore names are reserved for "standard" library use - I forget the details.
    • The NULL-checks are redundant: Consider getting rid of one of them.
    • The destroy flag is dispensable: You can check entry to be inside table->entries.
    • The paranoid set pointers to NULL or garbage after specifying them in free().

  • __CGL_hashtable_get_key_size_and_table_index():
    Using strlen((const char*)key) is one too few:
    Prefixes match longer strings.

  • __CGL_hashtable_get_entry_ptr():
    Doesn't check current_entry.set.

  • CGL_hashtable_create():
    Doesn't check allocation results.
    Far-out parameter values go silent.

  • CGL_hashtable_set():
    • Just overwrites entry_ptr->value … -
    this probably is the leak valgrind reported (there may be more).
    • … in duplicated code: avoidably hard to maintain.
    • Doesn't check allocation results.
    • I don't like "pre-filling" a struct and copying it once you know the destination.

  • CGL_hashtable_remove():
    Doesn't update entry->next_entry->prev_entry.
    This spells trouble when removing the formerly next entry, too.

  • Usage:

    • Never checks the result of CGL_hashtable_get():
      • Keys not found go unnoticed.
      • doesn't limit the number of characters printed in
      printf("Name…: %s\n", buffer)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.