← Back to branch summary

~jpakkane/libcolumbus/lessfuzz-test

« back to all changes in this revision

Viewing changes to src/Trie.cc

  • Committer: Jussi Pakkanen
  • Date: 2013-01-31 10:23:45 UTC
  • Revision ID: jussi.pakkanen@canonical.com-20130131102345-naze75up8ho9cigg
Use trie for word backing storage.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/Trie.cc
197
197
}
198
198
 
199
199
bool Trie::hasWord(const Word &word) const {
200
 
    TrieOffset node = p->root;
201
 
    for(size_t i=0; word.length() > i; i++) {
202
 
        Letter l = word[i];
203
 
        TrieOffset searcher = node;
204
 
        TrieOffset sibl = searcher + sizeof(TrieNode);
205
 
        TriePtrs *ptrs = (TriePtrs*)(p->map + sibl);
206
 
        while(ptrs->sibling != 0 && ptrs->l != l) {
207
 
            sibl = ptrs->sibling;
208
 
            ptrs = (TriePtrs*)(p->map + sibl);
209
 
        }
210
 
 
211
 
        if(ptrs->l != l)
212
 
            return false;
213
 
        node = ptrs->child;
214
 
    }
 
200
    TrieOffset node = findWord(word);
 
201
    if(!node)
 
202
        return false;
215
203
    TrieNode *n = (TrieNode*)(p->map+node);
216
204
    if(n->word != INVALID_WORDID)
217
205
        return true;
218
206
    return false;
219
207
}
220
208
 
 
209
TrieOffset Trie::findWord(const Word &word) const {
 
210
    TrieOffset node = p->root;
 
211
    for(size_t i=0; word.length() > i; i++) {
 
212
        Letter l = word[i];
 
213
        TrieOffset searcher = node;
 
214
        TrieOffset sibl = searcher + sizeof(TrieNode);
 
215
        TriePtrs *ptrs = (TriePtrs*)(p->map + sibl);
 
216
        while(ptrs->sibling != 0 && ptrs->l != l) {
 
217
            sibl = ptrs->sibling;
 
218
            ptrs = (TriePtrs*)(p->map + sibl);
 
219
        }
 
220
 
 
221
        if(ptrs->l != l)
 
222
            return 0;
 
223
        node = ptrs->child;
 
224
    }
 
225
    return node;
 
226
}
 
227
 
221
228
TrieOffset Trie::getRoot() const {
222
229
    return p->root;
223
230
}