Why BSD queue.h LIST called a list?

Question

My "mothertongue" is Java, and I need to write a project in C in educational purposes. I try to understand the queue.h library. In Java by default you add() an item to the end of the List, however in queue.hthere is only LIST_INSERT_HEAD macro that doesn't accept other members. In fact, a small test shows that it inserts to the HEAD (when traversing with LIST_FOREACH it goes from the last inserted element to the first). So, doen't this should be called FILO queue (that means a stack)?

Answer 1

List in Java corresponds to the List ADT: "an ordered sequence of values, where the same value may occur more than once".

LIST in queue.h is also a List ADT, in which you can see the implementation details (it is implemented as a doubly linked list). It is LIFO, as the very queue.h file states (though quite murkily). And yes, one way to implement a Stack ADT is by using a linked list.

Answer 2

You should have missed others, INSERT_TAIL must be present. Kindly do a find and confirm that.

It has both the functionalities, list and queue :)

May be the below, is not the one, you are looking, anyway http://bxr.su/o/queue.h

Answer 3

There are a number of queue options provided by queue.h.

Since this is all done by the pre-processor, and, also note that the full path of the file is src/sys/sys/queue.h on every BSD system, meaning that it's heavily used within the kernel for internal structures, each variant is highly optimised for efficiency and lowest memory footprint.

On OpenBSD, it appears that there are a couple of choices for queues to choose from (each BSD system may have a slightly different selection here):

• http://bxr.su/o/queue.h#SLIST_HEAD
• http://bxr.su/o/queue.h#LIST_HEAD
• http://bxr.su/o/queue.h#SIMPLEQ_HEAD
• http://bxr.su/o/queue.h#XSIMPLEQ_HEAD*
• http://bxr.su/o/queue.h#TAILQ_HEAD
• http://bxr.su/o/queue.h#CIRCLEQ_HEAD*

* For whichever reason, it appears that presently only 4 out of the 6 choices are officially documented in the manual page. See: http://bxr.su/o/share/man/man3/queue.3

If you want to be able to INSERT_TAIL into the queue/list, you still do have a lot of options to choose from here -- SIMPLEQ, XSIMPLEQ, TAILQ and CIRCLEQ.

So, in summary: there's no law that says that a queue/list implementation by the name LIST has to allow tail insertion!