Skip to content

Instantly share code, notes, and snippets.

@1devm0
Last active December 3, 2023 05:45

Revisions

  1. 1devm0 revised this gist Jun 20, 2023. 1 changed file with 22 additions and 24 deletions.
    46 changes: 22 additions & 24 deletions table.c
    Original file line number Diff line number Diff line change
    @@ -47,7 +47,7 @@ typedef struct _ht_i32_item_t {
    struct _ht_i32_item_t * next; // linked list
    } ht_i32_item_t;

    ht_i32_item_t * ht_mk_i32_item(const char * id, const i32 data) {
    ht_i32_item_t * ht_mk_i32_item(char * id, i32 data) {
    ht_i32_item_t * i = calloc(1, sizeof(ht_i32_item_t));
    i -> id = strdup(id);
    i -> data = data;
    @@ -63,14 +63,14 @@ typedef struct {
    } ht_i32_t;

    // Declarations
    void ht_i32_mk(ht_i32_t * table, const u64 sz);
    void ht_i32_mk(ht_i32_t * table, u64 sz);
    void ht_i32_resize(ht_i32_t * table);
    void ht_i32_add(ht_i32_t * table, const char * id, const i32 data);
    i32 ht_i32_get(ht_i32_t * table, const char * id);
    void ht_i32_add(ht_i32_t * table, char * id, i32 data);
    i32 ht_i32_get(ht_i32_t * table, char * id);
    void ht_i32_rm(ht_i32_t * table);

    // Implementation
    void ht_i32_mk(ht_i32_t * table, const u64 sz) {
    void ht_i32_mk(ht_i32_t * table, u64 sz) {
    // prime numbers
    table -> sz = next_prime(sz);
    table -> e = calloc(table -> sz, sizeof(ht_i32_item_t));
    @@ -80,47 +80,42 @@ void ht_i32_mk(ht_i32_t * table, const u64 sz) {

    u32 collisions = 0;

    void ht_i32_add(ht_i32_t * table, const char * id, const i32 data) {

    void ht_i32_add(ht_i32_t * table, char * id, i32 data) {
    ht_i32_item_t * i = ht_mk_i32_item(id, data);

    ht_i32_resize(table);

    u64 hash = hash_id(id);
    u64 idx = hash_id(id) % table -> sz;
    table -> used++;

    // Scenario 1: NULL -> current = i
    if (!table -> e[idx]) {
    table -> e[idx] = i;
    table -> used++;
    return;
    }

    // Scenario 2: Key exists
    // Scenario 2 + 3: Key exists or True Collision
    ht_i32_item_t * current = table -> e[idx];
    while (strcmp(id, current -> id) && current -> next) {
    while (current -> next && strcmp(id, current -> id)) {
    current = current -> next;
    }
    if (!strcmp(id, current -> id) && current) {
    if (!strcmp(id, current -> id)) {
    free(table -> e[idx]);
    table -> e[idx] = i;
    return;
    }

    // Scenario 3: COLLISION
    collisions++;
    current = table -> e[idx];
    while (current -> next) {
    current = current -> next;
    }
    current -> next = i;
    current -> next = i;
    table -> used++;
    return;
    }

    #define LOAD_FACTOR 0.5
    #define LOAD_FACTOR 0.75
    void ht_i32_resize(ht_i32_t * table) {
    if ((f32) table -> used / table -> sz > LOAD_FACTOR) {
    ht_i32_t * n = calloc(1, sizeof(ht_i32_t));
    ht_i32_mk(n, table -> sz * 3);
    ht_i32_mk(n, table -> sz * 3.5);
    for (u64 u = 0; u < table -> sz; u++) {
    ht_i32_item_t * current = table -> e[u];
    while (current){
    @@ -136,7 +131,7 @@ void ht_i32_resize(ht_i32_t * table) {
    }


    i32 ht_i32_get(ht_i32_t * table, const char * id) {
    i32 ht_i32_get(ht_i32_t * table, char * id) {
    u64 idx = hash_id(id) % table -> sz;

    // 1: return current_item;
    @@ -180,9 +175,11 @@ i32 main() {


    char * str = calloc(24, sizeof(char));
    for (i32 u = 0; u < 10000; u++) {
    ht_i32_add(&table, rand_string(str, 20), u);
    for (i32 u = 0; u < 1e4; u++) {
    str = rand_string(str, 20);
    ht_i32_add(&table, str, u);
    }
    ht_i32_add(&table, rand_string(str, 20),100);

    // ht_get
    u32 storage = 0;
    @@ -198,4 +195,5 @@ i32 main() {

    ht_i32_rm(&table);
    return 0;
    }
    }

  2. 1devm0 revised this gist Jun 19, 2023. No changes.
  3. 1devm0 revised this gist Jun 19, 2023. 1 changed file with 6 additions and 2 deletions.
    8 changes: 6 additions & 2 deletions table.c
    Original file line number Diff line number Diff line change
    @@ -96,15 +96,19 @@ void ht_i32_add(ht_i32_t * table, const char * id, const i32 data) {
    }

    // Scenario 2: Key exists
    if (!strcmp(id, table -> e[idx] -> id)) {
    ht_i32_item_t * current = table -> e[idx];
    while (strcmp(id, current -> id) && current -> next) {
    current = current -> next;
    }
    if (!strcmp(id, current -> id) && current) {
    free(table -> e[idx]);
    table -> e[idx] = i;
    return;
    }

    // Scenario 3: COLLISION
    collisions++;
    ht_i32_item_t * current = table -> e[idx];
    current = table -> e[idx];
    while (current -> next) {
    current = current -> next;
    }
  4. 1devm0 revised this gist Jun 19, 2023. 1 changed file with 7 additions and 7 deletions.
    14 changes: 7 additions & 7 deletions table.c
    Original file line number Diff line number Diff line change
    @@ -47,7 +47,7 @@ typedef struct _ht_i32_item_t {
    struct _ht_i32_item_t * next; // linked list
    } ht_i32_item_t;

    ht_i32_item_t * ht_mk_i32_item(char * id, i32 data) {
    ht_i32_item_t * ht_mk_i32_item(const char * id, const i32 data) {
    ht_i32_item_t * i = calloc(1, sizeof(ht_i32_item_t));
    i -> id = strdup(id);
    i -> data = data;
    @@ -63,14 +63,14 @@ typedef struct {
    } ht_i32_t;

    // Declarations
    void ht_i32_mk(ht_i32_t * table, u64 sz);
    void ht_i32_mk(ht_i32_t * table, const u64 sz);
    void ht_i32_resize(ht_i32_t * table);
    void ht_i32_add(ht_i32_t * table, char * id, i32 data);
    i32 ht_i32_get(ht_i32_t * table, char * id);
    void ht_i32_add(ht_i32_t * table, const char * id, const i32 data);
    i32 ht_i32_get(ht_i32_t * table, const char * id);
    void ht_i32_rm(ht_i32_t * table);

    // Implementation
    void ht_i32_mk(ht_i32_t * table, u64 sz) {
    void ht_i32_mk(ht_i32_t * table, const u64 sz) {
    // prime numbers
    table -> sz = next_prime(sz);
    table -> e = calloc(table -> sz, sizeof(ht_i32_item_t));
    @@ -80,7 +80,7 @@ void ht_i32_mk(ht_i32_t * table, u64 sz) {

    u32 collisions = 0;

    void ht_i32_add(ht_i32_t * table, char * id, i32 data) {
    void ht_i32_add(ht_i32_t * table, const char * id, const i32 data) {
    ht_i32_item_t * i = ht_mk_i32_item(id, data);

    ht_i32_resize(table);
    @@ -132,7 +132,7 @@ void ht_i32_resize(ht_i32_t * table) {
    }


    i32 ht_i32_get(ht_i32_t * table, char * id) {
    i32 ht_i32_get(ht_i32_t * table, const char * id) {
    u64 idx = hash_id(id) % table -> sz;

    // 1: return current_item;
  5. 1devm0 created this gist Jun 19, 2023.
    197 changes: 197 additions & 0 deletions table.c
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,197 @@
    #include <stdio.h>
    #include <stdint.h>
    #include <stdlib.h>
    #include <string.h>
    #include <math.h>

    typedef uint8_t u08;
    typedef uint32_t u32;
    typedef uint64_t u64;
    typedef int32_t i32;
    typedef float f32;
    typedef double f64;

    // PRIME NUMBERS
    i32 is_prime(const i32 x) {
    if (x < 2) { return -1; }
    if (x < 4) { return 1; }
    if ((x % 2) == 0) { return 0; }
    for (i32 i = 3; i <= floor(sqrt((f64) x)); i+= 2) {
    if ((x % i) == 0) {
    return 0;
    }
    }
    return 1;
    }

    i32 next_prime(i32 x) {
    while (is_prime(x) != 1) {
    x++;
    }
    return x;
    }

    // FNV-1a hashing function
    u64 hash_id(const char * id) {
    u64 hash = 0xcbf29ce484222325; // FNV_offset_basis: 14695981039346656037
    while (*id) hash = (hash ^ (u08)*id++) * 0x100000001b3; // FNV_prime: 1099511628211
    return hash;
    }



    // key: string, value: i32
    typedef struct _ht_i32_item_t {
    char * id;
    i32 data;
    struct _ht_i32_item_t * next; // linked list
    } ht_i32_item_t;

    ht_i32_item_t * ht_mk_i32_item(char * id, i32 data) {
    ht_i32_item_t * i = calloc(1, sizeof(ht_i32_item_t));
    i -> id = strdup(id);
    i -> data = data;
    i -> next = NULL;
    return i;
    }


    typedef struct {
    ht_i32_item_t ** e; // elements
    u64 used;
    u64 sz;
    } ht_i32_t;

    // Declarations
    void ht_i32_mk(ht_i32_t * table, u64 sz);
    void ht_i32_resize(ht_i32_t * table);
    void ht_i32_add(ht_i32_t * table, char * id, i32 data);
    i32 ht_i32_get(ht_i32_t * table, char * id);
    void ht_i32_rm(ht_i32_t * table);

    // Implementation
    void ht_i32_mk(ht_i32_t * table, u64 sz) {
    // prime numbers
    table -> sz = next_prime(sz);
    table -> e = calloc(table -> sz, sizeof(ht_i32_item_t));
    table -> used = 0;
    }


    u32 collisions = 0;

    void ht_i32_add(ht_i32_t * table, char * id, i32 data) {
    ht_i32_item_t * i = ht_mk_i32_item(id, data);

    ht_i32_resize(table);

    u64 hash = hash_id(id);
    u64 idx = hash_id(id) % table -> sz;
    table -> used++;

    // Scenario 1: NULL -> current = i
    if (!table -> e[idx]) {
    table -> e[idx] = i;
    return;
    }

    // Scenario 2: Key exists
    if (!strcmp(id, table -> e[idx] -> id)) {
    free(table -> e[idx]);
    table -> e[idx] = i;
    return;
    }

    // Scenario 3: COLLISION
    collisions++;
    ht_i32_item_t * current = table -> e[idx];
    while (current -> next) {
    current = current -> next;
    }
    current -> next = i;
    return;
    }

    #define LOAD_FACTOR 0.5
    void ht_i32_resize(ht_i32_t * table) {
    if ((f32) table -> used / table -> sz > LOAD_FACTOR) {
    ht_i32_t * n = calloc(1, sizeof(ht_i32_t));
    ht_i32_mk(n, table -> sz * 3);
    for (u64 u = 0; u < table -> sz; u++) {
    ht_i32_item_t * current = table -> e[u];
    while (current){
    ht_i32_add(n, current -> id, current -> data);
    current = current -> next;
    }
    }
    ht_i32_rm(table);
    table -> e = n -> e;
    table -> sz = n -> sz;
    table -> used = n -> used;
    }
    }


    i32 ht_i32_get(ht_i32_t * table, char * id) {
    u64 idx = hash_id(id) % table -> sz;

    // 1: return current_item;
    // 2: return traverse(list, id);
    ht_i32_item_t * current = table -> e[idx];
    while (current) {
    if (!strcmp(id, current -> id)) {
    return current -> data;
    }
    current = current -> next;
    }
    return INT32_MAX;
    }

    void ht_i32_rm(ht_i32_t * table) {
    free(table -> e);
    table -> e = NULL;
    table -> sz = 0;
    table -> used = 0;
    }


    // Copied from some StackOverflow thread
    static char *rand_string(char *str, size_t size)
    {
    const char charset[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    if (size) {
    --size;
    for (size_t n = 0; n < size; n++) {
    int key = rand() % (int) (sizeof charset - 1);
    str[n] = charset[key];
    }
    str[size] = '\0';
    }
    return str;
    }

    i32 main() {
    ht_i32_t table;
    ht_i32_mk(&table, 200);


    char * str = calloc(24, sizeof(char));
    for (i32 u = 0; u < 10000; u++) {
    ht_i32_add(&table, rand_string(str, 20), u);
    }

    // ht_get
    u32 storage = 0;
    printf("%u\n", table.used);
    for (u32 u = 0; u < table.sz; u++) {
    ht_i32_item_t * current = table.e[u];
    while (current) {
    storage++;
    current = current -> next;
    }
    }
    printf("Retrieved: %u, Collisions: %u\n", storage, collisions);

    ht_i32_rm(&table);
    return 0;
    }