Debian Codegraph @

protolib/src/manet/manetGraph.cpp

raw
1 #include "manetGraph.h"
2 #include <protoDebug.h>
3 #include <new>
4
5 NetGraph::Cost::Cost()
6 {
7 }
8
9 NetGraph::Cost::~Cost()
10 {
11 }
12
13 NetGraph::Link::Link()
14 {
15 }
16
17 NetGraph::Link::~Link()
18 {
19 }
20
21 void NetGraph::Link::SetCost(const Cost& cost)
22 {
23 AccessCost() = cost;
24 } // end NetGraph::Link::SetCost()
25
26 NetGraph::Interface::Interface(Node& theNode, const ProtoAddress& addr)
27 : node(&theNode),graph(NULL),default_addr_item(addr), name_ptr(NULL)
28 {
29 addr_list.InsertItem(default_addr_item);
30 }
31
32 NetGraph::Interface::Interface(Node& theNode)
33 : node(&theNode), graph(NULL), default_addr_item(PROTO_ADDR_NONE), name_ptr(NULL)
34 {
35 }
36
37 NetGraph::Interface::~Interface()
38 {
39 if(graph != NULL) graph->RemoveInterface(*this);
40 Cleanup(); // Note "Cleanup()" would also remove it from "graph"
41 if (!addr_list.IsEmpty())
42 {
43 node->RemoveInterface(*this);
44 addr_list.RemoveItem(default_addr_item);
45 // Note "addr_list" destructor destroys any remaining items in list
46 }
47 else if (NULL != name_ptr)
48 {
49 node->RemoveInterface(*this);
50 }
51 if (NULL != name_ptr) delete[] name_ptr;
52 }
53
54 bool NetGraph::Interface::SetName(const char* theName)
55 {
56 int length = strlen(theName);
57 char* namePtr = new char[length+1];
58 namePtr[length] = '\0';
59 bool reattach = false;//we will reattach iff a name already existed
60 if (NULL == namePtr)
61 {
62 PLOG(PL_ERROR,"NetGraph::Interface::SetName(): new name_ptr error: %s\n", GetErrorString());
63 return false;
64 }
65 if (NULL != name_ptr)
66 {
67 if (addr_list.IsEmpty())
68 {
69 reattach = true;
70 // Is using name as ProtoGraph::vertice_list index and Node::iface_list index
71 node->RemoveInterface(*this); // will reattach below
72 if (NULL != graph)
73 graph->SuspendInterface(*this); // will "resume" below
74 }
75 delete[] name_ptr; // delete old "name_ptr"
76 }
77 name_ptr = namePtr;
78 strcpy(name_ptr, theName);
79 if (addr_list.IsEmpty() && reattach)
80 {
81 // Now that we have an "indice" for this interface, it can be fully
82 // associated with its "graph" (if applicable) and "node"
83 if (NULL != graph) // if no addr, graph is only non-NULL if there was prior name
84 {
85 if (!graph->ResumeInterface(*this))
86 {
87 PLOG(PL_ERROR,"NetGraph::Interface::SetName() error: unable to reattach interface to graph: %s\n", GetErrorString());
88 graph->RemoveInterface(*this);
89 return false;
90 }
91 }
92 if (!node->AddInterface(*this))
93 {
94 PLOG(PL_ERROR,"NetGraph::Interface::SetName() error: unable to add interface to node: %s\n", GetErrorString());
95 delete[] name_ptr;
96 name_ptr = NULL;
97 return false;
98 }
99 }
100 return true;
101 } // end NetGraph::Interface::SetName()
102
103 void NetGraph::Interface::ClearName()
104 {
105 if (NULL != name_ptr)
106 {
107 if (addr_list.IsEmpty())
108 {
109 node->RemoveInterface(*this);
110 if (NULL != graph) graph->RemoveInterface(*this); // all links are lost
111 }
112 delete[] name_ptr;
113 name_ptr = NULL;
114 }
115 } // NetGraph::Interface::ClearName()
116
117 // TBD - add a "makeDefault" optional argument to make the new address the default?
118 bool NetGraph::Interface::AddAddress(const ProtoAddress& theAddress)
119 {
120 // Add the new address
121 if (addr_list.IsEmpty())
122 {
123 if (NULL != name_ptr)
124 {
125 // We're adding an address to a "name-only" interface,
126 // so we need to remove/reinsert this iface from the Node & Graph
127 // so that is properly indexed.
128 node->RemoveInterface(*this);
129 if (NULL != graph)
130 graph->SuspendInterface(*this); // temporarily remove from ProtoGraph::vertice_list
131 }
132 default_addr_item.SetAddress(theAddress);
133 if (NULL != graph) // note that "graph" will be non-null iff there _was_ a name_ptr
134 {
135 if (!graph->ResumeInterface(*this))
136 {
137 PLOG(PL_ERROR, "NetGraph::Interface::AddAddress() error: failed to add interface to graph\n");
138 default_addr_item.SetAddress(PROTO_ADDR_NONE);
139 return false;
140 }
141 if (!graph->AddInterfaceAddress(*this, theAddress))
142 {
143 PLOG(PL_ERROR, "NetGraph::Interface::AddAddress() error: failed to add address to graph\n");
144 graph->RemoveInterface(*this);
145 default_addr_item.SetAddress(PROTO_ADDR_NONE);
146 return false;
147 }
148 }
149 if (!node->AddInterface(*this))
150 {
151 // This should only occur if we're out of memory
152 PLOG(PL_ERROR, "NetGraph::Interface::AddAddress() error: failed to add interface to node\n");
153 if (NULL != graph) graph->RemoveInterface(*this); // removes links, too
154 default_addr_item.SetAddress(PROTO_ADDR_NONE);
155 return false;
156 }
157 }
158 else if (addr_list.Insert(theAddress))
159 {
160 // If already had address, it's a given that we're already in the node's iface_list
161 if (!node->AddExtraInterfaceAddress(*this, theAddress))
162 {
163 PLOG(PL_ERROR, "NetGraph::Interface::AddAddress() error: failed to add address to node\n");
164 RemoveAddress(theAddress);
165 return false;
166 }
167 if (NULL != graph)
168 {
169 if (!graph->AddInterfaceAddress(*this, theAddress))
170 {
171 PLOG(PL_ERROR, "NetGraph::Interface::AddAddress() error: failed to add address to graph\n");
172 RemoveAddress(theAddress);
173 return false;
174 }
175 }
176 }
177 else
178 {
179 PLOG(PL_ERROR, "NetGraph::Interface::AddAddress() error: %s\n", GetErrorString());
180 return false;
181 }
182 return true;
183 } // end NetGraph::Interface::AddAddress()
184
185 bool NetGraph::Interface::RemoveAddress(const ProtoAddress& theAddress)
186 {
187 #ifdef PROTO_DEBUG
188 ASSERT(Contains(theAddress)); // not good practice to call RemoveAddress()
189 #else
190 if (!Contains(theAddress)) return false;
191 #endif
192 if (theAddress.HostIsEqual(default_addr_item.GetAddress()))
193 {
194 // This is the address used for Node/Graph indices, so do some extra work here
195 node->RemoveInterface(*this);
196 if (NULL != graph)
197 {
198 addr_list.RemoveItem(default_addr_item);
199 if (addr_list.IsEmpty() && (NULL == name_ptr))
200 {
201 // Are not allowed to remove only address of interface with no name
202 addr_list.InsertItem(default_addr_item);
203 if (!node->AddInterface(*this))
204 PLOG(PL_ERROR, "NetGraph::Interface::RemoveAddress() error: failed to reattach interface to node\n");
205 return false;
206 }
207 addr_list.InsertItem(default_addr_item);
208 graph->SuspendInterface(*this); // we make sure to "resume" it below
209 }
210 addr_list.RemoveItem(default_addr_item);
211 if (addr_list.IsEmpty())
212 {
213 default_addr_item.SetAddress(PROTO_ADDR_NONE);
214 if (NULL != name_ptr)
215 {
216 if (NULL != graph)
217 {
218 // reinserts interface into graph now indexed by "name"
219 if (!graph->ResumeInterface(*this))
220 {
221 PLOG(PL_ERROR, "NetGraph::Interface::RemoveAddress() error: failed to reinsert interface into graph\n");
222 if (!node->AddInterface(*this)) // probably will fail, too
223 PLOG(PL_ERROR, "NetGraph::Interface::RemoveAddress() error: failed to reattach interface to node\n");
224 return false;
225 }
226 graph->RemoveInterfaceAddress(theAddress);
227 }
228 // Put iface into node iface_list now indexed by name
229 if (!node->AddInterface(*this))
230 {
231 PLOG(PL_ERROR, "NetGraph::Interface::RemoveAddress() error: failed to reattach interface to node\n");
232 if (NULL != graph) graph->RemoveInterface(*this); // note all links are lost
233 return false; // note address was removed, but ...
234 }
235 }
236 else
237 {
238 // No remaining name or address, so remove from graph, if applicable
239 if (NULL != graph) graph->RemoveInterface(*this); // note all links are lost
240 }
241 }
242 else
243 {
244 // We'll use a remaining address as the the new "default" address
245 ProtoAddressList::Item* rootItem = addr_list.RemoveRootItem();
246 default_addr_item = *rootItem;
247 delete rootItem;
248 addr_list.InsertItem(default_addr_item);
249 if (NULL != graph)
250 {
251 // reinserts interface into graph now indexed by new default address
252 if (!graph->ResumeInterface(*this))
253 {
254 PLOG(PL_ERROR, "NetGraph::Interface::RemoveAddress() error: failed to reinsert interface into graph\n");
255 if (!node->AddInterface(*this)) // probably will fail, too
256 PLOG(PL_ERROR, "NetGraph::Interface::RemoveAddress() error: failed to reattach interface to node\n");
257 return false;
258 }
259 graph->RemoveInterfaceAddress(theAddress);
260 }
261 // Put iface into node iface_list now indexed by new default address
262 if (!node->AddInterface(*this))
263 {
264 PLOG(PL_ERROR, "NetGraph::Interface::RemoveAddress() error: failed to reattach interface to node\n");
265 if (NULL != graph) graph->RemoveInterface(*this); // note all links are lost
266 return false; // note address was removed, but ...
267 }
268 }
269 }
270 else
271 {
272 addr_list.Remove(theAddress);
273 node->RemoveExtraInterfaceAddress(theAddress);
274 if (NULL != graph) graph->RemoveInterfaceAddress(theAddress);
275 }
276 return true;
277 } // end NetGraph::Interface::RemoveAddress()
278
279 bool NetGraph::Interface::ChangeNode(Node& theNode)
280 {
281 ASSERT(NULL != node);
282 node->RemoveInterface(*this);
283 node = &theNode;
284 if(!theNode.AddInterface(*this))
285 {
286 PLOG(PL_ERROR, "NetGraph::Interface::SetNode: error: AddInterface returned false\n");
287 return false;
288 }
289 return true;
290 } // end NetGraph::Interface::ChangeNode()
291
292 NetGraph::AdjacencyIterator::AdjacencyIterator(Interface& theInterface)
293 : ProtoGraph::AdjacencyIterator(theInterface)
294 {
295 }
296
297 NetGraph::AdjacencyIterator::~AdjacencyIterator()
298 {
299 }
300
301 NetGraph::Interface::SimpleList::SimpleList(ItemPool* itemPool)
302 : Vertice::SimpleList(itemPool)
303 {
304 }
305
306 NetGraph::Interface::SimpleList::~SimpleList()
307 {
308 }
309
310 NetGraph::Interface::SimpleList::Iterator::Iterator(const SimpleList& theList)
311 : ProtoGraph::Vertice::SimpleList::Iterator(theList)
312 {
313 }
314
315 NetGraph::Interface::SimpleList::Iterator::~Iterator()
316 {
317 }
318
319 NetGraph::Interface::SortedList::SortedList(ItemPool* itemPool)
320 : Vertice::SortedList(itemPool)
321 {
322 }
323
324 NetGraph::Interface::SortedList::~SortedList()
325 {
326 }
327
328 NetGraph::Interface::SortedList::Iterator::Iterator(SortedList& theList)
329 : ProtoGraph::Vertice::SortedList::Iterator(theList)
330 {
331 }
332
333 NetGraph::Interface::SortedList::Iterator::~Iterator()
334 {
335 }
336
337 NetGraph::Interface::PriorityQueue::Item::Item()
338 : prev_hop(NULL), next_hop_link(NULL)
339 {
340 }
341
342 NetGraph::Interface::PriorityQueue::Item::~Item()
343 {
344 }
345
346 NetGraph::Interface::PriorityQueue::ItemFactory::ItemFactory()
347 {
348 }
349
350 NetGraph::Interface::PriorityQueue::ItemFactory::~ItemFactory()
351 {
352 Destroy();
353 }
354
355 NetGraph::Interface::PriorityQueue::Item* NetGraph::Interface::PriorityQueue::ItemFactory::GetItem()
356 {
357 Item* item = static_cast<PriorityQueue::Item*>(item_pool.QueueStatePool::Get());
358 if (NULL == item) item = CreateItem();
359 if (NULL == item)
360 PLOG(PL_ERROR, "NetGraph::Interface::PriorityQueue::ItemFactory::GetItem() CreateItem() error: %s\n",
361 GetErrorString());
362 return item;
363 } // end NetGraph::Interface::PriorityQueue::ItemFactory::GetItem()
364
365 NetGraph::Interface::PriorityQueue::PriorityQueue(PriorityQueue::ItemFactory& itemFactory)
366 : item_factory(itemFactory)
367 {
368 }
369
370 NetGraph::Interface::PriorityQueue::~PriorityQueue()
371 {
372 Empty();
373 item_factory.Destroy();
374 }
375
376 bool NetGraph::Interface::PriorityQueue::Insert(Interface& iface, const Cost& cost)
377 {
378 Item* item = item_factory.GetItem();
379 if (NULL == item)
380 {
381 PLOG(PL_ERROR, "NetGraph::Interface::PriorityQueue::Insert() error: couldn't allocate item\n");
382 return false;
383 }
384 item->SetCost(cost);
385 Associate(iface, *item);
386 InsertItem(*item);
387 return true;
388 } // end NetGraph::Interface::PriorityQueue::Insert()
389
390 void NetGraph::Interface::PriorityQueue::Adjust(Interface& iface, const Cost& newCost)
391 {
392 Item* item = static_cast<Item*>(GetQueueState(iface));
393 ASSERT(item != NULL);
394 RemoveItem(*item);
395 item->SetCost(newCost);
396 InsertItem(*item);
397 } // end ProtoGraph::Vertice::PriorityQueue::Adjust()
398
399 bool NetGraph::Interface::PriorityQueue::AdjustDownward(Interface& iface, const Cost& newCost, const Interface* newPrevHop)
400 {
401 Item* item = static_cast<Item*>(GetQueueState(iface));
402 ASSERT(item != NULL);
403 if (newCost < item->GetCost())
404 {
405 RemoveItem(*item);
406 item->SetCost(newCost);
407 InsertItem(*item);
408 return true;
409 }
410 else
411 {
412 return false;
413 }
414 } // end ProtoGraph::Vertice::PriorityQueue::AdjustDownward()
415
416 bool NetGraph::Interface::PriorityQueue::AdjustUpward(Interface& iface, const Cost& newCost)
417 {
418 Item* item = static_cast<Item*>(GetQueueState(iface));
419 ASSERT(item != NULL);
420 if (newCost > item->GetCost())
421 {
422 //bunny TBD this is wrong! we don't know for certain that this is the correct "path"
423 //we need to search for alternative shorter paths (upstream only!) and update the cost and route table information
424 RemoveItem(*item);
425 item->SetCost(newCost);
426 InsertItem(*item);
427 return true;
428 }
429 else
430 {
431 return false;
432 }
433 } // end ProtoGraph::Vertice::PriorityQueue::AdjustUpward()
434
435 bool NetGraph::Interface::PriorityQueue::Append(Interface& iface)
436 {
437 Item* item = item_factory.GetItem();
438 if (NULL == item)
439 {
440 PLOG(PL_ERROR, "NetGraph::Interface::PriorityQueue::Insert() error: couldn't allocate item\n");
441 return false;
442 }
443 Associate(iface, *item);
444 SortedList::AppendItem(*item);
445 return true;
446 } // end NetGraph::Interface::PriorityQueue::Append()
447
448 NetGraph::Interface::PriorityQueue::Iterator::Iterator(PriorityQueue& theQueue)
449 : SortedList::Iterator(theQueue)
450 {
451 }
452
453 NetGraph::Interface::PriorityQueue::Iterator::~Iterator()
454 {
455 }
456
457 const char* NetGraph::Interface::GetVerticeKey() const
458 {
459 if (addr_list.IsEmpty())
460 return name_ptr;
461 else
462 return default_addr_item.GetAddress().GetRawHostAddress();
463 } // end NetGraph::Interface::GetVerticeKey()
464
465 unsigned int NetGraph::Interface::GetVerticeKeysize() const
466 {
467 // Perhaps it is worthwhile to add a "key_size" member for efficiency?
468 if (addr_list.IsEmpty())
469 {
470 if (NULL != name_ptr)
471 {
472 unsigned int nameSize = strlen(name_ptr);
473 if (0 == (nameSize & 0x01)) nameSize += 1; // includes '\0' to make needed odd byte size
474 return (nameSize << 3);
475 }
476 else
477 {
478 return 0;
479 }
480 }
481 else
482 {
483 return (default_addr_item.GetAddress().GetLength() << 3);
484 }
485 } // end NetGraph::Interface::GetVerticeKeysize()
486
487 NetGraph::Node::Node()
488 : iface_list(true), default_interface_ptr(NULL)
489 {
490 }
491
492 NetGraph::Node::~Node()
493 {
494 // Delete all interfaces
495 Interface* iface;
496 while (NULL != (iface = static_cast<Interface*>(iface_list.RemoveHead())))
497 {
498 delete iface;
499 }
500 }
501
502 // Remove interfaces from target node ("foodNode")
503 // and append to this node
504 void NetGraph::Node::Consume(Node& foodNode)
505 {
506 Interface* iface;
507 while(NULL != (iface= foodNode.GetDefaultInterface()))
508 {
509 //foodNode.RemoveInterface(*iface);
510 iface->ChangeNode(*this);
511 }
512 } // end NetGraph::Node::Consume()
513
514 bool NetGraph::Node::AddInterface(Interface& iface, bool makeDefault)
515 {
516 if(iface_list.IsEmpty()) makeDefault = true;
517 if(!iface_list.Insert(iface))
518 {
519 PLOG(PL_ERROR, "NetGraph::Node::AddInterface() error: Insert failed on the iface_list!\n");
520 return false;
521 }
522 ProtoAddressList::Iterator iterator(iface.GetAddressList());
523 ProtoAddress addr;
524 while(iterator.GetNextAddress(addr))
525 {
526 if (addr.HostIsEqual(iface.GetDefaultAddress())) continue; // don't insert default addr in "extra_addr_list"
527 if(!extra_addr_list.Insert(addr, &iface))
528 {
529 PLOG(PL_ERROR, "NetGraph::Node::AddInterface() error: appending %s to the addr_list?!\n",addr.GetHostString());
530 RemoveInterface(iface);
531 return false;
532 }
533 }
534 if (makeDefault) default_interface_ptr = &iface;
535 return true;
536 } // end NetGraph::AddInterface)
537
538 void NetGraph::Node::RemoveInterface(Interface& iface)
539 {
540 iface_list.Remove(iface);
541 ProtoAddressList::Iterator iterator(iface.GetAddressList());
542 ProtoAddress addr;
543 while(iterator.GetNextAddress(addr))
544 extra_addr_list.Remove(addr);
545 //check to see if was the default and reassign a default if it was
546 if (&iface == default_interface_ptr)
547 default_interface_ptr = (NetGraph::Interface*)(iface_list.GetRoot());
548 } // end NetGraph::Node::RemoveInterface()
549
550 bool NetGraph::Node::IsSymmetricNeighbor(Node& node)
551 {
552 NetGraph::Node::InterfaceIterator it(*this);
553 NetGraph::Interface* interface = it.GetNextInterface();
554 while(NULL != interface)
555 {
556 NetGraph::Node::InterfaceIterator it2(node);
557 NetGraph::Interface* interface2 = it2.GetNextInterface();
558 while(NULL != interface2)
559 {
560 if(interface->HasLinkTo(*interface2) &&
561 interface2->HasLinkTo(*interface))
562 {
563 return true;
564 }
565 interface2 = it2.GetNextInterface();
566 }
567 interface = it.GetNextInterface();
568 }
569 return false;
570 }
571 NetGraph::Interface* NetGraph::Node::FindInterface(const ProtoAddress& addr) const
572 {
573 // First, look in "iface_list"
574 Interface* iface = static_cast<Interface*>(iface_list.Find(addr.GetRawHostAddress(), addr.GetLength() << 3));
575 if (NULL == iface) // Not in "iface_list", so look for it in "extra_addr_list"
576 iface = (Interface*)(extra_addr_list.GetUserData(addr));
577 return iface;
578 } // end NetGraph::Node::FindInterface()
579
580 NetGraph::Interface* NetGraph::Node::FindInterfaceByName(const char* theName)
581 {
582 int nameSize = strlen(theName);
583 if (0 == (nameSize & 0x01)) nameSize++; // ensures odd byte count to differentiate from addrs
584 nameSize <<= 3;
585 NetGraph::Interface* iface = static_cast<Interface*>(iface_list.Find(theName, nameSize));
586 if (NULL == iface)
587 {
588 // O(N) search for iface with matching name
589 InterfaceIterator iterator(*this);
590 while (NULL != (iface = iterator.GetNextInterface()))
591 {
592 const char* ifaceName = iface->GetName();
593 if ((NULL != ifaceName) && (0 == strcmp(ifaceName, theName)))
594 break;
595 }
596 }
597 return iface;
598 } // end NetGraph::Node::FindInterfaceByName()
599
600 NetGraph::Interface* NetGraph::Node::FindInterfaceByString(const char* theString)
601 {
602 NetGraph::Interface* iface = FindInterfaceByName(theString);
603 if(NULL == iface)
604 {
605 ProtoAddress addr;
606 addr.ResolveFromString(theString);
607 if(addr.IsValid())
608 {
609 iface = FindInterface(addr);
610 }
611 }
612 return iface;
613 }
614
615 bool NetGraph::Node::SetDefaultInterface(Interface& iface)
616 {
617 // Make sure this "iface" is valid (has address or name)
618 if (iface.GetAddress().IsValid() || (NULL != iface.GetName()))
619 {
620 default_interface_ptr = &iface;
621 return true;
622 }
623 else
624 {
625 PLOG(PL_ERROR,"NetGraph::Node::SetDefaultInterface() error: iface has no address or name!\n");
626 return false;
627 }
628 } // end NetGraph::Node::SetDefaultInterface()
629
630
631 NetGraph::Node::InterfaceIterator::InterfaceIterator(Node& node)
632 : ProtoSortedTree::Iterator(node.iface_list)
633 {
634 }
635
636 NetGraph::Node::InterfaceIterator::~InterfaceIterator()
637 {
638 }
639
640 NetGraph::Node::NeighborIterator::NeighborIterator(Node& node)
641 : iface_iterator(node), adj_iterator(*node.GetDefaultInterface())
642 {
643 Reset();
644 }
645
646 NetGraph::Node::NeighborIterator::~NeighborIterator()
647 {
648 }
649
650 void NetGraph::Node::NeighborIterator::Reset()
651 {
652 iface_iterator.Reset();
653 Interface* firstLocalIface = iface_iterator.GetNextInterface();
654 // use in-place new operator to instate adj_iterator for next local interface
655 if (NULL != firstLocalIface)
656 {
657 adj_iterator.~AdjacencyIterator();
658 new (&adj_iterator) AdjacencyIterator(*firstLocalIface);
659 }
660 } // end NetGraph::Node::NeighborIterator::Reset()
661
662
663 NetGraph::Interface* NetGraph::Node::NeighborIterator::GetNextNeighborInterface()
664 {
665 // This avoids calling an invalid "adj_iterator" (initialized with invalid iface reference)
666 if (iface_iterator.HasEmptyList()) return NULL;
667 Interface* iface = adj_iterator.GetNextAdjacency();
668 if (NULL == iface)
669 {
670 Interface* nextLocalInterface;
671 while (NULL != (nextLocalInterface = iface_iterator.GetNextInterface()))
672 {
673 // use in-place new operator to instantiate adj_iterator for next local interface
674 adj_iterator.~AdjacencyIterator();
675 new (&adj_iterator) AdjacencyIterator(*nextLocalInterface);
676 iface = adj_iterator.GetNextAdjacency();
677 if (NULL != iface) break;
678 }
679 }
680 return iface;
681 } // end NetGraph::Node::NeighborIterator::GetNextNeighborInterface()
682
683 NetGraph::Link* NetGraph::Node::NeighborIterator::GetNextNeighborLink()
684 {
685 // This avoids calling an invalid "adj_iterator" (initialized with invalid iface reference)
686 if (iface_iterator.HasEmptyList()) return NULL;
687 Link* link = adj_iterator.GetNextAdjacencyLink();
688 if (NULL == link)
689 {
690 Interface* nextLocalInterface;
691 while (NULL != (nextLocalInterface = iface_iterator.GetNextInterface()))
692 {
693 // use in-place new operator to instate adj_iterator for next local interface
694 adj_iterator.~AdjacencyIterator();
695 new (&adj_iterator) AdjacencyIterator(*nextLocalInterface);
696 link = adj_iterator.GetNextAdjacencyLink();
697 if (NULL != link) break;
698 }
699 }
700 return link;
701 } // end NetGraph::Node::NeighborIterator::GetNextNeighborInterface()
702
703 NetGraph::NetGraph()
704 {
705 }
706
707 NetGraph::~NetGraph()
708 {
709 }
710
711 // this function will be removed in upcoming releases
712 bool NetGraph::InsertNode(Node& node, Interface* iface)
713 {
714 if (NULL != iface)
715 {
716 // Insert just the specified interface
717 if (node.Contains(*iface))
718 {
719 return InsertInterface(*iface);
720 }
721 else
722 {
723 PLOG(PL_ERROR, "NetGraph::InsertNode() error: iface doesn't belong to node!\n");
724 return false;
725 }
726 }
727 else
728 {
729 // Insert all of the interfaces
730 bool hasIface = false;
731 Node::InterfaceIterator it(node);
732 while (NULL != (iface = it.GetNextInterface()))
733 {
734 hasIface = true;
735 if (!InsertInterface(*iface))
736 {
737 PLOG(PL_ERROR, "NetGraph::InsertNode() error: failed to add iface to graph!\n");
738 RemoveNode(node);
739 return false;
740 }
741 }
742 if (!hasIface)
743 {
744 PLOG(PL_ERROR, "NetGraph::InsertNode() error: node has no interfaces?!\n");
745 return false;
746 }
747 return true;
748 }
749 } // end NetGraph::InsertNode()
750
751 void NetGraph::RemoveNode(Node& node, Interface* iface)
752 {
753 if (NULL == iface)
754 {
755 // Remove all interfaces associated with this node
756 Node::InterfaceIterator it(node);
757 Interface* iface;
758 while (NULL != (iface = it.GetNextInterface()))
759 {
760 RemoveInterface(*iface);
761 }
762 }
763 else
764 {
765 // Remove only the interface specified
766 RemoveInterface(*iface);
767 }
768 } // end NetGraph::RemoveNode()
769
770 bool NetGraph::InsertInterface(Interface& iface)
771 {
772 if (!iface.GetAddress().IsValid() && (NULL == iface.GetName()))
773 {
774 PLOG(PL_ERROR, "NetGraph::InsertInterface() error: iface has no address or name!\n");
775 return false;
776 }
777 // Can only be in one graph at once
778 if (NULL != iface.graph) iface.graph->RemoveInterface(iface);
779 if (ProtoGraph::InsertVertice(iface))
780 {
781 ProtoAddressList::Iterator iterator(iface.GetAddressList());
782 ProtoAddress addr;
783 while(iterator.GetNextAddress(addr))
784 {
785 if(!addr_list.Insert(addr, &iface))
786 {
787 PLOG(PL_ERROR, "NetGraph::InsertInterface() error: cannot add address %s to the netgraph addr_list\n",addr.GetHostString());
788 RemoveInterface(iface);
789 return false;
790 }
791 }
792 iface.graph = this;
793 }
794 return true;
795 } // end NetGraph::InsertInterface()
796
797 void NetGraph::RemoveInterface(Interface& iface)
798 {
799 ProtoAddressList::Iterator iterator(iface.GetAddressList());
800 ProtoAddress addr;
801 while(iterator.GetNextAddress(addr)) addr_list.Remove(addr);
802 if (vertice_list.Contains(iface)) RemoveVertice(iface);
803 iface.graph = NULL;
804 } // end NetGraph::RemoveInterface()
805
806
807 NetGraph::Interface* NetGraph::FindInterfaceByName(const char* theName)
808 {
809 if (NULL == theName) return NULL;
810 unsigned int nameSize = strlen(theName);
811 if (0 == (nameSize & 0x01)) nameSize++;
812 nameSize <<= 3;
813 Interface* iface = static_cast<Interface*>(vertice_list.FindVertice(theName, nameSize));
814 if (NULL == iface)
815 {
816 InterfaceIterator iterator(*this);
817 while(NULL != (iface = iterator.GetNextInterface()))
818 {
819 const char* ifaceName = iface->GetName();
820 if ((NULL != ifaceName) && (0 == strcmp(ifaceName,theName))) return iface;
821 }
822 }
823 return iface;
824 } // end FindInterfaceByName()
825
826 NetGraph::Interface* NetGraph::FindInterfaceByString(const char* theString)
827 {
828 NetGraph::Interface* iface = FindInterfaceByName(theString);
829 if(NULL == iface)
830 {
831 ProtoAddress addr;
832 addr.ResolveFromString(theString);
833 if(addr.IsValid())
834 {
835 iface = FindInterface(addr);
836 }
837 }
838 return iface;
839 }
840
841 NetGraph::Link* NetGraph::Connect(Interface& srcIface, Interface& dstIface, const Cost& cost)
842 {
843 // TBD - allow multiple links srcIface <-> dstIface ???
844 Link* link = srcIface.GetLinkTo(dstIface);
845 // Is there already a link, "srcIface" to "dstIface"?
846 if (NULL != link)
847 {
848 PLOG(PL_WARN, "NetGraph::Connect() error: srcIface -> dstIface already connected\n");
849 return Reconnect(srcIface, dstIface, cost);
850 }
851 // Get a new link from our edge factory (from pool or created as needed)
852 // IMPORTANT NOTE: We _cannot_ call ProtoGraph::Connect() here directly
853 // since it is important to set the link cost _before_ putting the connection
854 // in place so that the adjacency queue gets ordered properly (i.e. by cost)
855 link = static_cast<Link*>(GetEdge());
856 if (NULL == link)
857 {
858 PLOG(PL_ERROR, "NetGraph::Connect() error: unable to allocate link\n");
859 return NULL;
860 }
861 link->SetCost(cost);
862 ProtoGraph::Connect(srcIface, dstIface, *link);
863 return link;
864 } // end NetGraph::Connect(directed link only)
865
866
867 bool NetGraph::Connect(Interface& srcIface, Interface& dstIface, const Cost& cost, bool duplex)
868 {
869 Link* link = Connect(srcIface, dstIface, cost);
870 if (!duplex) return (NULL != link);
871 if (NULL == link)
872 {
873 PLOG(PL_ERROR, "NetGraph::Connect() error: unable to allocate forward link\n");
874 return false;
875 }
876 if (NULL == Connect(dstIface, srcIface, cost))
877 {
878 PLOG(PL_ERROR, "NetGraph::Connect() error: unable to allocate reverse link\n");
879 Disconnect(srcIface, dstIface, true);
880 return false;
881 }
882 return true;
883 } // end NetGraph::Connect(duplex option)
884
885 NetGraph::Link* NetGraph::Reconnect(Interface& srcIface, Interface& dstIface, const Cost& cost)
886 {
887 // TBD - allow multiple links srcIface <-> dstIface ???
888 Link* link = srcIface.GetLinkTo(dstIface);
889 // Is there already a link, "srcIface" to "dstIface"?
890 if (NULL == link)
891 {
892 PLOG(PL_WARN, "NetGraph::Reconnect() error: srcIface -> dstIface not connected\n");
893 return NULL;
894 }
895 else if (cost == link->GetCost())
896 {
897 return link;
898 }
899 this->SuspendEdge(srcIface, dstIface, *link);
900 link->SetCost(cost);
901 ProtoGraph::Reconnect(srcIface,dstIface,*link);
902 return link;
903 } // end NetGraph::Reconnect()
904
905 bool NetGraph::Reconnect(Interface& srcIface, Interface& dstIface, const Cost& cost, bool duplex)
906 {
907 Link* link = Reconnect(srcIface, dstIface, cost);
908 if (!duplex) return (NULL != link);
909 if (NULL == link)
910 {
911 PLOG(PL_ERROR, "NetGraph::Reconnect() error: unable to reconnect forward link\n");
912 return false;
913 }
914 if (NULL == Reconnect(dstIface, srcIface, cost))
915 {
916 PLOG(PL_ERROR, "NetGraph::Reconnect() error: unable to reconnect reverse link\n");
917 Disconnect(srcIface, dstIface, true);
918 return false;
919 }
920 return true;
921 } // end NetGraph::Reconnect()
922
923
924 NetGraph::InterfaceIterator::InterfaceIterator(NetGraph& theGraph)
925 : ProtoGraph::VerticeIterator(static_cast<ProtoGraph&>(theGraph))
926 {
927 }
928
929 NetGraph::InterfaceIterator::~InterfaceIterator()
930 {
931 }
932
933 NetGraph::SimpleTraversal::SimpleTraversal(const NetGraph& theGraph,
934 Interface& startIface,
935 bool traverseNodes,
936 bool collapseNodes,
937 bool depthFirst)
938 : ProtoGraph::SimpleTraversal(theGraph, startIface, depthFirst),
939 traverse_nodes(traverseNodes), collapse_nodes(collapseNodes)
940 {
941 Reset(true);
942 }
943
944 NetGraph::SimpleTraversal::~SimpleTraversal()
945 {
946 }
947
948 bool NetGraph::SimpleTraversal::Reset(bool constructor)
949 {
950 if (!constructor)
951 {
952 if (!ProtoGraph::SimpleTraversal::Reset())
953 {
954 PLOG(PL_ERROR, "NetGraph::SimpleTraversal::Reset() error: couldn't enqueue start_vertice\n");
955 return false;
956 }
957 }
958 if (traverse_nodes && collapse_nodes)
959 {
960 // Init with all interfaces of current node at level zero and init
961 // trans_vertice equal to last (note that NetGraph::SimpleTraversal::Reset()
962 // already inits queue_pending with start_vertice)
963 Interface& startIface = static_cast<Interface&>(start_vertice);
964 Node::InterfaceIterator ifaceIterator(startIface.GetNode());
965 Interface* nextIface;
966 while (NULL != (nextIface = ifaceIterator.GetNextInterface()))
967 {
968 if (static_cast<Interface*>(&start_vertice) == nextIface)
969 continue;
970 ASSERT(!nextIface->IsInQueue(queue_visited) && !nextIface->IsInQueue(queue_pending));
971 if (!AllowLink(startIface, *nextIface, NULL)) continue;
972 if (depth_first)
973 queue_pending.Prepend(*nextIface);
974 else
975 queue_pending.Append(*nextIface);
976 }
977 }
978 return true;
979 } // end ProtoGraph::SimpleTraversal::Reset()
980
981 // This traversal can use all of its nodes' local interfaces
982 NetGraph::Interface* NetGraph::SimpleTraversal::GetNextInterface(unsigned int* level)
983 {
984 Interface* currentIface = static_cast<Interface*>(queue_pending.GetHead());
985 if (NULL != currentIface)
986 {
987 queue_pending.TransferVertice(*currentIface, queue_visited);
988 Vertice* transAdjacency = NULL; // used to find "level" transitions
989 Interface* nextIface;
990 if (traverse_nodes && !collapse_nodes)
991 {
992 // Here we treat other ifaces on same node as adjacent
993 Node::InterfaceIterator ifaceIterator(currentIface->GetNode());
994 while (NULL != (nextIface = ifaceIterator.GetNextInterface()))
995 {
996 if (!nextIface->IsInQueue(queue_visited) &&
997 !nextIface->IsInQueue(queue_pending))
998 {
999 if (!AllowLink(*currentIface, *nextIface, NULL)) continue;
1000 if (depth_first)
1001 {
1002 queue_pending.Prepend(*nextIface);
1003 // (TBD) depth tracking for Depth-first search
1004 }
1005 else
1006 {
1007 queue_pending.Append(*nextIface);
1008 if (NULL == transAdjacency)
1009 transAdjacency = nextIface;
1010 }
1011 }
1012 }
1013 }
1014 // Now iterate to other neighboring interfaces
1015 AdjacencyIterator adjacencyIterator(*currentIface);
1016 Link* nextLink;
1017 while (NULL != (nextLink = adjacencyIterator.GetNextAdjacencyLink()))
1018 {
1019 nextIface = nextLink->GetDst();
1020 ASSERT(NULL != nextIface);
1021 if (!nextIface->IsInQueue(queue_visited) &&
1022 !nextIface->IsInQueue(queue_pending))
1023 {
1024 if (!AllowLink(*currentIface, *nextIface, nextLink)) continue;
1025 if (depth_first)
1026 {
1027 queue_pending.Prepend(*nextIface);
1028 // (TBD) depth tracking for Depth-first search
1029 }
1030 else
1031 {
1032 queue_pending.Append(*nextIface);
1033 if (NULL == transAdjacency)
1034 transAdjacency = nextIface;
1035 }
1036 if (traverse_nodes && collapse_nodes)
1037 {
1038 // Here co-interfaces are treated as equivalent adjacencies
1039 Node::InterfaceIterator ifaceIterator(nextIface->GetNode());
1040 Interface* nextCoface;
1041 while (NULL != (nextCoface = ifaceIterator.GetNextInterface()))
1042 {
1043 if (nextCoface == nextIface) continue;
1044 ASSERT(!nextCoface->IsInQueue(queue_visited) && !nextCoface->IsInQueue(queue_pending));
1045 if (depth_first)
1046 queue_pending.Prepend(*nextCoface);
1047 else
1048 queue_pending.Append(*nextCoface);
1049 }
1050 }
1051 }
1052 }
1053 if (NULL == trans_vertice)
1054 {
1055 trans_vertice = transAdjacency;
1056 }
1057 else if (trans_vertice == currentIface)
1058 {
1059 current_level++;
1060 trans_vertice = transAdjacency;
1061 }
1062 if (NULL != level) *level = current_level;
1063 }
1064 return currentIface;
1065
1066 } // end NetGraph::SimpleTraversal::GetNextInterface()
1067
1068 /*
1069 // This traversal can use all of its nodes' local interfaces
1070 NetGraph::Interface* NetGraph::SimpleTraversal::GetNextInterface(unsigned int* level)
1071 {
1072 if (traverse_nodes)
1073 {
1074 //TRACE("enter NetGraph::SimpleTraversal::GetNextInterface() ...\n");
1075 Interface* currentIface = static_cast<Interface*>(queue_pending.GetHead());
1076 if (NULL == currentIface) return NULL; // we're done
1077 //TRACE("level %u trans_vertice:%p currentIface:%p\n", level, trans_vertice, static_cast<Vertice*>(currentIface));
1078 if ((static_cast<Vertice*>(currentIface) == trans_vertice) || (NULL == trans_vertice))
1079 {
1080 if (NULL != trans_vertice) current_level++;
1081 // Enqueue adjacencies (and their co-interfaces)of queue_pending as next level
1082 Vertice::SimpleList::Iterator penderator(queue_pending);
1083 Interface* nextPending;
1084 Interface* transIface = NULL;
1085 //int p = 0;
1086 while (NULL != (nextPending = static_cast<Interface*>(penderator.GetNextVertice())))
1087 {
1088 if (nextPending == transIface) break;
1089 //TRACE(" pending iface %d ...\n", p++);
1090 AdjacencyIterator adjacencyIterator(*nextPending);
1091 Link* nextLink;
1092 while (NULL != (nextLink = adjacencyIterator.GetNextAdjacencyLink()))
1093 {
1094 Interface* nextIface = nextLink->GetDst();
1095 ASSERT(NULL != nextIface);
1096 if (!nextIface->IsInQueue(queue_visited) &&
1097 !nextIface->IsInQueue(queue_pending))
1098 {
1099 if (!AllowLink(*nextPending, *nextIface, nextLink)) continue;
1100 Node::InterfaceIterator ifaceIterator(nextIface->GetNode());
1101 Interface* nextCoface;
1102 while (NULL != (nextCoface = ifaceIterator.GetNextInterface()))
1103 {
1104 if (NULL == transIface) transIface = nextCoface;
1105 if (depth_first)
1106 {
1107 queue_pending.Prepend(*nextCoface);
1108 // (TBD) depth tracking for Depth-first search
1109 }
1110 else
1111 {
1112 //TRACE(" Appending level %u co-interface ...\n", current_level);
1113 queue_pending.Append(*nextCoface);
1114 }
1115 }
1116 }
1117 }
1118 }
1119 trans_vertice = static_cast<Vertice*>(transIface);
1120 }
1121 queue_pending.TransferVertice(*currentIface, queue_visited);
1122 if (NULL != level) *level = current_level;
1123 return currentIface;
1124 }
1125 else
1126 {
1127 // If not traversing nodes, then just use ProtoGraph::SimpleTraversal
1128 return static_cast<Interface*>(ProtoGraph::SimpleTraversal::GetNextVertice(level));
1129 }
1130 } // end NetGraph::SimpleTraversal::GetNextInterface()
1131 */
1132
1133
1134 NetGraph::DijkstraTraversal::DijkstraTraversal(NetGraph& theGraph,
1135 Interface* startIface)
1136 : manet_graph(theGraph), start_iface(startIface),
1137 queue_pending(static_cast<ItemFactory&>(*this)),
1138 queue_visited(static_cast<ItemFactory&>(*this)),
1139 trans_iface(NULL), current_level(0), dijkstra_completed(false), in_update(false), traverse_nodes(false), reset_required(false)
1140 {
1141
1142 }
1143
1144 NetGraph::DijkstraTraversal::DijkstraTraversal(NetGraph& theGraph,
1145 Node& startNode,
1146 Interface* startIface)
1147 : manet_graph(theGraph), start_iface((NULL != startIface) ? startIface : startNode.GetDefaultInterface()),
1148 queue_pending(static_cast<ItemFactory&>(*this)),
1149 queue_visited(static_cast<ItemFactory&>(*this)),
1150 trans_iface(NULL), current_level(0), dijkstra_completed(false), in_update(false), traverse_nodes(false), reset_required(false)
1151 {
1152 // ASSERT(&start_iface->GetNode() == &startNode);
1153 }
1154
1155 NetGraph::DijkstraTraversal::~DijkstraTraversal()
1156 {
1157 queue_pending.Empty();
1158 queue_visited.Empty();
1159 }
1160
1161 void
1162 NetGraph::DijkstraTraversal::TraverseNodes(bool traverse)
1163 {
1164 traverse_nodes = traverse;
1165 }
1166
1167 bool NetGraph::DijkstraTraversal::Reset(Interface* startIface)
1168 {
1169 // (TBD) use a dual queue approach so that we can avoid
1170 // visiting every iface twice everytime we run the Dijkstra.
1171 // I.e., we could maintain "visited" & "unvisited" queue, removing ifaces
1172 // from that queue as they are visited, and then at the end of
1173 // the Dijkstra, update the cost of any remaining unvisited ifaces
1174 // to COST_MAX and then swap visited and unvisited queues for next
1175 // Dijkstra run ... Thus each iface would be visited only once _or_ as
1176 // needed for Dijkstra instead of once _plus_ as needed for Dijkstra
1177 queue_visited.Empty();
1178 queue_pending.Empty();
1179 Cost& startCost = AccessCostTemp();
1180 startCost.Minimize();
1181
1182 if (NULL != startIface)
1183 start_iface = startIface;
1184
1185 if (NULL != start_iface)
1186 {
1187 if(traverse_nodes)
1188 {
1189 Node::InterfaceIterator ifaceIterator(start_iface->GetNode());
1190 Interface* nextIface;
1191 while (NULL != (nextIface = ifaceIterator.GetNextInterface()))
1192 {
1193 if (!queue_pending.Insert(*nextIface, startCost))
1194 {
1195 PLOG(PL_ERROR, "NetGraph::DijkstraTraversal::Reset() error: couldn't enqueue a start_iface (traverse_nodes)\n");
1196 return false;
1197 }
1198 }
1199 }
1200 else
1201 {
1202 if (!queue_pending.Insert(*start_iface, startCost))
1203 {
1204 PLOG(PL_ERROR, "NetGraph::DijkstraTraversal::Reset() error: couldn't enqueue start_iface\n");
1205 return false;
1206 }
1207 }
1208 //TRACE("dijkstra_completed = false bunny1\n");
1209 dijkstra_completed = false;
1210 }
1211 else
1212 {
1213 //TRACE("dijkstra_completed = true bunny2\n");
1214 dijkstra_completed = true;
1215 }
1216 return true;
1217 } // end NetGraph::DijkstraTraversal::Reset()
1218
1219
1220 // Dijkstra traversal step
1221 NetGraph::Interface* NetGraph::DijkstraTraversal::GetNextInterface()
1222 {
1223 // (TBD) We could be a little more efficient if we worked with PriorityQueue::Items directly
1224 Interface* currentIface = queue_pending.GetHead();
1225 if (NULL != currentIface)
1226 {
1227 queue_pending.TransferInterface(*currentIface, queue_visited);
1228 const Cost* currentCost = queue_visited.GetCost(*currentIface);
1229 ASSERT(NULL != currentCost);
1230 //TRACE(" %s being updated with cost %f\n",currentIface->GetAddress().GetHostString(),((ManetGraph::Cost*)currentCost)->GetValue());
1231 AdjacencyIterator linkIterator(*currentIface);
1232 Link* nextLink;
1233 while ((nextLink = linkIterator.GetNextAdjacencyLink()))
1234 {
1235 Interface* nextDst = nextLink->GetDst();
1236 ASSERT(NULL != nextDst);
1237 if (!AllowLink(*currentIface, *nextLink)) continue;
1238 const Cost& linkCost = nextLink->GetCost();
1239 Cost& nextCost = AccessCostTemp();
1240 nextCost = linkCost;
1241 nextCost += *currentCost;
1242
1243 Node::InterfaceIterator ifaceIterator(nextDst->GetNode());
1244 if(traverse_nodes)
1245 nextDst = ifaceIterator.GetNextInterface();
1246 do
1247 {
1248 bool saveState = true;
1249 if(!in_update)
1250 {
1251 if (nextDst->IsInQueue(queue_pending))
1252 {
1253 // We have found another path to this pending iface.
1254 // If it is a shorter path update the cost to lower value
1255 if (!queue_pending.AdjustDownward(*nextDst, nextCost, currentIface))
1256 saveState = false;
1257 }
1258 else if (!nextDst->IsInQueue(queue_visited))
1259 {
1260 // This is the first path found to this iface,
1261 // so enqueue it in our "queue_pending" queue
1262 if (!queue_pending.Insert(*nextDst, nextCost))
1263 {
1264 PLOG(PL_ERROR, "NetGraph::DijkstraTraversal::GetNextInterface() error: couldn't enqueue iface\n");
1265 return NULL;
1266 }
1267 }
1268 else
1269 {
1270 saveState = false;
1271 }
1272 }
1273 else // in_update
1274 {
1275 // visited queue nodes may not have been updated yet...we need a different way to check.
1276 Interface* prevHopIface;
1277 bool isInVisited = false;
1278 bool isNewIface = false;
1279 Interface::PriorityQueue* queuePtr = &queue_pending;
1280 if(nextDst->IsInQueue(queue_visited))
1281 {
1282 isInVisited = true;
1283 queuePtr = &queue_visited;
1284 }
1285 else if (!nextDst->IsInQueue(queue_pending))
1286 {
1287 //new interface so just go ahead and add it
1288 isNewIface = true;
1289 }
1290
1291 if(isNewIface)
1292 {
1293 if (!queue_pending.Insert(*nextDst, nextCost))
1294 {
1295 PLOG(PL_ERROR, "NetGraph::DijkstraTraversal::GetNextInterface() error: couldn't enqueue iface\n");
1296 return NULL;
1297 }
1298
1299 }
1300 else if (queuePtr->AdjustDownward(*nextDst, nextCost, currentIface)) // try and move it down
1301 {
1302 //TRACE(" %s moved downward\n",nextDst->GetAddress().GetHostString());
1303 if(isInVisited)
1304 {
1305 //TRACE(" was in visited queue adding it to the pending queue so children can be updated\n");
1306 queue_visited.TransferInterface(*nextDst, queue_pending); //it moved down so put it in the pending queue to updated it's children...
1307 }
1308 }
1309 else if(NULL != (prevHopIface = queuePtr->GetPrevHop(*nextDst)))
1310 {
1311 //need to check if we were the previous hop
1312 //Interface* bunnyTemp = queuePtr->GetNextHop(*currentIface);
1313 //if(bunnyTemp)
1314 // TRACE("bunny next hop current is %s\n",bunnyTemp->GetAddress().GetHostString());
1315 //TRACE("checking next nbr from current iface %s \n",currentIface->GetAddress().GetHostString());
1316 //TRACE("prev hop %s ",prevHopIface->GetAddress().GetHostString());
1317 //TRACE("of dst %s iface\n",nextDst->GetAddress().GetHostString());
1318 bool linkWasUsed = false;
1319 if(traverse_nodes)
1320 {
1321 if (currentIface->GetNode().Contains(*prevHopIface))
1322 linkWasUsed = true;
1323 }
1324 else
1325 {
1326 if (currentIface == prevHopIface)
1327 linkWasUsed = true;
1328 }
1329 if(linkWasUsed)
1330 {
1331 //TRACE("link was used was it longer? if yes then\n");
1332 if(queuePtr->AdjustUpward(*nextDst, nextCost))
1333 {
1334 //TRACE("link we are bailing out and setting the required reset bool true!\n");
1335 //we need to verify that this is the currently shortest path and if not fix it!
1336 //New function required or expand AdjustUpward to take care of this.
1337
1338 //using class variable to tell update to do a full reset...
1339 //Fixing AdjustingUpward and putting the some queue update stuff will then we can remove this
1340 reset_required = true;
1341 saveState = false;
1342 return NULL;
1343 //queue_visited.TransferInterface(*nextDst, queue_pending);
1344 //we need to check neighbors to see if they used this path and update them if they did.
1345 }
1346 else
1347 {
1348 //TRACE("link was same length as before not saving state\n");
1349 saveState = false;
1350 }
1351 }
1352 else
1353 {
1354 //TRACE("link wasn't used not saving\n");
1355 saveState = false;
1356 }
1357 }
1358 else
1359 {
1360 //TRACE("no prev hop\n");
1361 //no previous hop this can happen if currentIface is on the root node
1362 saveState = false;
1363 }
1364 // I _think_ this is currently broken? It seems we would need to shuffle nodes
1365 // from "queue_visited" to "queue_pending" here to work properly? ... Note that
1366 // it depends heavily on "Update()" being called with a proper "startIface"
1367 // This checks for shorter path to a "visited" iface
1368 // (must be in "Update()" mode! (i.e. "in_update == true")
1369 /*{
1370 // Update the routing tree state
1371 if (currentIface == start_iface)
1372 queue_visited.SetRouteInfo(*nextDst, nextLink, currentIface);
1373 else
1374 queue_visited.SetRouteInfo(*nextDst, queue_visited.GetNextHopLink(*currentIface), currentIface);
1375 }
1376 saveState = false;*/
1377 }
1378 // Save our routing tree state as we go
1379 if(saveState)
1380 {
1381 //if (currentIface == start_iface)
1382 if(start_iface->GetNode().Contains(*currentIface))
1383 {
1384 //leaving debug statements here but commented out for the time being JD
1385 if(nextDst==NULL)
1386 {
1387 //TRACE("nextDst is null!\n");
1388 }
1389 else
1390 {
1391 //TRACE("nextDst is %s\n",nextDst->GetAddress().GetHostString());
1392 }
1393 if(nextLink==NULL)
1394 {
1395 //TRACE("nextLink is null!\n");
1396 }
1397 else
1398 {
1399 //TRACE("nextLink src is %s dst is ",nextLink->GetSrc()->GetAddress().GetHostString());
1400 //TRACE("%s\n",nextLink->GetDst()->GetAddress().GetHostString());
1401 }
1402 if(currentIface==NULL)
1403 {
1404 //TRACE("currentIface is null!\n");
1405 }
1406 else
1407 {
1408 //TRACE("currentIface is %s\n",currentIface->GetAddress().GetHostString());
1409 }
1410 queue_pending.SetRouteInfo(*nextDst, nextLink, currentIface);
1411 }
1412 else
1413 {
1414 if(queue_visited.Contains(*currentIface))
1415 queue_pending.SetRouteInfo(*nextDst, queue_visited.GetNextHopLink(*currentIface), currentIface);
1416 else
1417 queue_pending.SetRouteInfo(*nextDst, queue_pending.GetNextHopLink(*currentIface), currentIface);
1418 }
1419 }
1420 if(traverse_nodes)
1421 nextDst = ifaceIterator.GetNextInterface();
1422 else
1423 nextDst = NULL;
1424 } while (nextDst != NULL);
1425 } // end while ((nextLink = linkIterator.GetNextAdjacencyLink()))
1426 }
1427 else
1428 {
1429 //TRACE("dijkstra_completed = true bunny2\n");
1430 dijkstra_completed = true;
1431 }
1432 return currentIface;
1433 } // end NetGraph::DijkstraTraversal::GetNextInterface()
1434
1435 bool NetGraph::DijkstraTraversal::PrevHopIsValid(Interface& currentIface)
1436 {
1437 ASSERT(start_iface != NULL);
1438 if (!traverse_nodes)
1439 {
1440 if (&currentIface == start_iface)
1441 return true;
1442 }
1443 else
1444 {
1445 if(currentIface.GetNode().Contains(*start_iface))
1446 return true;
1447 }
1448 const Cost* currCostPtr = GetCost(currentIface);
1449 if(currCostPtr == NULL)
1450 return false;
1451 Interface* prevHopIface = NULL;
1452 if(NULL != (prevHopIface = queue_visited.GetPrevHop(currentIface)))
1453 {
1454 const Cost* prevCostPtr = GetCost(*prevHopIface);
1455 if(prevCostPtr == NULL)
1456 return false;
1457
1458 if(!traverse_nodes)
1459 {
1460 Link* linkPtr = prevHopIface->GetLinkTo(currentIface);
1461 if(linkPtr != NULL)
1462 {
1463 if (AllowLink(*prevHopIface, *linkPtr))
1464 {
1465 Cost& sumCost = AccessCostTemp();
1466 sumCost = linkPtr->GetCost();
1467 sumCost += *prevCostPtr;
1468 if(sumCost > *currCostPtr)
1469 {
1470 // cost has increased and is no longer valid
1471 return false;
1472 }
1473 else if (sumCost < *currCostPtr)
1474 {
1475 // 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
1476 return true;
1477 }
1478 else
1479 {
1480 return true;
1481 }
1482 }
1483 }
1484 else
1485 {
1486 // no link exists from my previous hop, returning null
1487 return false;
1488 }
1489 }
1490 else
1491 {
1492 ManetNode::NeighborIterator nbIt(prevHopIface->GetNode());
1493 Link* linkPtr = NULL;
1494 while(NULL != (linkPtr = nbIt.GetNextNeighborLink()))
1495 {
1496 Interface* srcPtr = linkPtr->GetSrc();
1497 ASSERT(NULL != srcPtr);
1498 if (!AllowLink(*srcPtr, *linkPtr)) continue;
1499 Interface* dstPtr = linkPtr->GetDst();
1500 if(dstPtr!=NULL)
1501 {
1502 if(currentIface.GetNode().Contains(*dstPtr))
1503 {
1504 Cost& sumCost = AccessCostTemp();
1505 sumCost = linkPtr->GetCost();
1506 sumCost += *prevCostPtr;
1507 if(sumCost <= *currCostPtr)
1508 return true;
1509 if (sumCost == *currCostPtr)
1510 return true;
1511 }
1512 }
1513 }
1514 return false;
1515 }
1516 }
1517 else
1518 {
1519 // previous hop is null, returning false;
1520 return false;
1521 }
1522 return true;
1523 } //end NetGraph::Interface* NetGraph::DijkstraTraversal::PreviousHopIsValid()
1524
1525 void NetGraph::DijkstraTraversal::Update(Interface& startIface)
1526 {
1527 //TRACE(" calling update on interface %s\n",startIface.GetAddress().GetHostString());
1528 if (!dijkstra_completed)
1529 {
1530 //TRACE("bunny doing a full reset...\n");
1531 Reset();
1532 // Complete dijkstra traversal
1533 while (NULL != GetNextInterface());
1534 return;
1535 }
1536 if(!PrevHopIsValid(startIface))
1537 {
1538 //we might be able to find and update the "star cluster" for the next best paths but it might not be worth it
1539 //TRACE(" previous hop isn't valid....doing a full reset...\n");
1540 Reset();
1541 // Complete dijkstra traversal
1542 while (NULL != GetNextInterface());
1543 return;
1544 }
1545 ASSERT(queue_pending.IsEmpty());
1546
1547 //set up the initial state for walking through the graph stub.
1548 in_update = true;
1549 Interface* origStartIfacePtr = start_iface;
1550 start_iface=&startIface;
1551 if(startIface.IsInQueue(queue_visited))
1552 {
1553 //TRACE(" Interface was in the visited queue so setting up pending queue to update dijkstra state\n");
1554 if(traverse_nodes)
1555 {
1556 Node::InterfaceIterator ifaceIterator(startIface.GetNode());
1557 Interface* nextIface = NULL;
1558 while (NULL !=(nextIface = ifaceIterator.GetNextInterface()))
1559 queue_visited.TransferInterface(*nextIface, queue_pending);
1560 }
1561 else
1562 {
1563 queue_visited.TransferInterface(startIface, queue_pending);
1564 }
1565 }
1566 else
1567 {
1568 // Need to reset entire Dijkstra (as a new interface has been added and we don't know from where)
1569 // (TBD - maybe something smarter can be done here)
1570 // could be solved in a similar way to the star cluster as a single isolated branch/leaf is a subset of that problem
1571 //TRACE(" Interface to update isn't in the visited queue doing a full reset\n");
1572 reset_required = true;
1573 }
1574 //walk through and update the graph stub
1575 if(!reset_required)
1576 {
1577 //TRACE(" Going to walk through the graph\n");
1578 }
1579 Interface *nextIface = GetNextInterface();
1580 if(reset_required)
1581 nextIface = NULL;
1582 while (NULL != nextIface)
1583 {
1584 //TRACE(" %s is the next iface\n",nextIface->GetAddress().GetHostString());
1585 if(reset_required)
1586 nextIface = NULL;
1587 else
1588 nextIface = GetNextInterface();
1589 }
1590 //finished walking through stub check to make sure a reset isn't required
1591 //TRACE(" finishing up the state and checking to see if a reset is required\n");
1592 in_update = false;
1593 start_iface=origStartIfacePtr;
1594 if(reset_required)
1595 {
1596 //TRACE(" Needed a full reset\n");
1597 Reset();
1598 while (NULL != GetNextInterface());
1599 }
1600 //if (!dijkstra_completed)
1601 // TRACE("Getting out without dijkstra being finished!\n");
1602 } // end NetGraph::DijkstraTraversal::Update()
1603
1604 // Call this to setup re-traverse of tree computed via Dijkstra
1605 void NetGraph::DijkstraTraversal::Update(Interface& ifaceA, Interface& ifaceB)
1606 {
1607 const NetGraph::Cost* aCostPtr = GetCost(ifaceA);
1608 const NetGraph::Cost* bCostPtr = GetCost(ifaceB);
1609 if((aCostPtr != NULL) && (bCostPtr != NULL))
1610 {
1611 if(*aCostPtr > *bCostPtr)
1612 {
1613 Link* linkPtr = ifaceB.GetLinkTo(ifaceA);
1614 if(NULL != linkPtr)
1615 {
1616 // there is a link so lets try and update B without doing a full update
1617 if (!AllowLink(ifaceB, *linkPtr))
1618 {
1619 //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
1620 Update(ifaceA);
1621 }
1622 else
1623 {
1624 Update(ifaceB);
1625 }
1626 }
1627 else
1628 {
1629 //the link doesn't exists and if the link was on shortest path this will cause a full reset otherwise nothing will be updated
1630 Update(ifaceA);
1631 }
1632 }
1633 else
1634 {
1635 //a's cost is less than b's
1636 Link* linkPtr = ifaceA.GetLinkTo(ifaceB);
1637 if(NULL != linkPtr)
1638 {
1639 if (!AllowLink(ifaceA, *linkPtr))
1640 {
1641 //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
1642 Update(ifaceB);
1643 }
1644 else
1645 {
1646 //there is a link so lets try and update A without doing a full update
1647 Update(ifaceA);
1648 }
1649 }
1650 else
1651 {
1652 //the link doesn't exists and if the link was on shortest path this will cause a full rest otherwise nothing will be updated
1653 Update(ifaceB);
1654 }
1655 }
1656 }
1657 else if(aCostPtr != NULL)
1658 {
1659 Update(ifaceA);
1660 }
1661 else if (bCostPtr != NULL)
1662 {
1663 Update(ifaceB);
1664 }
1665 }
1666
1667 bool NetGraph::DijkstraTraversal::TreeWalkReset()
1668 {
1669 // If Dijkstra was not completed, run full Dijkstra
1670 if (!dijkstra_completed)
1671 {
1672 //TRACE("In reset...\n");
1673 Reset();
1674 while (NULL != GetNextInterface());
1675 }
1676 ASSERT(queue_pending.IsEmpty());
1677 if (NULL != start_iface)
1678 {
1679 if (!queue_pending.Append(*start_iface))
1680 {
1681 PLOG(PL_ERROR, "NetGraph::DijkstraTraversal::TreeWalkReset() error: couldn't append start_iface\n");
1682 return false;
1683 }
1684 }
1685 trans_iface = NULL;
1686 current_level = 0;
1687 return true;
1688 } // end NetGraph::DijkstraTraversal::TreeWalkReset()
1689
1690 NetGraph::Interface* NetGraph::DijkstraTraversal::TreeWalkNext(unsigned int* level)
1691 {
1692 Interface* currentIface = queue_pending.RemoveHead();
1693 if (NULL != currentIface)
1694 {
1695 // Find selected links
1696
1697 Link* nextLink;
1698 Link* firstLink = NULL;
1699 if(traverse_nodes)
1700 {
1701 NetGraph::Node::NeighborIterator linkIterator(currentIface->GetNode());
1702 while ((nextLink = linkIterator.GetNextNeighborLink()))
1703 {
1704 Interface* nextDst = nextLink->GetDst();
1705 ASSERT(NULL != nextDst);
1706 if (currentIface == GetPrevHop(*nextDst))
1707 {
1708 if (NULL == firstLink) firstLink = nextLink;
1709 queue_pending.Append(*nextDst);
1710 }
1711 }
1712 }
1713 else
1714 {
1715 AdjacencyIterator linkIterator(*currentIface);
1716 while ((nextLink = linkIterator.GetNextAdjacencyLink()))
1717 {
1718 Interface* nextDst = nextLink->GetDst();
1719 ASSERT(NULL != nextDst);
1720 if (currentIface == GetPrevHop(*nextDst))
1721 {
1722 if (NULL == firstLink) firstLink = nextLink;
1723 queue_pending.Append(*nextDst);
1724 }
1725 }
1726 }
1727 // Track depth as walk progresses ...
1728 if (NULL == trans_iface)
1729 {
1730 trans_iface = firstLink ? firstLink->GetDst() : NULL;
1731 }
1732 else if (trans_iface == currentIface)
1733 {
1734 trans_iface = firstLink ? firstLink->GetDst() : NULL;
1735 current_level++;
1736 }
1737 if (NULL != level) *level = current_level;
1738 }
1739 return currentIface;
1740 } // end NetGraph::DijkstraTraversal::TreeWalkNext()