17.3.1 Use of linked lists

Figure 17.4: Linked list implementation in ns.

There are a number of linked lists used heavily in the implementation:

• class Node maintains a (static) list of all objects of class Node in the simulator. The variable Node::nodehead_ stores the head of the list. The linked list of nodes is used for centralized routing, for finding satellites to hand off to, and for tracing.

• class Node maintains a list of all (satellite) links on the node. Specifically, the list is a list of objects of class LinkHead. The variable linklisthead_ stores the head of the list. The linked list of LinkHeads is used for checking whether or not to handoff links, and to discover topology adjacencies.

• class Channel maintains a list of all objects of class Phy on the channel. The head of the list is stored in the variable if_head_. This list is used to determine the set of interfaces on a channel that should receive a copy of a packet.

Figure 17.4 provides a schematic of how the linked list is organized. Each object in the list is linked through a ``LINK_ENTRY'' that is a protected member of the class. This entry contains a pointer to the next item in the list and also a pointer to the address of the previous ``next'' pointer in the preceding object. Various macros found in ~ns/list.h can be used to manipulate the list; the implementation of linked-lists in ns is similar to the queue implementation found in some variants of BSD UNIX.