|
| ||||||||||||||||
TrieNode's are the elements of a Trie. Each node is associated to a Key and possibly a Payload. Nodes with a Payload ("full") can have 0, 1 or 2 children. Nodes without a Payload ("empty") can only be internal nodes, and MUST have 2 children (or they have no reason to exist).
Children have a Key which is strictly contained in their parent's Key -- more precisely, they are in either the left or the right half of the parent's Key. The branch to which a child is attached (left or right) is defined accordingly.
| typedef IPNet<A> Key | Key |
| typedef MiniTraits<Payload>::NonConst PPayload | PPayload |
| TrieNode ()
| TrieNode |
| TrieNode (const Key& key, const Payload& p, TrieNode* up = 0)
| TrieNode |
| explicit TrieNode (const Key& key, TrieNode* up = 0)
| TrieNode |
| ~TrieNode ()
| ~TrieNode |
| TrieNode * insert (TrieNode **root,
const Key& key,
const Payload& p,
bool& replaced)
| insert |
[static]
add a node to a subtree
Returns: a pointer to the node.
| TrieNode * erase ()
| erase |
erase current node, replumb. Returns the new root.
| TrieNode * find (const Key& key)
| find |
main search routine. Given a key, returns a node.
| const TrieNode * const_find (const Key& key)
| const_find |
[const]
| TrieNode * find_subtree (const Key &key)
| find_subtree |
aux search routine. Given a key, returns a subtree contained in the key, irrespective of the presence of a payload in the node.
| TrieNode* lower_bound (const Key &key)
| lower_bound |
Given a key, find the node with that key and a payload. If the next doesn't exist or does not have a payload, find the next node in the iterator sequence. XXX check the description.
| TrieNode* get_left ()
| get_left |
| TrieNode* get_right ()
| get_right |
| TrieNode* get_parent ()
| get_parent |
| bool has_payload ()
| has_payload |
[const]
| const Payload & const_p ()
| const_p |
[const]
| Payload & p ()
| p |
| void set_payload (const Payload& p)
| set_payload |
| const Key & k ()
| k |
[const]
| void print (int indent, const char *msg)
|
[const]
| string str ()
| str |
[const]
| void delete_subtree ()
| delete_subtree |
helper function to delete an entire subtree (including the root).
| void validate (const TrieNode *parent)
| validate |
[const]
debugging, validates a node by checking pointers and Key invariants.
| TrieNode * leftmost ()
| leftmost |
Returns: the leftmost node under this node
| void find_bounds (const A& a, A &lo, A &hi)
| find_bounds |
[const]
Algorithm:
n = find(a);
if we have no route (hence no default), provide a fake 0/0;
set lo and hi to the boundaries of the current node.
if n.is_a_leaf() we are done (results are the extremes of the entry)
Otherwise: we are in an intermediate node, and a can be in positions
1..5 if the node has 2 children, or 1'..3' if it has 1 child.
n: |---------------.----------------|
a: 1 2 3 4 5
|--X--| |--Y--|
a: 1' 2' 3'
|--X--|
Behaviour is the following:
case 1 and 1': lo already set, hi = (lowest address in X)-1
case 2 and 2': set n = X and repeat
case 3: lo = (highest addr in X)+1, hi = (lowest addr in Y)-1
case 3': lo = (highest addr in X)+1, hi is already set
case 4: set n = Y and repeat
case 5: lo = (highest addr in Y)+1, hi is already set
Returns: the boundaries ("lo" and "hi") of the largest range that contains 'a' and maps to the same route entry.
| A low ()
| low |
[const]
Returns: the lowest address in a subtree which has a route. Search starting from left or right until a full node is found.
| A high ()
| high |
[const]
Returns: the highest address in a subtree which has a route. Search starting from right or left until a full node is found.