Skip to content
Snippets Groups Projects
Select Git revision
  • 9938437729e467f9ac9b809a08273cd42e674b50
  • master default protected
2 results

hm.c

Blame
  • Forked from algorithmique / cours
    Source project has a limited visibility.
    hm.c 2.10 KiB
    #include "hm.h"
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    static int hash(char *key, int capacity) {
        int h = 0;
        for (size_t i = 0; i < strlen(key); ++i) {
            h = (h + key[i] * 43) % capacity;
        }
        return h;
    }
    
    static int rehash(char *key) {
        return 1;
    }
    
    static int find_index(hm h, char *key) {
        int i    = hash(key, h.capacity);
        int init = i;
        while (h.table[i].state != empty &&
               strncmp(h.table[i].key, key, MAX_LEN) != 0) {
            i = (i + rehash(key)) % h.capacity;
            if (i == init) {
                return -1;
            }
        }
        return i;
    }
    
    void hm_init(hm *h, int capacity) {
        h->table    = malloc(capacity * sizeof(cell_t));
        h->capacity = capacity;
        for (int i = 0; i < h->capacity; ++i) {
            h->table[i].state = empty;
        }
    }
    
    void hm_destroy(hm *h) {
        free(h->table);
        h->table    = NULL;
        h->capacity = -1;
    }
    
    bool hm_set(hm *h, char *key, char *value) {
        int i    = hash(key, h->capacity);
        int init = i;
        while (h->table[i].state == occupied &&
               strncmp(h->table[i].key, key, MAX_LEN) != 0) {
            i = (i + rehash(key)) % h->capacity;
            if (i == init) {
                return false;
            }
        }
        if (strncpy(h->table[i].key, key, MAX_LEN) == NULL) {
            return false;
        };
        if (strncpy(h->table[i].value, value, MAX_LEN) == NULL) {
            return false;
        };
        h->table[i].state = occupied;
        return true;
    }
    
    char *hm_get(hm h, char *key) {
        int i = find_index(h, key);
        return (i >= 0 && h.table[i].state == occupied) ? h.table[i].value : NULL;
    }
    
    char *hm_remove(hm *h, char *key) {