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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
#ifndef TYPE
#error "Set TYPE before including this file"
#else
#include "err.h"
int CONSTRUCTOR_DECL ( TRIE(TYPE) ) {
NEW(TRIE_NODE(TYPE), t, '\0');
this->root = t;
return 0;
}
int CONSTRUCTOR_DECL (TRIE_NODE(TYPE), char c) {
this->c = c;
this->value = NULL;
this->next = NULL;
this->child = NULL;
return 0;
}
int CONSTRUCTOR_DECL (TRIE_NODE(TYPE),
char c,
TRIE_NODE(TYPE)* next,
TRIE_NODE(TYPE)* child )
{
this->c = c;
this->next = next;
this->child = child;
return 0;
}
int TRIE_PUT(TYPE) ( TRIE(TYPE)* trie, char* key, TYPE* val ) {
TRIE_NODE(TYPE) *cur, *last;
last = trie->root;
cur = last->child;
char* subkey = key;
// --------------------------------------------------
while (1) {
if (cur == NULL) {
/* Build direct LL for remaining subkey */
for (char* c = subkey; c[0] != '\0'; c++) {
NEW(TRIE_NODE(TYPE), t, *c);
last->child = t;
last = t;
}
last->value = val;
return 0;
} else if (cur->c == subkey[0]) {
/* This node belongs to the key,
* Decend further */
last = cur;
cur = cur->child;
subkey++;
} else if (subkey[0] == '\0') {
/* Key finished */
last->value = val;
return 0;
} else if (cur->next != NULL) {
/* This node was not part of the set, but it's sibling might */
cur = cur->next;
/* `last` not set since we aren't moving down */
} else {
/* No node on this level was part of the set, create a new
* sibling and follow down that parse */
NEW(TRIE_NODE(TYPE), t, *subkey);
cur->next = t;
last = cur;
cur = t;
}
}
return 0;
}
/*
* TODO what happens when I give an invalid key?
*/
TYPE* TRIE_GET(TYPE) ( TRIE(TYPE)* trie, char* key ) {
TRIE_NODE(TYPE)* n = trie->root->child;
char* subkey = key;
while (n != NULL) {
if (subkey[1] == '\0') {
return n->value;
} else if (subkey[0] == n->c) {
n = n->child;
subkey++;
} else {
n = n->next;
}
}
ERR("Position not found");
return 0;
}
int TRIE_NODE_FREE(TYPE) ( TRIE_NODE(TYPE)* node ) {
if (node == NULL) return 0;
if (node->value != NULL) FFREE(TYPE, node->value);
if (node->next != NULL) TRIE_NODE_FREE(TYPE)(node->next);
if (node->child != NULL) TRIE_NODE_FREE(TYPE)(node->child);
free (node);
return 0;
}
int TRIE_FREE(TYPE) ( TRIE(TYPE)* trie ) {
return TRIE_NODE_FREE(TYPE)(trie->root);
}
#endif /* TYPE */
// vim: ft=c
|
