xorp

trie.hh

00001 // -*- c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t -*-
00002 // vim:set sts=4 ts=8:
00003 
00004 // Copyright (c) 2001-2011 XORP, Inc and Others
00005 //
00006 // This program is free software; you can redistribute it and/or modify
00007 // it under the terms of the GNU Lesser General Public License, Version
00008 // 2.1, June 1999 as published by the Free Software Foundation.
00009 // Redistribution and/or modification of this program under the terms of
00010 // any other version of the GNU Lesser General Public License is not
00011 // permitted.
00012 // 
00013 // This program is distributed in the hope that it will be useful, but
00014 // WITHOUT ANY WARRANTY; without even the implied warranty of
00015 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. For more details,
00016 // see the GNU Lesser General Public License, Version 2.1, a copy of
00017 // which can be found in the XORP LICENSE.lgpl file.
00018 // 
00019 // XORP, Inc, 2953 Bunker Hill Lane, Suite 204, Santa Clara, CA 95054, USA;
00020 // http://xorp.net
00021 
00022 // $XORP: xorp/libxorp/trie.hh,v 1.29 2008/10/02 21:57:36 bms Exp $
00023 
00024 #ifndef __LIBXORP_TRIE_HH__
00025 #define __LIBXORP_TRIE_HH__
00026 
00027 #include "ipnet.hh"
00028 
00029 // Macros 
00030 //#define VALIDATE_XORP_TRIE
00031 //#define DEBUG_LOGGING
00032 
00033 #include "xlog.h"
00034 #include "debug.h"
00035 #include "minitraits.hh"
00036 
00037 #ifndef XORP_USE_USTL
00038 #include <stack>
00039 #endif
00040 
00041 #define trie_debug_msg(x...) /* debug_msg(x) */
00042 #define trie_debug_msg_indent(x)
00043 
00044 /*
00045  * This module implements a trie to support route lookups.
00046  *
00047  * The template should be invoked with two classes, the basetype "A"
00048  * for the search Key (which is a subnet, IPNet<A>), and the Payload.
00049  */
00050 
00051 
00067 template <class A, class Payload> 
00068 class TrieNode {
00069 public:
00070     typedef IPNet<A> Key;
00071     typedef typename MiniTraits<Payload>::NonConst PPayload;
00072 
00076     TrieNode() : _up(0), _left(0), _right(0), _k(Key()), _p(0) {}
00077     TrieNode(const Key& key, const Payload& p, TrieNode* up = 0) :
00078     _up(up), _left(0), _right(0), _k(key), _p(new PPayload(p)) {}
00079 
00080     explicit TrieNode(const Key& key, TrieNode* up = 0) :
00081     _up(up), _left(0), _right(0), _k(key), _p(0) {}
00082 
00083     ~TrieNode()                 
00084     { 
00085     if (_p)
00086         delete_payload(_p); 
00087     }
00088 
00093     static TrieNode *insert(TrieNode **root,
00094                 const Key& key,
00095                 const Payload& p,
00096                 bool& replaced);
00097 
00101     TrieNode *erase();
00102 
00106     TrieNode *find(const Key& key) ;
00107     const TrieNode *const_find(const Key& key) const {
00108     return const_cast<TrieNode*>(this)->find(key);
00109     }
00110 
00116     TrieNode *find_subtree(const Key &key);
00117 
00123     TrieNode* lower_bound(const Key &key);
00124 
00125     TrieNode* get_left()            { return this->_left;   }
00126     TrieNode* get_right()           { return this->_right;  }
00127     TrieNode* get_parent()          { return this->_up;   }
00128     bool has_payload() const            { return _p != NULL;    }
00129     const Payload &const_p() const      { return *_p;       }
00130     Payload &p()                        { return *_p;       }
00131 
00132     void set_payload(const Payload& p) {
00133     if (_p)
00134         delete_payload(_p);
00135     _p = new PPayload(p);
00136     }
00137 
00138     const Key &k() const            { return _k;        }
00139 
00140     void print(int indent, const char *msg) const;
00141     string str() const;
00142 
00146     void delete_subtree()           {
00147     if (_left)
00148         _left->delete_subtree();
00149     if (_right)
00150         _right->delete_subtree();
00151     delete this;    /* and we are gone too */
00152     }
00153 
00157     void validate(const TrieNode *parent) const {
00158     UNUSED(parent);
00159 #ifdef VALIDATE_XORP_TRIE
00160     if (_up != parent) {
00161         fprintf(stderr, "bad parent _up %x vs %x",
00162             (int)_up, (int)parent);
00163         abort();
00164     }
00165     if (_up && _k.contains(_up->_k)) {
00166         fprintf(stderr, "bad subnet order");
00167         abort();
00168     }
00169     if (_p == NULL && (!_left || !_right)) {
00170         fprintf(stderr, "useless internal node");
00171         abort();
00172     }
00173     if (_left)
00174         _left->validate(this);
00175     if (_right)
00176         _right->validate(this);
00177 #endif
00178     }
00179 
00184     TrieNode * leftmost() {
00185     TrieNode *n = this;
00186     while (n->_left || n->_right)
00187         n = (n->_left ? n->_left : n->_right);
00188     return n;
00189     }
00190 
00221     void find_bounds(const A& a, A &lo, A &hi) const    {
00222     TrieNode def = TrieNode();
00223     const TrieNode *n = const_find(Key(a, a.addr_bitlen()));
00224 
00225     if (n == NULL) {    // create a fake default entry
00226         def._left = const_cast<TrieNode *>(this);
00227         def._right = NULL;
00228         n = &def;
00229     }
00230     lo = n->_k.masked_addr();
00231     hi = n->_k.top_addr();
00232     for (const TrieNode *prev = NULL; prev != n;) {
00233         prev = n;
00234         TrieNode *x = (n->_left ? n->_left : n->_right);
00235         if (x == NULL)
00236         break;
00237         if (a < x->_k.masked_addr()) {      // case 1 and 1'
00238         hi = x->low(); --hi;
00239         } else if (a <= x->_k.top_addr()) {     // case 2 and 2'
00240         n = x; // and continue
00241         } else if (n->_left == NULL || n->_right == NULL) { // case 3'
00242         lo = x->high(); ++lo;
00243         } else if (a < n->_right->_k.masked_addr()) {   // case 3
00244         lo = x->high(); ++lo;
00245         hi = n->_right->low(); --hi;
00246         } else if (a <= n->_right->_k.top_addr()) { // case 4:
00247         n = n->_right; // and continue
00248         } else {                    // case 5:
00249         lo = n->_right->high(); ++lo;
00250         }
00251     }
00252     }
00253 
00258     A low() const                   {
00259     const TrieNode *n = this;
00260     while (!(n->has_payload()) && (n->_left || n->_right))
00261         n = (n->_left ? n->_left : n->_right);
00262     return n->_k.masked_addr();
00263     }
00264 
00269     A high() const                  {
00270     const TrieNode *n = this;
00271     while (!(n->has_payload()) && (n->_right || n->_left))
00272         n = (n->_right ? n->_right : n->_left);
00273     return n->_k.top_addr();
00274     }
00275 
00276 private:
00277     /* delete_payload is a separate method to allow specialization */
00278     void delete_payload(Payload* p) {
00279     delete p;
00280     }
00281 
00282     void dump(const char *msg) const
00283     {
00284     UNUSED(msg);
00285     trie_debug_msg(" %s %s %s\n",
00286                msg,
00287                _k.str().c_str(), _p ? "PL" : "[]");
00288     trie_debug_msg("  U   %s\n",
00289                _up ? _up->_k.str().c_str() : "NULL");
00290     trie_debug_msg("  L   %s\n",
00291                _left ? _left->_k.str().c_str() : "NULL");
00292     trie_debug_msg("  R   %s\n",
00293                _right ? _right->_k.str().c_str() : "NULL");
00294 
00295     }
00296 
00297     TrieNode    *_up, *_left, *_right;
00298     Key     _k;
00299     PPayload    *_p;
00300 };
00301 
00310 template <class A, class Payload>
00311 class TriePostOrderIterator {
00312 public:
00313     typedef IPNet<A> Key;
00314     typedef TrieNode<A, Payload> Node;
00315 
00319     TriePostOrderIterator()             {}
00320 
00325     explicit TriePostOrderIterator(Node *n)         {
00326     _cur = n;
00327     if (n)
00328         _root = n->k();
00329     }
00330 
00335     TriePostOrderIterator(Node *n, const Key &k)        {
00336     _root = k;
00337     _cur = n; 
00338     if (_cur) begin();
00339     }
00340 
00344     TriePostOrderIterator * begin() { 
00345     Node * n = _cur;
00346     while (n->get_parent() && _root.contains(n->get_parent()->k()))
00347         n = n->get_parent();
00348     _cur =  n->leftmost();
00349     return this;
00350     }
00351 
00358     TriePostOrderIterator operator ++(int)      { // postfix
00359     TriePostOrderIterator x = *this;
00360     next();
00361     return x;
00362     }
00363 
00370     TriePostOrderIterator& operator ++()        { // prefix
00371     next();
00372     return *this;
00373     }
00374 
00375     Node *cur() const           { return _cur;      };
00376 
00377     bool operator==(const TriePostOrderIterator & x) const {
00378     return (_cur == x._cur); 
00379     }
00380 
00381     bool has_payload() const        { return _cur->has_payload(); }
00382     Payload & payload()         { return _cur->p(); };
00383     const Key & key() const     { return _cur->k(); };
00384 
00385 private:
00386 
00387     bool node_is_left(Node * n) const; 
00388     void next();
00389 
00390     Node    *_cur;
00391     Key     _root;
00392 };
00393 
00402 template <class A, class Payload>
00403 class TriePreOrderIterator {
00404 public:
00405     typedef IPNet<A> Key;
00406     typedef TrieNode<A, Payload> Node;
00407 
00411     TriePreOrderIterator()              {}
00412 
00417     explicit TriePreOrderIterator(Node *n)          {
00418     _cur = n;
00419     if (_cur) _root = n->k();
00420     }
00421 
00426     TriePreOrderIterator(Node *n, const Key &k)     {
00427     _root = k;
00428     _cur = n; 
00429     if (_cur) begin();
00430     }
00431 
00435     TriePreOrderIterator * begin() { 
00436     while (!_stack.empty()) _stack.pop();
00437     while (_cur->get_parent() && _root.contains(_cur->get_parent()->k()))
00438         _cur = _cur->get_parent();
00439     _stack.push(_cur);
00440     next();
00441     return this;
00442     }
00443 
00450     TriePreOrderIterator operator ++(int)       { // postfix
00451     TriePreOrderIterator x = *this;
00452     next();
00453     return x;
00454     }
00455 
00462     TriePreOrderIterator& operator ++()     { // prefix
00463     next();
00464     return *this;
00465     }
00466 
00467     Node *cur() const           { return _cur;      };
00468 
00469     bool operator==(const TriePreOrderIterator & x) const {
00470     return (_cur == x._cur); 
00471     }
00472 
00473     bool has_payload() const        { return _cur->has_payload(); }
00474     Payload & payload()         { return _cur->p(); };
00475     const Key & key() const     { return _cur->k(); };
00476 
00477 private:
00478 
00479 
00480     bool node_is_left(Node * n) const; 
00481     void next();
00482 
00483     Node     *_cur;
00484     Key      _root;
00485     stack<Node*> _stack;
00486 };
00487 
00497 template <class A, class Payload, class __Iterator =
00498     TriePostOrderIterator<A,Payload> >
00499 class Trie {
00500 public:
00501     typedef IPNet<A> Key;
00502     typedef TrieNode<A,Payload> Node;
00503     typedef __Iterator iterator;
00504 
00508     Trie() : _root(0), _payload_count(0)    {}
00509 
00510     ~Trie()                 { delete_all_nodes(); }
00511 
00518     iterator insert(const Key & net, const Payload& p) {
00519     bool replaced = false;
00520     Node *out = Node::insert(&_root, net, p, replaced);
00521     if (replaced) {
00522         fprintf(stderr, "overwriting a full node"); //XXX
00523     } else {
00524         _payload_count++;
00525     }
00526     return iterator(out);
00527     }
00528 
00533     void erase(const Key &k)            { erase(find(k)); }
00534 
00538     void erase(iterator i)          {
00539     if (_root && i.cur() && i.cur()->has_payload()) {
00540         _payload_count--;
00541         _root = const_cast<Node *>(i.cur())->erase();
00542         // XXX should invalidate i ?
00543     }
00544     }
00545 
00554     iterator unbind_root(iterator i) const  {
00555     return iterator(i.cur(), _root->k());
00556     }
00557     
00562     iterator find(const Key &k) const       {
00563     return iterator(_root->find(k));
00564     }
00565 
00570     iterator find(const A& a) const     {
00571     return find(Key(a, a.addr_bitlen()));
00572     }
00573 
00574     iterator lower_bound(const Key &k) const {
00575 #ifdef NOTDEF
00576     iterator i = lookup_node(k);
00577     if (i != end())
00578         return i;
00579 #endif
00580     return iterator(_root->lower_bound(k));
00581     }
00582 
00583     iterator begin() const      { return iterator(_root, IPNet<A>()); }
00584     const iterator end() const          { return iterator(0); }
00585 
00586     void delete_all_nodes()         {
00587     if (_root)
00588         _root->delete_subtree();
00589     _root = NULL;
00590     _payload_count = 0;
00591     }
00592 
00597     iterator lookup_node(const Key & k) const   {
00598     Node *n = _root->find(k);
00599     return (n && n->k() == k) ? iterator(n) : end();
00600     }
00601 
00606     iterator search_subtree(const Key &key) const {
00607     return iterator(_root->find_subtree(key), key);
00608     }
00609 
00616     iterator find_less_specific(const Key &key) const {
00617     // there are no less specific routes than the default route
00618     if (key.prefix_len() == 0)
00619         return end();
00620 
00621     Key x(key.masked_addr(), key.prefix_len() - 1);
00622 
00623     return iterator(_root->find(x));
00624     }
00625 
00630     void find_bounds(const A& a, A &lo, A &hi) const    {
00631     _root->find_bounds(a, lo, hi);
00632     }
00633 #if 0   // compatibility stuff, has to go
00634     /*
00635      * return the lower and higher address in the range that contains a
00636      * and would map to the same route.
00637      */
00638     A find_lower_bound(const A a) const     {
00639     A lo, hi;
00640     _root->find_bounds(a, lo, hi);
00641     return lo;
00642     }
00643     A find_higher_bound(const A a) const        {
00644     A lo, hi;
00645     _root->find_bounds(a, lo, hi);
00646     return hi;
00647     }
00648 
00649 #endif // compatibility
00650     int route_count() const         { return _payload_count; }
00651 
00652     void print() const;
00653 
00654 private:
00655     void validate()             {
00656     if (_root)
00657         _root->validate(NULL);
00658     }
00659 
00660     Node    *_root;
00661     int     _payload_count;
00662 };
00663 
00664 
00670 template <class A, class Payload> 
00671 TrieNode<A, Payload> *
00672 TrieNode<A, Payload>::insert(TrieNode **root,
00673                  const Key& x,
00674                  const Payload& p,
00675                  bool& replaced)
00676 {
00677     /*
00678      * Loop until done in the following:
00679      *
00680      * If *root == NULL, create a new TrieNode containing x and we are DONE.
00681      * Otherwise consider the possible cases of overlaps between the subnets
00682      * in *root (call it y) and x (+ indicates the middle of the interval):
00683      *
00684      *   y = (*root)          .|===+===|
00685      *
00686      *   x  0         .|---+---|
00687      *   x  A       |--|  .    .
00688      *   x  B             .    .     |--|
00689      *   x  C             . |-|.
00690      *   x  D             .    .|-|
00691      *   x  E  |----------+----------|
00692      *   x  F             |----------+-----------|
00693      *
00694      * case 0:  Same subnet. Store payload if *root if empty, replace otherwise.
00695      * case A:  allocate a new empty root, make old *root the right child,
00696      *      make a new node with x the left child. DONE.
00697      * case B:  allocate a new empty root, make old *root the left child,
00698      *      make a new node with x the right child. DONE.
00699      * case C:  repeat with root = &((*root)->left)
00700      * case D:  repeat with root = &((*root)->right)
00701      * case E:  *root = new node with x, old *root the right child, DONE.
00702      * case F:  *root = new node with x, old *root the left child, DONE.
00703      *
00704      * In all case, when we exit the loop, newroot contains the new value to
00705      * be assigned to *root;
00706      */
00707 
00708     TrieNode **oldroot = root;  // do we need it ?
00709     TrieNode *newroot = NULL, *parent = NULL, *me = NULL;
00710 
00711     trie_debug_msg("++ insert %s\n", x.str().c_str());
00712     for (;;) {
00713     newroot = *root;
00714     if (newroot == NULL) {
00715         me = newroot = new TrieNode(x, p, parent);
00716         break;
00717     }
00718     parent = newroot->_up;
00719     Key y = newroot->_k;
00720     if (x == y) {                   /* case 0 */
00721         replaced = newroot->has_payload();
00722         newroot->set_payload(p);
00723         me = newroot;
00724         break;
00725         }
00726 
00727     // boundaries of x and y, and their midpoints.
00728 
00729     A x_m = x.masked_addr() | ( ~(x.netmask()) >> 1 );
00730     A y_m = y.masked_addr() | ( ~(y.netmask()) >> 1 );
00731     A x_l = x.masked_addr();
00732     A x_h = x.top_addr();
00733     A y_l = y.masked_addr();
00734     A y_h = y.top_addr();
00735 
00736     if (x_h < y_l) {                /* case A */
00737         //trie_debug_msg("case A:  |--x--|   |--y--|\n");
00738         Key k = Key::common_subnet(x, y);
00739         newroot = new TrieNode(k, parent);  // create new root
00740         newroot->_right = *root;        // old root goes right
00741         newroot->_right->_up = newroot;
00742         newroot->_left = me = new TrieNode(x, p, newroot);
00743         break;
00744     } else if (y_h < x_l) {             /* case B */
00745         //trie_debug_msg("case B:  |--y--|   |--x--|\n");
00746         Key k = Key::common_subnet(x, y);
00747         newroot = new TrieNode(k, parent);  // create new root
00748         newroot->_left = *root;
00749         newroot->_left->_up = newroot;
00750         newroot->_right = me = new TrieNode(x, p, newroot);
00751         break;
00752     } else if (x_l >= y_l && x_h <= y_m) {      /* case C */
00753         //trie_debug_msg("case C:  |--x-.----|\n");
00754         parent = *root;
00755         root = &(newroot->_left);
00756     } else if (x_l > y_m && x_h <= y_h) {       /* case D */
00757         //trie_debug_msg("case D:  |----.-x--|\n");
00758         parent = *root;
00759         root = &(newroot->_right);
00760     } else if (y_l > x_m && y_h <= x_h) {       /* case E */
00761         //trie_debug_msg("case E:  |----.-Y--|\n");
00762         newroot = me = new TrieNode(x, p, parent);
00763         newroot->_right = *root;
00764         newroot->_right->_up = newroot;
00765         break;
00766     } else if (y_l >= x_l && y_h <= x_m) {      /* case F */
00767         //trie_debug_msg("case F:  |--Y-.----|\n");
00768         newroot = me = new TrieNode(x, p, parent);
00769         newroot->_left = *root;
00770         newroot->_left->_up = newroot;
00771         break;
00772     } else
00773         abort();    // impossible case in TrieNode::insert()
00774     }
00775     *root = newroot;
00776     if (*oldroot)
00777     (*oldroot)->validate(NULL);
00778     // (*oldroot)->print(0, "");
00779     return me;
00780 }
00781 
00782 
00788 template <class A, class Payload>
00789 TrieNode<A, Payload> *
00790 TrieNode<A, Payload>::erase()
00791 {
00792     TrieNode *me, *parent, *child;
00793 
00794     if (_p) {
00795     delete_payload(_p);
00796     _p = NULL;
00797     }
00798 
00799     trie_debug_msg("++ erase %s\n", this->_k.str().c_str());
00800     /*
00801      * If the node ("me") exists, has no payload and at most one child,
00802      * then it is a useless internal node which needs to be removed by
00803      * linking the child to the parent. If the child is NULL, we need
00804      * to repeat the process up.
00805      */
00806     for (me = this; me && me->_p == NULL &&
00807          (me->_left == NULL || me->_right == NULL); ) {
00808 
00809     // me->dump("erase");           // debugging
00810 
00811     // Find parent and the one possible child (both can be NULL).
00812     parent = me->_up;
00813     child = me->_left ? me->_left : me->_right;
00814 
00815     if (child != NULL)      // if the child exists, link it to
00816         child->_up = parent;    // its new parent
00817 
00818     if (parent == NULL)     // no parent, child becomes new root
00819         parent = child;
00820     else { // i have a parent, link my child to it (left or right)
00821         if (parent->_left == me)
00822         parent->_left = child;
00823         else
00824         parent->_right = child;
00825     }
00826     delete me;          // nuke the node
00827     me = parent;
00828     }
00829     // now navigate up to find and return the new root of the trie
00830     for ( ; me && me->_up ; me = me->_up)
00831     ;
00832     return me;
00833 }
00834 
00839 template <class A, class Payload> 
00840 TrieNode<A, Payload> *
00841 TrieNode<A,Payload>::find(const Key &key)
00842 {
00843     TrieNode * cand = NULL;
00844     TrieNode * r = this;
00845 
00846     for ( ; r && r->_k.contains(key) ; ) {
00847     if (r->_p)
00848         cand = r;       // we have a candidate.
00849     if (r->_left && r->_left->_k.contains(key))
00850         r = r->_left;
00851     else            // should check that right contains(key), but
00852         r = r->_right;  // the loop condition will do it for us.
00853     }
00854     return cand;
00855 }
00856 
00860 template <class A, class Payload> 
00861 TrieNode<A, Payload> *
00862 TrieNode<A,Payload>::lower_bound(const Key &key)
00863 {
00864     TrieNode * cand = NULL;
00865     TrieNode * r = this;
00866     //printf("lower bound: %s\n", key.str().c_str());
00867     for ( ; r && r->_k.contains(key) ; ) {
00868     cand = r;       // any node is good, irrespective of payload.
00869     if (r->_left && r->_left->_k.contains(key))
00870         r = r->_left;
00871     else            // should check that right contains(key), but
00872         r = r->_right;  // the loop condition will do it for us.
00873     }
00874     if (cand == NULL)
00875     cand = this;
00876 
00877     if (cand->_k == key) {  // we found an exact match
00878     if (cand->_p) {     // we also have a payload, so we are done.
00879         // printf("exact match\n");
00880         return cand;
00881     } else {        // no payload, skip to the next (in postorder)
00882                 // node in the entire tree (null Key as root)
00883         // printf("exact match on empty node - calling next\n");
00884         TriePostOrderIterator<A,Payload> iterator(cand, Key());
00885         ++iterator;
00886         return iterator.cur();
00887     }
00888     }
00889     
00890     // printf("no exact match\n");
00891     // No exact match exists.
00892     // cand holds what would be the parent of the node, if it existed.
00893     while (cand != NULL) {
00894     // printf("cand = %s\n", cand->str().c_str());
00895     if (cand->_left && (key < cand->_left->_k)) {
00896         return cand->_left->leftmost();
00897     }
00898     if (cand->_right && (key < cand->_right->_k)) {
00899         return cand->_right->leftmost();
00900     }
00901     cand = cand->_up;
00902     }
00903     return NULL;
00904 }
00905 
00909 template <class A, class Payload> 
00910 TrieNode<A, Payload> *
00911 TrieNode<A,Payload>::find_subtree(const Key &key)
00912 {
00913     TrieNode *r = this;
00914     TrieNode *cand = r && key.contains(r->_k) ? r : NULL;
00915 
00916     for ( ; r && r->_k.contains(key) ; ) {
00917     if (key.contains(r->_k))
00918         cand = r;       // we have a candidate.
00919     if (r->_left && r->_left->_k.contains(key))
00920         r = r->_left;
00921     else            // should check that right contains(key), but
00922         r = r->_right;  // the loop condition will do it for us.
00923     }
00924     return cand;
00925 }
00926 
00927 template <class A, class Payload> 
00928 void 
00929 TrieNode<A,Payload>::print(int indent, const char *msg) const
00930 {
00931 #ifdef DEBUG_LOGGING
00932     trie_debug_msg_indent(indent);
00933 
00934     if (this == NULL) {
00935     trie_debug_msg("%sNULL\n", msg);
00936     return;
00937     }
00938     trie_debug_msg("%skey: %s %s\n",
00939            msg, _k.str().c_str(), _p ? "PL" : "[]");
00940     trie_debug_msg("    U: %s\n", _up ? _up->_k.str().c_str() : "NULL");
00941     _left->print(indent+4, "L: ");
00942     _right->print(indent+4, "R: ");
00943     trie_debug_msg_indent(0);
00944 #endif /* DEBUG_LOGGING */
00945     UNUSED(indent);
00946     UNUSED(msg);
00947 }
00948 
00949 template <class A, class Payload> 
00950 string
00951 TrieNode<A,Payload>::str() const
00952 {
00953     string s;
00954     if (this == NULL) {
00955     s = "NULL";
00956     return s;
00957     }
00958     s = c_format("key: %s %s\n", _k.str().c_str(), _p ? "PL" : "[]");
00959     s += c_format("    U: %s\n", _up ? _up->_k.str().c_str() : "NULL");
00960     return s;
00961 }
00962 
00963 template <class A, class Payload, class __Iterator>
00964 void 
00965 Trie<A,Payload,__Iterator>::print() const
00966 {
00967     //this is called print - it should NOT use debug_msg!!!
00968     printf("---- print trie ---\n");
00969     // _root->print(0, "");
00970     iterator ti;
00971     for (ti = begin() ; ti != end() ; ti++)
00972     printf("*** node: %-26s %s\n",
00973            ti.cur()->k().str().c_str(),
00974            ti.cur()->has_payload() ? "PL" : "[]");
00975     printf("---------------\n");
00976 }
00977 
00978 template <class A, class Payload>
00979 bool 
00980 TriePostOrderIterator<A,Payload>::node_is_left(Node* n) const 
00981 { 
00982     return n->get_parent() && n  == n->get_parent()->get_left(); 
00983 }
00984 
00985 template <class A, class Payload>
00986 void
00987 TriePostOrderIterator<A,Payload>::next() 
00988 {
00989     Node * n = _cur;
00990     do {
00991     if (n->get_parent() == NULL) {
00992         _cur = NULL;
00993         return;     // cannot backtrack, finished
00994     }
00995     bool was_left_child = node_is_left(n);
00996     n = n->get_parent();
00997     // backtrack one level, then explore the leftmost path
00998     // on the right branch if not done already.
00999     if (was_left_child && n->get_right()) {
01000         n = n->get_right()->leftmost();
01001     }
01002     if (_root.contains(n->k()) == false) {
01003         _cur = NULL;
01004         return;
01005     }
01006     } while (n->has_payload() == false);    // found a good node.
01007     _cur = n;
01008 }
01009 
01010 
01011 template <class A, class Payload>
01012 void
01013 TriePreOrderIterator<A,Payload>::next() 
01014 {
01015     if (_stack.empty()) {
01016     _cur = NULL;
01017     return;
01018     }
01019 
01020     do {
01021     _cur = _stack.top();
01022     _stack.pop();
01023     if( _cur->get_right( ) != NULL )
01024         _stack.push(_cur->get_right());
01025     if( _cur->get_left() != NULL )
01026         _stack.push(_cur->get_left());
01027     } while (_cur->has_payload() == false); // found a good node.
01028 }
01029 
01030 #endif // __LIBXORP_TRIE_HH__
 All Classes Namespaces Functions Variables Typedefs Enumerations