Quick actions

cmd+k|ctrl+k

Navigation

Languages

Fixed size array only hash table

Snippet info

Language

Cpp

Visibility

public

Author

evine

Created

2018-03-30T01:29:24Z

Updated

2018-03-30T10:08:25Z

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
// Fixed size array only hash table
// How do I know empty?

void p(int v) {
    printf("%i\n", v);
}

void p(char *v) {
    printf("%s\n", v);
}

uint32_t f(void *data, size_t size) {
    return *(int *)data;
}

struct Rae {
    int k;
    char *v;
};

Rae *init(size_t count, int empty) {
    Rae *t = (Rae *)malloc(32 * sizeof(Rae));
    for(uint32_t i = 0; i < count; ++i) {
        t[i].k = empty;
    }
    
    return t;
}

bool add(Rae *t, uint32_t (*f)(void *, size_t), size_t count, int empty, int k, char *v) {
    uint32_t hash = f(&k, sizeof(k));
    for(uint32_t i_ = 0; i_ < count; ++i_) {
        uint32_t i = (i_ + hash) & (count - 1);
        if(t[i].k == empty) {
            t[i].k = k;
            t[i].v = v;
            return false;
        } else if(t[i].k == k) {
            t[i].k = k;
            t[i].v = v;
            return true;
        }
    }
    
    assert(0 && "Out of space");
    return false;
}
/*
    xor eax, eax
    
    mov mask, count
    dec mask
    mov i_raw, slot
    mov end, slot
    add end, count

loop_inc:
    inc i_raw
    cmp i_raw, end
    jae out_of_space
    mov i, i_raw
    and i, mask
    
    cmp m.k, empty
    je loop_inc
    cmp m.k, key
    jne loop_inc
    inc rax
enter:
    mov m.k, k
    mov m.v, v
    ret
out_of_space:
    int 3
    ret

*/


char *get(Rae *t, uint32_t (*f)(void *, size_t), size_t count, int empty, int k) {
    uint32_t hash = f(&k, sizeof(k));
    for(uint32_t i_ = 0; i_ < count; ++i_) {
        uint32_t i = (i_ + hash) & (count - 1);
        if(t[i].k == k) {
            return t[i].v;
        }
    }
    
    return 0;
}

int main() {
    size_t count = 32;
    Rae *t = init(count, -1);
    add(t, f, count, -1, 20, "Tera");
    add(t, f, count, -1, 20, "Virk");
    add(t, f, count, -1, 52, "Hello");
    add(t, f, count, -1, 22, "ets");
    char *v = get(t, f, count, -1, 20);
    p(v);
    
    
    free(t);
    return 0;
}
INFO