| 1 |
#ifndef _MANET_GRAPH |
| 2 |
#define _MANET_GRAPH |
| 3 |
|
| 4 |
#include "protoGraph.h" |
| 5 |
#include "protoAddress.h" |
| 6 |
|
| 7 |
/** |
| 8 |
* @class NetGraph |
| 9 |
* |
| 10 |
* @brief This "NetGraph" stuff (incl. its embedded classes) are base classes |
| 11 |
* that will be used, along with some help from a template defined afterward, |
| 12 |
* for maintaining state, computing Dijkstra or other traversals, for |
| 13 |
* Mobile Ad-hoc Network (MANET) routing, etc. |
| 14 |
* |
| 15 |
* (It is also useful for any routing, but the motivation for this is to |
| 16 |
* support MANET R&D we are conducting. The "NetGraph" contains a set of |
| 17 |
* "NetGraph::Interface" instances that may be connected with some associated |
| 18 |
* "Cost" with "NetGraph::Link" instances (NetGraph::Link's are uni-directional, |
| 19 |
* but convenience methods for bi-directional connectivity are provided). |
| 20 |
* Additionally, a "ManetNode" class is provide to associate a set of |
| 21 |
* interfaces together, but these associate interfaces are only considered |
| 22 |
* "connected" if explicitly done. |
| 23 |
*/ |
| 24 |
|
| 25 |
// TBD - it may make sense to rename "NetGraph" defined here to "NetGraphBase" and |
| 26 |
// keep the name "NetGraph" free or just use it for our example |
| 27 |
// template usage instead of ManetGraph and actually rename this |
| 28 |
// entire ".h" as "netGraph.h" instead of "manetGraph.h" and then |
| 29 |
// "ManetGraph" would be available as a name. |
| 30 |
// |
| 31 |
// This would makes sense since "NetGraph" here essentially just adds |
| 32 |
// the notion of "cost" to graph edges and provides for some |
| 33 |
// cost-based traversals (e.g. Dijkstra). It also defines "Interfaces" |
| 34 |
// as vertices that are identified by a ProtoAddress. Then the derived |
| 35 |
// Protolib "ManetGraph" could add ProtoTimer and other elements to |
| 36 |
// to links (edges) and interfaces (vertices) that are more applicable |
| 37 |
// for the dynamic wireless environment that MANET strives to support. |
| 38 |
|
| 39 |
|
| 40 |
class NetGraph : public ProtoGraph |
| 41 |
{ |
| 42 |
public: |
| 43 |
virtual ~NetGraph(); |
| 44 |
|
| 45 |
/** |
| 46 |
* @class NetGraph::Cost |
| 47 |
* |
| 48 |
* @brief Base class for variants of "Cost" we can use for |
| 49 |
* various graph traversals (e.g. Dyjkstra), etc |
| 50 |
*/ |
| 51 |
class Cost |
| 52 |
{ |
| 53 |
public: |
| 54 |
virtual ~Cost(); |
| 55 |
|
| 56 |
// Required overrides |
| 57 |
virtual const char* GetCostKey() const = 0; |
| 58 |
virtual unsigned int GetCostKeysize() const = 0; // in bits |
| 59 |
|
| 60 |
// These methods help ProtoSortedTree when comparing keys (i.e. cost value) |
| 61 |
// (Note the ProtoSortedTree does a modified lexical sort based on these) |
| 62 |
virtual bool GetCostKeySigned() const = 0; |
| 63 |
virtual bool GetCostKeyComplement2() const = 0; |
| 64 |
virtual ProtoTree::Endian GetCostKeyEndian() const = 0; |
| 65 |
|
| 66 |
// Copy operator |
| 67 |
virtual Cost& operator=(const Cost& cost) = 0; |
| 68 |
|
| 69 |
// Value control |
| 70 |
virtual void Minimize() = 0; |
| 71 |
|
| 72 |
// Addition operator |
| 73 |
virtual void operator+=(const Cost& cost) = 0; |
| 74 |
|
| 75 |
// Cost comparison methods |
| 76 |
virtual bool operator>(const Cost& cost) const = 0; |
| 77 |
|
| 78 |
virtual bool operator==(const Cost& cost) const = 0; |
| 79 |
|
| 80 |
bool operator!=(const Cost& cost) const |
| 81 |
{return (!(cost == *this));} |
| 82 |
|
| 83 |
bool operator>=(const Cost& cost) const |
| 84 |
{return ((*this > cost) || (*this == cost));} |
| 85 |
|
| 86 |
bool operator<(const Cost& cost) const |
| 87 |
{return ((*this >= cost) ? false : true);} |
| 88 |
|
| 89 |
bool operator<=(const Cost& cost) const |
| 90 |
{return ((*this > cost) ? false : true);} |
| 91 |
|
| 92 |
protected: |
| 93 |
Cost(); |
| 94 |
|
| 95 |
}; // end class NetGraph::Cost |
| 96 |
|
| 97 |
/** |
| 98 |
* @class NetGraph::SimpleCostTemplate |
| 99 |
* |
| 100 |
* @brief This wraps "double" floating point cost value. We assume |
| 101 |
* IEEE754 format for the "value" member (I do have code for |
| 102 |
* converting native machine floating point values to/from |
| 103 |
* IEEE754 if needed) |
| 104 |
* |
| 105 |
* (TBD) Make "SimpleCost" a template class based upon a built-in type? |
| 106 |
* (e.g., double, int, etc) |
| 107 |
*/ |
| 108 |
template <class SIMPLE_TYPE> |
| 109 |
class SimpleCostTemplate : public Cost |
| 110 |
{ |
| 111 |
public: |
| 112 |
SimpleCostTemplate() : value(0) {} |
| 113 |
SimpleCostTemplate(SIMPLE_TYPE theValue) : value(theValue) {} |
| 114 |
virtual ~SimpleCostTemplate() {} |
| 115 |
|
| 116 |
void SetValue(SIMPLE_TYPE theValue) |
| 117 |
{value = theValue;} |
| 118 |
|
| 119 |
SIMPLE_TYPE GetValue() const |
| 120 |
{return value;} |
| 121 |
|
| 122 |
operator SIMPLE_TYPE() const |
| 123 |
{return value;} |
| 124 |
|
| 125 |
SimpleCostTemplate& operator=(SIMPLE_TYPE theValue) |
| 126 |
{ |
| 127 |
value = theValue; |
| 128 |
return *this; |
| 129 |
} |
| 130 |
|
| 131 |
SimpleCostTemplate& operator=(const SimpleCostTemplate& cost) |
| 132 |
{ |
| 133 |
value = cost.value; |
| 134 |
return *this; |
| 135 |
} |
| 136 |
|
| 137 |
// Required overrides of pure virtual methods |
| 138 |
// (These are used to help sorting by value) |
| 139 |
const char* GetCostKey() const |
| 140 |
{return ((char*)&value);} |
| 141 |
unsigned int GetCostKeysize() const |
| 142 |
{return (sizeof(SIMPLE_TYPE) << 3);} |
| 143 |
virtual bool GetCostKeySigned() const |
| 144 |
{return true;} |
| 145 |
virtual bool GetCostKeyComplement2() const |
| 146 |
{return false;} |
| 147 |
virtual ProtoTree::Endian GetCostKeyEndian() const |
| 148 |
{return ProtoTree::GetNativeEndian();} |
| 149 |
|
| 150 |
Cost& operator=(const Cost& cost) |
| 151 |
{ |
| 152 |
ASSERT(NULL != dynamic_cast<const SimpleCostTemplate*>(&cost)); |
| 153 |
value = static_cast<const SimpleCostTemplate&>(cost).value; |
| 154 |
return *this; |
| 155 |
} |
| 156 |
|
| 157 |
void Minimize() |
| 158 |
{ value = 0;} |
| 159 |
|
| 160 |
bool operator==(const Cost& cost) const |
| 161 |
{ |
| 162 |
ASSERT(NULL != dynamic_cast<const SimpleCostTemplate*>(&cost)); |
| 163 |
return (value == static_cast<const SimpleCostTemplate&>(cost).value); |
| 164 |
} |
| 165 |
|
| 166 |
bool operator>(const Cost& cost) const |
| 167 |
{ |
| 168 |
ASSERT(NULL != dynamic_cast<const SimpleCostTemplate*>(&cost)); |
| 169 |
return (value > static_cast<const SimpleCostTemplate&>(cost).value); |
| 170 |
} |
| 171 |
|
| 172 |
void operator+=(const Cost& cost) |
| 173 |
{ |
| 174 |
ASSERT(NULL != dynamic_cast<const SimpleCostTemplate*>(&cost)); |
| 175 |
value += static_cast<const SimpleCostTemplate&>(cost).value; |
| 176 |
} |
| 177 |
|
| 178 |
protected: |
| 179 |
SIMPLE_TYPE value; |
| 180 |
|
| 181 |
}; // end class NetGraph::SimpleCostTemplate |
| 182 |
|
| 183 |
/** |
| 184 |
* @class NetGraph::SimpleCostDouble |
| 185 |
* |
| 186 |
* @brief This SimpleCost variant holds a "double" floating point cost value. |
| 187 |
* We assume an IEEE754 format for the "value" member (I do have |
| 188 |
* code for converting native machine floating point values to/from |
| 189 |
* IEEE754 if needed) |
| 190 |
*/ |
| 191 |
class SimpleCostDouble : public SimpleCostTemplate<double> |
| 192 |
{ |
| 193 |
public: |
| 194 |
SimpleCostDouble() {} |
| 195 |
SimpleCostDouble(double theValue) : SimpleCostTemplate<double>(theValue) {} |
| 196 |
}; // end class NetGraph::SimpleCostDouble |
| 197 |
|
| 198 |
class SimpleCostUINT32 : public SimpleCostTemplate<UINT32> |
| 199 |
{ |
| 200 |
public: |
| 201 |
SimpleCostUINT32() {} |
| 202 |
SimpleCostUINT32(UINT32 theValue) : SimpleCostTemplate<UINT32>(theValue) {} |
| 203 |
// Don't use the sign bit since it's "unsigned" |
| 204 |
bool GetCostKeySigned() const |
| 205 |
{return false;} |
| 206 |
}; // end class NetGraph::SimpleCostUINT32 |
| 207 |
|
| 208 |
class SimpleCostUINT8 : public SimpleCostTemplate<UINT8> |
| 209 |
{ |
| 210 |
public: |
| 211 |
SimpleCostUINT8() {} |
| 212 |
SimpleCostUINT8(UINT8 theValue) : SimpleCostTemplate<UINT8>(theValue) {} |
| 213 |
// Don't use the sign bit since it's "unsigned" |
| 214 |
bool GetCostKeySigned() const |
| 215 |
{return false;} |
| 216 |
}; // end class NetGraph::SimpleCostUINT8 |
| 217 |
|
| 218 |
class Interface; |
| 219 |
class Link; |
| 220 |
|
| 221 |
// TBD - Should the AdjacentyIterator be declared inside the Interface declaration? |
| 222 |
// If we did this, the templated version could return the correct types |
| 223 |
class AdjacencyIterator : public ProtoGraph::AdjacencyIterator |
| 224 |
{ |
| 225 |
public: |
| 226 |
AdjacencyIterator(Interface& iface); |
| 227 |
virtual ~AdjacencyIterator(); |
| 228 |
|
| 229 |
Interface* GetNextAdjacency() |
| 230 |
{return static_cast<Interface*>(ProtoGraph::AdjacencyIterator::GetNextAdjacency());} |
| 231 |
|
| 232 |
Link* GetNextAdjacencyLink() |
| 233 |
{return static_cast<Link*>(ProtoGraph::AdjacencyIterator::GetNextAdjacencyEdge());} |
| 234 |
|
| 235 |
Interface* GetNextConnector() |
| 236 |
{return static_cast<Interface*>(ProtoGraph::AdjacencyIterator::GetNextConnector());} |
| 237 |
|
| 238 |
}; // end class NetGraph::AdjacencyIterator |
| 239 |
|
| 240 |
/** |
| 241 |
* @class NetGraph::Link |
| 242 |
* |
| 243 |
* @brief adds "cost" attribute to ProtoGraph::Edge |
| 244 |
*/ |
| 245 |
class Link : public Edge |
| 246 |
{ |
| 247 |
public: |
| 248 |
virtual ~Link(); |
| 249 |
|
| 250 |
// Our template below will override this for us. |
| 251 |
virtual const Cost& GetCost() const = 0; |
| 252 |
|
| 253 |
void SetCost(const Cost& cost); |
| 254 |
|
| 255 |
Interface* GetSrc() const |
| 256 |
{return static_cast<Interface*>(Edge::GetSrc());} |
| 257 |
|
| 258 |
Interface* GetDst() const |
| 259 |
{return static_cast<Interface*>(Edge::GetDst());} |
| 260 |
|
| 261 |
// Required overrides |
| 262 |
virtual const char* GetKey() const |
| 263 |
{return GetCost().GetCostKey();} |
| 264 |
virtual unsigned int GetKeysize() const |
| 265 |
{return (GetCost().GetCostKeysize());} |
| 266 |
virtual ProtoTree::Endian GetEndian() const |
| 267 |
{return GetCost().GetCostKeyEndian();} |
| 268 |
virtual bool UseSignBit() const |
| 269 |
{return GetCost().GetCostKeySigned();} |
| 270 |
virtual bool UseComplement2() const |
| 271 |
{return GetCost().GetCostKeyComplement2();} |
| 272 |
|
| 273 |
protected: |
| 274 |
Link(); |
| 275 |
// Our template below will override this for us. |
| 276 |
virtual Cost& AccessCost() = 0; |
| 277 |
|
| 278 |
}; // end class NetGraph::Link |
| 279 |
|
| 280 |
class Node; // a "Node" is a "super-vertice" in a NetGraph while an |
| 281 |
// "Interface" is an actual vertice. The "Interfaces" |
| 282 |
// associated with a "Node" may or may not be connected. |
| 283 |
/** |
| 284 |
* @class NetGraph::Interface |
| 285 |
* |
| 286 |
* @brief adds "address" identifier to ProtoGraph::Vertice and also |
| 287 |
* ties "Interface" to NetGraph::Node |
| 288 |
* Note the "ProtoSortedTree::Item()" aspect is for its inclusion its |
| 289 |
* "node" iface_list only |
| 290 |
*/ |
| 291 |
class Interface : public ProtoGraph::Vertice, public ProtoSortedTree::Item |
| 292 |
{ |
| 293 |
friend class NetGraph; |
| 294 |
public: |
| 295 |
Interface(Node& theNode, const ProtoAddress& addr); |
| 296 |
Interface(Node& theNode); |
| 297 |
virtual ~Interface(); |
| 298 |
|
| 299 |
const ProtoAddress& GetAddress() const |
| 300 |
{return default_addr_item.GetAddress();} |
| 301 |
const ProtoAddress& GetAnyAddress() const |
| 302 |
{return GetAddress();} |
| 303 |
ProtoAddressList& GetAddressList() |
| 304 |
{return addr_list;} |
| 305 |
|
| 306 |
bool SetName(const char* theName); |
| 307 |
const char* GetName() const |
| 308 |
{return name_ptr;} |
| 309 |
void ClearName(); // nullifies name |
| 310 |
|
| 311 |
// Use to add additional "extra" addresses |
| 312 |
// Note: Any graphs currently containing this interface get be updated as well |
| 313 |
bool AddAddress(const ProtoAddress& theAddress); |
| 314 |
bool RemoveAddress(const ProtoAddress& theAddress); |
| 315 |
|
| 316 |
bool Contains(const ProtoAddress& theAddress) const |
| 317 |
{return addr_list.Contains(theAddress);} |
| 318 |
|
| 319 |
const ProtoAddress& GetDefaultAddress() const |
| 320 |
{return default_addr_item.GetAddress();} |
| 321 |
|
| 322 |
//void SetAddress(const ProtoAddress& theAddress) |
| 323 |
// {address = theAddress;} |
| 324 |
|
| 325 |
Node& GetNode() const |
| 326 |
{return *node;} |
| 327 |
|
| 328 |
const Node* GetNodePtr() const |
| 329 |
{return node;} |
| 330 |
|
| 331 |
bool ChangeNode(Node& theNode); |
| 332 |
|
| 333 |
bool HasLinkTo(const Interface& dstIface) const |
| 334 |
{return ProtoGraph::Vertice::HasEdgeTo(dstIface);} |
| 335 |
|
| 336 |
Link* GetLinkTo(const Interface& dstIface) const |
| 337 |
{return static_cast<Link*>(ProtoGraph::Vertice::GetEdgeTo(dstIface));} |
| 338 |
|
| 339 |
// This maintains a simple, unsorted (non-indexed) list of Interfaces |
| 340 |
class SimpleList : public Vertice::SimpleList |
| 341 |
{ |
| 342 |
public: |
| 343 |
SimpleList(ItemPool* itemPool = NULL); |
| 344 |
virtual ~SimpleList(); |
| 345 |
|
| 346 |
Interface* GetHead() const |
| 347 |
{return static_cast<Interface*>(Vertice::SimpleList::GetHead());} |
| 348 |
|
| 349 |
Interface* RemoveHead() |
| 350 |
{return static_cast<Interface*>(Vertice::SimpleList::RemoveHead());} |
| 351 |
|
| 352 |
class Iterator : public Vertice::SimpleList::Iterator |
| 353 |
{ |
| 354 |
public: |
| 355 |
Iterator(const SimpleList& theList); |
| 356 |
virtual ~Iterator(); |
| 357 |
|
| 358 |
Interface* GetNextInterface() |
| 359 |
{return static_cast<Interface*>(GetNextVertice());} |
| 360 |
|
| 361 |
}; // end class NetGraph::Interface::SimpleList::Iterator |
| 362 |
|
| 363 |
}; // end class NetGraph::Interface::SimpleList |
| 364 |
|
| 365 |
// This maintains a list of Interfaces, sorted by their "key", etc |
| 366 |
class SortedList : public Vertice::SortedList |
| 367 |
{ |
| 368 |
public: |
| 369 |
SortedList(ItemPool* itemPool = NULL); |
| 370 |
virtual ~SortedList(); |
| 371 |
|
| 372 |
Interface* FindInterface(const ProtoAddress& addr) const |
| 373 |
{return static_cast<Interface*>(FindVertice(addr.GetRawHostAddress(), addr.GetLength() << 3));} |
| 374 |
|
| 375 |
Interface* GetHead() const |
| 376 |
{return static_cast<Interface*>(Vertice::SortedList::GetHead());} |
| 377 |
|
| 378 |
Interface* RemoveHead() |
| 379 |
{return static_cast<Interface*>(Vertice::SortedList::RemoveHead());} |
| 380 |
|
| 381 |
class Iterator : public Vertice::SortedList::Iterator |
| 382 |
{ |
| 383 |
public: |
| 384 |
Iterator(SortedList& theList); |
| 385 |
virtual ~Iterator(); |
| 386 |
|
| 387 |
Interface* GetNextInterface() |
| 388 |
{return static_cast<Interface*>(GetNextVertice());} |
| 389 |
|
| 390 |
}; // end class NetGraph::Interface::SortedList::Iterator |
| 391 |
|
| 392 |
}; // end class NetGraph::Interface::SortedList |
| 393 |
|
| 394 |
// PriorityQueue class to use for traversal purposes |
| 395 |
// This sorts by "Cost" associated with the interface |
| 396 |
class PriorityQueue : public Vertice::SortedList |
| 397 |
{ |
| 398 |
public: |
| 399 |
class ItemFactory; |
| 400 |
|
| 401 |
PriorityQueue(ItemFactory& itemFactory); |
| 402 |
virtual ~PriorityQueue(); |
| 403 |
|
| 404 |
bool Insert(Interface& iface, const Cost& cost); |
| 405 |
|
| 406 |
void Remove(Interface& iface) |
| 407 |
{SortedList::Remove(iface);} |
| 408 |
|
| 409 |
Interface* RemoveHead() |
| 410 |
{return static_cast<Interface*>(SortedList::RemoveHead());} |
| 411 |
|
| 412 |
bool IsEmpty() const |
| 413 |
{return iface_list.IsEmpty();} |
| 414 |
|
| 415 |
Interface* GetHead() const |
| 416 |
{return static_cast<Interface*>(SortedList::GetHead());} |
| 417 |
|
| 418 |
const Cost* GetCost(const Interface& iface) const |
| 419 |
{ |
| 420 |
Item* item = static_cast<Item*>(GetQueueState(iface)); |
| 421 |
return ((NULL != item) ? &(item->GetCost()) : NULL); |
| 422 |
} |
| 423 |
|
| 424 |
// Move vertice from this PriorityQueue to another |
| 425 |
void TransferInterface(Interface& iface, PriorityQueue& dstQueue) |
| 426 |
{SortedList::TransferVertice(iface, dstQueue);} |
| 427 |
|
| 428 |
void TransferItem(Item& item, PriorityQueue& dstQueue) |
| 429 |
{SortedList::TransferItem(item, dstQueue);} |
| 430 |
|
| 431 |
// These are used to query enqueued interfaces post-Dijkstra |
| 432 |
Interface* GetNextHop(const Interface& iface) const |
| 433 |
{ |
| 434 |
Item* item = static_cast<Item*>(GetQueueState(iface)); |
| 435 |
return ((NULL != item) ? item->GetNextHop() : NULL); |
| 436 |
} |
| 437 |
Link* GetNextHopLink(const Interface& iface) const |
| 438 |
{ |
| 439 |
Item* item = static_cast<Item*>(GetQueueState(iface)); |
| 440 |
return ((NULL != item) ? item->GetNextHopLink() : NULL); |
| 441 |
} |
| 442 |
Interface* GetPrevHop(const Interface& iface) const |
| 443 |
{ |
| 444 |
Item* item = static_cast<Item*>(GetQueueState(iface)); |
| 445 |
return ((NULL != item) ? item->GetPrevHop() : NULL); |
| 446 |
} |
| 447 |
void SetRouteInfo(Interface& iface, Link* nextHopLink, Interface* prevHop) |
| 448 |
{ |
| 449 |
Item* item = static_cast<Item*>(GetQueueState(iface)); |
| 450 |
ASSERT(NULL != item); |
| 451 |
item->SetNextHopLink(nextHopLink); |
| 452 |
item->SetPrevHop(prevHop); |
| 453 |
} |
| 454 |
|
| 455 |
void Adjust(Interface& iface, const Cost& newCost); |
| 456 |
bool AdjustDownward(Interface& iface, const Cost& newCost,const Interface* newPrevHop = NULL); |
| 457 |
bool AdjustUpward(Interface& iface, const Cost& newCost); |
| 458 |
|
| 459 |
// Note use of this method does not maintain priority queue sorting order! |
| 460 |
bool Append(Interface& iface); // used for Dijkstra "tree walking" only |
| 461 |
|
| 462 |
class Item : public SortedList::Item |
| 463 |
{ |
| 464 |
public: |
| 465 |
virtual ~Item(); |
| 466 |
|
| 467 |
// Our subclass templates will override these |
| 468 |
virtual const Cost& GetCost() const = 0; |
| 469 |
virtual void SetCost(const Cost& cost) = 0; |
| 470 |
|
| 471 |
// "ProtoGraph::Vertice::SortedList::Item" overrides |
| 472 |
// (We sort our PriorityQueue items by "cost") |
| 473 |
const char* GetKey() const |
| 474 |
{return GetCost().GetCostKey();} |
| 475 |
unsigned int GetKeysize() const |
| 476 |
{return GetCost().GetCostKeysize();} |
| 477 |
virtual ProtoTree::Endian GetEndian() const |
| 478 |
{return GetCost().GetCostKeyEndian();} |
| 479 |
virtual bool UseSignBit() const |
| 480 |
{return GetCost().GetCostKeySigned();} |
| 481 |
virtual bool UseComplement2() const |
| 482 |
{return GetCost().GetCostKeyComplement2();} |
| 483 |
|
| 484 |
Interface* GetInterface() const |
| 485 |
{return static_cast<Interface*>(GetVertice());} |
| 486 |
|
| 487 |
// These are useful post-Djikstra completion |
| 488 |
void SetPrevHop(Interface* prevHop) |
| 489 |
{prev_hop = prevHop;} |
| 490 |
Interface* GetPrevHop() const |
| 491 |
{return prev_hop;} |
| 492 |
|
| 493 |
void SetNextHopLink(Link* nextHopLink) |
| 494 |
{next_hop_link = nextHopLink;} |
| 495 |
Link* GetNextHopLink() const |
| 496 |
{return next_hop_link;} |
| 497 |
Interface* GetNextHop() const |
| 498 |
{return ((NULL != next_hop_link) ? next_hop_link->GetDst() : NULL);} |
| 499 |
|
| 500 |
protected: |
| 501 |
Item(); |
| 502 |
// Our subclass templates will override this |
| 503 |
virtual Cost& AccessCost() = 0; |
| 504 |
|
| 505 |
private: |
| 506 |
Interface* prev_hop; // reverse path towards srcIFace |
| 507 |
Link* next_hop_link; // forward path from srcIface to here |
| 508 |
|
| 509 |
}; // end class NetGraph::Interface::PriorityQueue::Item |
| 510 |
|
| 511 |
class ItemFactory |
| 512 |
{ |
| 513 |
public: |
| 514 |
virtual ~ItemFactory(); |
| 515 |
|
| 516 |
void Destroy() |
| 517 |
{item_pool.Destroy();} |
| 518 |
|
| 519 |
Item* GetItem(); |
| 520 |
|
| 521 |
void PutItem(Item& item) |
| 522 |
{item_pool.PutItem(item);} |
| 523 |
|
| 524 |
protected: |
| 525 |
ItemFactory(); |
| 526 |
virtual Item* CreateItem() const = 0; |
| 527 |
|
| 528 |
// Member variables |
| 529 |
SortedList::ItemPool item_pool; |
| 530 |
|
| 531 |
}; // end class NetGraph::Interface::PriorityQueue::ItemFactory |
| 532 |
|
| 533 |
class Iterator : public SortedList::Iterator |
| 534 |
{ |
| 535 |
public: |
| 536 |
Iterator(PriorityQueue& priorityQueue); |
| 537 |
virtual ~Iterator(); |
| 538 |
|
| 539 |
Interface* GetNextInterface() |
| 540 |
{return static_cast<Interface*>(SortedList::Iterator::GetNextVertice());} |
| 541 |
|
| 542 |
Item* GetNextItem() |
| 543 |
{return static_cast<Item*>(SortedList::Iterator::GetNextItem());} |
| 544 |
|
| 545 |
}; // end NetGraph::Interface::PriorityQueue::Iterator |
| 546 |
|
| 547 |
protected: |
| 548 |
// Member variables |
| 549 |
ProtoSortedTree iface_list; // sorted by "Cost" value |
| 550 |
ItemFactory& item_factory; |
| 551 |
|
| 552 |
private: |
| 553 |
using Vertice::SortedList::Remove; // gets rid of hidden overloaded virtual function warning |
| 554 |
|
| 555 |
}; // end NetGraph::Interface::PriorityQueue |
| 556 |
|
| 557 |
protected: |
| 558 |
// Overrides for interfaces with "key" based on address |
| 559 |
// ProtoGraph::Vertice parent class overrides |
| 560 |
// Subclasses _may_ want to override these methods |
| 561 |
// (These are used for default sorting of |
| 562 |
// of the Vertice::SortedList if used) |
| 563 |
// _BUT_ if these are overridden, the derived |
| 564 |
// class destructor _MUST_ call Vertice::Cleanup() so |
| 565 |
// that these _are_ not indirectly called in the Vertice |
| 566 |
// destructor!!! |
| 567 |
|
| 568 |
// These affect the Interface's sorting criteria |
| 569 |
// in the ProtoGraph::vertice_list and any Interface::SortedList |
| 570 |
// membership. |
| 571 |
virtual const char* GetVerticeKey() const; |
| 572 |
virtual unsigned int GetVerticeKeysize() const; |
| 573 |
|
| 574 |
private: |
| 575 |
// ProtoSortedTree::Item parent class overrides |
| 576 |
virtual const char* GetKey() const |
| 577 |
{return GetVerticeKey();} |
| 578 |
virtual unsigned int GetKeysize() const |
| 579 |
{return GetVerticeKeysize();} |
| 580 |
|
| 581 |
Node* node; |
| 582 |
NetGraph* graph; |
| 583 |
ProtoAddressList addr_list; |
| 584 |
ProtoAddressList::Item default_addr_item; |
| 585 |
char* name_ptr; |
| 586 |
}; // end class NetGraph::Interface |
| 587 |
|
| 588 |
// The "Node" class associates multiple interfaces together even if they |
| 589 |
// are not connected in a ManetGraph. A "Node" reference is required in |
| 590 |
// the "Interface" constructor. Note that when a "Node" is deleted, it |
| 591 |
// deletes any Interfaces contained in its "iface_list" |
| 592 |
class Node |
| 593 |
{ |
| 594 |
public: |
| 595 |
Node(); |
| 596 |
virtual ~Node(); |
| 597 |
|
| 598 |
void Consume(Node& foodNode); |
| 599 |
|
| 600 |
Interface* FindInterface(const ProtoAddress& addr) const; |
| 601 |
// {return static_cast<Interface*>(iface_list.Find(addr.GetRawHostAddress(), addr.GetLength() << 3));} |
| 602 |
// {return reinterpret_cast<Interface*>((void*)addr_list.GetUserData(addr));} |
| 603 |
Interface* FindInterfaceByName(const char* theName); |
| 604 |
|
| 605 |
Interface* FindInterfaceByString(const char* theString); //looks for it as both a name and address |
| 606 |
|
| 607 |
bool AddInterface(Interface& iface, bool makeDefault = false); |
| 608 |
|
| 609 |
void RemoveInterface(Interface& iface); |
| 610 |
|
| 611 |
// Note "AppendInterface() should be deprecated |
| 612 |
bool AppendInterface(Interface& iface, bool makeDefault = false) |
| 613 |
{return AddInterface(iface, makeDefault);} |
| 614 |
|
| 615 |
bool Contains(const Interface& iface) const |
| 616 |
{return (iface.GetNodePtr() == this);} |
| 617 |
|
| 618 |
Interface* GetAnyInterface() const |
| 619 |
{return static_cast<Interface*>(iface_list.GetRoot());} |
| 620 |
Interface* GetDefaultInterface() const |
| 621 |
{return static_cast<Interface*>(default_interface_ptr);} |
| 622 |
|
| 623 |
bool IsSymmetricNeighbor(Node& node); |
| 624 |
|
| 625 |
class InterfaceIterator : public ProtoSortedTree::Iterator |
| 626 |
{ |
| 627 |
public: |
| 628 |
InterfaceIterator(Node& theNode); |
| 629 |
virtual ~InterfaceIterator(); |
| 630 |
|
| 631 |
bool HasEmptyList() |
| 632 |
{return HasEmptyTree();} |
| 633 |
|
| 634 |
void Reset() |
| 635 |
{ProtoSortedTree::Iterator::Reset();} |
| 636 |
|
| 637 |
Interface* GetNextInterface() |
| 638 |
{return static_cast<Interface*>(GetNextItem());} |
| 639 |
|
| 640 |
}; // end class NetGraph::Node::InterfaceIterator |
| 641 |
|
| 642 |
friend class InterfaceIterator; |
| 643 |
friend class NetGraph::Interface; |
| 644 |
|
| 645 |
// Iterate over all _neighboring_ interfaces |
| 646 |
class NeighborIterator |
| 647 |
{ |
| 648 |
public: |
| 649 |
NeighborIterator(Node& theNode); |
| 650 |
virtual ~NeighborIterator(); |
| 651 |
|
| 652 |
void Reset(); |
| 653 |
|
| 654 |
Interface* GetNextNeighborInterface(); |
| 655 |
|
| 656 |
Link* GetNextNeighborLink(); |
| 657 |
|
| 658 |
private: |
| 659 |
InterfaceIterator iface_iterator; |
| 660 |
AdjacencyIterator adj_iterator; |
| 661 |
}; // end class NetGraph::Node::NeighborIterator |
| 662 |
|
| 663 |
protected: |
| 664 |
|
| 665 |
ProtoSortedTree iface_list; |
| 666 |
ProtoAddressList extra_addr_list; // contains list of ifaces' "extra" addresses |
| 667 |
|
| 668 |
private: |
| 669 |
bool AddExtraInterfaceAddress(const Interface& iface,const ProtoAddress& addr) |
| 670 |
{return extra_addr_list.Insert(addr, &iface);} |
| 671 |
void RemoveExtraInterfaceAddress(const ProtoAddress& addr) |
| 672 |
{extra_addr_list.Remove(addr);} |
| 673 |
bool SetDefaultInterface(Interface& iface); |
| 674 |
|
| 675 |
Interface* default_interface_ptr; |
| 676 |
}; // end class NetGraph::Node |
| 677 |
|
| 678 |
// NetGraph control/query methods |
| 679 |
bool InsertNode(Node& node, Interface* iface = NULL); //this function will be removed in upcoming releases |
| 680 |
bool InsertInterface(Interface& iface); // this function should be used instead of InsertNode() |
| 681 |
void RemoveNode(Node& node, Interface* iface = NULL); |
| 682 |
void RemoveInterface(Interface& iface); // This removes the interface _and_ its links |
| 683 |
|
| 684 |
Interface* FindInterface(const ProtoAddress& addr) const |
| 685 |
{return ((Interface*)addr_list.GetUserData(addr));} |
| 686 |
|
| 687 |
Node* FindNode(const ProtoAddress& theAddress) |
| 688 |
{ |
| 689 |
Interface* iface = FindInterface(theAddress); |
| 690 |
return ((NULL != iface) ? &iface->GetNode() : NULL); |
| 691 |
} |
| 692 |
|
| 693 |
Interface* FindInterfaceByName(const char *theName); |
| 694 |
|
| 695 |
Interface* FindInterfaceByString(const char *theString); // finds the interface both by name and address |
| 696 |
|
| 697 |
Node* FindNodeByName(const char *theName) |
| 698 |
{ |
| 699 |
Interface* iface = FindInterfaceByName(theName); |
| 700 |
return ((NULL != iface) ? &iface->GetNode() : NULL); |
| 701 |
} |
| 702 |
|
| 703 |
Node* FindNodeByString(const char* theString) |
| 704 |
{ |
| 705 |
Interface* iface = FindInterfaceByString(theString); |
| 706 |
return ((NULL != iface) ? &iface->GetNode() : NULL); |
| 707 |
} |
| 708 |
|
| 709 |
class InterfaceIterator : public ProtoGraph::VerticeIterator |
| 710 |
{ |
| 711 |
public: |
| 712 |
InterfaceIterator(NetGraph& theGraph); |
| 713 |
virtual ~InterfaceIterator(); |
| 714 |
|
| 715 |
Interface* GetNextInterface() |
| 716 |
{return static_cast<Interface*>(GetNextVertice());} |
| 717 |
|
| 718 |
}; // end class NetGraph::InterfaceIterator |
| 719 |
|
| 720 |
|
| 721 |
class SimpleTraversal : protected ProtoGraph::SimpleTraversal |
| 722 |
{ |
| 723 |
public: |
| 724 |
SimpleTraversal(const NetGraph& theGraph, |
| 725 |
Interface& startIface, |
| 726 |
bool traverseNodes = true, |
| 727 |
bool collapseNodes = true, |
| 728 |
bool depthFirst = false); |
| 729 |
|
| 730 |
virtual ~SimpleTraversal(); |
| 731 |
|
| 732 |
bool Reset() |
| 733 |
{return Reset(false);} |
| 734 |
|
| 735 |
Interface* GetNextInterface(unsigned int* level = NULL); |
| 736 |
|
| 737 |
protected: |
| 738 |
// Override this method to filter which edges are included in traversal |
| 739 |
// (return "false" to disallow specific edges) |
| 740 |
// Note "link" will be NULL is src/dst are on same node |
| 741 |
virtual bool AllowLink(const Interface& srcIface, const Interface& dstIface, Link* link) |
| 742 |
{return true;} |
| 743 |
|
| 744 |
bool Reset(bool constructor); // arg for internal-use only |
| 745 |
|
| 746 |
bool traverse_nodes; // traverse all node interfaces |
| 747 |
bool collapse_nodes; // treat node co-interfaces as a common vertice |
| 748 |
|
| 749 |
}; // end class NetGraph::SimpleTraversal |
| 750 |
|
| 751 |
class DijkstraTraversal : public Interface::PriorityQueue::ItemFactory |
| 752 |
{ |
| 753 |
public: |
| 754 |
virtual ~DijkstraTraversal(); |
| 755 |
|
| 756 |
// Set to false by default; If set to true the traversal will iterate over nodes as well as interfaces. |
| 757 |
void TraverseNodes(bool traverse); |
| 758 |
|
| 759 |
bool Reset(Interface* startIface = NULL); |
| 760 |
|
| 761 |
Interface* GetNextInterface(); |
| 762 |
|
| 763 |
bool PrevHopIsValid(Interface& currentIface); |
| 764 |
|
| 765 |
void Update(Interface& startIface); |
| 766 |
|
| 767 |
void Update(Interface& ifaceA, Interface& ifaceB); |
| 768 |
|
| 769 |
// Override this method to filter which edges are included in traversal |
| 770 |
// (return "false" to disallow specific links) |
| 771 |
virtual bool AllowLink(const Interface& srcIface, const Link& link) |
| 772 |
{return true;} |
| 773 |
|
| 774 |
// (use these post-Dijkstra (after "GetNextInterface" returns NULL) |
| 775 |
Interface* GetNextHop(const Interface& dstIface) // from "startIface" towards "dstIface" |
| 776 |
{return (queue_visited.GetNextHop(dstIface));} |
| 777 |
|
| 778 |
Interface* GetPrevHop(const Interface& dstIface) // back towards "startIface" |
| 779 |
{return (queue_visited.GetPrevHop(dstIface));} |
| 780 |
|
| 781 |
const Cost* GetCost(const Interface& dstIface) const |
| 782 |
{return (queue_visited.GetCost(dstIface));} |
| 783 |
|
| 784 |
// BFS traversal of routing tree ("tree walk") |
| 785 |
bool TreeWalkReset(); |
| 786 |
Interface* TreeWalkNext(unsigned int* level = NULL); |
| 787 |
|
| 788 |
protected: |
| 789 |
DijkstraTraversal(NetGraph& theGraph, |
| 790 |
Interface* startIface); |
| 791 |
|
| 792 |
DijkstraTraversal(NetGraph& theGraph, |
| 793 |
Node& startNode, |
| 794 |
Interface* startIface = NULL); |
| 795 |
|
| 796 |
// Note: The template subclass provides the "ItemFactory::CreateItem()" method |
| 797 |
|
| 798 |
// Our templates below override this one |
| 799 |
virtual Cost& AccessCostTemp() = 0; |
| 800 |
|
| 801 |
NetGraph& manet_graph; |
| 802 |
Interface* start_iface; |
| 803 |
Interface::PriorityQueue queue_pending; |
| 804 |
Interface::PriorityQueue queue_visited; |
| 805 |
|
| 806 |
// These two members support the "tree walk" BFS |
| 807 |
Interface* trans_iface; |
| 808 |
unsigned int current_level; |
| 809 |
|
| 810 |
bool dijkstra_completed; |
| 811 |
bool in_update; |
| 812 |
bool traverse_nodes; |
| 813 |
bool reset_required; |
| 814 |
}; // end class NetGraph::DijkstraTraversal |
| 815 |
|
| 816 |
|
| 817 |
// These Link and Interface Template definitions may be used by developers along |
| 818 |
// with the NetGraphTemplate definition below to build custom link/interface/graph types. |
| 819 |
template <class COST_TYPE, class IFACE_TYPE = Interface> |
| 820 |
class LinkTemplate : public Link |
| 821 |
{ |
| 822 |
public: |
| 823 |
LinkTemplate() {} |
| 824 |
virtual ~LinkTemplate() {} |
| 825 |
|
| 826 |
// required override |
| 827 |
const COST_TYPE& GetCost() const |
| 828 |
{return cost;} |
| 829 |
|
| 830 |
void SetCost(COST_TYPE& theCost) |
| 831 |
{cost = theCost;} |
| 832 |
|
| 833 |
IFACE_TYPE* GetSrc() const |
| 834 |
{return static_cast<IFACE_TYPE*>(Edge::GetSrc());} |
| 835 |
|
| 836 |
IFACE_TYPE* GetDst() const |
| 837 |
{return static_cast<IFACE_TYPE*>(Edge::GetDst());} |
| 838 |
|
| 839 |
private: |
| 840 |
virtual Cost& AccessCost() |
| 841 |
{return static_cast<Cost&>(cost);} |
| 842 |
COST_TYPE cost; |
| 843 |
|
| 844 |
}; // end class NetGraph::LinkTemplate |
| 845 |
|
| 846 |
|
| 847 |
template <class COST_TYPE, class MY_TYPE, class LINK_TYPE = Link, class NODE_TYPE = Node> |
| 848 |
class InterfaceTemplate : public Interface |
| 849 |
{ |
| 850 |
public: |
| 851 |
InterfaceTemplate(NODE_TYPE& theNode, const ProtoAddress& addr) : Interface(theNode, addr) {} |
| 852 |
InterfaceTemplate(NODE_TYPE& theNode) : Interface(theNode) {} |
| 853 |
virtual ~InterfaceTemplate() {} |
| 854 |
|
| 855 |
LINK_TYPE* GetLinkTo(const InterfaceTemplate& dst) const |
| 856 |
{return static_cast<LINK_TYPE*>(Interface::GetLinkTo(dst));} |
| 857 |
|
| 858 |
NODE_TYPE& GetNode() const |
| 859 |
{return static_cast<NODE_TYPE&>(Interface::GetNode());} |
| 860 |
|
| 861 |
const NODE_TYPE* GetNodePtr() const |
| 862 |
{return static_cast<NODE_TYPE&>(Interface::GetNodePtr());} |
| 863 |
|
| 864 |
const COST_TYPE* GetCostTo(const InterfaceTemplate& dst) const |
| 865 |
{ |
| 866 |
LINK_TYPE* link = GetLinkTo(dst); |
| 867 |
return (NULL != link) ? static_cast<const COST_TYPE*>(&(link->GetCost())) : (COST_TYPE*)NULL; |
| 868 |
} |
| 869 |
|
| 870 |
static MY_TYPE* GetSrc(Link& theLink) |
| 871 |
{return static_cast<MY_TYPE*>(theLink.GetSrc());} |
| 872 |
|
| 873 |
static MY_TYPE* GetDst(Link& theLink) |
| 874 |
{return static_cast<MY_TYPE*>(theLink.GetDst());} |
| 875 |
|
| 876 |
class SimpleList : public NetGraph::Interface::SimpleList |
| 877 |
{ |
| 878 |
public: |
| 879 |
SimpleList(ItemPool* itemPool = NULL) : NetGraph::Interface::SimpleList(itemPool) {} |
| 880 |
virtual ~SimpleList() {} |
| 881 |
|
| 882 |
MY_TYPE* GetHead() const |
| 883 |
{return static_cast<MY_TYPE*>(NetGraph::Interface::SimpleList::GetHead());} |
| 884 |
|
| 885 |
MY_TYPE* RemoveHead() |
| 886 |
{return static_cast<MY_TYPE*>(NetGraph::Interface::SimpleList::RemoveHead());} |
| 887 |
|
| 888 |
class Iterator : public NetGraph::Interface::SimpleList::Iterator |
| 889 |
{ |
| 890 |
public: |
| 891 |
Iterator(const SimpleList& theList) : NetGraph::Interface::SimpleList::Iterator(theList) {} |
| 892 |
virtual ~Iterator() {} |
| 893 |
|
| 894 |
MY_TYPE* GetNextInterface() |
| 895 |
{return static_cast<MY_TYPE*>(NetGraph::Interface::SimpleList::Iterator::GetNextInterface());} |
| 896 |
|
| 897 |
}; // end class NetGraph::InterfaceTemplate::SimpleList::Iterator |
| 898 |
|
| 899 |
}; // end class NetGraph::InterfaceTemplate::SimpleList |
| 900 |
|
| 901 |
class SortedList : public NetGraph::Interface::SortedList |
| 902 |
{ |
| 903 |
public: |
| 904 |
SortedList(ItemPool* itemPool = NULL) : NetGraph::Interface::SortedList(itemPool) {} |
| 905 |
virtual ~SortedList() {} |
| 906 |
|
| 907 |
|
| 908 |
MY_TYPE* FindInterface(const ProtoAddress& addr) const |
| 909 |
{return static_cast<MY_TYPE*>(FindVertice(addr.GetRawHostAddress(), addr.GetLength() << 3));} |
| 910 |
|
| 911 |
MY_TYPE* FindInterfaceByName(const char* name) |
| 912 |
{return static_cast<MY_TYPE*>(FindVertice(name,(strlen(name) & 0x01) ? (strlen(name) << 3) : ((strlen(name)+1) << 3)));} |
| 913 |
|
| 914 |
MY_TYPE* GetHead() const |
| 915 |
{return static_cast<MY_TYPE*>(Vertice::SortedList::GetHead());} |
| 916 |
|
| 917 |
MY_TYPE* RemoveHead() |
| 918 |
{return static_cast<MY_TYPE*>(Vertice::SortedList::RemoveHead());} |
| 919 |
|
| 920 |
class Iterator : public NetGraph::Interface::SortedList::Iterator |
| 921 |
{ |
| 922 |
public: |
| 923 |
Iterator(SortedList& theList) : NetGraph::Interface::SortedList::Iterator(theList) {} |
| 924 |
virtual ~Iterator() {} |
| 925 |
|
| 926 |
MY_TYPE* GetNextInterface() |
| 927 |
{return static_cast<MY_TYPE*>(NetGraph::Interface::SortedList::Iterator::GetNextInterface());} |
| 928 |
|
| 929 |
}; // end class NetGraph::InterfaceTemplate::SortedList::Iterator |
| 930 |
|
| 931 |
}; // end class NetGraph::InterfaceTemplate::SortedList |
| 932 |
|
| 933 |
class PriorityQueue : public NetGraph::Interface::PriorityQueue |
| 934 |
{ |
| 935 |
public: |
| 936 |
PriorityQueue() : NetGraph::Interface::PriorityQueue(builtin_item_factory) {} |
| 937 |
PriorityQueue(ItemFactory& itemFactory) : NetGraph::Interface::PriorityQueue(itemFactory) {} |
| 938 |
virtual ~PriorityQueue() {} |
| 939 |
|
| 940 |
class Item : public NetGraph::Interface::PriorityQueue::Item |
| 941 |
{ |
| 942 |
public: |
| 943 |
Item() {} |
| 944 |
virtual ~Item() {} |
| 945 |
|
| 946 |
const Cost& GetCost() const |
| 947 |
{return static_cast<const Cost&>(cost);} |
| 948 |
|
| 949 |
void SetCost(const Cost& theCost) |
| 950 |
{cost = static_cast<const COST_TYPE&>(theCost);} |
| 951 |
|
| 952 |
private: |
| 953 |
virtual Cost& AccessCost() |
| 954 |
{return static_cast<Cost&>(cost);} |
| 955 |
COST_TYPE cost; |
| 956 |
}; // end class NetGraph::PriorityQueue::Item |
| 957 |
|
| 958 |
class ItemFactory : public NetGraph::Interface::PriorityQueue::ItemFactory |
| 959 |
{ |
| 960 |
public: |
| 961 |
ItemFactory() {} |
| 962 |
virtual ~ItemFactory() {} |
| 963 |
|
| 964 |
protected: |
| 965 |
NetGraph::Interface::PriorityQueue::Item* CreateItem() const |
| 966 |
{return static_cast<NetGraph::Interface::PriorityQueue:: Item*>(new Item);} // creates new templated "Item" |
| 967 |
|
| 968 |
}; // end class NetGraph::InterfaceTemplate::PriorityQueue::ItemFactory() |
| 969 |
|
| 970 |
private: |
| 971 |
ItemFactory builtin_item_factory; |
| 972 |
|
| 973 |
}; // end class NetGraph::InterfaceTemplate::PriorityQueue |
| 974 |
|
| 975 |
}; // end class NetGraph::InterfaceTemplate |
| 976 |
|
| 977 |
template <class COST_TYPE, class NODE_TYPE = NetGraph::Node> |
| 978 |
class DefaultInterfaceTemplate : public InterfaceTemplate<COST_TYPE, NODE_TYPE, DefaultInterfaceTemplate<COST_TYPE> > |
| 979 |
{ |
| 980 |
public: |
| 981 |
DefaultInterfaceTemplate(NODE_TYPE& theNode, const ProtoAddress& addr) |
| 982 |
: InterfaceTemplate<COST_TYPE, NODE_TYPE, DefaultInterfaceTemplate>(theNode, addr) {} |
| 983 |
virtual ~DefaultInterfaceTemplate() {} |
| 984 |
}; // end class NetGraph::DefaultInterfaceTemplate |
| 985 |
|
| 986 |
|
| 987 |
template <class IFACE_TYPE = Interface, class LINK_TYPE = Link> |
| 988 |
class NodeTemplate : public Node |
| 989 |
{ |
| 990 |
public: |
| 991 |
NodeTemplate() {} |
| 992 |
virtual ~NodeTemplate() {} |
| 993 |
|
| 994 |
IFACE_TYPE* FindInterface(const ProtoAddress& addr) const |
| 995 |
{return static_cast<IFACE_TYPE*>(NetGraph::Node::FindInterface(addr));} |
| 996 |
|
| 997 |
IFACE_TYPE* FindInterfaceByName(const char* theName) |
| 998 |
{return static_cast<IFACE_TYPE*>(NetGraph::Node::FindInterfaceByName(theName));} |
| 999 |
|
| 1000 |
IFACE_TYPE* GetDefaultInterface() const |
| 1001 |
{return static_cast<IFACE_TYPE*>(NetGraph::Node::GetDefaultInterface());} |
| 1002 |
|
| 1003 |
class InterfaceIterator : public NetGraph::Node::InterfaceIterator |
| 1004 |
{ |
| 1005 |
public: |
| 1006 |
InterfaceIterator(Node& node) : NetGraph::Node::InterfaceIterator(node) {} |
| 1007 |
virtual ~InterfaceIterator() {} |
| 1008 |
|
| 1009 |
IFACE_TYPE* GetNextInterface() |
| 1010 |
{return static_cast<IFACE_TYPE*>(NetGraph::Node::InterfaceIterator::GetNextInterface());} |
| 1011 |
|
| 1012 |
}; // end class NetGraphTemplate::Node::InterfaceIterator |
| 1013 |
class NeighborIterator : public NetGraph::Node::NeighborIterator |
| 1014 |
{ |
| 1015 |
public: |
| 1016 |
NeighborIterator(Node& node) : NetGraph::Node::NeighborIterator(node) {} |
| 1017 |
virtual ~NeighborIterator() {} |
| 1018 |
|
| 1019 |
IFACE_TYPE* GetNextNeighborInterface() |
| 1020 |
{return static_cast<IFACE_TYPE*>(NetGraph::Node::NeighborIterator::GetNextNeighborInterface());} |
| 1021 |
|
| 1022 |
LINK_TYPE* GetNextNeighborLink() |
| 1023 |
{return static_cast<LINK_TYPE*>(NetGraph::Node::NeighborIterator::GetNextNeighborLink());} |
| 1024 |
}; // end class NetGraph::NodeTemplate::NeighborIterator |
| 1025 |
|
| 1026 |
}; // end class NetGraph::NodeTemplate |
| 1027 |
|
| 1028 |
|
| 1029 |
protected: |
| 1030 |
NetGraph(); |
| 1031 |
|
| 1032 |
// Netgraph::Interface calls these when adding or removing addresses |
| 1033 |
bool AddInterfaceAddress(const Interface& iface, const ProtoAddress& addr) |
| 1034 |
{return addr_list.Insert(addr, &iface);} |
| 1035 |
void RemoveInterfaceAddress(const ProtoAddress& addr) |
| 1036 |
{addr_list.Remove(addr);} |
| 1037 |
void SuspendInterface(Interface& iface) |
| 1038 |
{vertice_list.Remove(iface);} |
| 1039 |
bool ResumeInterface(Interface& iface) |
| 1040 |
{return vertice_list.Insert(iface);} |
| 1041 |
|
| 1042 |
// Our template provides a type-safe "public" override of this |
| 1043 |
Link* Connect(Interface& srcIface, Interface& dstIface, const Cost& cost); |
| 1044 |
bool Connect(Interface& srcIface, Interface& dstIface, const Cost& cost, bool duplex); |
| 1045 |
|
| 1046 |
Link* Reconnect(Interface& srcIface, Interface& dstIface, const Cost& cost); |
| 1047 |
bool Reconnect(Interface& srcIface, Interface& dstIface, const Cost& cost, bool duplex); |
| 1048 |
|
| 1049 |
private: |
| 1050 |
ProtoAddressList addr_list; // list of _all_ addresses of all contained interfaces |
| 1051 |
|
| 1052 |
}; // end class NetGraph |
| 1053 |
|
| 1054 |
|
| 1055 |
// The "NetGraph" stuff declared above are the base (interface) classes for |
| 1056 |
// actual subclasses we will derive and use. The following provides a template |
| 1057 |
// class based on the "Cost" type. This lets us easily derive different types |
| 1058 |
// of "Cost" subclasses and then derive a "NetGraph" subclass that uses that |
| 1059 |
// new "Cost" subclass for its Dijkstra, etc. Cool!, huh? |
| 1060 |
// |
| 1061 |
// Note that further below we declare a "ManetGraph" subclass as an example |
| 1062 |
// that uses the "NetGraph::SimpleCost" that was declared above. |
| 1063 |
|
| 1064 |
template <class COST_TYPE = NetGraph::SimpleCostDouble, |
| 1065 |
class IFACE_TYPE = NetGraph::DefaultInterfaceTemplate<COST_TYPE>, |
| 1066 |
class LINK_TYPE = NetGraph::LinkTemplate<COST_TYPE, IFACE_TYPE>, |
| 1067 |
class NODE_TYPE = NetGraph::NodeTemplate<IFACE_TYPE> > |
| 1068 |
class NetGraphTemplate : public NetGraph |
| 1069 |
{ |
| 1070 |
public: |
| 1071 |
NetGraphTemplate() {} |
| 1072 |
virtual ~NetGraphTemplate() {} |
| 1073 |
|
| 1074 |
// These typedefs let us use DerivedGraph::Interface and DerivedGraph::Link types that |
| 1075 |
// are synonomous with passed-in template interface/link types |
| 1076 |
typedef COST_TYPE Cost; |
| 1077 |
typedef IFACE_TYPE Interface; |
| 1078 |
typedef LINK_TYPE Link; |
| 1079 |
typedef NODE_TYPE Node; |
| 1080 |
|
| 1081 |
NODE_TYPE* FindNode(const ProtoAddress& theAddress) |
| 1082 |
{return static_cast<NODE_TYPE*>(NetGraph::FindNode(theAddress));} |
| 1083 |
|
| 1084 |
IFACE_TYPE* FindInterface(const ProtoAddress& addr) const |
| 1085 |
{return static_cast<IFACE_TYPE*>(NetGraph::FindInterface(addr));} |
| 1086 |
|
| 1087 |
IFACE_TYPE* FindInterfaceByName(const char* name) |
| 1088 |
{return static_cast<IFACE_TYPE*>(NetGraph::FindInterfaceByName(name));} |
| 1089 |
|
| 1090 |
IFACE_TYPE* FindInterfaceByString(const char* theString) |
| 1091 |
{return static_cast<IFACE_TYPE*>(NetGraph::FindInterfaceByString(theString));} |
| 1092 |
|
| 1093 |
// Note for the "SimpleTypeTemplate" and its derivatives for "double", "int", etc |
| 1094 |
// have casting/conversion operators defined that allow direct use of the |
| 1095 |
// corresponding "simple" type (i.e. "double", etc) for the "cost" argument here. |
| 1096 |
LINK_TYPE* Connect(IFACE_TYPE& srcIface, IFACE_TYPE& dstIface, const COST_TYPE& cost) |
| 1097 |
{return static_cast<LINK_TYPE*>(NetGraph::Connect(srcIface, dstIface, cost));} |
| 1098 |
|
| 1099 |
bool Connect(IFACE_TYPE& srcIface, IFACE_TYPE& dstIface, const COST_TYPE& cost, bool duplex) |
| 1100 |
{return NetGraph::Connect(srcIface, dstIface, cost, duplex);} |
| 1101 |
|
| 1102 |
LINK_TYPE* Reconnect(Interface& srcIface, Interface& dstIface, const Cost& cost) |
| 1103 |
{return static_cast<LINK_TYPE*>(NetGraph::Reconnect(srcIface, dstIface, cost));} |
| 1104 |
|
| 1105 |
bool Reconnect(IFACE_TYPE& srcIface, IFACE_TYPE& dstIface, const COST_TYPE& cost, bool duplex) |
| 1106 |
{return NetGraph::Reconnect(srcIface, dstIface, cost, duplex);} |
| 1107 |
|
| 1108 |
// TBD - provide a GetLinkList() to get list of links from "srcIface" to "dstIface" |
| 1109 |
LINK_TYPE* GetLink(IFACE_TYPE& srcIface, IFACE_TYPE& dstIface) |
| 1110 |
{return static_cast<LINK_TYPE*>(srcIface.GetLinkTo(dstIface));} |
| 1111 |
|
| 1112 |
|
| 1113 |
class AdjacencyIterator : public NetGraph::AdjacencyIterator |
| 1114 |
{ |
| 1115 |
public: |
| 1116 |
AdjacencyIterator(IFACE_TYPE& iface) : NetGraph::AdjacencyIterator(iface) {} |
| 1117 |
virtual ~AdjacencyIterator() {} |
| 1118 |
|
| 1119 |
IFACE_TYPE* GetNextAdjacency() |
| 1120 |
{return static_cast<IFACE_TYPE*>(NetGraph::AdjacencyIterator::GetNextAdjacency());} |
| 1121 |
|
| 1122 |
LINK_TYPE* GetNextAdjacencyLink() |
| 1123 |
{return static_cast<LINK_TYPE*>(NetGraph::AdjacencyIterator::GetNextAdjacencyLink());} |
| 1124 |
|
| 1125 |
IFACE_TYPE* GetNextConnector() |
| 1126 |
{return static_cast<IFACE_TYPE*>(NetGraph::AdjacencyIterator::GetNextConnector());} |
| 1127 |
|
| 1128 |
}; // end class NetGraphTemplate::AdjacencyIterator |
| 1129 |
|
| 1130 |
class InterfaceIterator : public NetGraph::InterfaceIterator |
| 1131 |
{ |
| 1132 |
public: |
| 1133 |
InterfaceIterator(NetGraphTemplate& theGraph) : NetGraph::InterfaceIterator(theGraph) {} |
| 1134 |
virtual ~InterfaceIterator() {} |
| 1135 |
|
| 1136 |
IFACE_TYPE* GetNextInterface() |
| 1137 |
{return static_cast<IFACE_TYPE*>(NetGraph::InterfaceIterator::GetNextVertice());} |
| 1138 |
|
| 1139 |
}; // end class NetGraphTemplate::InterfaceIterator |
| 1140 |
|
| 1141 |
class SimpleTraversal : public NetGraph::SimpleTraversal |
| 1142 |
{ |
| 1143 |
public: |
| 1144 |
SimpleTraversal(const NetGraphTemplate& theGraph, |
| 1145 |
IFACE_TYPE& startIface, |
| 1146 |
bool traverseNodes = true, |
| 1147 |
bool collapseNodes = true, |
| 1148 |
bool depthFirst = false) |
| 1149 |
: NetGraph::SimpleTraversal(theGraph, startIface, traverseNodes, collapseNodes, depthFirst) {} |
| 1150 |
virtual ~SimpleTraversal() {} |
| 1151 |
|
| 1152 |
IFACE_TYPE* GetNextInterface(unsigned int* level = NULL) |
| 1153 |
{return static_cast<IFACE_TYPE*>(NetGraph::SimpleTraversal::GetNextInterface(level));} |
| 1154 |
|
| 1155 |
}; // end class NetGraphTemplate::SimpleTraversal |
| 1156 |
|
| 1157 |
class DijkstraTraversal : public NetGraph::DijkstraTraversal |
| 1158 |
{ |
| 1159 |
public: |
| 1160 |
DijkstraTraversal(NetGraphTemplate& theGraph, |
| 1161 |
Node& startNode, |
| 1162 |
IFACE_TYPE* startIface = NULL) |
| 1163 |
: NetGraph::DijkstraTraversal(theGraph, startNode, startIface) |
| 1164 |
{ |
| 1165 |
Reset(); |
| 1166 |
} |
| 1167 |
|
| 1168 |
virtual ~DijkstraTraversal() {} |
| 1169 |
|
| 1170 |
IFACE_TYPE* GetNextInterface() |
| 1171 |
{return static_cast<IFACE_TYPE*>(NetGraph::DijkstraTraversal::GetNextInterface());} |
| 1172 |
|
| 1173 |
// (use these post-Dijkstra (i.e., after "GetNextInterface" returns NULL) |
| 1174 |
const COST_TYPE* GetCost(const IFACE_TYPE& iface) const |
| 1175 |
{return static_cast<const COST_TYPE*>(NetGraph::DijkstraTraversal::GetCost(iface));} |
| 1176 |
|
| 1177 |
IFACE_TYPE* GetNextHop(const IFACE_TYPE& dstIface) // from "startIface" towards "dstIface" |
| 1178 |
{return static_cast<IFACE_TYPE*>(queue_visited.GetNextHop(dstIface));} |
| 1179 |
|
| 1180 |
IFACE_TYPE* GetPrevHop(const IFACE_TYPE& dstIface) // back towards "startIface" |
| 1181 |
{return static_cast<IFACE_TYPE*>(queue_visited.GetPrevHop(dstIface));} |
| 1182 |
|
| 1183 |
// BFS traversal of routing tree ("tree walk") |
| 1184 |
IFACE_TYPE* TreeWalkNext(unsigned int* level = NULL) |
| 1185 |
{return static_cast<IFACE_TYPE*>(NetGraph::DijkstraTraversal::TreeWalkNext(level));} |
| 1186 |
|
| 1187 |
protected: |
| 1188 |
Cost& AccessCostTemp() |
| 1189 |
{return static_cast<Cost&>(cost_temp);} |
| 1190 |
|
| 1191 |
// Required override of NetGraph::Interface::PriorityQueue::ItemFactory::CreateItem() |
| 1192 |
NetGraph::Interface::PriorityQueue::Item* CreateItem() const |
| 1193 |
{return static_cast<NetGraph::Interface::PriorityQueue::Item*>(new typename IFACE_TYPE::PriorityQueue::Item);} |
| 1194 |
|
| 1195 |
COST_TYPE cost_temp; |
| 1196 |
|
| 1197 |
}; // end class NetGraphTemplate::DijkstraTraversal |
| 1198 |
|
| 1199 |
protected: |
| 1200 |
// Override of ProtoGraph::CreateEdge() |
| 1201 |
virtual Edge* CreateEdge() const |
| 1202 |
{return static_cast<Edge*>(new LINK_TYPE);} |
| 1203 |
|
| 1204 |
}; // end class NetGraphTemplate |
| 1205 |
|
| 1206 |
// TBD - Rename the above "NetGraphTemplate" -> "NetGraphBase" and then declare |
| 1207 |
// a new "NetGraphTemplate" here (using NetGraphBase) that allows users to |
| 1208 |
// provide their own Node (and Link?) derivatives as well as Cost type |
| 1209 |
// so that the proper return types are automatically provided from |
| 1210 |
// Iterators, etc ... need to think about this a little ... i.e. the "Node" |
| 1211 |
// is not a problem, but the templating of the COST_TYPE member of Link |
| 1212 |
// is problematic ... A trick might be to have Dijkstra Traversal keep |
| 1213 |
// a Link just for cost storage ... i.e. to contain the templating on |
| 1214 |
// the COST_TYPE contained in the Link?? more thought needed! |
| 1215 |
|
| 1216 |
|
| 1217 |
// And finally, here we use our "NetGraph" base class and "NetGraphTemplate" |
| 1218 |
// to generate an _example_ (but usable) "ManetGraph" class that uses the |
| 1219 |
// "NetGraph::SimpleCostDouble" type as its "cost" metric for Dijkstra, etc |
| 1220 |
/** |
| 1221 |
* @class ManetGraph |
| 1222 |
* |
| 1223 |
* @brief Derived from NetGraphTemplate using "SimpleCostDouble" as its COST_TYPE. |
| 1224 |
* Hopefully a suitable graph structure for keeping and exploring multi-hop network state. |
| 1225 |
* Supports a notion of multiple interfaces per node, etc. |
| 1226 |
*/ |
| 1227 |
|
| 1228 |
|
| 1229 |
class ManetInterface; // predeclared so it can be passed to templated ManetLink definition below |
| 1230 |
class ManetNode; // predeclared so it can be passed to templated ManetInterface definition below |
| 1231 |
|
| 1232 |
// Define a ManetLink type that uses the "SimpleCostDouble" as its cost metric |
| 1233 |
class ManetLink : public NetGraph::LinkTemplate<NetGraph::SimpleCostDouble, ManetInterface> {}; |
| 1234 |
|
| 1235 |
// Define a ManetInterface type to help "wire up" our example templated ManetGraph below |
| 1236 |
class ManetInterface : public NetGraph::InterfaceTemplate<NetGraph::SimpleCostDouble, ManetInterface, ManetLink, ManetNode> |
| 1237 |
{ |
| 1238 |
public: |
| 1239 |
ManetInterface(ManetNode& theNode, const ProtoAddress& addr) |
| 1240 |
: NetGraph::InterfaceTemplate<NetGraph::SimpleCostDouble, ManetInterface, ManetLink, ManetNode>(theNode, addr) {} |
| 1241 |
ManetInterface(ManetNode& theNode) |
| 1242 |
: NetGraph::InterfaceTemplate<NetGraph::SimpleCostDouble, ManetInterface, ManetLink, ManetNode>(theNode) {} |
| 1243 |
}; // end class ManetInterface |
| 1244 |
|
| 1245 |
// Define a "ManetNode" type that has the ManetInterface thpye |
| 1246 |
class ManetNode : public NetGraph::NodeTemplate<ManetInterface> {}; |
| 1247 |
|
| 1248 |
// Finally, declare a ManetGraph from our NetGraphTemplate |
| 1249 |
// Note this also creates ManetGraph::Interface and ManetGraph::Link typedef |
| 1250 |
// equivalents to ManetInterface/ManetLink |
| 1251 |
class ManetGraph : public NetGraphTemplate<NetGraph::SimpleCostDouble, ManetInterface, ManetLink, ManetNode> {}; |
| 1252 |
|
| 1253 |
|
| 1254 |
// Note that the following equivalent types are "nested in the ManetGraph namespace via typedef |
| 1255 |
// ManetGraph::Node == ManetNode |
| 1256 |
// ManetGraph::Interface == ManetInterface |
| 1257 |
// ManetGraph::Link == ManetLink |
| 1258 |
|
| 1259 |
|
| 1260 |
// This simple definition gives you the same sort of "default" ManetGraph |
| 1261 |
// (the above steps illustrate how to create an opportunity for custom Interface and Link classes) |
| 1262 |
// class ManetGraph : public NetGraphTemplate<> {}; |
| 1263 |
|
| 1264 |
|
| 1265 |
// |
| 1266 |
// Also, this could have been similarly (and perhaps more elegantly) done with a namespace as follows: |
| 1267 |
// |
| 1268 |
// namespace Manet |
| 1269 |
// { |
| 1270 |
// typedef NetGraph::SimpleCostDouble Cost; |
| 1271 |
// class Interface; |
| 1272 |
// class Node; |
| 1273 |
// class Link : public NetGraph::LinkTemplate<Cost, Interface> {}; |
| 1274 |
// class Interface : public NetGraph::InterfaceTemplate<Cost, Node, Interface, Link> {}; |
| 1275 |
// class Graph : public NetGraphTemplate<Cost, Node, Interface, Link> {}; |
| 1276 |
// }; // end namespace Manet |
| 1277 |
// |
| 1278 |
// This would result in Maent::Node, Manet::Interface, Manet::Link, and Manet::Graph classes |
| 1279 |
// (And equivalent Manet::Graph::Node, Manet::Graph::Interface and Manet::Graph::Link class names. |
| 1280 |
// Other elements (e.g., enums, classed, etc) could be also added to the namespace as needed) |
| 1281 |
|
| 1282 |
// To summarize, one can define their own custom "Cost", "Node", "Interface", and/or "Link" subclasses |
| 1283 |
// and then use the template to define your own custom "Graph" class made up of these elements. |
| 1284 |
// Alternatively, one could subclass from "NetGraph" directly, but the templates provide the convenience |
| 1285 |
// of iterators, etc that return proper typenames (so arduous casting is not needed) |
| 1286 |
|
| 1287 |
|
| 1288 |
#endif // _MANET_GRAPH |