This file includes 4 data-structures..

Insteresting because they are written in 1994.. to make it easier using the structures..

LIST:

the common usage of the structures is to create a structure containing the list-entry as manage-tools of its pointers, this structure might contain prev|next pointers.

Then to create a header of the specific data-structure.. this header contains only 1 pointer pointing to the first struct of the data-structure..

then the pointed struct‘s next pointer is pointing to the next struct of the list, or null, the prev pointer is pointing to the previous pointer‘s address.

so this kind of design has its problem: cannot know if it‘s the first struct of this structure, even do not know if it has a prev pointer.. and actually cannot traverse backward..

As i forseen, this kind of design can back-traverse, but in other way like using methods like container_of(le_prev,type). though no macros in queue.h can do this. As the document says, it‘s a list may only be traversed in forward direction.

this doubly linked list has its fast insertion in the middle of the list, if buildt a hash table for all the **prev address and their entries. O(1).

the usages:

Learning BSD.sys/queue.h