CTable | Frank Mitchell's Blog

MODIFIED 2023-07-23: As coding began I hit upon a radical simplification of the C_Table interface. Expect more over the next few weeks.

While planning CPort, M-Strings, and other projects I identified a need for some even more basic portable utilities.

C_Symbol needs a simple but solid hashtable implementation. To avoid unnecessary dependencies, we will provide our own.

The table accepts three types of keys:

A void * compared by pointer value.
A const char * compared by string value (strcmp).
A C_Userdata struct compared by binary equivalence or a custom comparison function.

Values may likewise include an unmanaged void *, an unmanaged const char*, or managed C_Userdata structs stored and retrieved by deep copy.

Examples

Creating a Table

C_Table* t;

C_Table_new(&t, 50);

ASSERT(t != NULL);

Storing Keys

C_Userdata key, val;

C_Userdata_set_string(&key, "foo");
C_Userdata_set_pointer(&val, xptr);

C_Table_put(t, &key, &val);

The put functions write the new value, overwriting any previous value.

The add functions only write a value it the key is not in the table. They return false if a value already exists.

Retrieving Keys

C_Userdata key, val;

C_Userdata_set_string(&key, "foo");

C_Table_get(t, &key, &val);

ASSERT(val.ptr == xptr);
ASSERT(val.len == 0);
ASSERT(val.tag == 0);

Iterating Over Keys

C_Table_Iterator* iter;

C_Table_new_iterator(t, &iter);

for (; !C_Table_Iterator_at_end(iter) ; C_Table_Iterator_next()) {
    C_Userdata* key;
    C_Userdata* val;

    C_Table_Iterator_current_pair(iter, &key, &val);

    /* do something with the key and value */
}

C_Table_Iterator_del(&iter);

Deleting a Table

C_Table_del(&t);

ASSERT(t == NULL);

API

Basic Types

#include <stddef.h>   /* defines size_t */
#include <stdbool.h>  /* defines bool */
#include <stdint.h>   /* defines {,u}intN_t */


typedef struct _C_Table          C_Table;
typedef struct _C_Table_Iterator C_Table_Iterator;

Table Functions

void C_Table_new(C_Table* *tptr, int size_t minsz);

void C_Table_define_userdata_eq(C_Table* t, C_Userdata_Eq);

void C_Table_define_userdata_copy(C_Table* t, C_Userdata_Copy);

void C_Table_define_userdata_free(C_Table* t, C_Userdata_Free);

bool C_Table_add(C_Table* t, const C_Userdata* key, const C_Userdata* value);

bool C_Table_get(C_Table* t, const C_Userdata* key, C_Userdata* value);

bool C_Table_has(C_Table* t, const C_Userdata* key);

void C_Table_put(C_Table* t, const C_Userdata* key, const C_Userdata* value);

bool C_Table_remove(C_Table* t, const C_Userdata* key);

void C_Table_del(C_Table* *tptr);

Iterator Functions

void C_Table_new_iterator(C_Table* t, C_Table_Iterator* *iptr);

bool C_Table_Iterator_at_end(C_Table_Iterator* i);

void C_Table_Iterator_next(C_Table_Iterator* i);

bool C_Table_Iterator_current_key(C_Table_Iterator* i, C_Userdata* *key);

bool C_Table_Iterator_current_pair(C_Table_Iterator* i, 
                                    const C_Userdata* *keyptr, 
                                    C_Userdata* *valptr);

bool C_Table_Iterator_remove_current(C_Table_Iterator* i);

bool C_Table_Iterator_del(C_Table_Iterator* *iptr);

Userdata Type

typedef unsigned int tag_t;

typedef struct _ctbl_userdata {
    tag_t   tag;    /* identifies type */
    size_t  len;    /* size of (*ptr) */
    void*   ptr;    /* pointer to data */
} C_Userdata;

typedef bool (C_Userdata_Eq)(const C_Userdata* a, const C_Userdata* b);

typedef void (C_Userdata_Copy)(const C_Userdata* a, const C_Userdata* (*bptr));

typedef void (C_Userdata_Free)(C_Userdata* a);

/** Clears all values in struct */
void C_Userdata_clear(C_Userdata* *udptr);

/** Allocates and sets new userdata contents into existing struct. */
void C_Userdata_set(C_Userdata* ud, tag_t tag, size_t len, const void* ptr);

/** Sets the pointer *value* into the structg. */
void C_Userdata_set_pointer(C_Userdata* ud, const void* ref);

/** Sets the null-terminated string into the struct. */
void C_Userdata_set_string(C_Userdata* ud, const char* cptr);

/** 
 * If len is nonzero, sets the contents of `ref` into the struct.
 * Otherwise, sets the pointer *value* of `ref`.
 */
void C_Userdata_set_value(C_Userdata* ud, const void* ptr, size_t len);