1.1 --- a/core/sm_trie.cpp Wed Dec 06 14:52:11 2006 +0000
1.2 +++ b/core/sm_trie.cpp Wed Dec 06 23:35:51 2006 +0000
1.3 @@ -118,12 +118,31 @@
1.4 return (unsigned char)c;
1.5 }
1.6
1.7 -unsigned int x_check(Trie *trie, char c)
1.8 +bool sm_trie_grow(Trie *trie)
1.9 +{
1.10 + /* The current # of nodes in the tree is trie->baseSize + 1 */
1.11 + unsigned int curSize = trie->baseSize;
1.12 + unsigned int newSize = curSize * 2;
1.13 +
1.14 + //:TODO: Make functions calling this return failure if this fails
1.15 + trie->base = (TrieNode *)realloc(trie->base, (newSize + 1) * sizeof(TrieNode));
1.16 + if (!trie->base)
1.17 + {
1.18 + return false;
1.19 + }
1.20 +
1.21 + memset(&trie->base[curSize+1], 0, (newSize - curSize) * sizeof(TrieNode));
1.22 + trie->baseSize = newSize;
1.23 +
1.24 + return true;
1.25 +}
1.26 +
1.27 +unsigned int x_check(Trie *trie, char c, unsigned int start=1)
1.28 {
1.29 TrieNode *base = trie->base;
1.30 unsigned char _c = charval(c);
1.31 unsigned int to_check = trie->baseSize - _c;
1.32 - for (unsigned int i=1; i<to_check; i++)
1.33 + for (unsigned int i=start; i<=to_check; i++)
1.34 {
1.35 if (base[i+_c].mode == Node_Unused)
1.36 {
1.37 @@ -131,21 +150,18 @@
1.38 }
1.39 }
1.40
1.41 - trie->base = (TrieNode *)realloc(trie->base, trie->baseSize * sizeof(TrieNode) * 2);
1.42 - memset(trie->base + trie->baseSize, 0, trie->baseSize * sizeof(TrieNode));
1.43 - to_check = trie->baseSize;
1.44 - trie->baseSize *= 2;
1.45 + sm_trie_grow(trie);
1.46
1.47 - return to_check;
1.48 + return x_check(trie, c, to_check+1);
1.49 }
1.50
1.51 -unsigned int x_check2(Trie *trie, char c1, char c2)
1.52 +unsigned int x_check2(Trie *trie, char c1, char c2, unsigned int start=1)
1.53 {
1.54 TrieNode *base = trie->base;
1.55 unsigned char _c1 = charval(c1);
1.56 unsigned char _c2 = charval(c2);
1.57 unsigned int to_check = trie->baseSize - (_c1 > _c2 ? _c1 : _c2);
1.58 - for (unsigned int i=1; i<to_check; i++)
1.59 + for (unsigned int i=start; i<=to_check; i++)
1.60 {
1.61 if (base[i+_c1].mode == Node_Unused
1.62 && base[i+_c2].mode == Node_Unused)
1.63 @@ -154,22 +170,32 @@
1.64 }
1.65 }
1.66
1.67 - trie->base = (TrieNode *)realloc(trie->base, trie->baseSize * sizeof(TrieNode) * 2);
1.68 - memset(trie->base + trie->baseSize, 0, trie->baseSize * sizeof(TrieNode));
1.69 - to_check = trie->baseSize;
1.70 - trie->baseSize *= 2;
1.71 + sm_trie_grow(trie);
1.72
1.73 - return to_check;
1.74 + return x_check2(trie, c1, c2, to_check+1);
1.75 }
1.76
1.77 unsigned int x_check_multi(Trie *trie,
1.78 unsigned int offsets[],
1.79 - unsigned int count)
1.80 + unsigned int count,
1.81 + unsigned int start=1)
1.82 {
1.83 TrieNode *base = trie->base;
1.84 TrieNode *cur;
1.85 unsigned int to_check = trie->baseSize;
1.86 - for (unsigned int i=1; i<to_check; i++)
1.87 + unsigned int highest = 0;
1.88 +
1.89 + for (unsigned int i=0; i<count; i++)
1.90 + {
1.91 + if (offsets[i] > highest)
1.92 + {
1.93 + highest = offsets[i];
1.94 + }
1.95 + }
1.96 +
1.97 + to_check -= highest;
1.98 +
1.99 + for (unsigned int i=start; i<=to_check; i++)
1.100 {
1.101 bool okay = true;
1.102 for (unsigned int j=0; j<count; j++)
1.103 @@ -187,19 +213,16 @@
1.104 }
1.105 }
1.106
1.107 - trie->base = (TrieNode *)realloc(trie->base, trie->baseSize * sizeof(TrieNode) * 2);
1.108 - memset(trie->base + trie->baseSize, 0, trie->baseSize * sizeof(TrieNode));
1.109 - to_check = trie->baseSize;
1.110 - trie->baseSize *= 2;
1.111 + sm_trie_grow(trie);
1.112
1.113 - return to_check;
1.114 + return x_check_multi(trie, offsets, count, to_check+1);
1.115 }
1.116
1.117 unsigned int x_addstring(Trie *trie, const char *ptr)
1.118 {
1.119 size_t len = strlen(ptr) + 1;
1.120
1.121 - if (len > trie->stSize)
1.122 + if (trie->tail + len >= trie->stSize)
1.123 {
1.124 while (trie->tail + len >= trie->stSize)
1.125 {
1.126 @@ -219,13 +242,13 @@
1.127 {
1.128 Trie *t = new Trie;
1.129
1.130 - t->base = (TrieNode *)malloc(sizeof(TrieNode) * 256);
1.131 + t->base = (TrieNode *)malloc(sizeof(TrieNode) * (256 + 1));
1.132 t->stringtab = (char *)malloc(sizeof(char) * 256);
1.133 t->baseSize = 256;
1.134 t->stSize = 256;
1.135 t->tail = 0;
1.136
1.137 - memset(t->base, 0, sizeof(TrieNode) * 256);
1.138 + memset(t->base, 0, sizeof(TrieNode) * (256 + 1));
1.139 memset(t->stringtab, 0, sizeof(char) * 256);
1.140
1.141 /* Sentinel root node */
1.142 @@ -373,6 +396,7 @@
1.143 /* Now we need to find all the arcs leaving our parent...
1.144 * Note: the inconsistency is the base of our parent.
1.145 */
1.146 + assert(base[node->parent].mode == Node_Arc);
1.147 unsigned int incoming_list[256];
1.148 unsigned int incoming_base = base[node->parent].idx;
1.149 unsigned int incoming_count = 0;
1.150 @@ -392,8 +416,11 @@
1.151 {
1.152 unsigned int q = x_check_multi(trie, incoming_list, incoming_count);
1.153
1.154 + base = trie->base;
1.155 + node = &base[curidx];
1.156 +
1.157 /* If we're incoming, we need to modify our parent */
1.158 - base[incoming_base].idx = q;
1.159 + base[node->parent].idx = q;
1.160
1.161 /* For each node in the "to move" list,
1.162 * Relocate the node's info to the new position.
1.163 @@ -415,7 +442,7 @@
1.164 if (base[newidx].mode == Node_Arc)
1.165 {
1.166 TrieNode *check_base = &base[base[newidx].idx] + 1;
1.167 - for (unsigned int i=1; i<=255; i++, check_base++)
1.168 + for (unsigned int j=1; j<=255; j++, check_base++)
1.169 {
1.170 if (check_base->parent == oldidx)
1.171 {
1.172 @@ -427,6 +454,9 @@
1.173 } else {
1.174 unsigned int q = x_check_multi(trie, outgoing_list, outgoing_count);
1.175
1.176 + base = trie->base;
1.177 + node = &base[curidx];
1.178 +
1.179 /* If we're outgoing, we need to modify our own base */
1.180 base[lastidx].idx = q;
1.181
1.182 @@ -455,7 +485,7 @@
1.183 if (base[newidx].mode == Node_Arc)
1.184 {
1.185 TrieNode *check_base = &base[base[newidx].idx] + 1;
1.186 - for (unsigned int i=1; i<=255; i++, check_base++)
1.187 + for (unsigned int j=1; j<=255; j++, check_base++)
1.188 {
1.189 if (check_base->parent == oldidx)
1.190 {
1.191 @@ -505,12 +535,16 @@
1.192 */
1.193 void *oldvalue = node->value;
1.194 bool oldvalset = node->valset;
1.195 + if (*term == *keyptr)
1.196 + {
1.197 while (*term == *keyptr)
1.198 {
1.199 /* Find the next free slot in the check array.
1.200 * This is the "vector base" essentially
1.201 */
1.202 q = x_check(trie, *term);
1.203 + base = trie->base;
1.204 + node = &base[curidx];
1.205 /* Point the node to the next new base */
1.206 node->idx = q;
1.207 node->mode = Node_Arc;
1.208 @@ -525,6 +559,9 @@
1.209 *term = '\0'; /* Unmark the string table here */
1.210 term++;
1.211 keyptr++;
1.212 + }
1.213 + } else {
1.214 + node->valset = false;
1.215 }
1.216 /* We're done inserting new pairs. If one of them is exhausted,
1.217 * we take special shortcuts.
1.218 @@ -544,7 +581,11 @@
1.219 * B,A,D,G,E,R*,H*->OUSE (* = value set).
1.220 * NOTE: parent was last set at the end of the while loop.
1.221 */
1.222 + /* Get the new base and apply re-basing */
1.223 q = x_check(trie, *keyptr);
1.224 + base = trie->base;
1.225 + node = &base[curidx];
1.226 +
1.227 node->idx = q;
1.228 node->mode = Node_Arc;
1.229 lastidx = curidx;
1.230 @@ -570,7 +611,11 @@
1.231 node->valset = true;
1.232 node->value = value;
1.233
1.234 + /* Get the new base and apply re-basing */
1.235 q = x_check(trie, *term);
1.236 + base = trie->base;
1.237 + node = &base[curidx];
1.238 +
1.239 node->idx = q;
1.240 node->mode = Node_Arc;
1.241 lastidx = curidx;
1.242 @@ -593,7 +638,11 @@
1.243 /* Finally, we have to create two new nodes instead of just one. */
1.244 node->mode = Node_Arc;
1.245
1.246 + /* Get the new base and apply re-basing */
1.247 q = x_check2(trie, *keyptr, *term);
1.248 + base = trie->base;
1.249 + node = &base[curidx];
1.250 +
1.251 node->idx = q;
1.252 lastidx = curidx;
1.253
