How to use list from sys/queue.h?

Question

Currently, I have implemented a singly linked list, like so:

struct PeerNode {
     struct Peer* cargo;
     struct PeerNode* next;
};

...and I have a struct that contains a couple of these linked lists, like so:

struct Torrent {
     ...
     struct PeerNode* peer_list;
     struct PeerNode* unchoked_peers;
     ...
}

I would like to replace this by using the macros provided by sys/queue.h. I gather that I could replace my code with something like this:

struct Torrent {
     ...
     LIST_ENTRY(PeerNode, Peer) peer_list;
     struct PeerNode* unchoked_peers;
     ...
}

Then, from looking at man queue, I believe I would initialize the lists by doing something like this:

LIST_INIT(&peer_list);
LIST_INIT(unchoked_peers);

However, I don't understand how LIST_ENTRY factors into usage of the list. From the man page, it says: "The macro LIST_ENTRY declares a structure that connects the elements in the list," but I don't really understand what this means.

Why would I want to declare a structure to connect the elements in the list? Shouldn't each node be connected to the next node via a pointer, like my initial linked list implementation? How would I replace my linked lists with the implementation provided by sys/queue.h? How would I insert an element into the list?

Failsafe

Answer 1

LIST_ENTRY creates fields to put into your structure that are suitable for linking the elements, so you do not have to concern yourself with the specifics of those pointers.

struct foo {
    int a, b, c;
    /* This is instead of "struct foo *next" */
    LIST_ENTRY(foo) pointers;
};

To then create a list you'd use LIST_HEAD():

struct Torrent {
    LIST_HEAD(foo_list, foo) bar;
};

You can initialise the list header using LIST_INIT():

struct Torrent t;
LIST_INIT(&t.bar);

You can insert elements using the LIST_INSERT_*() macros:

struct foo *item = malloc(sizeof(struct foo));
LIST_INSERT_HEAD(&t.bar, item, pointers);

This was all taken from the list example in the man pages at http://www.manpagez.com/man/3/queue/

For a full example: http://infnis.wikidot.com/list-from-sys-queue-h

Plastic

Hi, I'm looking for a comprehensive usage example for queue based on <sys/queue.h> and it seems like the example link is no longer valid .. perhaps do you have an alternate Link ? – Kabob

Answer 2

try to use the man instruction:

man queue

Or this site

Endamoeba

Although @Plastic has already linked the manual page, this can be a nice answer if you add some text from inside the manual page, or even provide an example, instead of just a link. – Dissyllable

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Mares