Hello Folks, It’s been a long time since i posted. i had been studying the AODV routing protocol and am still trying to make it energy aware. Most of the people who are reading this post must already know about BSD linked list. This list is under the directory /ns-2.34/lib/bsd-list.h. It contains few macros for defining a doubly linked list that is used in AODV for maintaining routing tables, precursor lists, neighbor caches and Broadcast ID cache.
I searched a lot trying to understand the aodv code but the usage of bsd-list was a major hindrance in understanding it. Even after a lot of searching i could not find good material to read as it involved complex use of pointers. In the end I studied the bsd-list.h and few help from the internet I was able to relate how things are actually working. In this post I would explain the working of BSD list and how it actually works. I would not go into the inner details as the macros defined do most of the functionality themselves therefore studying them in huge detail becomes irrelevant. And yes this post would assume that you first go and read about pointers and try implementing a singly linked list and a doubly linked list on your own in C++. (Believe me that would really help).
The source files needed for this program can be downloaded from here:
Step 1) bsd-list.h contains the following macros
#define LIST_HEAD(name, type) \
struct name { \
type *lh_first; /* first element */ \
}
#define LIST_ENTRY(type) \
struct { \
type *le_next; /* next element */ \
type **le_prev; /* address of previous next element */ \
}
#define LIST_INIT(head) { \
(head)->lh_first = NULL; \
}
#define LIST_INSERT_AFTER(listelm, elm, field) { \
if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
(listelm)->field.le_next->field.le_prev = \
&(elm)->field.le_next; \
(listelm)->field.le_next = (elm); \
(elm)->field.le_prev = &(listelm)->field.le_next; \
}
#define LIST_INSERT_BEFORE(listelm, elm, field) { \
(elm)->field.le_prev = (listelm)->field.le_prev; \
(elm)->field.le_next = (listelm); \
*(listelm)->field.le_prev = (elm); \
(listelm)->field.le_prev = &(elm)->field.le_next; \
}
#define LIST_INSERT_HEAD(head, elm, field) { \
if (((elm)->field.le_next = (head)->lh_first) != NULL) \
(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
(head)->lh_first = (elm); \
(elm)->field.le_prev = &(head)->lh_first; \
}
#define LIST_REMOVE(elm, field) { \
if ((elm)->field.le_next != NULL) \
(elm)->field.le_next->field.le_prev = \
(elm)->field.le_prev; \
*(elm)->field.le_prev = (elm)->field.le_next; \
}
Now i will give a certain example to understand the working of the above bsd-list.
Step 2) First of all create a .cpp file with the name workingbsdlist.cpp and inside the same directory copy the file bsd-list.h from /ns-2.34/lib/bsd-list.h directory.
The code for workingbsdlist.cpp is as follows (u can always copy paste)
#include
#include
#include"bsd-list.h"
using namespace std;
struct foo {
int a;
LIST_ENTRY(foo) pointers; // pointers is the object of the structure generated by List Entry
}*temp, *var, *ptr;
LIST_HEAD(foo_list, foo);
int main(void)
{
LIST_HEAD(foo_list, foo) head;
LIST_INIT(&head);
struct foo *item1 = new foo;
struct foo *item2 = new foo;
struct foo *item3 = new foo;
item1->a = 60;
item2->a = 120;
item3->a = 240;
LIST_INSERT_HEAD(&head, item1, pointers);
LIST_INSERT_AFTER(item1, item2, pointers);
LIST_INSERT_BEFORE(item2, item3, pointers);
//Displaying inner details of list
{
cout<<"HEAD's Address : "<<head.lh_first<<endl;
cout<<"Item 1 next value : "<pointers.le_next<<endl;
cout<<"Item 1 prev value : "<pointers.le_prev<<endl;
cout<<"HEAD's Address : "<<head.lh_first<<endl;
cout<<"Item 2 next value : "<pointers.le_next<<endl;
cout<<"Item 2 prev value : "<pointers.le_prev<<endl;
cout<<"HEAD's Address : "<<head.lh_first<<endl;
cout<<"Item 3 next value : "<pointers.le_next<<endl;
cout<<"Item 3 prev value : "<pointers.le_prev<pointers.le_next)
{
cout<a<<endl;
}
return (0);
}
Although the above example may be quite vague and non-coherent but it is good for an intermediate C++ programmer to learn.
Step 3) Now i shall explain each and every line of this program and how it uses the bsd-list.h header file to create a doubly linked list. Once u understand this it becomes very easy to understand code in aodv.cc
Firstly we create a structure named as foo and within it we declare a variable a.
Within the structure we call the macro using
LIST_ENTRY(foo) pointers;
Seeing the macro in bsd-list.h. This expands to the following (keep watching closely)
struct foo {
int a;
struct { // This is a nameless structure within a structure
struct foo *le_next; // pointer to structure foo
struct foo **le_prev; // pointer to a pointer that points to structure foo
} pointers; // structure variable of nameless structure
}*temp, *var, *ptr; // pointers to structure foo
Then we call the another macro in bsd-list.h as:
LIST_HEAD(foo_list, foo);
This expands to the following code:
struct foo_list // A new structure with the name foo_list that holds pointer to struct foo
{
foo *lh_first; //pointer to struct foo
}
Now in the main() function we call the same macro LIST_HEAD but this time an variable is also created for the structure foo_list. See below.
LIST_HEAD(foo_list, foo) head;
expands to
struct foo_list // A new structure with the name foo_list that holds pointer to struct foo
{
foo *lh_first; //pointer to struct foo
}head;
In the next statement another macro is called
LIST_INIT(&head);
This macro call expands to
(head)->lh_first = NULL;
This is same as head->lh_first = NULL, and it puts the value of the pointer lh_first to NULL. But see one thing the *lh_first is declared inside struct foo_list so it can only be accessed by variables of foo_list. Thus we can access it using head. Thus we write head->lh_first = NULL. This also means that the head element currently will point to NULL.
Next we declare 3 generate 3 new nodes item1, item2, item3 which are actually pointers to struct foo. We enter info in their variable a using item1->a = 60; etc.
Now we shall use the three macros that actually define the insertion operations. U do not need to study the internal details of these three macros. They shall do as they say. For example
The first macro we use is to insert at the head of the list.
LIST_INSERT_HEAD(&head, item1, pointers);
seeing this macro in bsd-list.h we have
#define LIST_INSERT_HEAD(head, elm, field)
This macro takes three arguments
1. address of head (remember that head initially points to nothing because we set its value to NULL initially).
2. node that you want to insert (item1, item2, item3 etc).
3. field which is structure variable of the nameless structure that resulted on macro expansion
The other two items are after and before that are defined in bsd-list.h as
#define LIST_INSERT_AFTER(listelm, elm, field) {....}
#define LIST_INSERT_BEFORE(listelm, elm, field) {....}
They take three arguments.
1. First argument is the listelm after or before which u want to insert.
2. Node which u want to insert such as item1, item2 etc.
3. field which is a structure variable of nameless structure defined above (pointers in our ex)
Similarly the remove macro. It becomes very easy to use and understand if above two are clear.
Then we display some inner details of the list and variables. Usually to see how addresses are used and nodes are referenced. What values are stored in next and prev. What are their addresses. Have we achieved success.
In the end we print all the elements of the list. This is a tricky for loop to understand and is quite different from the conventional method. Remember this for loop can be written in two ways. I shall explain both of them so that u do not face any difficulty when u see them in AODV code in ns-2.34.
1st One)
ptr = head.lh_first;
for(;;ptr = ptr->pointers.le_next)
{
cout<a<<endl;
}
First ptr is a pointer to struct foo. We want it to point to head of the list. And head is pointed to by lh_first. So we make it point using ptr = head.lh_first. (u should understand why we used head.lh_first).
This for loop will check for ptr is not equal to NULL and it will be incremented every time by
ptr = ptr->pointers.le_next.
Remember ptr is pointer variable of struct foo. And by definition we will have to use -> sign to access le_next. But le_next is inside a nameless structure whose variable is pointers.
Thus we write ptr = ptr->pointers.le_next.
2nd One) It is similar to earlier one except
for(;ptr;ptr = ptr->pointers.le_next)
This is one more method to access or traverse the list. This will check till ptr has a valid value or not.
Hope u understand this. And if any queries arise please feel free to ask.
Note:- These are my own views and I am not a professional C++ programmer. Some things may have totally different interpretations when seen by different experienced programmers. If i am wrong somewhere please correct it and accept my apologies.
Researching Wirelessly 