xorp

spt.hh

00001 // -*- c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t -*-
00002 // vim:set sts=4 ts=8 sw=4:
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/libproto/spt.hh,v 1.23 2008/10/02 21:57:18 bms Exp $
00023 
00024 #ifndef __LIBPROTO_SPT_HH__
00025 #define __LIBPROTO_SPT_HH__
00026 
00027 // #define INCREMENTAL_SPT
00028 
00029 //#define DEBUG_LOGGING
00030 #define DEBUG_PRINT_FUNCTION_NAME
00031 
00032 #include "libxorp/ref_ptr.hh"
00033 #include "libxorp/c_format.hh"
00034 
00035 
00036 
00037 
00038 template <typename A> class Spt;
00039 template <typename A> class Edge;
00040 template <typename A> class Node;
00041 template <typename A> class PriorityQueue;
00042 template <typename A> class RouteCmd;
00043 
00050 template <typename A>
00051 class Spt {
00052  public:
00053     //    typedef Node<A>::NodeRef NodeRef;
00054     typedef map<A, typename Node<A>::NodeRef> Nodes;
00055 
00056     Spt(bool trace = true) : _trace(trace)
00057     {}
00058 
00059     ~Spt();
00060 
00064     void clear();
00065 
00071     bool set_origin(const A& node);
00072 
00078     bool add_node(const A& node);
00079 
00085     bool update_node(const A& node);
00086 
00093     bool remove_node(const A& node);
00094 
00100     bool exists_node(const A& node);
00101 
00110     bool add_edge(const A& src, int weight, const A& dst);
00111 
00120     bool update_edge_weight(const A& src, int weight, const A& dst);
00121 
00130     bool get_edge_weight(const A& src, int& weight, const A& dst);
00131 
00139     bool remove_edge(const A& src, const A& dst);
00140     
00148     bool compute(list<RouteCmd<A> >& routes);
00149 
00156     string str() const;
00157 
00161     typename Node<A>::NodeRef find_node(const A& node);
00162 
00163  private:
00164     bool _trace;        // True of tracing is enabled.
00170     bool dijkstra();
00171     
00177     bool incremental_spt();
00178 
00182     void garbage_collect();
00183 
00184     typename Node<A>::NodeRef _origin;  // Origin node
00185 
00186     Nodes _nodes;       // Nodes
00187 };
00188 
00189 template <typename A>
00190 class Node {
00191  public:
00192     typedef map <A, Edge<A> > adjacency; // Only one edge allowed
00193                      // between nodes.
00194 
00195     typedef ref_ptr<Node<A> > NodeRef;
00196 
00197     Node(A a, bool trace = false);
00198 
00199     ~Node();
00200 
00204     A nodename();
00205 
00214     bool set_nodename(A nodename);
00215 
00221     bool add_edge(NodeRef dst, int weight);
00222 
00228    bool update_edge_weight(NodeRef dst, int weight);
00229 
00235    bool get_edge_weight(NodeRef dst, int& weight);
00236 
00240     bool remove_edge(NodeRef dst);
00241 
00246     void drop_adjacencies();
00247 
00251     void garbage_collect();
00252 
00256     void set_valid(bool p) { _valid = p; }
00257 
00261     bool valid() { return _valid;}
00262 
00266     void set_tentative(bool p) { _tentative = p; }
00267 
00271     bool tentative() { return _tentative; }
00272 
00276     void invalidate_weights() { _current._valid = false; }
00277 
00281     bool valid_weight() { return _current._valid; }
00282 
00291     void set_adjacent_weights(NodeRef me, int delta_weight,
00292                   PriorityQueue<A>& tentative);
00293 
00301     bool set_local_weight(int weight);
00302 
00307     int get_local_weight();
00308 
00312     void set_first_hop(NodeRef n) { _current._first_hop = n; }
00313 
00317     NodeRef get_first_hop() {
00318     XLOG_ASSERT(_current._valid);
00319     return _current._first_hop;
00320     }
00321 
00325     void set_last_hop(NodeRef n) { _current._last_hop = n; }
00326 
00330     NodeRef get_last_hop() {
00331     XLOG_ASSERT(_current._valid);
00332     return _current._last_hop;
00333     }
00334 
00341     bool delta(RouteCmd<A>& rcmd);
00342 
00347     void clear() {
00348     _current.clear();
00349     _previous.clear();
00350     _adjacencies.clear();
00351     }
00352 
00356     string pp() const;
00357 
00362     string str() const;
00363  private:
00364     bool _valid;        // True if node is not marked for deletion.
00365     A _nodename;        // Node name, external name of this node.
00366     adjacency _adjacencies; // Adjacency list
00367     bool _trace;        // True of tracing is enabled.
00368 
00369     // private:
00370     //    friend class Spt<A>;
00371 
00372     bool _tentative;        // Intermediate state for Dijkstra.
00373 
00374     struct path {
00375     path()
00376         : _valid(false) {}
00377 
00378     bool _valid;        // Are these entries valid.
00379     NodeRef _first_hop; // On the path to this node, the
00380                 // neighbour of the origin.
00381     NodeRef _last_hop;  // On the path to this node the
00382                 // previous node.
00383     int _path_length;   // The sum of all the edge weights.
00384 
00385     void clear() {
00386         _first_hop = _last_hop = typename Node<A>::NodeRef();
00387     }
00388     };
00389 
00390     path _current;      // Current computation.
00391     path _previous;     // Previous computation.
00392 };
00393 
00394 template <typename A>
00395 class Edge {
00396  public:
00397     Edge() {}
00398     Edge(typename Node<A>::NodeRef dst, int weight) :
00399     _dst(dst), _weight(weight)
00400     {}
00401 
00402     string str() const {
00403     return c_format("%s(%d) ", _dst->str().c_str(), _weight);
00404     }
00405 
00406     typename Node<A>::NodeRef _dst;
00407     int _weight;
00408 };
00409 
00410 
00414 template <typename A> 
00415 class PriorityQueue {
00416  public:
00421     bool add(typename Node<A>::NodeRef n, int weight);
00422 
00426     typename Node<A>::NodeRef pop();
00427 
00428     bool empty() { return _tentative.empty(); }
00429  private:
00430 #ifndef XORP_USE_USTL
00431     template <typename B>
00432     struct lweight {
00433     bool
00434     operator ()(const typename Node<B>::NodeRef& a,
00435             const typename Node<B>::NodeRef& b) const {
00436         int aw = a->get_local_weight();
00437         int bw = b->get_local_weight();
00438 
00439         // If the weights match then sort on node names which must
00440         // be unique.
00441         if (aw == bw)
00442         return a.get() < b.get();
00443 
00444         return aw < bw;
00445     }
00446     };
00447 #endif
00448 
00449 #ifdef XORP_USE_USTL
00450     // TODO:  I tried making ref-ptr compare work..but don't know if
00451     // it is actually functional.  Need to fix up uSTL probably.
00452     typedef set<typename Node<A>::NodeRef> Tent;
00453 #else
00454     typedef set<typename Node<A>::NodeRef, lweight<A> > Tent;
00455 #endif
00456     Tent _tentative;
00457 };
00458 
00462 template <typename A>
00463 class RouteCmd {
00464  public:
00465     enum Cmd {ADD, DELETE, REPLACE};
00466 
00467     RouteCmd() {}
00468 
00469     RouteCmd(Cmd cmd, A node, A nexthop, A prevhop, int weight = 0,
00470          bool next_hop_changed = false, bool weight_changed = false) :
00471     _cmd(cmd), _node(node), _nexthop(nexthop), _prevhop(prevhop), 
00472     _weight(weight),_next_hop_changed(next_hop_changed),
00473     _weight_changed(weight_changed)
00474     
00475     {}
00476 
00477     Cmd cmd() const { return _cmd; }
00478     const A& node() const { return _node; }
00479     const A& nexthop() const { return _nexthop; }
00480     const A& prevhop() const { return _prevhop; }
00481     int weight() const { return _weight; }
00482     bool next_hop_changed() const { return _next_hop_changed; }
00483     bool weight_changed() const { return _weight_changed; }
00484 
00485     bool operator==(const RouteCmd& lhs) {
00486     return _cmd == lhs._cmd &&
00487         _node == lhs._node &&
00488         _nexthop == lhs._nexthop &&
00489         _prevhop == lhs._prevhop &&
00490         _weight == lhs._weight &&
00491         _next_hop_changed == lhs._next_hop_changed &&
00492         _weight_changed == lhs._weight_changed;
00493     }
00494 
00495     string c() const {
00496     string cmd;
00497     switch(_cmd) {
00498     case ADD:
00499         cmd = "ADD";
00500         break;
00501     case DELETE:
00502         cmd = "DELETE";
00503         break;
00504     case REPLACE:
00505         cmd = "REPLACE";
00506         break;
00507     }
00508     return cmd;
00509     }
00510 
00511 
00512     string str() const {
00513     return c() + " node: " + _node.str() +
00514         " nexthop: " + _nexthop.str() +
00515         " prevhop: " + _prevhop.str() +
00516         " weight: " + c_format("%d", _weight) +
00517         " next hop changed: " + bool_c_str(_next_hop_changed) +
00518         " weight changed: " + bool_c_str(_weight_changed);
00519     }
00520 
00521  private:
00522     Cmd _cmd;
00523     A _node;
00524     A _nexthop;
00525     A _prevhop;
00526     int _weight;
00527     bool _next_hop_changed;
00528     bool _weight_changed;
00529 };
00530 
00531 template <typename A>
00532 Spt<A>::~Spt()
00533 {
00534     clear();
00535 }
00536 
00537 template <typename A>
00538 void
00539 Spt<A>::clear()
00540 {
00541     //XLOG_TRACE(_trace, "Clearing spt %p.", this);
00542 
00543     // Release the origin node by assigning an empty value to its ref_ptr.
00544     _origin = typename Node<A>::NodeRef();
00545 
00546     // Free all node state in the Spt.
00547     // A depth first traversal might be more efficient, but we just want
00548     // to free memory here. Container Nodes knows nothing about the
00549     // degree of each Node.
00550     // Because the last node reference is held in the container we must be
00551     // careful not to introduce another one in this scope by using
00552     // a reference to a Node ref_ptr.
00553     while (! _nodes.empty()) {
00554     typename Nodes::iterator ii;
00555     for (ii = _nodes.begin(); ii != _nodes.end(); ) {
00556         typename Node<A>::NodeRef& rnr = (*ii).second;
00557         //XLOG_ASSERT(! rnr.is_empty());
00558         rnr->clear();
00559         if (rnr.is_only()) {
00560         _nodes.erase(ii++);
00561         } else {
00562         ii++;
00563         }
00564     }
00565     }
00566 }
00567 
00568 template <typename A>
00569 bool
00570 Spt<A>::set_origin(const A& node)
00571 {
00572     // Lookup this node. It must exist.
00573     typename Node<A>::NodeRef srcnode = find_node(node);
00574     if (srcnode.is_empty()) {
00575     XLOG_WARNING("Node does not exist %s", Node<A>(node).str().c_str());
00576     return false;
00577     }
00578 
00579     _origin = srcnode;
00580     return true;
00581 }
00582 
00583 template <typename A>
00584 bool
00585 Spt<A>::add_node(const A& node)
00586 {
00587     // If a valid node already exists return false
00588     typename Node<A>::NodeRef srcnode = find_node(node);
00589     if (!srcnode.is_empty()) {
00590     if (srcnode->valid()) {
00591         XLOG_WARNING("Node already exists %s",
00592              Node<A>(node).str().c_str());
00593         return false;
00594     } else {
00595         // We are going to revive this node so dump its adjacency
00596         // info.
00597         srcnode->drop_adjacencies();
00598         srcnode->set_valid(true);
00599         return true;
00600     }
00601     }
00602 
00603     Node<A> *n = new Node<A>(node, _trace);
00604     _nodes[node] = typename Node<A>::NodeRef(n);
00605 
00606     //debug_msg("added node %p\n", n);
00607 
00608     return true;
00609 }
00610 
00611 template <typename A>
00612 bool
00613 Spt<A>::update_node(const A& node)
00614 {
00615     // If a valid node doesn't exist return false
00616     typename Node<A>::NodeRef srcnode = find_node(node);
00617     if (srcnode.is_empty()) {
00618     XLOG_WARNING("Request to update non-existant node %s",
00619              Node<A>(node).str().c_str());
00620     return false;
00621     }
00622     if (!srcnode->valid()) {
00623     XLOG_WARNING("Node is not valid %s", Node<A>(node).str().c_str());
00624     return false;
00625     }
00626     srcnode->set_nodename(node);
00627 
00628     return true;
00629 }
00630 
00631 template <typename A>
00632 bool
00633 Spt<A>::remove_node(const A& node)
00634 {
00635     // If a valid node doesn't exist return false
00636     typename Node<A>::NodeRef srcnode = find_node(node);
00637     if (srcnode.is_empty()) {
00638     XLOG_WARNING("Request to delete non-existant node %s",
00639              Node<A>(node).str().c_str());
00640     return false;
00641     }
00642     if (!srcnode->valid()) {
00643     XLOG_WARNING("Node already removed %s", Node<A>(node).str().c_str());
00644     return false;
00645     }
00646     srcnode->set_valid(false);
00647 
00648     return true;
00649 }
00650 
00651 template <typename A>
00652 bool
00653 Spt<A>::exists_node(const A& node)
00654 {
00655     return _nodes.count(node);
00656 }
00657 
00658 template <typename A>
00659 bool
00660 Spt<A>::add_edge(const A& src, int weight, const A& dst)
00661 {
00662     // Find the src node it must exist.
00663     typename Node<A>::NodeRef srcnode = find_node(src);
00664     if (srcnode.is_empty()) {
00665     XLOG_WARNING("Node: %s not found", Node<A>(src).str().c_str());
00666     return false;
00667     }
00668 
00669     // The dst node doesn't have to exist. If it doesn't exist create it.
00670     typename Node<A>::NodeRef dstnode = find_node(dst);
00671     if (dstnode.is_empty()) {
00672     if (!add_node(dst)) {
00673         XLOG_WARNING("Add node %s failed", Node<A>(dst).str().c_str());
00674         return false;
00675     }
00676     }
00677     
00678     dstnode = find_node(dst);
00679     if (dstnode.is_empty()) {
00680     XLOG_WARNING("Node: %s not found",  Node<A>(dst).str().c_str());
00681     return false;
00682     }
00683 
00684     return srcnode->add_edge(dstnode, weight);
00685 }
00686 
00687 template <typename A>
00688 bool
00689 Spt<A>::update_edge_weight(const A& src, int weight, const A& dst)
00690 {
00691     typename Node<A>::NodeRef srcnode = find_node(src);
00692     if (srcnode.is_empty()) {
00693     debug_msg("Node: %s not found\n", Node<A>(src).str().c_str());
00694     return false;
00695     }
00696 
00697     typename Node<A>::NodeRef dstnode = find_node(dst);
00698     if (dstnode.is_empty()) {
00699     debug_msg("Node: %s not found\n", Node<A>(dst).str().c_str());
00700     return false;
00701     }
00702 
00703     return srcnode->update_edge_weight(dstnode, weight);
00704 }
00705 
00706 template <typename A>
00707 bool
00708 Spt<A>::get_edge_weight(const A& src, int& weight, const A& dst)
00709 {
00710     typename Node<A>::NodeRef srcnode = find_node(src);
00711     if (srcnode.is_empty()) {
00712     debug_msg("Node: %s not found\n", Node<A>(src).str().c_str());
00713     return false;
00714     }
00715 
00716     typename Node<A>::NodeRef dstnode = find_node(dst);
00717     if (dstnode.is_empty()) {
00718     debug_msg("Node: %s not found\n", Node<A>(dst).str().c_str());
00719     return false;
00720     }
00721 
00722     return srcnode->get_edge_weight(dstnode, weight);
00723 }
00724 
00725 template <typename A>
00726 bool
00727 Spt<A>::remove_edge(const A& src, const A& dst)
00728 {
00729     typename Node<A>::NodeRef srcnode = find_node(src);
00730     if (srcnode.is_empty()) {
00731     debug_msg("Node: %s not found\n", Node<A>(src).str().c_str());
00732     return false;
00733     }
00734 
00735     typename Node<A>::NodeRef dstnode = find_node(dst);
00736     if (dstnode.is_empty()) {
00737     debug_msg("Node: %s not found\n", Node<A>(dst).str().c_str());
00738     return false;
00739     }
00740 
00741     return srcnode->remove_edge(dstnode);
00742 }
00743 
00744 template <typename A>
00745 bool
00746 Spt<A>::compute(list<RouteCmd<A> >& routes)
00747 {
00748 #ifdef  INCREMENTAL_SPT
00749     if (!incremental_spt())
00750     return false;
00751 #else
00752     if (!dijkstra())
00753     return false;
00754 #endif
00755 
00756     for(typename Nodes::const_iterator ni = _nodes.begin();
00757     ni != _nodes.end(); ni++) {
00758     // We don't need to know how to reach ourselves.
00759     if (ni->second == _origin)
00760         continue;
00761     RouteCmd<A> rcmd;
00762     if (ni->second->delta(rcmd))
00763         routes.push_back(rcmd);
00764     }
00765 
00766     // Remove all the deleted nodes.
00767     garbage_collect();
00768 
00769     return true;
00770 }
00771 
00772 template <typename A>
00773 string
00774 Spt<A>::str() const
00775 {
00776     string pres;
00777 
00778     if (_origin.is_empty()) {
00779     pres = "No origin\n";
00780     } else
00781     pres = "Origin: " + _origin->str() + "\n";
00782 
00783     for(typename Nodes::const_iterator ni = _nodes.begin();
00784     ni != _nodes.end(); ni++) {
00785     pres += ni->second->pp() + "\n";
00786     }
00787 
00788     return pres;
00789 }
00790 
00791 template <typename A>
00792 inline
00793 void
00794 init_dijkstra(const pair<A, typename Node<A>::NodeRef >& p)
00795 {
00796     p.second->set_tentative(true);
00797     p.second->invalidate_weights();
00798 }
00799 
00800 template <typename A>
00801 bool
00802 Spt<A>::dijkstra()
00803 {
00804     if (_origin.is_empty()) {
00805     XLOG_WARNING("No origin");
00806     return false;
00807     }
00808 
00809     for_each(_nodes.begin(), _nodes.end(), init_dijkstra<A>);
00810 
00811     typename Node<A>::NodeRef current = _origin;
00812     _origin->set_tentative(false);
00813 
00814     int weight = 0;
00815     // Map of tentative nodes.
00816     PriorityQueue<A> tentative;
00817 
00818     for(;;) {
00819     // Set the weight on all the nodes that are adjacent to this one.
00820     current->set_adjacent_weights(current, weight, tentative);
00821 
00822     if (tentative.empty())
00823         break;
00824 
00825     current = tentative.pop();
00826     XLOG_ASSERT(!current.is_empty());
00827 
00828     // Get the weight of this node.
00829     weight = current->get_local_weight();
00830 
00831     // Make the node permanent.
00832     current->set_tentative(false);
00833 
00834     // Compute the next hop to get to this node.
00835     typename Node<A>::NodeRef prev = current->get_last_hop();
00836     if (prev == _origin)
00837         current->set_first_hop(current);
00838     else
00839         current->set_first_hop(prev->get_first_hop());
00840 
00841     debug_msg("Previous: %s\n", prev->str().c_str());
00842     debug_msg("Permanent: %s distance %d next hop %s\n",
00843           current->str().c_str(),
00844           weight,
00845           current->get_first_hop()->str().c_str());
00846     }
00847     
00848     return true;
00849 }
00850 
00851 template <typename A>
00852 bool
00853 Spt<A>::incremental_spt()
00854 {
00855     XLOG_UNFINISHED();
00856 
00857     return true;
00858 }
00859 
00860 template <typename A>
00861 typename Node<A>::NodeRef
00862 Spt<A>::find_node(const A& node)
00863 {
00864     typename map<A, typename Node<A>::NodeRef>::iterator i = _nodes.find(node);
00865 
00866     if (i != _nodes.end()) {
00867     // debug_msg("Node %s found\n", Node<A>(node).str().c_str());
00868     return (*i).second;
00869     }
00870 
00871     //  debug_msg("Node %s not found\n", Node<A>(node).str().c_str());
00872 
00873 //    Node<A> *n = 0;
00874     return typename Node<A>::NodeRef(/*n*/);
00875 }
00876 
00877 template <typename A>
00878 Node<A>::Node(A nodename, bool trace)
00879     :  _valid(true), _nodename(nodename), _trace(trace)
00880 {
00881 }
00882 
00883 template <typename A>
00884 Node<A>::~Node()
00885 {
00886     clear();
00887 }
00888 
00889 template <typename A>
00890 A
00891 Node<A>::nodename()
00892 {
00893     return _nodename;
00894 }
00895 
00896 template <typename A>
00897 bool
00898 Node<A>::set_nodename(A nodename)
00899 {
00900     _nodename = nodename;
00901     
00902     return true;
00903 }
00904 
00905 template <typename A>
00906 bool
00907 Node<A>::add_edge(NodeRef dst, int weight)
00908 {
00909     // See if this edge already exists.
00910     typename adjacency::iterator i = _adjacencies.find(dst->nodename());
00911 
00912     // If this edge already exists consider this an error.
00913     if (i != _adjacencies.end()) {
00914     debug_msg("Edge from %s to %s exists\n", str().c_str(),
00915           dst->str().c_str());
00916     return false;
00917     }
00918 
00919     _adjacencies.insert(make_pair(dst->nodename(), Edge<A>(dst, weight)));
00920 
00921     return true;
00922 }
00923 
00924 template <typename A>
00925 bool
00926 Node<A>::update_edge_weight(NodeRef dst, int weight)
00927 {
00928     typename adjacency::iterator i = _adjacencies.find(dst->nodename());
00929 
00930     // This edge should exist.
00931     if (i == _adjacencies.end()) {
00932     debug_msg("Edge from %s to %s doesn't exists\n", str().c_str(),
00933           dst->str().c_str());
00934     return false;
00935     }
00936 
00937     Edge<A> edge = i->second;
00938     edge._weight = weight;
00939     i->second = edge;
00940 
00941     return true;
00942 }
00943 
00944 template <typename A>
00945 bool
00946 Node<A>::get_edge_weight(NodeRef dst, int& weight)
00947 {
00948     typename adjacency::iterator i = _adjacencies.find(dst->nodename());
00949 
00950     // This edge should exist.
00951     if (i == _adjacencies.end()) {
00952     debug_msg("Edge from %s to %s doesn't exists\n", str().c_str(),
00953           dst->str().c_str());
00954     return false;
00955     }
00956 
00957     Edge<A> edge = i->second;
00958     weight = edge._weight;
00959 
00960     return true;
00961 }
00962 
00963 template <typename A>
00964 bool
00965 Node<A>::remove_edge(NodeRef dst)
00966 {
00967     typename adjacency::iterator i = _adjacencies.find(dst->nodename());
00968 
00969     if (i == _adjacencies.end()) {
00970     XLOG_WARNING("Edge from %s to %s doesn't exists", str().c_str(),
00971              dst->str().c_str());
00972     return false;
00973     }
00974 
00975     _adjacencies.erase(i);
00976 
00977     return true;
00978 }
00979 
00980 template <typename A>
00981 void
00982 Node<A>::drop_adjacencies()
00983 {
00984     _adjacencies.clear();
00985 }
00986 
00987 template <typename A>
00988 void
00989 Node<A>::garbage_collect()
00990 {
00991     typename adjacency::iterator ni;
00992     for(ni = _adjacencies.begin(); ni != _adjacencies.end();) {
00993     NodeRef node = ni->second._dst;
00994     if (!node->valid()) {
00995         // Clear any references that this node may have to itself.
00996         node->clear();
00997         _adjacencies.erase(ni++);
00998     } else {
00999         ni++;
01000     }
01001     }    
01002 }
01003 
01004 template <typename A>
01005 void
01006 Node<A>::set_adjacent_weights(NodeRef me, int delta_weight,
01007                   PriorityQueue<A>& tentative)
01008 {
01009     typename adjacency::iterator i;
01010     for(i = _adjacencies.begin(); i != _adjacencies.end(); i++) {
01011     NodeRef n = i->second._dst;
01012     debug_msg("Node: %s\n", n->str().c_str());
01013     if (n->valid() && n->tentative()) {
01014         // It is critial that the weight of a node is not changed
01015         // while it is in the PriorityQueue.
01016         if (tentative.add(n, delta_weight + i->second._weight))
01017         n->set_last_hop(me);
01018     }
01019     }
01020 }
01021 
01022 template <typename A>
01023 bool
01024 Node<A>::set_local_weight(int weight)
01025 {
01026     // If this node is no longer tentative we shouldn't be changing
01027     // its value.
01028     XLOG_ASSERT(_tentative);
01029 
01030     bool accepted = false;
01031 
01032     // If no valid state exists just set the weight otherwise make
01033     // sure it's less than the value already present.
01034     if (!_current._valid) {
01035     _current._path_length = weight;
01036     _current._valid = true;
01037     accepted = true;
01038     } else {
01039     if (_current._path_length > weight) {
01040         _current._path_length = weight;
01041         accepted = true;
01042     }
01043     }
01044 
01045     return accepted;
01046 }
01047 
01048 template <typename A>
01049 int
01050 Node<A>::get_local_weight()
01051 {
01052 //     debug_msg("Node: %s\n", str().c_str());
01053 
01054     // This node must be valid, tentative and its value must be valid.
01055 
01056     XLOG_ASSERT(_valid);
01057     XLOG_ASSERT(_tentative);
01058     XLOG_ASSERT(_current._valid);
01059 
01060     return _current._path_length;
01061 }
01062 
01063 template <typename A>
01064 bool
01065 Node<A>::delta(RouteCmd<A>& rcmd)
01066 {
01067     // Has this node been deleted?
01068     if (!valid()) {
01069     rcmd = RouteCmd<A>(RouteCmd<A>::DELETE,
01070                nodename(), nodename(), nodename());
01071     return true;
01072     }
01073 
01074     path p,c;
01075     c = _current;
01076     p = _previous;
01077     _previous = _current;
01078 
01079     // It is possible that this node is not reachable.
01080     if (!c._valid) {
01081     XLOG_TRACE(_trace, "Node: %s not reachable", str().c_str());
01082     if (p._valid) {
01083         rcmd = RouteCmd<A>(RouteCmd<A>::DELETE,
01084                    nodename(), nodename(), nodename());
01085         return true;        
01086     }
01087     return false;
01088     }
01089 
01090     // If the previous result is invalid this is a new route.
01091     if (!p._valid) {
01092     XLOG_ASSERT(_current._valid);
01093     rcmd = RouteCmd<A>(RouteCmd<A>::ADD, nodename(),
01094                _current._first_hop->nodename(),
01095                _current._last_hop->nodename(),
01096                _current._path_length);
01097     return true;
01098     }
01099 
01100     XLOG_ASSERT(c._valid);
01101     XLOG_ASSERT(p._valid);
01102 
01103     // If nothing has changed, nothing to report.
01104     if (c._first_hop == p._first_hop && c._path_length == p._path_length)
01105     return false;
01106 
01107     rcmd = RouteCmd<A>(RouteCmd<A>::REPLACE, nodename(),
01108                _current._first_hop->nodename(),
01109                _current._last_hop->nodename(),
01110                _current._path_length,
01111                c._first_hop != p._first_hop,
01112                c._path_length != p._path_length);
01113 
01114     return true;
01115 }
01116 
01117 template <typename A>
01118 class Pa: public unary_function<pair<A, Edge<A> >, void> {
01119  public:
01120     void operator()(const pair<A, Edge<A> >& p) {
01121     Edge<A> e = p.second;
01122     _result += e.str();
01123     }
01124 
01125     string result() const {
01126     return _result;
01127     }
01128  private:
01129     string _result;
01130 };
01131 
01132 template <typename A>
01133 string
01134 Node<A>::pp() const
01135 {
01136     string result = str() + ":: ";
01137 
01138     result += for_each(_adjacencies.begin(),_adjacencies.end(),
01139                Pa<A>()).result();
01140 
01141     return result;
01142 }
01143 
01144 template <typename A>
01145 string
01146 Node<A>::str() const
01147 {
01148     return _nodename.str();
01149 }
01150 
01151 #if 0
01152 template <>
01153 string
01154 Node<string>::str() const
01155 {
01156     return _nodename;
01157 }
01158 #endif
01159 
01160 template <typename A>
01161 inline
01162 void
01163 gc(const pair<A, typename Node<A>::NodeRef >& p)
01164 {
01165     p.second->garbage_collect();
01166 }
01167 
01168 template <typename A>
01169 void
01170 Spt<A>::garbage_collect()
01171 {
01172     // Remove all the invalid nodes.
01173     // Use a reference, no need to bump the ref_ptr in this scope.
01174     for(typename Nodes::iterator ni = _nodes.begin(); ni != _nodes.end();) {
01175     typename Node<A>::NodeRef& node = ni->second;
01176     if (!node->valid()) {
01177         _nodes.erase(ni++);
01178     } else {
01179         ni++;
01180     }
01181     }
01182 
01183     // Garbage collect all the edges that point at deleted nodes.
01184     for_each(_nodes.begin(), _nodes.end(), gc<A>);
01185 }
01186 
01187 template <typename A> 
01188 bool
01189 PriorityQueue<A>::add(typename Node<A>::NodeRef n, int weight)
01190 {
01191     // Find this node if its already in set and remove it.
01192     if (n->valid_weight()) {
01193     typename Tent::iterator i = _tentative.find(n);
01194     for(; i != _tentative.end(); i++) {
01195         if ((*i) == n) {
01196 //      debug_msg("Erase %s\n", (*i)->str().c_str());
01197         _tentative.erase(i);
01198         break;
01199         }
01200     }
01201     }
01202     bool accepted = n->set_local_weight(weight);
01203     _tentative.insert(n);
01204 
01205     return accepted;
01206 //     debug_msg("Insert %s\n", n->str().c_str());
01207 }
01208 
01209 template <typename A> 
01210 typename Node<A>::NodeRef
01211 PriorityQueue<A>::pop()
01212 {
01213     // Find this node if its already in set and remove it.
01214     typename Tent::iterator i = _tentative.begin();
01215     if (i == _tentative.end())
01216     return typename Node<A>::NodeRef();
01217 
01218     typename Node<A>::NodeRef n = *i;
01219     _tentative.erase(i);
01220 
01221 //     debug_msg("Pop %s\n", n->str().c_str());
01222 
01223     return n;
01224 }
01225 
01226 #endif // __LIBPROTO_SPT_HH__
 All Classes Namespaces Functions Variables Typedefs Enumerations