class TrieNode
|
TrieNode definition. More... |
|
|
Public Types
- typedef IPNet<A> Key
- typedef MiniTraits<Payload>::NonConst PPayload
Public Methods
Public Static Methods
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 MiniTraits<Payload>::NonConst PPayload | PPayload |
Constructors
TrieNode (const Key& key, const Payload& p, TrieNode* up = 0)
| TrieNode |
TrieNode (const Key& key, TrieNode* up = 0)
| 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.
erase current node, replumb. Returns the new root.
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.
bool has_payload ()
| has_payload |
[const]
const Payload & const_p ()
| const_p |
[const]
void set_payload (const Payload& p)
| set_payload |
[const]
void print (int indent, const char *msg)
| print |
[const]
[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.
[const]
helper methods for iterators.
Visit order: start from the leaves and then go up.
begin() moves to the first node we want to explore, which is
the leftmost node in the subtree.
next() finds the 'next' node in the visit order.
Invariant for next(): being on _cur means that we have visited its
subtrees (and the node itself, of course, which is the current one).
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.
[const]
Returns: the lowest address in a subtree which has a route.
Search starting from left or right until a full node is found.
[const]
Returns: the highest address in a subtree which has a route.
Search starting from right or left until a full node is found.
| Generated by: pavlin on possum.icir.org on Wed Dec 11 16:50:31 2002, using kdoc 2.0a54+XORP. |
