#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include "intmap.h"

#define INITIAL_MASK    127
#define SLOT_EMPTY      0xffffffff
#define IS_SLOT_FREE(n) ((n)->key == SLOT_EMPTY)


void _grow(IntMap *imap) {
    uint32_t i, newfill, newmask, slot;
    struct intmap_node *new, *node;
    assert(imap);
    
    /* Create a new table twice the size */
    newfill = 0;
    newmask = (imap->mask << 1) | 1;
    new = malloc(sizeof(struct intmap_node) * (newmask + 1));
    assert(new);
    memset(new, SLOT_EMPTY, sizeof(struct intmap_node) * (newmask + 1));
    
    /* For every item in the old table, put it in the new table */
    for (i = 0; i <= imap->mask; i++) {
        node = imap->table + i;
        if (!IS_SLOT_FREE(node)) {
            slot = node->key & newmask;
            while (1) {
                if (IS_SLOT_FREE(&new[slot])) {
                    new[slot] = *node;
                    newfill++;
                    break;
                }
                slot = (slot + 1) & newmask;
            }
        }
    }
    
    /* Free the old table space and save the new values */
    imap->fill = newfill;
    imap->mask = newmask;
    free(imap->table);
    imap->table = new;
}


void intmap_init(IntMap *imap) {
    assert(imap);
    imap->fill = 0;
    imap->mask = INITIAL_MASK;
    imap->table = malloc(sizeof(struct intmap_node) * (INITIAL_MASK + 1));
    assert(imap->table);
    memset(imap->table, SLOT_EMPTY,
        sizeof(struct intmap_node) * (INITIAL_MASK + 1));
}


void intmap_cleanup(IntMap *imap) {
    assert(imap);
    if (imap->table != NULL)
        free(imap->table);
}


void intmap_put(IntMap *imap, uint32_t key, uint32_t value) {
    uint32_t slot;
    struct intmap_node *node;
    assert(imap);
    assert(key != SLOT_EMPTY);
    if (((double) imap->fill) / imap->mask >= 0.7)
        _grow(imap);
    slot = key & imap->mask;
    while (1) {
        node = imap->table + slot;
        if (IS_SLOT_FREE(node)) {
            node->key = key;
            node->value = value;
            imap->fill++;
            break;
        }
        slot = (slot + 1) & imap->mask;
    }
}


int intmap_get(IntMap *imap, uint32_t key, uint32_t *value) {
    uint32_t count, slot;
    struct intmap_node *node;
    assert(imap);
    assert(key != SLOT_EMPTY);
    slot = key & imap->mask;
    for (count = 0; count <= imap->mask; count++) {
        node = imap->table + slot;
        if (IS_SLOT_FREE(node))
            break;
        else if (node->key == key) {
            if (value != NULL)
                *value = node->value;
            return 1;
        }
    }
    return 0;
}