#include "manetGraph.h" #include #include NetGraph::Cost::Cost() { } NetGraph::Cost::~Cost() { } NetGraph::Link::Link() { } NetGraph::Link::~Link() { } void NetGraph::Link::SetCost(const Cost& cost) { AccessCost() = cost; } // end NetGraph::Link::SetCost() NetGraph::Interface::Interface(Node& theNode, const ProtoAddress& addr) : node(&theNode),graph(NULL),default_addr_item(addr), name_ptr(NULL) { addr_list.InsertItem(default_addr_item); } NetGraph::Interface::Interface(Node& theNode) : node(&theNode), graph(NULL), default_addr_item(PROTO_ADDR_NONE), name_ptr(NULL) { } NetGraph::Interface::~Interface() { if(graph != NULL) graph->RemoveInterface(*this); Cleanup(); // Note "Cleanup()" would also remove it from "graph" if (!addr_list.IsEmpty()) { node->RemoveInterface(*this); addr_list.RemoveItem(default_addr_item); // Note "addr_list" destructor destroys any remaining items in list } else if (NULL != name_ptr) { node->RemoveInterface(*this); } if (NULL != name_ptr) delete[] name_ptr; } bool NetGraph::Interface::SetName(const char* theName) { int length = strlen(theName); char* namePtr = new char[length+1]; namePtr[length] = '\0'; bool reattach = false;//we will reattach iff a name already existed if (NULL == namePtr) { PLOG(PL_ERROR,"NetGraph::Interface::SetName(): new name_ptr error: %s\n", GetErrorString()); return false; } if (NULL != name_ptr) { if (addr_list.IsEmpty()) { reattach = true; // Is using name as ProtoGraph::vertice_list index and Node::iface_list index node->RemoveInterface(*this); // will reattach below if (NULL != graph) graph->SuspendInterface(*this); // will "resume" below } delete[] name_ptr; // delete old "name_ptr" } name_ptr = namePtr; strcpy(name_ptr, theName); if (addr_list.IsEmpty() && reattach) { // Now that we have an "indice" for this interface, it can be fully // associated with its "graph" (if applicable) and "node" if (NULL != graph) // if no addr, graph is only non-NULL if there was prior name { if (!graph->ResumeInterface(*this)) { PLOG(PL_ERROR,"NetGraph::Interface::SetName() error: unable to reattach interface to graph: %s\n", GetErrorString()); graph->RemoveInterface(*this); return false; } } if (!node->AddInterface(*this)) { PLOG(PL_ERROR,"NetGraph::Interface::SetName() error: unable to add interface to node: %s\n", GetErrorString()); delete[] name_ptr; name_ptr = NULL; return false; } } return true; } // end NetGraph::Interface::SetName() void NetGraph::Interface::ClearName() { if (NULL != name_ptr) { if (addr_list.IsEmpty()) { node->RemoveInterface(*this); if (NULL != graph) graph->RemoveInterface(*this); // all links are lost } delete[] name_ptr; name_ptr = NULL; } } // NetGraph::Interface::ClearName() // TBD - add a "makeDefault" optional argument to make the new address the default? bool NetGraph::Interface::AddAddress(const ProtoAddress& theAddress) { // Add the new address if (addr_list.IsEmpty()) { if (NULL != name_ptr) { // We're adding an address to a "name-only" interface, // so we need to remove/reinsert this iface from the Node & Graph // so that is properly indexed. node->RemoveInterface(*this); if (NULL != graph) graph->SuspendInterface(*this); // temporarily remove from ProtoGraph::vertice_list } default_addr_item.SetAddress(theAddress); if (NULL != graph) // note that "graph" will be non-null iff there _was_ a name_ptr { if (!graph->ResumeInterface(*this)) { PLOG(PL_ERROR, "NetGraph::Interface::AddAddress() error: failed to add interface to graph\n"); default_addr_item.SetAddress(PROTO_ADDR_NONE); return false; } if (!graph->AddInterfaceAddress(*this, theAddress)) { PLOG(PL_ERROR, "NetGraph::Interface::AddAddress() error: failed to add address to graph\n"); graph->RemoveInterface(*this); default_addr_item.SetAddress(PROTO_ADDR_NONE); return false; } } if (!node->AddInterface(*this)) { // This should only occur if we're out of memory PLOG(PL_ERROR, "NetGraph::Interface::AddAddress() error: failed to add interface to node\n"); if (NULL != graph) graph->RemoveInterface(*this); // removes links, too default_addr_item.SetAddress(PROTO_ADDR_NONE); return false; } } else if (addr_list.Insert(theAddress)) { // If already had address, it's a given that we're already in the node's iface_list if (!node->AddExtraInterfaceAddress(*this, theAddress)) { PLOG(PL_ERROR, "NetGraph::Interface::AddAddress() error: failed to add address to node\n"); RemoveAddress(theAddress); return false; } if (NULL != graph) { if (!graph->AddInterfaceAddress(*this, theAddress)) { PLOG(PL_ERROR, "NetGraph::Interface::AddAddress() error: failed to add address to graph\n"); RemoveAddress(theAddress); return false; } } } else { PLOG(PL_ERROR, "NetGraph::Interface::AddAddress() error: %s\n", GetErrorString()); return false; } return true; } // end NetGraph::Interface::AddAddress() bool NetGraph::Interface::RemoveAddress(const ProtoAddress& theAddress) { #ifdef PROTO_DEBUG ASSERT(Contains(theAddress)); // not good practice to call RemoveAddress() #else if (!Contains(theAddress)) return false; #endif if (theAddress.HostIsEqual(default_addr_item.GetAddress())) { // This is the address used for Node/Graph indices, so do some extra work here node->RemoveInterface(*this); if (NULL != graph) { addr_list.RemoveItem(default_addr_item); if (addr_list.IsEmpty() && (NULL == name_ptr)) { // Are not allowed to remove only address of interface with no name addr_list.InsertItem(default_addr_item); if (!node->AddInterface(*this)) PLOG(PL_ERROR, "NetGraph::Interface::RemoveAddress() error: failed to reattach interface to node\n"); return false; } addr_list.InsertItem(default_addr_item); graph->SuspendInterface(*this); // we make sure to "resume" it below } addr_list.RemoveItem(default_addr_item); if (addr_list.IsEmpty()) { default_addr_item.SetAddress(PROTO_ADDR_NONE); if (NULL != name_ptr) { if (NULL != graph) { // reinserts interface into graph now indexed by "name" if (!graph->ResumeInterface(*this)) { PLOG(PL_ERROR, "NetGraph::Interface::RemoveAddress() error: failed to reinsert interface into graph\n"); if (!node->AddInterface(*this)) // probably will fail, too PLOG(PL_ERROR, "NetGraph::Interface::RemoveAddress() error: failed to reattach interface to node\n"); return false; } graph->RemoveInterfaceAddress(theAddress); } // Put iface into node iface_list now indexed by name if (!node->AddInterface(*this)) { PLOG(PL_ERROR, "NetGraph::Interface::RemoveAddress() error: failed to reattach interface to node\n"); if (NULL != graph) graph->RemoveInterface(*this); // note all links are lost return false; // note address was removed, but ... } } else { // No remaining name or address, so remove from graph, if applicable if (NULL != graph) graph->RemoveInterface(*this); // note all links are lost } } else { // We'll use a remaining address as the the new "default" address ProtoAddressList::Item* rootItem = addr_list.RemoveRootItem(); default_addr_item = *rootItem; delete rootItem; addr_list.InsertItem(default_addr_item); if (NULL != graph) { // reinserts interface into graph now indexed by new default address if (!graph->ResumeInterface(*this)) { PLOG(PL_ERROR, "NetGraph::Interface::RemoveAddress() error: failed to reinsert interface into graph\n"); if (!node->AddInterface(*this)) // probably will fail, too PLOG(PL_ERROR, "NetGraph::Interface::RemoveAddress() error: failed to reattach interface to node\n"); return false; } graph->RemoveInterfaceAddress(theAddress); } // Put iface into node iface_list now indexed by new default address if (!node->AddInterface(*this)) { PLOG(PL_ERROR, "NetGraph::Interface::RemoveAddress() error: failed to reattach interface to node\n"); if (NULL != graph) graph->RemoveInterface(*this); // note all links are lost return false; // note address was removed, but ... } } } else { addr_list.Remove(theAddress); node->RemoveExtraInterfaceAddress(theAddress); if (NULL != graph) graph->RemoveInterfaceAddress(theAddress); } return true; } // end NetGraph::Interface::RemoveAddress() bool NetGraph::Interface::ChangeNode(Node& theNode) { ASSERT(NULL != node); node->RemoveInterface(*this); node = &theNode; if(!theNode.AddInterface(*this)) { PLOG(PL_ERROR, "NetGraph::Interface::SetNode: error: AddInterface returned false\n"); return false; } return true; } // end NetGraph::Interface::ChangeNode() NetGraph::AdjacencyIterator::AdjacencyIterator(Interface& theInterface) : ProtoGraph::AdjacencyIterator(theInterface) { } NetGraph::AdjacencyIterator::~AdjacencyIterator() { } NetGraph::Interface::SimpleList::SimpleList(ItemPool* itemPool) : Vertice::SimpleList(itemPool) { } NetGraph::Interface::SimpleList::~SimpleList() { } NetGraph::Interface::SimpleList::Iterator::Iterator(const SimpleList& theList) : ProtoGraph::Vertice::SimpleList::Iterator(theList) { } NetGraph::Interface::SimpleList::Iterator::~Iterator() { } NetGraph::Interface::SortedList::SortedList(ItemPool* itemPool) : Vertice::SortedList(itemPool) { } NetGraph::Interface::SortedList::~SortedList() { } NetGraph::Interface::SortedList::Iterator::Iterator(SortedList& theList) : ProtoGraph::Vertice::SortedList::Iterator(theList) { } NetGraph::Interface::SortedList::Iterator::~Iterator() { } NetGraph::Interface::PriorityQueue::Item::Item() : prev_hop(NULL), next_hop_link(NULL) { } NetGraph::Interface::PriorityQueue::Item::~Item() { } NetGraph::Interface::PriorityQueue::ItemFactory::ItemFactory() { } NetGraph::Interface::PriorityQueue::ItemFactory::~ItemFactory() { Destroy(); } NetGraph::Interface::PriorityQueue::Item* NetGraph::Interface::PriorityQueue::ItemFactory::GetItem() { Item* item = static_cast(item_pool.QueueStatePool::Get()); if (NULL == item) item = CreateItem(); if (NULL == item) PLOG(PL_ERROR, "NetGraph::Interface::PriorityQueue::ItemFactory::GetItem() CreateItem() error: %s\n", GetErrorString()); return item; } // end NetGraph::Interface::PriorityQueue::ItemFactory::GetItem() NetGraph::Interface::PriorityQueue::PriorityQueue(PriorityQueue::ItemFactory& itemFactory) : item_factory(itemFactory) { } NetGraph::Interface::PriorityQueue::~PriorityQueue() { Empty(); item_factory.Destroy(); } bool NetGraph::Interface::PriorityQueue::Insert(Interface& iface, const Cost& cost) { Item* item = item_factory.GetItem(); if (NULL == item) { PLOG(PL_ERROR, "NetGraph::Interface::PriorityQueue::Insert() error: couldn't allocate item\n"); return false; } item->SetCost(cost); Associate(iface, *item); InsertItem(*item); return true; } // end NetGraph::Interface::PriorityQueue::Insert() void NetGraph::Interface::PriorityQueue::Adjust(Interface& iface, const Cost& newCost) { Item* item = static_cast(GetQueueState(iface)); ASSERT(item != NULL); RemoveItem(*item); item->SetCost(newCost); InsertItem(*item); } // end ProtoGraph::Vertice::PriorityQueue::Adjust() bool NetGraph::Interface::PriorityQueue::AdjustDownward(Interface& iface, const Cost& newCost, const Interface* newPrevHop) { Item* item = static_cast(GetQueueState(iface)); ASSERT(item != NULL); if (newCost < item->GetCost()) { RemoveItem(*item); item->SetCost(newCost); InsertItem(*item); return true; } else { return false; } } // end ProtoGraph::Vertice::PriorityQueue::AdjustDownward() bool NetGraph::Interface::PriorityQueue::AdjustUpward(Interface& iface, const Cost& newCost) { Item* item = static_cast(GetQueueState(iface)); ASSERT(item != NULL); if (newCost > item->GetCost()) { //bunny TBD this is wrong! we don't know for certain that this is the correct "path" //we need to search for alternative shorter paths (upstream only!) and update the cost and route table information RemoveItem(*item); item->SetCost(newCost); InsertItem(*item); return true; } else { return false; } } // end ProtoGraph::Vertice::PriorityQueue::AdjustUpward() bool NetGraph::Interface::PriorityQueue::Append(Interface& iface) { Item* item = item_factory.GetItem(); if (NULL == item) { PLOG(PL_ERROR, "NetGraph::Interface::PriorityQueue::Insert() error: couldn't allocate item\n"); return false; } Associate(iface, *item); SortedList::AppendItem(*item); return true; } // end NetGraph::Interface::PriorityQueue::Append() NetGraph::Interface::PriorityQueue::Iterator::Iterator(PriorityQueue& theQueue) : SortedList::Iterator(theQueue) { } NetGraph::Interface::PriorityQueue::Iterator::~Iterator() { } const char* NetGraph::Interface::GetVerticeKey() const { if (addr_list.IsEmpty()) return name_ptr; else return default_addr_item.GetAddress().GetRawHostAddress(); } // end NetGraph::Interface::GetVerticeKey() unsigned int NetGraph::Interface::GetVerticeKeysize() const { // Perhaps it is worthwhile to add a "key_size" member for efficiency? if (addr_list.IsEmpty()) { if (NULL != name_ptr) { unsigned int nameSize = strlen(name_ptr); if (0 == (nameSize & 0x01)) nameSize += 1; // includes '\0' to make needed odd byte size return (nameSize << 3); } else { return 0; } } else { return (default_addr_item.GetAddress().GetLength() << 3); } } // end NetGraph::Interface::GetVerticeKeysize() NetGraph::Node::Node() : iface_list(true), default_interface_ptr(NULL) { } NetGraph::Node::~Node() { // Delete all interfaces Interface* iface; while (NULL != (iface = static_cast(iface_list.RemoveHead()))) { delete iface; } } // Remove interfaces from target node ("foodNode") // and append to this node void NetGraph::Node::Consume(Node& foodNode) { Interface* iface; while(NULL != (iface= foodNode.GetDefaultInterface())) { //foodNode.RemoveInterface(*iface); iface->ChangeNode(*this); } } // end NetGraph::Node::Consume() bool NetGraph::Node::AddInterface(Interface& iface, bool makeDefault) { if(iface_list.IsEmpty()) makeDefault = true; if(!iface_list.Insert(iface)) { PLOG(PL_ERROR, "NetGraph::Node::AddInterface() error: Insert failed on the iface_list!\n"); return false; } ProtoAddressList::Iterator iterator(iface.GetAddressList()); ProtoAddress addr; while(iterator.GetNextAddress(addr)) { if (addr.HostIsEqual(iface.GetDefaultAddress())) continue; // don't insert default addr in "extra_addr_list" if(!extra_addr_list.Insert(addr, &iface)) { PLOG(PL_ERROR, "NetGraph::Node::AddInterface() error: appending %s to the addr_list?!\n",addr.GetHostString()); RemoveInterface(iface); return false; } } if (makeDefault) default_interface_ptr = &iface; return true; } // end NetGraph::AddInterface) void NetGraph::Node::RemoveInterface(Interface& iface) { iface_list.Remove(iface); ProtoAddressList::Iterator iterator(iface.GetAddressList()); ProtoAddress addr; while(iterator.GetNextAddress(addr)) extra_addr_list.Remove(addr); //check to see if was the default and reassign a default if it was if (&iface == default_interface_ptr) default_interface_ptr = (NetGraph::Interface*)(iface_list.GetRoot()); } // end NetGraph::Node::RemoveInterface() bool NetGraph::Node::IsSymmetricNeighbor(Node& node) { NetGraph::Node::InterfaceIterator it(*this); NetGraph::Interface* interface = it.GetNextInterface(); while(NULL != interface) { NetGraph::Node::InterfaceIterator it2(node); NetGraph::Interface* interface2 = it2.GetNextInterface(); while(NULL != interface2) { if(interface->HasLinkTo(*interface2) && interface2->HasLinkTo(*interface)) { return true; } interface2 = it2.GetNextInterface(); } interface = it.GetNextInterface(); } return false; } NetGraph::Interface* NetGraph::Node::FindInterface(const ProtoAddress& addr) const { // First, look in "iface_list" Interface* iface = static_cast(iface_list.Find(addr.GetRawHostAddress(), addr.GetLength() << 3)); if (NULL == iface) // Not in "iface_list", so look for it in "extra_addr_list" iface = (Interface*)(extra_addr_list.GetUserData(addr)); return iface; } // end NetGraph::Node::FindInterface() NetGraph::Interface* NetGraph::Node::FindInterfaceByName(const char* theName) { int nameSize = strlen(theName); if (0 == (nameSize & 0x01)) nameSize++; // ensures odd byte count to differentiate from addrs nameSize <<= 3; NetGraph::Interface* iface = static_cast(iface_list.Find(theName, nameSize)); if (NULL == iface) { // O(N) search for iface with matching name InterfaceIterator iterator(*this); while (NULL != (iface = iterator.GetNextInterface())) { const char* ifaceName = iface->GetName(); if ((NULL != ifaceName) && (0 == strcmp(ifaceName, theName))) break; } } return iface; } // end NetGraph::Node::FindInterfaceByName() NetGraph::Interface* NetGraph::Node::FindInterfaceByString(const char* theString) { NetGraph::Interface* iface = FindInterfaceByName(theString); if(NULL == iface) { ProtoAddress addr; addr.ResolveFromString(theString); if(addr.IsValid()) { iface = FindInterface(addr); } } return iface; } bool NetGraph::Node::SetDefaultInterface(Interface& iface) { // Make sure this "iface" is valid (has address or name) if (iface.GetAddress().IsValid() || (NULL != iface.GetName())) { default_interface_ptr = &iface; return true; } else { PLOG(PL_ERROR,"NetGraph::Node::SetDefaultInterface() error: iface has no address or name!\n"); return false; } } // end NetGraph::Node::SetDefaultInterface() NetGraph::Node::InterfaceIterator::InterfaceIterator(Node& node) : ProtoSortedTree::Iterator(node.iface_list) { } NetGraph::Node::InterfaceIterator::~InterfaceIterator() { } NetGraph::Node::NeighborIterator::NeighborIterator(Node& node) : iface_iterator(node), adj_iterator(*node.GetDefaultInterface()) { Reset(); } NetGraph::Node::NeighborIterator::~NeighborIterator() { } void NetGraph::Node::NeighborIterator::Reset() { iface_iterator.Reset(); Interface* firstLocalIface = iface_iterator.GetNextInterface(); // use in-place new operator to instate adj_iterator for next local interface if (NULL != firstLocalIface) { adj_iterator.~AdjacencyIterator(); new (&adj_iterator) AdjacencyIterator(*firstLocalIface); } } // end NetGraph::Node::NeighborIterator::Reset() NetGraph::Interface* NetGraph::Node::NeighborIterator::GetNextNeighborInterface() { // This avoids calling an invalid "adj_iterator" (initialized with invalid iface reference) if (iface_iterator.HasEmptyList()) return NULL; Interface* iface = adj_iterator.GetNextAdjacency(); if (NULL == iface) { Interface* nextLocalInterface; while (NULL != (nextLocalInterface = iface_iterator.GetNextInterface())) { // use in-place new operator to instantiate adj_iterator for next local interface adj_iterator.~AdjacencyIterator(); new (&adj_iterator) AdjacencyIterator(*nextLocalInterface); iface = adj_iterator.GetNextAdjacency(); if (NULL != iface) break; } } return iface; } // end NetGraph::Node::NeighborIterator::GetNextNeighborInterface() NetGraph::Link* NetGraph::Node::NeighborIterator::GetNextNeighborLink() { // This avoids calling an invalid "adj_iterator" (initialized with invalid iface reference) if (iface_iterator.HasEmptyList()) return NULL; Link* link = adj_iterator.GetNextAdjacencyLink(); if (NULL == link) { Interface* nextLocalInterface; while (NULL != (nextLocalInterface = iface_iterator.GetNextInterface())) { // use in-place new operator to instate adj_iterator for next local interface adj_iterator.~AdjacencyIterator(); new (&adj_iterator) AdjacencyIterator(*nextLocalInterface); link = adj_iterator.GetNextAdjacencyLink(); if (NULL != link) break; } } return link; } // end NetGraph::Node::NeighborIterator::GetNextNeighborInterface() NetGraph::NetGraph() { } NetGraph::~NetGraph() { } // this function will be removed in upcoming releases bool NetGraph::InsertNode(Node& node, Interface* iface) { if (NULL != iface) { // Insert just the specified interface if (node.Contains(*iface)) { return InsertInterface(*iface); } else { PLOG(PL_ERROR, "NetGraph::InsertNode() error: iface doesn't belong to node!\n"); return false; } } else { // Insert all of the interfaces bool hasIface = false; Node::InterfaceIterator it(node); while (NULL != (iface = it.GetNextInterface())) { hasIface = true; if (!InsertInterface(*iface)) { PLOG(PL_ERROR, "NetGraph::InsertNode() error: failed to add iface to graph!\n"); RemoveNode(node); return false; } } if (!hasIface) { PLOG(PL_ERROR, "NetGraph::InsertNode() error: node has no interfaces?!\n"); return false; } return true; } } // end NetGraph::InsertNode() void NetGraph::RemoveNode(Node& node, Interface* iface) { if (NULL == iface) { // Remove all interfaces associated with this node Node::InterfaceIterator it(node); Interface* iface; while (NULL != (iface = it.GetNextInterface())) { RemoveInterface(*iface); } } else { // Remove only the interface specified RemoveInterface(*iface); } } // end NetGraph::RemoveNode() bool NetGraph::InsertInterface(Interface& iface) { if (!iface.GetAddress().IsValid() && (NULL == iface.GetName())) { PLOG(PL_ERROR, "NetGraph::InsertInterface() error: iface has no address or name!\n"); return false; } // Can only be in one graph at once if (NULL != iface.graph) iface.graph->RemoveInterface(iface); if (ProtoGraph::InsertVertice(iface)) { ProtoAddressList::Iterator iterator(iface.GetAddressList()); ProtoAddress addr; while(iterator.GetNextAddress(addr)) { if(!addr_list.Insert(addr, &iface)) { PLOG(PL_ERROR, "NetGraph::InsertInterface() error: cannot add address %s to the netgraph addr_list\n",addr.GetHostString()); RemoveInterface(iface); return false; } } iface.graph = this; } return true; } // end NetGraph::InsertInterface() void NetGraph::RemoveInterface(Interface& iface) { ProtoAddressList::Iterator iterator(iface.GetAddressList()); ProtoAddress addr; while(iterator.GetNextAddress(addr)) addr_list.Remove(addr); if (vertice_list.Contains(iface)) RemoveVertice(iface); iface.graph = NULL; } // end NetGraph::RemoveInterface() NetGraph::Interface* NetGraph::FindInterfaceByName(const char* theName) { if (NULL == theName) return NULL; unsigned int nameSize = strlen(theName); if (0 == (nameSize & 0x01)) nameSize++; nameSize <<= 3; Interface* iface = static_cast(vertice_list.FindVertice(theName, nameSize)); if (NULL == iface) { InterfaceIterator iterator(*this); while(NULL != (iface = iterator.GetNextInterface())) { const char* ifaceName = iface->GetName(); if ((NULL != ifaceName) && (0 == strcmp(ifaceName,theName))) return iface; } } return iface; } // end FindInterfaceByName() NetGraph::Interface* NetGraph::FindInterfaceByString(const char* theString) { NetGraph::Interface* iface = FindInterfaceByName(theString); if(NULL == iface) { ProtoAddress addr; addr.ResolveFromString(theString); if(addr.IsValid()) { iface = FindInterface(addr); } } return iface; } NetGraph::Link* NetGraph::Connect(Interface& srcIface, Interface& dstIface, const Cost& cost) { // TBD - allow multiple links srcIface <-> dstIface ??? Link* link = srcIface.GetLinkTo(dstIface); // Is there already a link, "srcIface" to "dstIface"? if (NULL != link) { PLOG(PL_WARN, "NetGraph::Connect() error: srcIface -> dstIface already connected\n"); return Reconnect(srcIface, dstIface, cost); } // Get a new link from our edge factory (from pool or created as needed) // IMPORTANT NOTE: We _cannot_ call ProtoGraph::Connect() here directly // since it is important to set the link cost _before_ putting the connection // in place so that the adjacency queue gets ordered properly (i.e. by cost) link = static_cast(GetEdge()); if (NULL == link) { PLOG(PL_ERROR, "NetGraph::Connect() error: unable to allocate link\n"); return NULL; } link->SetCost(cost); ProtoGraph::Connect(srcIface, dstIface, *link); return link; } // end NetGraph::Connect(directed link only) bool NetGraph::Connect(Interface& srcIface, Interface& dstIface, const Cost& cost, bool duplex) { Link* link = Connect(srcIface, dstIface, cost); if (!duplex) return (NULL != link); if (NULL == link) { PLOG(PL_ERROR, "NetGraph::Connect() error: unable to allocate forward link\n"); return false; } if (NULL == Connect(dstIface, srcIface, cost)) { PLOG(PL_ERROR, "NetGraph::Connect() error: unable to allocate reverse link\n"); Disconnect(srcIface, dstIface, true); return false; } return true; } // end NetGraph::Connect(duplex option) NetGraph::Link* NetGraph::Reconnect(Interface& srcIface, Interface& dstIface, const Cost& cost) { // TBD - allow multiple links srcIface <-> dstIface ??? Link* link = srcIface.GetLinkTo(dstIface); // Is there already a link, "srcIface" to "dstIface"? if (NULL == link) { PLOG(PL_WARN, "NetGraph::Reconnect() error: srcIface -> dstIface not connected\n"); return NULL; } else if (cost == link->GetCost()) { return link; } this->SuspendEdge(srcIface, dstIface, *link); link->SetCost(cost); ProtoGraph::Reconnect(srcIface,dstIface,*link); return link; } // end NetGraph::Reconnect() bool NetGraph::Reconnect(Interface& srcIface, Interface& dstIface, const Cost& cost, bool duplex) { Link* link = Reconnect(srcIface, dstIface, cost); if (!duplex) return (NULL != link); if (NULL == link) { PLOG(PL_ERROR, "NetGraph::Reconnect() error: unable to reconnect forward link\n"); return false; } if (NULL == Reconnect(dstIface, srcIface, cost)) { PLOG(PL_ERROR, "NetGraph::Reconnect() error: unable to reconnect reverse link\n"); Disconnect(srcIface, dstIface, true); return false; } return true; } // end NetGraph::Reconnect() NetGraph::InterfaceIterator::InterfaceIterator(NetGraph& theGraph) : ProtoGraph::VerticeIterator(static_cast(theGraph)) { } NetGraph::InterfaceIterator::~InterfaceIterator() { } NetGraph::SimpleTraversal::SimpleTraversal(const NetGraph& theGraph, Interface& startIface, bool traverseNodes, bool collapseNodes, bool depthFirst) : ProtoGraph::SimpleTraversal(theGraph, startIface, depthFirst), traverse_nodes(traverseNodes), collapse_nodes(collapseNodes) { Reset(true); } NetGraph::SimpleTraversal::~SimpleTraversal() { } bool NetGraph::SimpleTraversal::Reset(bool constructor) { if (!constructor) { if (!ProtoGraph::SimpleTraversal::Reset()) { PLOG(PL_ERROR, "NetGraph::SimpleTraversal::Reset() error: couldn't enqueue start_vertice\n"); return false; } } if (traverse_nodes && collapse_nodes) { // Init with all interfaces of current node at level zero and init // trans_vertice equal to last (note that NetGraph::SimpleTraversal::Reset() // already inits queue_pending with start_vertice) Interface& startIface = static_cast(start_vertice); Node::InterfaceIterator ifaceIterator(startIface.GetNode()); Interface* nextIface; while (NULL != (nextIface = ifaceIterator.GetNextInterface())) { if (static_cast(&start_vertice) == nextIface) continue; ASSERT(!nextIface->IsInQueue(queue_visited) && !nextIface->IsInQueue(queue_pending)); if (!AllowLink(startIface, *nextIface, NULL)) continue; if (depth_first) queue_pending.Prepend(*nextIface); else queue_pending.Append(*nextIface); } } return true; } // end ProtoGraph::SimpleTraversal::Reset() // This traversal can use all of its nodes' local interfaces NetGraph::Interface* NetGraph::SimpleTraversal::GetNextInterface(unsigned int* level) { Interface* currentIface = static_cast(queue_pending.GetHead()); if (NULL != currentIface) { queue_pending.TransferVertice(*currentIface, queue_visited); Vertice* transAdjacency = NULL; // used to find "level" transitions Interface* nextIface; if (traverse_nodes && !collapse_nodes) { // Here we treat other ifaces on same node as adjacent Node::InterfaceIterator ifaceIterator(currentIface->GetNode()); while (NULL != (nextIface = ifaceIterator.GetNextInterface())) { if (!nextIface->IsInQueue(queue_visited) && !nextIface->IsInQueue(queue_pending)) { if (!AllowLink(*currentIface, *nextIface, NULL)) continue; if (depth_first) { queue_pending.Prepend(*nextIface); // (TBD) depth tracking for Depth-first search } else { queue_pending.Append(*nextIface); if (NULL == transAdjacency) transAdjacency = nextIface; } } } } // Now iterate to other neighboring interfaces AdjacencyIterator adjacencyIterator(*currentIface); Link* nextLink; while (NULL != (nextLink = adjacencyIterator.GetNextAdjacencyLink())) { nextIface = nextLink->GetDst(); ASSERT(NULL != nextIface); if (!nextIface->IsInQueue(queue_visited) && !nextIface->IsInQueue(queue_pending)) { if (!AllowLink(*currentIface, *nextIface, nextLink)) continue; if (depth_first) { queue_pending.Prepend(*nextIface); // (TBD) depth tracking for Depth-first search } else { queue_pending.Append(*nextIface); if (NULL == transAdjacency) transAdjacency = nextIface; } if (traverse_nodes && collapse_nodes) { // Here co-interfaces are treated as equivalent adjacencies Node::InterfaceIterator ifaceIterator(nextIface->GetNode()); Interface* nextCoface; while (NULL != (nextCoface = ifaceIterator.GetNextInterface())) { if (nextCoface == nextIface) continue; ASSERT(!nextCoface->IsInQueue(queue_visited) && !nextCoface->IsInQueue(queue_pending)); if (depth_first) queue_pending.Prepend(*nextCoface); else queue_pending.Append(*nextCoface); } } } } if (NULL == trans_vertice) { trans_vertice = transAdjacency; } else if (trans_vertice == currentIface) { current_level++; trans_vertice = transAdjacency; } if (NULL != level) *level = current_level; } return currentIface; } // end NetGraph::SimpleTraversal::GetNextInterface() /* // This traversal can use all of its nodes' local interfaces NetGraph::Interface* NetGraph::SimpleTraversal::GetNextInterface(unsigned int* level) { if (traverse_nodes) { //TRACE("enter NetGraph::SimpleTraversal::GetNextInterface() ...\n"); Interface* currentIface = static_cast(queue_pending.GetHead()); if (NULL == currentIface) return NULL; // we're done //TRACE("level %u trans_vertice:%p currentIface:%p\n", level, trans_vertice, static_cast(currentIface)); if ((static_cast(currentIface) == trans_vertice) || (NULL == trans_vertice)) { if (NULL != trans_vertice) current_level++; // Enqueue adjacencies (and their co-interfaces)of queue_pending as next level Vertice::SimpleList::Iterator penderator(queue_pending); Interface* nextPending; Interface* transIface = NULL; //int p = 0; while (NULL != (nextPending = static_cast(penderator.GetNextVertice()))) { if (nextPending == transIface) break; //TRACE(" pending iface %d ...\n", p++); AdjacencyIterator adjacencyIterator(*nextPending); Link* nextLink; while (NULL != (nextLink = adjacencyIterator.GetNextAdjacencyLink())) { Interface* nextIface = nextLink->GetDst(); ASSERT(NULL != nextIface); if (!nextIface->IsInQueue(queue_visited) && !nextIface->IsInQueue(queue_pending)) { if (!AllowLink(*nextPending, *nextIface, nextLink)) continue; Node::InterfaceIterator ifaceIterator(nextIface->GetNode()); Interface* nextCoface; while (NULL != (nextCoface = ifaceIterator.GetNextInterface())) { if (NULL == transIface) transIface = nextCoface; if (depth_first) { queue_pending.Prepend(*nextCoface); // (TBD) depth tracking for Depth-first search } else { //TRACE(" Appending level %u co-interface ...\n", current_level); queue_pending.Append(*nextCoface); } } } } } trans_vertice = static_cast(transIface); } queue_pending.TransferVertice(*currentIface, queue_visited); if (NULL != level) *level = current_level; return currentIface; } else { // If not traversing nodes, then just use ProtoGraph::SimpleTraversal return static_cast(ProtoGraph::SimpleTraversal::GetNextVertice(level)); } } // end NetGraph::SimpleTraversal::GetNextInterface() */ NetGraph::DijkstraTraversal::DijkstraTraversal(NetGraph& theGraph, Interface* startIface) : manet_graph(theGraph), start_iface(startIface), queue_pending(static_cast(*this)), queue_visited(static_cast(*this)), trans_iface(NULL), current_level(0), dijkstra_completed(false), in_update(false), traverse_nodes(false), reset_required(false) { } NetGraph::DijkstraTraversal::DijkstraTraversal(NetGraph& theGraph, Node& startNode, Interface* startIface) : manet_graph(theGraph), start_iface((NULL != startIface) ? startIface : startNode.GetDefaultInterface()), queue_pending(static_cast(*this)), queue_visited(static_cast(*this)), trans_iface(NULL), current_level(0), dijkstra_completed(false), in_update(false), traverse_nodes(false), reset_required(false) { // ASSERT(&start_iface->GetNode() == &startNode); } NetGraph::DijkstraTraversal::~DijkstraTraversal() { queue_pending.Empty(); queue_visited.Empty(); } void NetGraph::DijkstraTraversal::TraverseNodes(bool traverse) { traverse_nodes = traverse; } bool NetGraph::DijkstraTraversal::Reset(Interface* startIface) { // (TBD) use a dual queue approach so that we can avoid // visiting every iface twice everytime we run the Dijkstra. // I.e., we could maintain "visited" & "unvisited" queue, removing ifaces // from that queue as they are visited, and then at the end of // the Dijkstra, update the cost of any remaining unvisited ifaces // to COST_MAX and then swap visited and unvisited queues for next // Dijkstra run ... Thus each iface would be visited only once _or_ as // needed for Dijkstra instead of once _plus_ as needed for Dijkstra queue_visited.Empty(); queue_pending.Empty(); Cost& startCost = AccessCostTemp(); startCost.Minimize(); if (NULL != startIface) start_iface = startIface; if (NULL != start_iface) { if(traverse_nodes) { Node::InterfaceIterator ifaceIterator(start_iface->GetNode()); Interface* nextIface; while (NULL != (nextIface = ifaceIterator.GetNextInterface())) { if (!queue_pending.Insert(*nextIface, startCost)) { PLOG(PL_ERROR, "NetGraph::DijkstraTraversal::Reset() error: couldn't enqueue a start_iface (traverse_nodes)\n"); return false; } } } else { if (!queue_pending.Insert(*start_iface, startCost)) { PLOG(PL_ERROR, "NetGraph::DijkstraTraversal::Reset() error: couldn't enqueue start_iface\n"); return false; } } //TRACE("dijkstra_completed = false bunny1\n"); dijkstra_completed = false; } else { //TRACE("dijkstra_completed = true bunny2\n"); dijkstra_completed = true; } return true; } // end NetGraph::DijkstraTraversal::Reset() // Dijkstra traversal step NetGraph::Interface* NetGraph::DijkstraTraversal::GetNextInterface() { // (TBD) We could be a little more efficient if we worked with PriorityQueue::Items directly Interface* currentIface = queue_pending.GetHead(); if (NULL != currentIface) { queue_pending.TransferInterface(*currentIface, queue_visited); const Cost* currentCost = queue_visited.GetCost(*currentIface); ASSERT(NULL != currentCost); //TRACE(" %s being updated with cost %f\n",currentIface->GetAddress().GetHostString(),((ManetGraph::Cost*)currentCost)->GetValue()); AdjacencyIterator linkIterator(*currentIface); Link* nextLink; while ((nextLink = linkIterator.GetNextAdjacencyLink())) { Interface* nextDst = nextLink->GetDst(); ASSERT(NULL != nextDst); if (!AllowLink(*currentIface, *nextLink)) continue; const Cost& linkCost = nextLink->GetCost(); Cost& nextCost = AccessCostTemp(); nextCost = linkCost; nextCost += *currentCost; Node::InterfaceIterator ifaceIterator(nextDst->GetNode()); if(traverse_nodes) nextDst = ifaceIterator.GetNextInterface(); do { bool saveState = true; if(!in_update) { if (nextDst->IsInQueue(queue_pending)) { // We have found another path to this pending iface. // If it is a shorter path update the cost to lower value if (!queue_pending.AdjustDownward(*nextDst, nextCost, currentIface)) saveState = false; } else if (!nextDst->IsInQueue(queue_visited)) { // This is the first path found to this iface, // so enqueue it in our "queue_pending" queue if (!queue_pending.Insert(*nextDst, nextCost)) { PLOG(PL_ERROR, "NetGraph::DijkstraTraversal::GetNextInterface() error: couldn't enqueue iface\n"); return NULL; } } else { saveState = false; } } else // in_update { // visited queue nodes may not have been updated yet...we need a different way to check. Interface* prevHopIface; bool isInVisited = false; bool isNewIface = false; Interface::PriorityQueue* queuePtr = &queue_pending; if(nextDst->IsInQueue(queue_visited)) { isInVisited = true; queuePtr = &queue_visited; } else if (!nextDst->IsInQueue(queue_pending)) { //new interface so just go ahead and add it isNewIface = true; } if(isNewIface) { if (!queue_pending.Insert(*nextDst, nextCost)) { PLOG(PL_ERROR, "NetGraph::DijkstraTraversal::GetNextInterface() error: couldn't enqueue iface\n"); return NULL; } } else if (queuePtr->AdjustDownward(*nextDst, nextCost, currentIface)) // try and move it down { //TRACE(" %s moved downward\n",nextDst->GetAddress().GetHostString()); if(isInVisited) { //TRACE(" was in visited queue adding it to the pending queue so children can be updated\n"); queue_visited.TransferInterface(*nextDst, queue_pending); //it moved down so put it in the pending queue to updated it's children... } } else if(NULL != (prevHopIface = queuePtr->GetPrevHop(*nextDst))) { //need to check if we were the previous hop //Interface* bunnyTemp = queuePtr->GetNextHop(*currentIface); //if(bunnyTemp) // TRACE("bunny next hop current is %s\n",bunnyTemp->GetAddress().GetHostString()); //TRACE("checking next nbr from current iface %s \n",currentIface->GetAddress().GetHostString()); //TRACE("prev hop %s ",prevHopIface->GetAddress().GetHostString()); //TRACE("of dst %s iface\n",nextDst->GetAddress().GetHostString()); bool linkWasUsed = false; if(traverse_nodes) { if (currentIface->GetNode().Contains(*prevHopIface)) linkWasUsed = true; } else { if (currentIface == prevHopIface) linkWasUsed = true; } if(linkWasUsed) { //TRACE("link was used was it longer? if yes then\n"); if(queuePtr->AdjustUpward(*nextDst, nextCost)) { //TRACE("link we are bailing out and setting the required reset bool true!\n"); //we need to verify that this is the currently shortest path and if not fix it! //New function required or expand AdjustUpward to take care of this. //using class variable to tell update to do a full reset... //Fixing AdjustingUpward and putting the some queue update stuff will then we can remove this reset_required = true; saveState = false; return NULL; //queue_visited.TransferInterface(*nextDst, queue_pending); //we need to check neighbors to see if they used this path and update them if they did. } else { //TRACE("link was same length as before not saving state\n"); saveState = false; } } else { //TRACE("link wasn't used not saving\n"); saveState = false; } } else { //TRACE("no prev hop\n"); //no previous hop this can happen if currentIface is on the root node saveState = false; } // I _think_ this is currently broken? It seems we would need to shuffle nodes // from "queue_visited" to "queue_pending" here to work properly? ... Note that // it depends heavily on "Update()" being called with a proper "startIface" // This checks for shorter path to a "visited" iface // (must be in "Update()" mode! (i.e. "in_update == true") /*{ // Update the routing tree state if (currentIface == start_iface) queue_visited.SetRouteInfo(*nextDst, nextLink, currentIface); else queue_visited.SetRouteInfo(*nextDst, queue_visited.GetNextHopLink(*currentIface), currentIface); } saveState = false;*/ } // Save our routing tree state as we go if(saveState) { //if (currentIface == start_iface) if(start_iface->GetNode().Contains(*currentIface)) { //leaving debug statements here but commented out for the time being JD if(nextDst==NULL) { //TRACE("nextDst is null!\n"); } else { //TRACE("nextDst is %s\n",nextDst->GetAddress().GetHostString()); } if(nextLink==NULL) { //TRACE("nextLink is null!\n"); } else { //TRACE("nextLink src is %s dst is ",nextLink->GetSrc()->GetAddress().GetHostString()); //TRACE("%s\n",nextLink->GetDst()->GetAddress().GetHostString()); } if(currentIface==NULL) { //TRACE("currentIface is null!\n"); } else { //TRACE("currentIface is %s\n",currentIface->GetAddress().GetHostString()); } queue_pending.SetRouteInfo(*nextDst, nextLink, currentIface); } else { if(queue_visited.Contains(*currentIface)) queue_pending.SetRouteInfo(*nextDst, queue_visited.GetNextHopLink(*currentIface), currentIface); else queue_pending.SetRouteInfo(*nextDst, queue_pending.GetNextHopLink(*currentIface), currentIface); } } if(traverse_nodes) nextDst = ifaceIterator.GetNextInterface(); else nextDst = NULL; } while (nextDst != NULL); } // end while ((nextLink = linkIterator.GetNextAdjacencyLink())) } else { //TRACE("dijkstra_completed = true bunny2\n"); dijkstra_completed = true; } return currentIface; } // end NetGraph::DijkstraTraversal::GetNextInterface() bool NetGraph::DijkstraTraversal::PrevHopIsValid(Interface& currentIface) { ASSERT(start_iface != NULL); if (!traverse_nodes) { if (¤tIface == start_iface) return true; } else { if(currentIface.GetNode().Contains(*start_iface)) return true; } const Cost* currCostPtr = GetCost(currentIface); if(currCostPtr == NULL) return false; Interface* prevHopIface = NULL; if(NULL != (prevHopIface = queue_visited.GetPrevHop(currentIface))) { const Cost* prevCostPtr = GetCost(*prevHopIface); if(prevCostPtr == NULL) return false; if(!traverse_nodes) { Link* linkPtr = prevHopIface->GetLinkTo(currentIface); if(linkPtr != NULL) { if (AllowLink(*prevHopIface, *linkPtr)) { Cost& sumCost = AccessCostTemp(); sumCost = linkPtr->GetCost(); sumCost += *prevCostPtr; if(sumCost > *currCostPtr) { // cost has increased and is no longer valid return false; } else if (sumCost < *currCostPtr) { // we could return false here but the link has only gotten "better" so should still be a valid prev hop just with the wrong value return true; } else { return true; } } } else { // no link exists from my previous hop, returning null return false; } } else { ManetNode::NeighborIterator nbIt(prevHopIface->GetNode()); Link* linkPtr = NULL; while(NULL != (linkPtr = nbIt.GetNextNeighborLink())) { Interface* srcPtr = linkPtr->GetSrc(); ASSERT(NULL != srcPtr); if (!AllowLink(*srcPtr, *linkPtr)) continue; Interface* dstPtr = linkPtr->GetDst(); if(dstPtr!=NULL) { if(currentIface.GetNode().Contains(*dstPtr)) { Cost& sumCost = AccessCostTemp(); sumCost = linkPtr->GetCost(); sumCost += *prevCostPtr; if(sumCost <= *currCostPtr) return true; if (sumCost == *currCostPtr) return true; } } } return false; } } else { // previous hop is null, returning false; return false; } return true; } //end NetGraph::Interface* NetGraph::DijkstraTraversal::PreviousHopIsValid() void NetGraph::DijkstraTraversal::Update(Interface& startIface) { //TRACE(" calling update on interface %s\n",startIface.GetAddress().GetHostString()); if (!dijkstra_completed) { //TRACE("bunny doing a full reset...\n"); Reset(); // Complete dijkstra traversal while (NULL != GetNextInterface()); return; } if(!PrevHopIsValid(startIface)) { //we might be able to find and update the "star cluster" for the next best paths but it might not be worth it //TRACE(" previous hop isn't valid....doing a full reset...\n"); Reset(); // Complete dijkstra traversal while (NULL != GetNextInterface()); return; } ASSERT(queue_pending.IsEmpty()); //set up the initial state for walking through the graph stub. in_update = true; Interface* origStartIfacePtr = start_iface; start_iface=&startIface; if(startIface.IsInQueue(queue_visited)) { //TRACE(" Interface was in the visited queue so setting up pending queue to update dijkstra state\n"); if(traverse_nodes) { Node::InterfaceIterator ifaceIterator(startIface.GetNode()); Interface* nextIface = NULL; while (NULL !=(nextIface = ifaceIterator.GetNextInterface())) queue_visited.TransferInterface(*nextIface, queue_pending); } else { queue_visited.TransferInterface(startIface, queue_pending); } } else { // Need to reset entire Dijkstra (as a new interface has been added and we don't know from where) // (TBD - maybe something smarter can be done here) // could be solved in a similar way to the star cluster as a single isolated branch/leaf is a subset of that problem //TRACE(" Interface to update isn't in the visited queue doing a full reset\n"); reset_required = true; } //walk through and update the graph stub if(!reset_required) { //TRACE(" Going to walk through the graph\n"); } Interface *nextIface = GetNextInterface(); if(reset_required) nextIface = NULL; while (NULL != nextIface) { //TRACE(" %s is the next iface\n",nextIface->GetAddress().GetHostString()); if(reset_required) nextIface = NULL; else nextIface = GetNextInterface(); } //finished walking through stub check to make sure a reset isn't required //TRACE(" finishing up the state and checking to see if a reset is required\n"); in_update = false; start_iface=origStartIfacePtr; if(reset_required) { //TRACE(" Needed a full reset\n"); Reset(); while (NULL != GetNextInterface()); } //if (!dijkstra_completed) // TRACE("Getting out without dijkstra being finished!\n"); } // end NetGraph::DijkstraTraversal::Update() // Call this to setup re-traverse of tree computed via Dijkstra void NetGraph::DijkstraTraversal::Update(Interface& ifaceA, Interface& ifaceB) { const NetGraph::Cost* aCostPtr = GetCost(ifaceA); const NetGraph::Cost* bCostPtr = GetCost(ifaceB); if((aCostPtr != NULL) && (bCostPtr != NULL)) { if(*aCostPtr > *bCostPtr) { Link* linkPtr = ifaceB.GetLinkTo(ifaceA); if(NULL != linkPtr) { // there is a link so lets try and update B without doing a full update if (!AllowLink(ifaceB, *linkPtr)) { //the link isn't allowed and if the link was on the shortest path this will cause a full rest otherwise nothing will be updated Update(ifaceA); } else { Update(ifaceB); } } else { //the link doesn't exists and if the link was on shortest path this will cause a full reset otherwise nothing will be updated Update(ifaceA); } } else { //a's cost is less than b's Link* linkPtr = ifaceA.GetLinkTo(ifaceB); if(NULL != linkPtr) { if (!AllowLink(ifaceA, *linkPtr)) { //the link isn't allowed and if the link was on the shortest path this will cause a full reset otherwise nothing will be updated Update(ifaceB); } else { //there is a link so lets try and update A without doing a full update Update(ifaceA); } } else { //the link doesn't exists and if the link was on shortest path this will cause a full rest otherwise nothing will be updated Update(ifaceB); } } } else if(aCostPtr != NULL) { Update(ifaceA); } else if (bCostPtr != NULL) { Update(ifaceB); } } bool NetGraph::DijkstraTraversal::TreeWalkReset() { // If Dijkstra was not completed, run full Dijkstra if (!dijkstra_completed) { //TRACE("In reset...\n"); Reset(); while (NULL != GetNextInterface()); } ASSERT(queue_pending.IsEmpty()); if (NULL != start_iface) { if (!queue_pending.Append(*start_iface)) { PLOG(PL_ERROR, "NetGraph::DijkstraTraversal::TreeWalkReset() error: couldn't append start_iface\n"); return false; } } trans_iface = NULL; current_level = 0; return true; } // end NetGraph::DijkstraTraversal::TreeWalkReset() NetGraph::Interface* NetGraph::DijkstraTraversal::TreeWalkNext(unsigned int* level) { Interface* currentIface = queue_pending.RemoveHead(); if (NULL != currentIface) { // Find selected links Link* nextLink; Link* firstLink = NULL; if(traverse_nodes) { NetGraph::Node::NeighborIterator linkIterator(currentIface->GetNode()); while ((nextLink = linkIterator.GetNextNeighborLink())) { Interface* nextDst = nextLink->GetDst(); ASSERT(NULL != nextDst); if (currentIface == GetPrevHop(*nextDst)) { if (NULL == firstLink) firstLink = nextLink; queue_pending.Append(*nextDst); } } } else { AdjacencyIterator linkIterator(*currentIface); while ((nextLink = linkIterator.GetNextAdjacencyLink())) { Interface* nextDst = nextLink->GetDst(); ASSERT(NULL != nextDst); if (currentIface == GetPrevHop(*nextDst)) { if (NULL == firstLink) firstLink = nextLink; queue_pending.Append(*nextDst); } } } // Track depth as walk progresses ... if (NULL == trans_iface) { trans_iface = firstLink ? firstLink->GetDst() : NULL; } else if (trans_iface == currentIface) { trans_iface = firstLink ? firstLink->GetDst() : NULL; current_level++; } if (NULL != level) *level = current_level; } return currentIface; } // end NetGraph::DijkstraTraversal::TreeWalkNext()