src/base/trie.hh

119      * node being examined.
120      * @param parent The node we're currently "at", which can be updated.
121      * @param kid The node we may want to move to.
163         Node *node = &head;
164         while (node) {
165             if (node->value)
166                 return node;
168             if (node->kids[0] && node->kids[0]->matches(key))
169                 node = node->kids[0];
170             else if (node->kids[1] && node->kids[1]->matches(key))
171                 node = node->kids[1];
173                 node = NULL;
201         // Walk past all the nodes this new node will be inserted after. They
203         Node *node = &head;
204         while (goesAfter(&node, node->kids[0], key, new_mask) ||
205                goesAfter(&node, node->kids[1], key, new_mask))
207         assert(node);
209         Key cur_mask = node->mask;
212             assert(!node->value);
213             node->value = val;
214             return node;
218             Node *&kid = node->kids[i];
223                 new_node->parent = node;
241             if (cur_mask == node->mask)
244             // At the point we walked to above, add a new node.
246             new_node->parent = node;
257             // Still more bits to deal with, so add a new node for that path.
276         Node *node = lookupHandle(key);
277         if (node)
278             return node->value;
285      * @param node A Handle to remove.
291         Node *node = handle;
292         Value *val = node->value;
293         if (node->kids[1]) {
294             assert(node->value);
295             node->value = NULL;
298         if (!node->parent)
299             panic("Trie: Can't remove root node.\n");
301         Node *parent = node->parent;
304         if (node->kids[0])
305             node->kids[0]->parent = parent;
307         if (parent->kids[0] == node)
308             parent->kids[0] = node->kids[0];
309         else if (parent->kids[1] == node)
310             parent->kids[1] = node->kids[0];
323         delete node;