queue(3) macros for linked lists

Dear students and aspiring C programmers,

This is applicable even to C coders with a decade of experience.

All of us know that linked lists form the most important data
structure/building block in coding/design.

The kernel is full of linked list manipulations. Take the TCP/IP stack
for instance. All the packet queues are implemented using linked lists.

Issues like appending, deleting, reordering and so on occur all the
time.

And our IT industry is never tired of asking interview questions like

"How to reverse a linked list?"

Anyway I have been fortunate enough not to wrack my brains designing
doubly linked lists and solve other complex problems using linked lists.
For instance how to build an AVL tree of a red black tree using lists?

To answer all that nowadays we have queue(3) macros

You can find the implementation in /usr/include/sys/queue.h.

And using them is really trivial. ;)

Here is an example code attached.

And you can find the man page here.

http://sirsasana.org/misc/queue.pdf

-Girish

#include <stdio.h>
#include <unistd.h>
#include <sys/queue.h>

struct lines {
	char line[512];
	LIST_ENTRY(lines) next;
};

LIST_HEAD(, lines) linesh;

char po[] = "This is a long line\nThis is a short line\nand this is the third line";

int
print_lines()
{
	struct lines *tmp;

	LIST_FOREACH(tmp, &linesh, next)
		printf("[%s]\n", tmp->line);

}

int
girish_remove(struct lines *foo)
{
	LIST_REMOVE(foo, next);
	free(foo);

}
int
free_list()
{
	 while (!LIST_EMPTY(&linesh))
		girish_remove(LIST_FIRST(&linesh));
}

int 
main() 
{
	char *p1, *p2, *ba;
	LIST_INIT(&linesh);
	struct lines *boo, *tmp;

	ba = strdup(po);
	for (;;) {
		
		p2 = strsep(&ba, "\n");
		if (p2 == NULL)
			break;

		boo = (struct lines *)malloc(sizeof(struct lines));
		
		strlcpy(boo->line, p2, sizeof(boo->line));
		LIST_INSERT_HEAD(&linesh, boo, next);
	}

	print_lines();
	
	free_list();

	if (LIST_EMPTY(&linesh))
		printf("List is really empty ;)\n");
	boo = NULL;
	tmp = LIST_NEXT(boo, next);
		
}

_______________________________________________
To unsubscribe, email ilugc-request@... with 
"unsubscribe <password> <address>"
in the subject or body of the message.  
http://www.ae.iitm.ac.in/mailman/listinfo/ilugc