table.c

/*
 * table.c - Functions to manipulate generic tables.
 * Copyright (c) 1997 Andrew W. Appel.
 */

#include "table.h"
#include <stdio.h>
#include "util.h"

#define TABSIZE 127

typedef struct binder_ *binder;
struct binder_ {
    void *key;
    void *value;
    binder next;
    void *prevtop;
};
struct TAB_table_ {
    binder table[TABSIZE];
    void *top;
};

static binder Binder(void *key, void *value, binder next, void *prevtop) {
    binder b = checked_malloc(sizeof(*b));
    b->key = key;
    b->value = value;
    b->next = next;
    b->prevtop = prevtop;
    return b;
}

TAB_table TAB_empty(void) {
    TAB_table t = checked_malloc(sizeof(*t));
    int i;
    t->top = NULL;
    for (i = 0; i < TABSIZE; i++) t->table[i] = NULL;
    return t;
}

/* The cast from pointer to integer in the expression
 *   ((unsigned)key) % TABSIZE
 * may lead to a warning message.  However, the code is safe,
 * and will still operate correctly.  This line is just hashing
 * a pointer value into an integer value, and no matter how the
 * conversion is done, as long as it is done consistently, a
 * reasonable and repeatable index into the table will result.
 */

void TAB_enter(TAB_table t, void *key, void *value) {
    int index;
    assert(t && key);
    index = ((unsigned long)key) % TABSIZE;
    t->table[index] = Binder(key, value, t->table[index], t->top);
    t->top = key;
}

void *TAB_look(TAB_table t, void *key) {
    int index;
    binder b;
    assert(t && key);
    index = ((unsigned long)key) % TABSIZE;
    for (b = t->table[index]; b; b = b->next)
        if (b->key == key) return b->value;
    return NULL;
}

void *TAB_pop(TAB_table t) {
    void *k;
    binder b;
    int index;
    assert(t);
    k = t->top;
    assert(k);
    index = ((unsigned long)k) % TABSIZE;
    b = t->table[index];
    assert(b);
    t->table[index] = b->next;
    t->top = b->prevtop;
    return b->key;
}

void TAB_dump(TAB_table t, void (*show)(void *key, void *value)) {
    void *k = t->top;
    int index = ((unsigned long)k) % TABSIZE;
    binder b = t->table[index];
    if (b == NULL) return;
    t->table[index] = b->next;
    t->top = b->prevtop;
    show(b->key, b->value);
    TAB_dump(t, show);
    assert(t->top == b->prevtop && t->table[index] == b->next);
    t->top = k;
    t->table[index] = b;
}