turing/table.c

#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>

#include "table.h"

struct table *table_new(int capacity, int increment,
                        item_clone_f clone_f, item_free_f free_f, item_compare_f compare_f, item_repr_f repr_f)
{
    struct table *r;

    r = (struct table *)malloc(sizeof(*r));
    if (r != NULL) {
        r->items = (void **)malloc(capacity*sizeof(void *));
        if (r->items == NULL) {
            free(r);
            return NULL;
        }
        r->indexes = (int *)malloc(capacity*sizeof(int));
        if (r->indexes == NULL) {
            free(r->items);
            free(r);
            return NULL;
        }
        r->size = 0;
        r->capacity = capacity;
        r->increment = increment;
        r->clone_f = clone_f;
        r->free_f = free_f;
        r->compare_f = compare_f;
        r->repr_f = repr_f;
        r->dirty = true;
        r->lookup = NULL;
    }

    return r;
}

void table_free(struct table *t)
{
    if (t->lookup != NULL)
        free(t->lookup);
    if (t->free_f != NULL)
        for (int i=0; i < t->size; i++)
            t->free_f(t->items[i]);
    free(t->indexes);
    free(t->items);
    free(t);
}

static bool table_find_internal(struct table *t, void *entry, int *pos)
{
    int cmp;

    for (*pos=0; *pos < t->size; (*pos)++) {
        cmp = t->compare_f(entry, t->items[*pos]);
        if (cmp == 0)
            return true;
        if (cmp < 0)
            return false;
    }

    return false;
}

int table_find(struct table *t, void *entry)
{
    int pos;

    if (table_find_internal(t, entry, &pos))
        return t->indexes[pos];
    else
        return -1;
}

int table_insert(struct table *t, void *entry)
{
    bool found;
    int pos;
    void **newitems;
    int *newindexes;
    void *swap;
    int swapidx;
    int r;
    int newcapacity;

    found = table_find_internal(t, entry, &pos);

    if (!found) {
        if (t->capacity <= t->size) {
            newcapacity = t->capacity + t->increment;
            newitems = (void **) realloc(
                           t->items, newcapacity*sizeof(void *));
            if (newitems == NULL)
                return -1;
            newindexes = (int *) realloc(
                             t->indexes, newcapacity*sizeof(int));
            if (newindexes == NULL) {
                t->items = (void **) realloc(
                               newitems, t->capacity*sizeof(void *));
                return -1;
            }
            t->items = newitems;
            t->indexes = newindexes;
            t->capacity = newcapacity;
        }
        r = t->size;
        if (t->clone_f != NULL)
            entry = t->clone_f(entry);
        for (int i=pos; i <= t->size; i++) {
            swap = t->items[i];
            swapidx = t->indexes[i];
            t->items[i] = entry;
            t->indexes[i] = r;
            entry = swap;
            r = swapidx;
        }
        t->size++;
        t->dirty = true;
    }

    return t->indexes[pos];
}

void *table_lookup(struct table *t, int idx)
{
    if (t->size < 1)
        return NULL;

    if (t->dirty) {
        t->lookup = realloc(t->lookup, t->size*sizeof(void *));
        // TODO: check allocation
        for (int i=0; i<t->size; i++)
            t->lookup[t->indexes[i]] = t->items[i];
        t->dirty = false;
    }

    return t->lookup[idx];
}

void table_print(struct table *t)
{
    char buf[200];

    printf("size=%d capacity=%d increment=%d\n", t->size, t->capacity, t->increment);
    for (int i=0; i<t->size; i++) {
        if (t->repr_f != NULL)
            t->repr_f(t->items[i], buf, sizeof(buf));
        printf(" %d (%d) %s\n", i, t->indexes[i],
               (t->repr_f != NULL ? buf : "???"));
    }
}