1.1 --- a/core/sm_trie.cpp Wed Aug 29 02:36:41 2007 +0000
1.2 +++ b/core/sm_trie.cpp Wed Aug 29 02:37:25 2007 +0000
1.3 @@ -107,13 +107,6 @@
1.4 * This would drastically speed up x_check*
1.5 */
1.6
1.7 -enum NodeType
1.8 -{
1.9 - Node_Unused = 0, /* Node is not being used (sparse) */
1.10 - Node_Arc, /* Node is part of an arc and does not terminate */
1.11 - Node_Term, /* Node is a terminator */
1.12 -};
1.13 -
1.14 struct TrieNode
1.15 {
1.16 /**
1.17 @@ -303,7 +296,7 @@
1.18 delete trie;
1.19 }
1.20
1.21 -bool sm_trie_delete(Trie *trie, const char *key)
1.22 +TrieNode *sm_trie_internal_retrieve(Trie *trie, const char *key)
1.23 {
1.24 unsigned int lastidx = 1; /* the last node index */
1.25 unsigned int curidx; /* current node index */
1.26 @@ -313,7 +306,7 @@
1.27
1.28 if (!*key)
1.29 {
1.30 - return false;
1.31 + return NULL;
1.32 }
1.33
1.34 /* Start traversing at the root node */
1.35 @@ -329,7 +322,7 @@
1.36 /* Check if this slot is supposed to be empty or is a collision */
1.37 if ((curidx > trie->baseSize) || node->mode == Node_Unused || node->parent != lastidx)
1.38 {
1.39 - return false;
1.40 + return NULL;
1.41 } else if (node->mode == Node_Term) {
1.42 char *term = &trie->stringtab[node->idx];
1.43 if (strcmp(keyptr, term) == 0)
1.44 @@ -340,59 +333,27 @@
1.45 lastidx = curidx;
1.46 } while (*keyptr != '\0');
1.47
1.48 - assert(node != NULL);
1.49 + return node;
1.50 +}
1.51
1.52 - if (!node->valset)
1.53 +bool sm_trie_delete(Trie *trie, const char *key)
1.54 +{
1.55 + TrieNode *node = sm_trie_internal_retrieve(trie, key);
1.56 + if (!node || !node->valset)
1.57 {
1.58 return false;
1.59 }
1.60
1.61 + node->value = NULL;
1.62 node->valset = false;
1.63 - node->value = NULL;
1.64
1.65 return true;
1.66 }
1.67
1.68 bool sm_trie_retrieve(Trie *trie, const char *key, void **value)
1.69 {
1.70 - unsigned int lastidx = 1; /* the last node index */
1.71 - unsigned int curidx; /* current node index */
1.72 - const char *keyptr = key; /* input stream at current token */
1.73 - TrieNode *node = NULL; /* current node being processed */
1.74 - TrieNode *base = trie->base;
1.75 -
1.76 - if (!*key)
1.77 - {
1.78 - return false;
1.79 - }
1.80 -
1.81 - /* Start traversing at the root node */
1.82 - do
1.83 - {
1.84 - /* Find where the next character is, then advance */
1.85 - curidx = base[lastidx].idx;
1.86 - node = &base[curidx];
1.87 - curidx += charval(*keyptr);
1.88 - node = &base[curidx];
1.89 - keyptr++;
1.90 -
1.91 - /* Check if this slot is supposed to be empty or is a collision */
1.92 - if ((curidx > trie->baseSize) || node->mode == Node_Unused || node->parent != lastidx)
1.93 - {
1.94 - return false;
1.95 - } else if (node->mode == Node_Term) {
1.96 - char *term = &trie->stringtab[node->idx];
1.97 - if (strcmp(keyptr, term) == 0)
1.98 - {
1.99 - break;
1.100 - }
1.101 - }
1.102 - lastidx = curidx;
1.103 - } while (*keyptr != '\0');
1.104 -
1.105 - assert(node != NULL);
1.106 -
1.107 - if (!node->valset)
1.108 + TrieNode *node = sm_trie_internal_retrieve(trie, key);
1.109 + if (!node || !node->valset)
1.110 {
1.111 return false;
1.112 }
1.113 @@ -405,7 +366,7 @@
1.114 return true;
1.115 }
1.116
1.117 -bool sm_trie_add(Trie *trie, const char *key, void *value, bool replace_allowed)
1.118 +bool sm_trie_insert(Trie *trie, const char *key, void *value)
1.119 {
1.120 unsigned int lastidx = 1; /* the last node index */
1.121 unsigned int curidx; /* current node index */
1.122 @@ -650,7 +611,7 @@
1.123 /* Do an initial browsing to make sure they're not the same string */
1.124 if (strcmp(keyptr, term) == 0)
1.125 {
1.126 - if (!node->valset || replace_allowed)
1.127 + if (!node->valset)
1.128 {
1.129 node->valset = true;
1.130 node->value = value;
1.131 @@ -830,7 +791,7 @@
1.132 */
1.133 assert(node->mode == Node_Arc);
1.134
1.135 - if (!node->valset || replace_allowed)
1.136 + if (!node->valset)
1.137 {
1.138 /* Insert is only possible if we have no production */
1.139 node->valset = true;
1.140 @@ -841,12 +802,16 @@
1.141 return false;
1.142 }
1.143
1.144 -bool sm_trie_insert(Trie *trie, const char *key, void *value)
1.145 -{
1.146 - return sm_trie_add(trie, key, value, false);
1.147 -}
1.148 -
1.149 bool sm_trie_replace(Trie *trie, const char *key, void *value)
1.150 {
1.151 - return sm_trie_add(trie, key, value, true);
1.152 + TrieNode *node = sm_trie_internal_retrieve(trie, key);
1.153 + if (!node)
1.154 + {
1.155 + return sm_trie_insert(trie, key, value);
1.156 + }
1.157 +
1.158 + node->value = value;
1.159 + node->valset = true;
1.160 +
1.161 + return true;
1.162 }
