Please consider a donation to the Higher Intellect project. See https://preterhuman.net/donate.php or the Donate to Higher Intellect page for more info.

Queue Utilities

From Higher Intellect Vintage Wiki
Jump to navigation Jump to search

The Macintosh Operating System stores some of the information it uses in data structures called queues. The Queue Utilities allow you to manipulate those queues directly by adding and removing elements.

Ordinarily, you do not need to use the Queue Utilities. The Operating System itself is responsible for managing the various operating-system queues that it creates internally, and you should manipulate those queues only indirectly. For example, to add an element to the notification queue maintained by the Notification Manager, you should call the NMInstall function. To remove an element from that queue, you should call the NMRemove function. But if you discover some unusual need for adding or removing such elements directly, you can use the Queue Utilities routines. In addition, you can use the Queue Utilities routines for directly manipulating queues that you create.

About Queues

The Macintosh Operating System uses operating-system queues to keep track of a wide variety of items, including VBL tasks, notifications, I/O requests, events, mounted volumes, and disk drives (or other block-formatted devices). A queue is a list of identically structured entries linked together by pointers. A single entry in a queue is called a queue element.

The addresses of the first and last elements in the queue are stored in a queue header. The queue header also contains some queue flags, which contain information about the queue.

Each queue element contains the address of the next element in the queue (or the value NIL if there is no next element), an indication of the type of queue to which the next element belongs, and some data. The exact format and size of the data differs among the various queue types. In some cases, the data in the queue element contains the address of a routine to be executed.

The Queue Header

The queue header is the head of a list of identically structured entries linked together by pointers.

A queue header is a record defined by a data structure of type QHdr, which contains three fields: flags, a pointer to the first element in the queue (qHead), and a pointer to the last element in the queue (qTail). The flags field contains information specific to each queue. Ordinarily, these flags are for use by the system software only, and your application should not need to read or manipulate these flags. The qHead field is a pointer to the first element in a queue, and the qTail field is a pointer to the last element in a queue. If the queue has no elements, both of these fields are set to NIL. Thus, if you have access to a variable myQueueHdr of type QHdrPtr, you can access the corresponding first queue element of a non-empty queue with myQueueHdr^.qHead^ and access the last element with myQueueHdr^.qTail^.

Each queue element itself is a record of type QElem, which is described in the next section.

The Queue Element

The exact format of a queue element is not the same for all types of operating-system queues; thus, a queue element is defined by a variant record that is a data structure of type QElem.

Each queue element contains two fixed fields: a pointer to the next element in the queue (qLink), a value describing the queue type (qType), and a variable data field specific to each queue type.

The qLink field contains a pointer to the next element in the queue. All queue elements are linked through these pointers. Each pointer points to the qLink field in the next queue element, and the last queue element contains a NIL pointer. The data type of the pointer to the next queue element is always QElemPtr.

The qType field contains an integer that usually designates the queue type; for example, ORD(evType) for the event queue.

Often, you need to set the qType field of a queue element to an appropriate value before installing the queue element. However, some operating-system queues use this field for different purposes. For example, the Time Manager uses an operating-system queue to track Time Manager tasks. In the high bit of this field, the revised Time Manager places a flag to indicate whether a task timer is active. The Time Manager (along with other parts of the Operating System that use this field for their own purposes) shields you from the implementation-level details of operating a queue. Indeed, there is no way for you to access a Time Manager queue directly, and the QElem data type does not support access of Time Manager task records from Time Manager queue elements.

The third field contains data that is specific to the type of operating-system queue to which the queue element belongs. For example, a queue element in a vertical retrace queue, maintained by the Vertical Retrace Manager, includes information about the task procedure to be called, the number of interrupts, and the task phase. A queue element in a notification queue, maintained by the Notification Manager, includes information about the alert box, the sound response, the item to be marked in the Application menu, a response procedure, and some reserved values.

An element of type vType (a vertical retrace queue element) uses 10 bytes for VBL-specific data, whereas an element of type nmType (a notification queue element) uses 30 bytes for notification-specific data. All operating-system queue elements use at least 6 bytes: 4 bytes to store a pointer to the next element in the queue and 2 bytes to store a value indicating the queue type.

Routines

The Queue Utilities provide two routines: Enqueue and Dequeue. The Enqueue procedure allows you to add queue elements directly to an operating-system queue, and the Dequeue function allows you to remove the element. Ordinarily, these routines are used only by system software. If possible, you should manipulate an operating-system queue indirectly, by calling special-purpose routines. For example, to install a task record into a slot-based vertical retrace queue, your application should use the SlotVInstall function (provided by the Vertical Retrace Manager) instead of the Enqueue procedure. In addition, you can use the Queue Utilities routines for directly manipulating queues that you create.

See Also