#include "mtable.h"

#include <stdlib.h>

#include <string.h>

#include <stdio.h>

#define mtable_left_index(k, e)   ((~((1<<(e))-1) & (k))>>(e))

#define mtable_right_index(k, e)  (((1<<(e))-1) & (k))

static void *

mallocc(size_t size)

{

    void *p = malloc(size);

    if(p == NULL) {

        fprintf(stderr, "out of memory\n");

        abort();

    }

    return p;

}

static mtable_t 

mtable_new2(int *exponents)

{

    void **p = mallocc(sizeof(void *) * (1 + (1<

    p[0] = exponents;

    memset(p+1, 0, sizeof(void *) * (1<

    return (mtable_t) p;

}

mtable_t 

mtable_new(int *exponents)

{

    int n;

    int *exponents_copy;

    for(n=0; exponents[n++] != 0; );

    exponents_copy = mallocc(sizeof(int) * n);

    while(n > 0) {

        n--;

        exponents_copy[n] = exponents[n];

    }

    return mtable_new2(exponents_copy);

}

static void 

mtable_delete2(mtable_t mtab, int e_sum, int start)

{

    if(mtab->exponents[1] != 0) {

        int k;

        int e = mtab->exponents[0];

        void **p = &(mtab->slots[0]);

        for(k=0; k<(1<

            if(*p != NULL)

                mtable_delete2(*p, e_sum-e, start+(k<<(e_sum-e)));

            p++;

        }

    }

    free(mtab);

}

void 

mtable_delete(mtable_t mtab)

{

    int i, e_sum=0, *exponents;

    for(i=0; mtab->exponents[i] != 0; i++)

        e_sum += mtab->exponents[i];

    exponents = mtab->exponents;

    mtable_delete2(mtab, e_sum, 0);

    free(exponents);

}

#if 0

static void

mtable_change_exponents(mtable_t mtab, int *exponents)

{

    if(mtab->exponents[1] != 0) {

        int k;

        int e = mtab->exponents[0];

        void **p = &(mtab->slots[0]);

        for(k=0; k<(1<

            if(*p != NULL)

                mtable_change_exponents(*p, exponents+1);

            p++;

        }

    }

    mtab->exponents = exponents;

}

mtable_t

mtable_extend(mtable_t mtab, int *exponents)

{

    struct mtable *p;

    int *all_exponents, *old_exponents;

    int n = 0;

    int i = 0;

    for(n=0; exponents[n++] != 0; );

    for(i=0; mtab->exponents[i++] != 0; );

    all_exponents = mallocc(sizeof(int) * (n-1+i));

    for(i=0; exponents[i] != 0; i++)

        all_exponents[i] = exponents[i];

    for(i=0; mtab->exponents[i] != 0; i++)

        all_exponents[n-1+i] = mtab->exponents[i];

    all_exponents[n-1+i] = 0;

    p = mtable_new2(exponents);

    mtable_set(p, 0, mtab);

    old_exponents = mtab->exponents;

    mtable_change_exponents(p, all_exponents);

    mtable_change_exponents(mtab, all_exponents+n-1);

    free(old_exponents);

    return p;

}

#endif

void

mtable_set(mtable_t mtab, mtable_key key, void *data)

{

    int i, e=0;

    struct mtable *p;

    mtable_key k;

    for(i=0; mtab->exponents[i] != 0; i++)

        e += mtab->exponents[i];

    p = mtab;

    k = key;

    for(;;) {

        if(p->exponents[1] == 0) {

            p->slots[k] = data;

            return;

        } else {

            e -= p->exponents[0];

            i = mtable_left_index(k, e);

            k = mtable_right_index(k, e);

            if(p->slots[i] == NULL) 

                p->slots[i] = mtable_new2(p->exponents+1);

            p = p->slots[i];

        }

    }

}

void 

*mtable_get(mtable_t mtab, mtable_key key)

{

    int i, e=0;

    struct mtable *p;

    mtable_key k;

    for(i=0; mtab->exponents[i] != 0; i++)

        e += mtab->exponents[i];

    p = mtab;

    k = key;

    while(p != NULL) {

        if(p->exponents[1] == 0) {

            return p->slots[k];

        } else {

            e -= p->exponents[0];

            i = mtable_left_index(k, e);

            k = mtable_right_index(k, e);

            p = p->slots[i];

        }

    }

    return NULL;

}