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);