xorp

ref_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-2009 XORP, Inc.
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/ref_trie.hh,v 1.34 2008/10/02 21:57:32 bms Exp $
00023 
00024 #ifndef __LIBXORP_REF_TRIE_HH__
00025 #define __LIBXORP_REF_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 #include "stack"
00037 
00038 
00039 #define NODE_DELETED 0x8000
00040 #define NODE_REFS_MASK 0x7fff
00041 
00042 /*
00043  * This module implements a trie to support route lookups.
00044  *
00045  */
00046 
00047 template <class A, class Payload>
00048 class RefTriePostOrderIterator;
00049 
00050 template <class A, class Payload>
00051 class RefTriePreOrderIterator;
00052 
00053 template <class A, class Payload>
00054 class RefTrie;
00055 
00071 template <class A, class Payload>
00072 class RefTrieNode {
00073 public:
00074     typedef IPNet<A> Key;
00075     typedef typename MiniTraits<Payload>::NonConst PPayload;
00076 
00080     RefTrieNode() : _up(0), _left(0), _right(0), _k(Key()), _p(0),
00081     _references(0){}
00082     RefTrieNode(const Key& key, const Payload& p, RefTrieNode* up = 0) :
00083     _up(up), _left(0), _right(0), _k(key), _p(new PPayload(p)),
00084     _references(0) {}
00085 
00086     RefTrieNode(const Key& key, RefTrieNode* up = 0) :
00087     _up(up), _left(0), _right(0), _k(key), _p(0), _references(0) {}
00088 
00089     ~RefTrieNode()
00090     {
00091     // assert that the node has been deleted and it's reference
00092     // count is zero
00093     XLOG_ASSERT((_references&(NODE_DELETED|NODE_REFS_MASK)) == NODE_DELETED);
00094     if (_p)
00095         delete_payload(_p);
00096     }
00097 
00102     static RefTrieNode *insert(RefTrieNode **root,
00103                 const Key& key,
00104                 const Payload& p,
00105                 bool& replaced);
00106 
00110     RefTrieNode *erase();
00111 
00115     RefTrieNode *find(const Key& key) ;
00116     const RefTrieNode *const_find(const Key& key) const {
00117     return const_cast<RefTrieNode*>(this)->find(key);
00118     }
00119 
00125     RefTrieNode *find_subtree(const Key &key);
00126 
00132     RefTrieNode* lower_bound(const Key &key);
00133 
00134     RefTrieNode* get_left()                       { return this->_left;   }
00135     RefTrieNode* get_right()                      { return this->_right;  }
00136     RefTrieNode* get_parent()                     { return this->_up;   }
00137 
00138     bool has_payload() const            { return _p != NULL;    }
00139     bool has_active_payload() const
00140     {
00141     return ((_p != NULL) && ((_references & NODE_DELETED) == 0));
00142     }
00143     const Payload &const_p() const      { return *_p;       }
00144     Payload &p()                        { return *_p;       }
00145 
00146     void set_payload(const Payload& p) {
00147     if (_p)
00148         delete_payload(_p);
00149     _p = new PPayload(p);
00150     // clear the DELETED flag
00151     _references ^= _references & NODE_DELETED;
00152     }
00153 
00154     uint32_t references() const {
00155     return _references & NODE_REFS_MASK;
00156     }
00157 
00158     void incr_refcount() {
00159     XLOG_ASSERT((_references & NODE_REFS_MASK) != NODE_REFS_MASK);
00160     _references++;
00161     // printf("++ _references = %d\n", _references & NODE_REFS_MASK);
00162     }
00163 
00164     void decr_refcount() {
00165     XLOG_ASSERT((_references & NODE_REFS_MASK) > 0);
00166     _references--;
00167     // printf("-- _references = %d\n", _references & NODE_REFS_MASK);
00168     }
00169 
00170     bool deleted() const {
00171     return ((_references & NODE_DELETED) != 0);
00172     }
00173 
00174     const Key &k() const            { return _k;        }
00175 
00176     void print(int indent, const char *msg) const;
00177     string str() const;
00178 
00183     void delete_subtree()           {
00184     if (_left)
00185         _left->delete_subtree();
00186     if (_right)
00187         _right->delete_subtree();
00188     // keep the destructor happy
00189     _references = NODE_DELETED;
00190     delete this;    /* and we are gone too */
00191     }
00192 
00196     void validate(const RefTrieNode *parent) const  {
00197     UNUSED(parent);
00198 #ifdef VALIDATE_XORP_TRIE
00199     if (_up != parent) {
00200         fprintf(stderr, "bad parent _up %x vs %x",
00201             (int)_up, (int)parent);
00202         abort();
00203     }
00204     if (_up && _k.contains(_up->_k)) {
00205         fprintf(stderr, "bad subnet order");
00206         abort();
00207     }
00208     if (_p == NULL && (!_left || !_right)) {
00209         fprintf(stderr, "useless internal node");
00210         abort();
00211     }
00212     if (_left)
00213         _left->validate(this);
00214     if (_right)
00215         _right->validate(this);
00216 #endif
00217     }
00218 
00223     bool is_left() const        { return _up && this == _up->_left; }
00224 
00225     RefTrieNode *leftmost() {
00226     RefTrieNode *n = this;
00227     while (n->_left || n->_right)
00228         n = (n->_left ? n->_left : n->_right);
00229     return n;
00230     }
00231 
00232 
00263     void find_bounds(const A& a, A &lo, A &hi) const    {
00264     RefTrieNode def = RefTrieNode();
00265     const RefTrieNode *n = const_find(Key(a, a.addr_bitlen()));
00266 
00267     if (n == NULL) {    // create a fake default entry
00268         def._left = const_cast<RefTrieNode *>(this);
00269         def._right = NULL;
00270         n = &def;
00271     }
00272     lo = n->_k.masked_addr();
00273     hi = n->_k.top_addr();
00274     for (const RefTrieNode *prev = NULL; prev != n;) {
00275         prev = n;
00276         RefTrieNode *x = (n->_left ? n->_left : n->_right);
00277         if (x == NULL)
00278         break;
00279         if (a < x->_k.masked_addr()) {      // case 1 and 1'
00280         hi = x->low();
00281         --hi;
00282         } else if (a <= x->_k.top_addr()) {     // case 2 and 2'
00283         n = x; // and continue
00284         } else if (n->_left == NULL || n->_right == NULL) { // case 3'
00285         lo = x->high();
00286         ++lo;
00287         } else if (a < n->_right->_k.masked_addr()) {   // case 3
00288         lo = x->high();
00289         ++lo;
00290         hi = n->_right->low();
00291         --hi;
00292         } else if (a <= n->_right->_k.top_addr()) { // case 4:
00293         n = n->_right; // and continue
00294         } else {                    // case 5:
00295         lo = n->_right->high();
00296         ++lo;
00297         }
00298     }
00299     // ensure destructor sanity check is happy
00300     def._references |= NODE_DELETED;
00301     }
00302 
00307     A low() const                   {
00308     const RefTrieNode *n = this;
00309     while (!(n->has_active_payload())
00310            && (n->_left || n->_right))
00311         n = (n->_left ? n->_left : n->_right);
00312     return n->_k.masked_addr();
00313     }
00314 
00319     A high() const                  {
00320     const RefTrieNode *n = this;
00321     while (!(n->has_active_payload())
00322            && (n->_right || n->_left))
00323         n = (n->_right ? n->_right : n->_left);
00324     return n->_k.top_addr();
00325     }
00326 
00327 private:
00328     /* delete_payload is a separate method to allow specialization */
00329     void delete_payload(Payload* p) {
00330     delete p;
00331     }
00332 
00333 
00334     void dump(const char *msg) const            {
00335 #if 0
00336     debug_msg(" %s %s %s\n",
00337           msg,
00338           _k.str().c_str(), _p ? "PL" : "[]");
00339     debug_msg("  U   %s\n",
00340           _up ? _up->_k.str().c_str() : "NULL");
00341     debug_msg("  L   %s\n",
00342           _left ? _left->_k.str().c_str() : "NULL");
00343     debug_msg("  R   %s\n",
00344           _right ? _right->_k.str().c_str() : "NULL");
00345 #endif
00346     UNUSED(msg);
00347     }
00348 
00349     RefTrieNode *_up, *_left, *_right;
00350     Key     _k;
00351     PPayload    *_p;
00352     uint32_t    _references;
00353 };
00354 
00355 
00364 template <class A, class Payload>
00365 class RefTriePostOrderIterator {
00366 public:
00367     typedef IPNet<A> Key;
00368     typedef ::RefTrie<A, Payload> RefTrie;
00369     typedef RefTrieNode<A, Payload> Node;
00370 
00374     RefTriePostOrderIterator()
00375     {
00376     _cur = NULL;
00377     _trie = NULL;
00378     }
00379 
00384     RefTriePostOrderIterator(const RefTrie* trie, Node *n)
00385     {
00386     _trie = trie;
00387     _cur = n;
00388     if (_cur) {
00389         _cur->incr_refcount();
00390         _root = n->k();
00391     }
00392     }
00393 
00398     RefTriePostOrderIterator(const RefTrie* trie, Node *n, const Key &k)
00399     {
00400     _trie = trie;
00401     _root = k;
00402     _cur = n;
00403 
00404     if (_cur) {
00405         begin();
00406         _cur->incr_refcount();
00407     }
00408     }
00409 
00410     RefTriePostOrderIterator(const RefTriePostOrderIterator& x)
00411     {
00412     // printf("copy constructor , new node: %p\n", x._cur);
00413     _trie = x._trie;
00414     _cur = x._cur;
00415     _root = x._root;
00416 
00417     if (_cur)
00418         _cur->incr_refcount();
00419     }
00420 
00421     ~RefTriePostOrderIterator()
00422     {
00423     if (_cur) {
00424         _cur->decr_refcount();
00425         if (_cur->deleted() && _cur->references() == 0) {
00426         // XXX uglyness alert.
00427         // printf("erasing node %p from iterator destructor\n", _cur);
00428         const_cast<RefTrie*>(_trie)->
00429             set_root(_cur->erase());
00430         }
00431     }
00432     }
00433 
00437     RefTriePostOrderIterator * begin()
00438     {
00439     Node * n = _cur;
00440     while (n->get_parent() && _root.contains(n->get_parent()->k()))
00441        n = n->get_parent();
00442     _cur = n->leftmost();
00443     return this;
00444     }
00445 
00452     RefTriePostOrderIterator operator ++(int)
00453     {
00454     // printf("postfix iterator: node was %p\n", _cur);
00455     RefTriePostOrderIterator x = *this;
00456     next();
00457     return x;
00458     }
00459 
00466     RefTriePostOrderIterator& operator ++()
00467     {
00468     next();
00469     return *this;
00470     }
00471 
00477     operator RefTriePreOrderIterator<A, Payload>() const
00478     {
00479     return RefTriePreOrderIterator<A, Payload>(_trie, _cur, _root);
00480     }
00481 
00482     void next() const
00483     {
00484     Node * oldnode = _cur;
00485     do {
00486        if (_cur->get_parent() == NULL) {
00487            _cur = NULL;
00488            break;             // cannot backtrack, finished
00489        }
00490        bool was_left_child = node_is_left(_cur);
00491        _cur = _cur->get_parent();
00492        // backtrack one level, then explore the leftmost path
00493        // on the right branch if not done already.
00494        if (was_left_child && _cur->get_right()) {
00495            _cur = _cur->get_right()->leftmost();
00496        }
00497        if (_root.contains(_cur->k()) == false) {
00498            _cur = NULL;
00499            break;
00500        }
00501     } while (_cur->has_payload() == false);       // found a good node.
00502 
00503     if (_cur)
00504         _cur->incr_refcount();
00505 
00506     // cleanup if this reduces the reference count on a deleted
00507     // node to zero
00508     if (oldnode) {
00509         oldnode->decr_refcount();
00510         if (oldnode->deleted() && oldnode->references() == 0) {
00511         // XXX uglyness alert.
00512         // printf("erasing node %p from prefix increment\n", oldnode);
00513         const_cast<RefTrie*>(_trie)->set_root(oldnode->erase());
00514         }
00515     }
00516     }
00517 
00518     void force_valid() const {
00519     while (_cur && _cur->deleted())
00520         next();
00521     }
00522 
00523     Node *cur() const { return _cur; }
00524 
00525     bool operator==(const RefTriePostOrderIterator & x) const
00526     {
00527     force_valid();
00528     x.force_valid();
00529     return (_cur == x._cur);
00530     }
00531 
00532     bool operator!=(const RefTriePostOrderIterator & x) const
00533     {
00534     force_valid();
00535     x.force_valid();
00536     return (_cur != x._cur);
00537     }
00538 
00539     Payload & payload()
00540     {
00541     /* Usage note: the node the iterator points at can be deleted.
00542        If there is any possibility that the node might have been
00543        deleted since the iterator was last examined, the user
00544        should compare this iterator with end() to force the
00545        iterator to move to the next undeleted node or move to
00546        end() if there is no undeleted node after the node that was
00547        deleted.  */
00548     /* Implementation node: We could have put a call to force_valid
00549            here, but the force_valid can move the iterator to the end
00550            of the trie, which would cause _cur to become NULL.  Then
00551            we'd have to assert here anyway.  Doing it this way makes
00552            it more likely that a failure to check will be noticed
00553            early */
00554     XLOG_ASSERT(!_cur->deleted());
00555     return _cur->p();
00556     };
00557     const Key & key() const
00558     {
00559     /* see payload() for usage note*/
00560     XLOG_ASSERT(!_cur->deleted());
00561     return _cur->k();
00562     };
00563 
00564     RefTriePostOrderIterator& operator=(const RefTriePostOrderIterator& x)
00565     {
00566     // printf("operator= , old node: %p new node: %p\n", _cur, x._cur);
00567     Node *oldnode = _cur;
00568     _cur = x._cur;
00569     _root = x._root;
00570 
00571     // need to increment before decrement, as the decrement might
00572     // cause deletion, which would be bad if the old Node was the
00573     // same as the new Node.
00574     if (_cur)
00575         _cur->incr_refcount();
00576     if (oldnode) {
00577         oldnode->decr_refcount();
00578         if (oldnode->deleted() && oldnode->references() == 0) {
00579         // XXX uglyness alert.
00580                 // printf("erasing node %p from prefix increment\n", oldnode);
00581         const_cast<RefTrie*>(_trie)->
00582             set_root(oldnode->erase());
00583         }
00584     }
00585     _trie = x._trie;
00586     return *this;
00587     }
00588 private:
00589     friend class RefTriePreOrderIterator<A, Payload>;
00590 
00591     mutable Node *_cur; /*this is mutable because const methods can
00592               cause the iterator to move from a deleted
00593               node to the first non-deleted node or
00594               end. */
00595 
00596     bool node_is_left(Node* n) const
00597     {
00598     return n->get_parent() && n  == n->get_parent()->get_left();
00599     }
00600     Key _root;
00601     const RefTrie* _trie;
00602 };
00603 
00604 /*
00605  * Preorder Iterator on a trie.
00606  *
00607  * _cur points to the current object, _root contains the search key for
00608  * root of the subtree we want to scan. The iterator does preorder traversal,
00609  * that is, current node first, then left then right.  This guarantees that
00610  * keys returned are sorted by prefix length.
00611  */
00612 template <class A, class Payload>
00613 class RefTriePreOrderIterator {
00614 public:
00615     typedef IPNet<A> Key;
00616     typedef ::RefTrie<A, Payload> RefTrie;
00617     typedef RefTrieNode<A, Payload> Node;
00618 
00622     RefTriePreOrderIterator()
00623     {
00624     _cur = NULL;
00625     _trie = NULL;
00626     }
00627 
00632     explicit RefTriePreOrderIterator(const RefTrie* trie, Node *n)
00633     {
00634     _trie = trie;
00635     _cur = n;
00636     if (_cur) {
00637         _cur->incr_refcount();
00638         _root = n->k();
00639     }
00640     }
00641 
00646     RefTriePreOrderIterator(const RefTrie* trie, Node *n,
00647     const Key &k)
00648     {
00649     _trie = trie;
00650     _root = k;
00651     _cur = n;
00652     if (_cur) {
00653         begin();
00654         _cur->incr_refcount();
00655     }
00656     }
00657 
00658     RefTriePreOrderIterator(const RefTriePreOrderIterator& x)
00659     {
00660     // printf("copy constructor , new node: %p\n", x._cur);
00661     _trie = x._trie;
00662     _cur = x._cur;
00663     _root = x._root;
00664 
00665     if (_cur)
00666         _cur->incr_refcount();
00667     }
00668 
00669     ~RefTriePreOrderIterator()
00670     {
00671     if (_cur) {
00672         _cur->decr_refcount();
00673         if (_cur->deleted() && _cur->references() == 0) {
00674         // XXX uglyness alert.
00675         // printf("erasing node %p from iterator destructor\n", _cur);
00676         const_cast<RefTrie*>(_trie)->
00677             set_root(_cur->erase());
00678         }
00679     }
00680     }
00681 
00685     RefTriePreOrderIterator * begin()
00686     {
00687     while (_cur->get_parent() && _root.contains(_cur->get_parent()->k()))
00688         _cur = _cur->get_parent();
00689     return this;
00690     }
00691 
00698     RefTriePreOrderIterator operator ++(int)
00699     {
00700     RefTriePreOrderIterator x = *this;
00701     next();
00702     return x;
00703     }
00704 
00711     RefTriePreOrderIterator& operator ++()
00712     {
00713     next();
00714     return *this;
00715     }
00716 
00722     operator RefTriePostOrderIterator<A, Payload>() const
00723     {
00724     return RefTriePostOrderIterator<A, Payload>(_trie, _cur, _root);
00725     }
00726 
00727     void next() const
00728     {
00729     Node * oldnode = _cur;
00730 
00731     if (_cur == NULL) return;
00732 
00733     do {
00734         if (_cur->get_left()) _cur=_cur->get_left();
00735         else {
00736         bool was_right_child = node_is_right(_cur);
00737         while (!(_cur->get_right() && !was_right_child) &&
00738             _cur->get_parent() &&
00739             _root.contains(_cur->get_parent()->k())) {
00740             was_right_child = node_is_right(_cur);
00741             _cur = _cur->get_parent();
00742         }
00743         if (!was_right_child && _cur->get_right())
00744             _cur = _cur->get_right();
00745         else {
00746             _cur = NULL;
00747             break;
00748         }
00749         }
00750     } while (_cur->has_payload() == false);      // found a good node.
00751 
00752     if (_cur)
00753         _cur->incr_refcount();
00754 
00755     // cleanup if this reduces the reference count on a deleted
00756     // node to zero
00757     if (oldnode) {
00758         oldnode->decr_refcount();
00759         if (oldnode->deleted() && oldnode->references() == 0) {
00760         // XXX uglyness alert.
00761         // printf("erasing node %p from prefix increment\n", oldnode);
00762         const_cast<RefTrie*>(_trie)->set_root(oldnode->erase());
00763         }
00764     }
00765     }
00766 
00767     void force_valid() const {
00768     while (_cur && _cur->deleted())
00769         next();
00770     }
00771 
00772     Node *cur() const { return _cur; }
00773 
00774     bool operator==(const RefTriePreOrderIterator & x) const
00775     {
00776     force_valid();
00777     x.force_valid();
00778     return (_cur == x._cur);
00779     }
00780 
00781     bool operator!=(const RefTriePreOrderIterator & x) const
00782     {
00783     force_valid();
00784     x.force_valid();
00785     return (_cur != x._cur);
00786     }
00787 
00788     Payload & payload()
00789     {
00790     /* Usage note: the node the iterator points at can be deleted.
00791        If there is any possibility that the node might have been
00792        deleted since the iterator was last examined, the user
00793        should compare this iterator with end() to force the
00794        iterator to move to the next undeleted node or move to
00795        end() if there is no undeleted node after the node that was
00796        deleted.  */
00797     /* Implementation node: We could have put a call to force_valid
00798            here, but the force_valid can move the iterator to the end
00799            of the trie, which would cause _cur to become NULL.  Then
00800            we'd have to assert here anyway.  Doing it this way makes
00801            it more likely that a failure to check will be noticed
00802            early */
00803     XLOG_ASSERT(!_cur->deleted());
00804     return _cur->p();
00805     };
00806     const Key & key() const
00807     {
00808     /* see payload() for usage note*/
00809     XLOG_ASSERT(!_cur->deleted());
00810     return _cur->k();
00811     };
00812 
00813     RefTriePreOrderIterator& operator=(const RefTriePreOrderIterator& x)
00814     {
00815     // printf("operator= , old node: %p new node: %p\n", _cur, x._cur);
00816     Node *oldnode = _cur;
00817     _cur = x._cur;
00818     _root = x._root;
00819 
00820     // need to increment before decrement, as the decrement might
00821     // cause deleetion, which would be bad if the old Node was the
00822     // same as the new Node.
00823     if (_cur)
00824         _cur->incr_refcount();
00825     if (oldnode) {
00826         oldnode->decr_refcount();
00827         if (oldnode->deleted() && oldnode->references() == 0) {
00828         // XXX uglyness alert.
00829                 // printf("erasing node %p from iter assignment\n", oldnode);
00830         const_cast<RefTrie*>(_trie)->set_root(oldnode->erase());
00831         }
00832     }
00833     _trie = x._trie;
00834     return *this;
00835     }
00836 
00837 private:
00838 
00839     friend class RefTriePostOrderIterator<A, Payload>;
00840 
00841     mutable Node* _cur; /*this is mutable because const methods can
00842               cause the iterator to move from a deleted
00843               node to the first non-deleted node or
00844               end. */
00845 
00846     bool node_is_right(Node* n) const
00847     {
00848     return n->get_parent() && n  == n->get_parent()->get_right();
00849     }
00850 
00851     Key      _root;
00852     const RefTrie* _trie;
00853 };
00854 
00855 
00865 template <class A, class Payload>
00866 class RefTrie {
00867 public:
00868     typedef IPNet<A> Key;
00869     typedef RefTrieNode<A, Payload> Node;
00870     typedef RefTriePostOrderIterator<A, Payload> iterator;
00871     typedef RefTriePostOrderIterator<A, Payload> PostOrderIterator;
00872     typedef RefTriePreOrderIterator<A, Payload> PreOrderIterator;
00873 
00877     RefTrie() : _root(0), _payload_count(0), _deleted(false)    {}
00878 
00879     virtual ~RefTrie()  { delete_all_nodes(); }
00880 
00881     void delete_self() {
00882     _deleted = true;
00883     if (_root == NULL)
00884         delete this;
00885     }
00886 
00887     void set_root(Node *root) { 
00888     _root = root; 
00889     if (_deleted) {
00890         delete this;
00891     }
00892     }
00893 
00900     iterator insert(const Key & net, const Payload& p) {
00901     bool replaced = false;
00902     Node *out = Node::insert(&_root, net, p, replaced);
00903     if (replaced) {
00904         fprintf(stderr, "overwriting a full node"); // XXX
00905         fprintf(stderr, "net %s\n", net.str().c_str());
00906     } else {
00907         _payload_count++;
00908     }
00909 #if 0
00910     printf("out->references: %d\n", out->references());
00911     if (out->deleted())
00912         printf("node is deleted\n");
00913 #endif
00914     return iterator(this, out);
00915     }
00916 
00921     void erase(const Key &k)            { erase(find(k)); }
00922 
00926     void erase(iterator i)          {
00927     if (_root && i.cur() && i.cur()->has_active_payload()) {
00928         _payload_count--;
00929             // printf("explicit erase on node %p\n", i.cur());
00930         _root = const_cast<Node *>(i.cur())->erase();
00931         // XXX should invalidate i ?
00932     }
00933     }
00934 
00939     iterator find(const Key &k) const       {
00940     return iterator(this, _root->find(k));
00941     }
00942 
00947     iterator find(const A& a) const     {
00948     return find(Key(a, a.addr_bitlen()));
00949     }
00950 
00951     iterator lower_bound(const Key &k) const {
00952 #ifdef NOTDEF
00953     iterator i = lookup_node(k);
00954     if (i != end())
00955         return i;
00956 #endif
00957     return iterator(this, _root->lower_bound(k));
00958     }
00959 
00960     iterator begin() const
00961     {
00962     return iterator(this, _root, IPNet<A>());
00963     }
00964 
00965     const iterator end() const
00966     {
00967     return iterator(const_cast<RefTrie*>(this), 0);
00968     }
00969 
00970     void delete_all_nodes()         {
00971     if (_root)
00972         _root->delete_subtree();
00973     _root = NULL;
00974     _payload_count = 0;
00975     }
00976 
00981     iterator lookup_node(const Key & k) const   {
00982     Node *n = _root->find(k);
00983     return (n && n->k() == k) ? iterator(this, n) : end();
00984     }
00985 
00990     iterator search_subtree(const Key &key) const {
00991     return iterator(this, _root->find_subtree(key), key);
00992     }
00993 
01000     iterator find_less_specific(const Key &key) const {
01001     // there are no less specific routes than the default route
01002     if(key.prefix_len() == 0)
01003         return end();
01004 
01005     Key x(key.masked_addr(), key.prefix_len() - 1);
01006 
01007     return iterator(this, _root->find(x));
01008     }
01009 
01014     void find_bounds(const A& a, A &lo, A &hi) const    {
01015     _root->find_bounds(a, lo, hi);
01016     }
01017 #if 0   // compatibility stuff, has to go
01018     /*
01019      * return the lower and higher address in the range that contains a
01020      * and would map to the same route.
01021      */
01022     A find_lower_bound(const A a) const     {
01023     A lo, hi;
01024     _root->find_bounds(a, lo, hi);
01025     return lo;
01026     }
01027     A find_higher_bound(const A a) const        {
01028     A lo, hi;
01029     _root->find_bounds(a, lo, hi);
01030     return hi;
01031     }
01032 
01033 #endif // compatibility
01034     int route_count() const         { return _payload_count; }
01035 
01036     void print() const;
01037     string str() const;
01038 
01039 private:
01040     void validate()             {
01041     if (_root)
01042         _root->validate(NULL);
01043     }
01044 
01045     Node    *_root;
01046     int     _payload_count;
01047 
01058     bool        _deleted;
01059 };
01060 
01061 
01067 template <class A, class Payload>
01068 RefTrieNode<A, Payload> *
01069 RefTrieNode<A, Payload>::insert(RefTrieNode **root,
01070                  const Key& x,
01071                  const Payload& p,
01072                  bool& replaced)
01073 {
01074     /*
01075      * Loop until done in the following:
01076      *
01077      * If *root == NULL, create a new RefTrieNode containing x and we are DONE.
01078      * Otherwise consider the possible cases of overlaps between the subnets
01079      * in *root (call it y) and x (+ indicates the middle of the interval):
01080      *
01081      *   y = (*root)          .|===+===|
01082      *
01083      *   x  0         .|---+---|
01084      *   x  A       |--|  .    .
01085      *   x  B             .    .     |--|
01086      *   x  C             . |-|.
01087      *   x  D             .    .|-|
01088      *   x  E  |----------+----------|
01089      *   x  F             |----------+-----------|
01090      *
01091      * case 0:  Same subnet. Store payload if *root if empty, replace otherwise.
01092      * case A:  allocate a new empty root, make old *root the right child,
01093      *      make a new node with x the left child. DONE.
01094      * case B:  allocate a new empty root, make old *root the left child,
01095      *      make a new node with x the right child. DONE.
01096      * case C:  repeat with root = &((*root)->left)
01097      * case D:  repeat with root = &((*root)->right)
01098      * case E:  *root = new node with x, old *root the right child, DONE.
01099      * case F:  *root = new node with x, old *root the left child, DONE.
01100      *
01101      * In all case, when we exit the loop, newroot contains the new value to
01102      * be assigned to *root;
01103      */
01104 
01105     RefTrieNode **oldroot = root;   // do we need it ?
01106     RefTrieNode *newroot = NULL, *parent = NULL, *me = NULL;
01107 
01108     debug_msg("++ insert %s\n", x.str().c_str());
01109     for (;;) {
01110     newroot = *root;
01111     if (newroot == NULL) {
01112         me = newroot = new RefTrieNode(x, p, parent);
01113         break;
01114     }
01115     parent = newroot->_up;
01116     Key y = newroot->_k;
01117     if (x == y) {                   /* case 0 */
01118         debug_msg("case 0\n");
01119         replaced = newroot->has_payload() & (!newroot->deleted());
01120         newroot->set_payload(p);
01121         me = newroot;
01122         break;
01123         }
01124 
01125     // boundaries of x and y, and their midpoints.
01126 
01127     A x_m = x.masked_addr() | ( ~(x.netmask()) >> 1 );
01128     A y_m = y.masked_addr() | ( ~(y.netmask()) >> 1 );
01129     A x_l = x.masked_addr();
01130     A x_h = x.top_addr();
01131     A y_l = y.masked_addr();
01132     A y_h = y.top_addr();
01133 
01134     if (x_h < y_l) {                /* case A */
01135         debug_msg("case A:  |--x--|   |--y--|\n");
01136         Key k = Key::common_subnet(x, y);
01137         newroot = new RefTrieNode(k, parent);   // create new root
01138         newroot->_right = *root;        // old root goes right
01139         newroot->_right->_up = newroot;
01140         newroot->_left = me = new RefTrieNode(x, p, newroot);
01141         break;
01142     } else if (y_h < x_l) {             /* case B */
01143         debug_msg("case B:  |--y--|   |--x--|\n");
01144         Key k = Key::common_subnet(x, y);
01145         newroot = new RefTrieNode(k, parent);   // create new root
01146         newroot->_left = *root;
01147         newroot->_left->_up = newroot;
01148         newroot->_right = me = new RefTrieNode(x, p, newroot);
01149         break;
01150     } else if (x_l >= y_l && x_h <= y_m) {      /* case C */
01151         debug_msg("case C:  |--x-.----|\n");
01152         parent = *root;
01153         root = &(newroot->_left);
01154     } else if (x_l > y_m && x_h <= y_h) {       /* case D */
01155         debug_msg("case D:  |----.-x--|\n");
01156         parent = *root;
01157         root = &(newroot->_right);
01158     } else if (y_l > x_m && y_h <= x_h) {       /* case E */
01159         debug_msg("case E:  |----.-Y--|\n");
01160         newroot = me = new RefTrieNode(x, p, parent);
01161         newroot->_right = *root;
01162         newroot->_right->_up = newroot;
01163         break;
01164     } else if (y_l >= x_l && y_h <= x_m) {      /* case F */
01165         debug_msg("case F:  |--Y-.----|\n");
01166         newroot = me = new RefTrieNode(x, p, parent);
01167         newroot->_left = *root;
01168         newroot->_left->_up = newroot;
01169         break;
01170     } else
01171         abort();    // impossible case in RefTrieNode::insert()
01172     }
01173     *root = newroot;
01174     if (*oldroot)
01175     (*oldroot)->validate(NULL);
01176     // (*oldroot)->print(0, "");
01177     return me;
01178 }
01179 
01180 
01186 template <class A, class Payload>
01187 RefTrieNode<A, Payload> *
01188 RefTrieNode<A, Payload>::erase()
01189 {
01190     RefTrieNode *me, *parent, *child;
01191     if ((_references & NODE_REFS_MASK) > 0) {
01192     _references |= NODE_DELETED;
01193     me = this;
01194     } else {
01195     _references |= NODE_DELETED;
01196     if (_p) {
01197         delete_payload(_p);
01198         _p = NULL;
01199     }
01200 
01201     debug_msg("++ erase %s\n", this->_k.str().c_str());
01202     /*
01203      * If the node ("me") exists, has no payload and at most one child,
01204      * then it is a useless internal node which needs to be removed by
01205      * linking the child to the parent. If the child is NULL, we need
01206      * to repeat the process up.
01207      */
01208     for (me = this; me && me->_p == NULL &&
01209          (me->_left == NULL || me->_right == NULL); ) {
01210 
01211         // me->dump("erase");           // debugging
01212 
01213         // Find parent and the one possible child (both can be NULL).
01214         parent = me->_up;
01215         child = me->_left ? me->_left : me->_right;
01216 
01217         if (child != NULL)      // if the child exists, link it to
01218         child->_up = parent;    // its new parent
01219 
01220         if (parent == NULL)     // no parent, child becomes new root
01221         parent = child;
01222         else { // i have a parent, link my child to it (left or right)
01223         if (parent->_left == me)
01224             parent->_left = child;
01225         else
01226             parent->_right = child;
01227         }
01228         // if we're deleting an intermediate node, mark it as
01229         // deleted to satisfy destructor sanity checks
01230         if (me->has_payload() == false)
01231         me->_references |= NODE_DELETED;
01232         delete me;          // nuke the node
01233         me = parent;
01234     }
01235     }
01236     // now navigate up to find and return the new root of the trie
01237     for ( ; me && me->_up ; me = me->_up)
01238     ;
01239     return me;
01240 }
01241 
01246 template <class A, class Payload>
01247 RefTrieNode<A, Payload> *
01248 RefTrieNode<A, Payload>::find(const Key &key)
01249 {
01250     RefTrieNode * cand = NULL;
01251     RefTrieNode * r = this;
01252 
01253     for ( ; r && r->_k.contains(key) ; ) {
01254     if (r->_p && !r->deleted())
01255         cand = r;       // we have a candidate.
01256     if (r->_left && r->_left->_k.contains(key))
01257         r = r->_left;
01258     else            // should check that right contains(key), but
01259         r = r->_right;  // the loop condition will do it for us.
01260     }
01261     return cand;
01262 }
01263 
01267 template <class A, class Payload>
01268 RefTrieNode<A, Payload> *
01269 RefTrieNode<A, Payload>::lower_bound(const Key &key)
01270 {
01271     RefTrieNode * cand = NULL;
01272     RefTrieNode * r = this;
01273     // printf("lower bound: %s\n", key.str().c_str());
01274     for ( ; r && r->_k.contains(key) ; ) {
01275     cand = r;       // any node is good, irrespective of payload.
01276     if (r->_left && r->_left->_k.contains(key))
01277         r = r->_left;
01278     else            // should check that right contains(key), but
01279         r = r->_right;  // the loop condition will do it for us.
01280     }
01281     if (cand == NULL)
01282     cand = this;
01283 
01284     if (cand->_k == key) {  // we found an exact match
01285     if (cand->_p) {     // we also have a payload, so we are done.
01286         // printf("exact match\n");
01287         return cand;
01288     } else {        // no payload, skip to the next (in postorder)
01289                 // node in the entire tree (null key as root)
01290         RefTriePostOrderIterator<A, Payload> iterator(NULL, cand, Key());
01291         ++iterator;
01292         return iterator.cur();
01293     }
01294     }
01295 
01296     // printf("no exact match\n");
01297     // No exact match exists.
01298     // cand holds what would be the parent of the node, if it existed.
01299     while (cand != NULL) {
01300     // printf("cand = %s\n", cand->str().c_str());
01301     if (cand->_left && (key < cand->_left->_k)) {
01302         return cand->_left->leftmost();
01303     }
01304     if (cand->_right && (key < cand->_right->_k)) {
01305         return cand->_right->leftmost();
01306     }
01307     cand = cand->_up;
01308     }
01309     return NULL;
01310 }
01311 
01315 template <class A, class Payload>
01316 RefTrieNode<A, Payload> *
01317 RefTrieNode<A, Payload>::find_subtree(const Key &key)
01318 {
01319     RefTrieNode *r = this;
01320     RefTrieNode *cand = r && key.contains(r->_k) ? r : NULL;
01321 
01322     for ( ; r && r->_k.contains(key) ; ) {
01323         cand = r;       // we have a candidate.
01324     if (r->_left && r->_left->_k.contains(key))
01325         r = r->_left;
01326     else            // should check that right contains(key), but
01327         r = r->_right;  // the loop condition will do it for us.
01328     }
01329     return cand;
01330 }
01331 
01332 template <class A, class Payload>
01333 void
01334 RefTrieNode<A, Payload>::print(int indent, const char *msg) const
01335 {
01336 #ifdef DEBUG_LOGGING
01337     debug_msg_indent(indent);
01338 
01339     if (this == NULL) {
01340     debug_msg("%sNULL\n", msg);
01341     return;
01342     }
01343     debug_msg("%skey: %s %s\n",
01344           msg, _k.str().c_str(), _p ? "PL" : "[]");
01345     debug_msg("    U: %s\n", _up ? _up->_k.str().c_str() : "NULL");
01346     _left->print(indent+4, "L: ");
01347     _right->print(indent+4, "R: ");
01348     debug_msg_indent(0);
01349 #endif /* DEBUG_LOGGING */
01350     UNUSED(indent);
01351     UNUSED(msg);
01352 }
01353 
01354 template <class A, class Payload>
01355 string
01356 RefTrieNode<A, Payload>::str() const
01357 {
01358     string s;
01359     if (this == NULL) {
01360     s = "NULL";
01361     return s;
01362     }
01363     s = c_format("key: %s ", _k.str().c_str());
01364     if (_p)
01365     s += "PL";
01366     else
01367     s += "[]";
01368     if ((_references & NODE_DELETED) != 0)
01369     s += " *DEL*";
01370     s += c_format("\n    U: %s\n", _up ? _up->_k.str().c_str() : "NULL");
01371     return s;
01372 }
01373 
01374 template <class A, class Payload>
01375 void
01376 RefTrie<A, Payload>::print() const
01377 {
01378     // this is called print - it should NOT use debug_msg!!!
01379     printf("---- print trie ---\n");
01380     _root->print(0, "");
01381     iterator ti;
01382     for (ti = begin() ; ti != end() ; ti++) {
01383     printf("*** node: %-26s ",
01384            ti.cur()->k().str().c_str());
01385     if (ti.cur()->has_active_payload())
01386         printf("PL\n");
01387     else if (ti.cur()->has_payload())
01388         printf("PL *DELETED* (%u refs)\n",
01389            XORP_UINT_CAST(ti.cur()->references()));
01390     else
01391         printf("[]\n");
01392     }
01393     printf("---------------\n");
01394 }
01395 
01396 template <class A, class Payload>
01397 string
01398 RefTrie<A, Payload>::str() const
01399 {
01400     string s = _root->str();
01401     iterator ti;
01402     for (ti = begin() ; ti != end() ; ti++) {
01403     s += c_format("*** node: %-26s ",
01404               ti.cur()->k().str().c_str());
01405     if (ti.cur()->has_active_payload())
01406         s += "PL\n";
01407     else if (ti.cur()->has_payload())
01408         s += c_format("PL *DELETED* (%u refs)\n",
01409               XORP_UINT_CAST(ti.cur()->references()));
01410     else
01411         s += "[]\n";
01412     }
01413     s += ("---------------\n");
01414     return s;
01415 }
01416 
01417 #endif // __LIBXORP_REF_TRIE_HH__
 All Classes Namespaces Functions Variables Typedefs Enumerations