Advanced Search

Log In | Not a Member? Contact ADC

Queues

As part of its BSD infrastructure, the Mac OS X kernel provides a number of basic support macros to simplify handling of linked lists and queues. These are implemented as C macros, and assume a standard C struct. As such, they are probably not suited for writing code in C++.

The basic types of lists and queues included are

• SLIST, a singly linked list

• STAILQ, a singly linked tail queue

• LIST, a doubly linked list

• TAILQ, a doubly linked tail queue

SLIST is ideal for creating stacks or for handling large sets of data with few or no removals. Arbitrary removal, however, requires an O(n) traversal of the list.

STAILQ is similar to SLIST except that it maintains pointers to both ends of the queue. This makes it ideal for simple FIFO queues by adding entries at the tail and fetching entries from the head. Like SLIST, it is inefficient to remove arbitrary elements.

LIST is a doubly linked version of SLIST. The extra pointers require additional space, but allow O(1) (constant time) removal of arbitrary elements and bidirectional traversal.

TAILQ is a doubly linked version of STAILQ. Like LIST, the extra pointers require additional space, but allow O(1) (constant time) removal of arbitrary elements and bidirectional traversal.

Because their functionality is relatively simple, their use is equally straightforward. These macros can be found in xnu/bsd/sys/queue.h.

Did this document help you? Yes: Tell us what works for you. It’s good, but: Report typos, inaccuracies, and so forth. It wasn’t helpful: Tell us what would have helped.

	Get information on Apple products. Visit the Apple Store online or at retail locations. 1-800-MY-APPLE Copyright © 2007 Apple Inc. All rights reserved. | Terms of use | Privacy Notice