1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
// WARNING: there is a system header by this name
#ifndef DB_H
#define DB_H
# include "sanity.h"
# include <stdarg.h>
/// Number of tree roots
// Somewhat arbitrary - larger wastes more space but is faster for large trees
// num % HASH_SIZE minimize collisions even for similar num
# define HASH_SIZE (256+27)
typedef enum dbn_color
{
RED,
BLACK
} dbn_color;
typedef intptr_t numdb_key_t;
typedef union db_key_t
{
char *ms __attribute__((deprecated));
const char* s;
numdb_key_t i;
} db_key_t;
typedef void* db_val_t;
typedef uint32_t hash_t;
typedef void (*db_func_t)(db_key_t, db_val_t, va_list);
/// DataBase Node
struct dbn
{
struct dbn *parent, *left, *right;
dbn_color color;
db_key_t key;
db_val_t data;
};
typedef enum dbt_type
{
DB_NUMBER,
DB_STRING,
} dbt_type;
/// DataBase Table
struct dbt
{
dbt_type type;
/// Note, before replacement, key/values to be replaced
// TODO refactor to decrease/eliminate the uses of this?
void (*release) (db_key_t, db_val_t) __attribute__((deprecated));
/// Maximum length of a string key - TODO refactor to ensure all strings are NUL-terminated
size_t maxlen __attribute__((deprecated));
/// The root trees
struct dbn *ht[HASH_SIZE];
};
# define strdb_search(t,k) db_search((t),(db_key_t)(k))
# define strdb_insert(t,k,d) db_insert((t),(db_key_t)(k),(db_val_t)(d))
# define strdb_erase(t,k) db_erase ((t),(db_key_t)(k))
# define strdb_foreach db_foreach
# define strdb_final db_final
# define numdb_search(t,k) db_search((t),(db_key_t)(k))
# define numdb_insert(t,k,d) db_insert((t),(db_key_t)(k),(db_val_t)(d))
# define numdb_erase(t,k) db_erase ((t),(db_key_t)(k))
# define numdb_foreach db_foreach
# define numdb_final db_final
/// Create a map from char* to void*, with strings possibly not null-terminated
struct dbt *strdb_init (size_t maxlen);
/// Create a map from int to void*
struct dbt *numdb_init (void);
/// Return the value corresponding to the key, or NULL if not found
db_val_t db_search (struct dbt *table, db_key_t key);
/// Add or replace table[key] = data
// if it was already there, call release
struct dbn *db_insert (struct dbt *table, db_key_t key, db_val_t data);
/// Remove a key from the table, returning the data
db_val_t db_erase (struct dbt *table, db_key_t key);
/// Execute a function for every element, in unspecified order
void db_foreach (struct dbt *, db_func_t, ...);
// opposite of init? Calls release for every element and frees memory
// This probably isn't really needed: we don't have to free memory while exiting
void db_final (struct dbt *, db_func_t, ...) __attribute__((deprecated));
#endif
|
