|
|
| |
|
|
|
Queue Management Utility Functions
21.1 Overview
This chapter defines queue management utility functions.
21.2 Queue Management
The queuing interfaces are designed using macros built on top of two basic functional interfaces in order to provide a high-performance and fully functional set of queue management interfaces. The interfaces are provided for the convenience of the UDI driver writer for driver-internal queuing. The driver may design its own internal queuing routines and algorithms, but it is recommended that, where applicable, the driver use these interfaces as a high-performance standard queuing interface. It is expected that the interfaces provided here will serve several common queuing needs in UDI drivers, helping ease driver development effort.
21.2.1 Queue Element Structure
The queues defined in UDI are circular doubly-linked lists that are linked together via udi_queue_t structures (known as queue elements) as depicted in Figure 21-1
.A UDI queue is composed of a list head element and zero or more queue elements. The queue is referred to via the list head, which is the only permanent piece of memory associated with a given queue: an empty queue is composed of a list head linked to itself. UDI drivers will typically instantiate internal queues in their region data area or channel contexts by placing udi_queue_t list head structures in their region contexts, and calling UDI_QUEUE_INIT on each queue before operating on it.
Additional UDI queue terminology: "head of queue" and "first element in queue" are equivalent and refer to the element immediately following the list head. Similarly for "tail of queue" and "last element in queue," which refer to the element immediately preceding the list head.
NAME udi_queue_t
Queue element structure
#include <udi.h>MEMBERS next is a pointer to the next element in the queue.
prev is a pointer to the previous element in the queue.
DESCRIPTION The udi_queue_t structure is the queue element structure. UDI queues are linked together via these structures. The list head used to reference a particular queue is also a structure of this type, and is the only permanent piece of memory associated with a given queue.
21.2.2 Queuing Functions
There are two queuing functions defined in UDI that provide high-performance basic queuing and dequeuing functionality: udi_enqueue, which inserts a specified element at the head of the specified queue, and udi_dequeue, which removes the specified element from the queue. The macros that follow build on top of these two functions to provide a rich set of queue management utilities.
NAME udi_enqueue
Insert a queue element into a queue
#include <udi.h>ARGUMENTS new_el is a pointer to a queue element.
old_el is a pointer to the queue's list head or an element already on the queue.
DESCRIPTION udi_enqueue inserts new_el after old_el in the queue to which old_el belongs.
udi_enqueue shall be equivalent to the following implementation:
void udi_enqueue( udi_queue_t *new_el, udi_queue_t *old_el) { new_el->next = old_el->next; new_el->prev = old_el; old_el->next->prev = new_el; old_el->next = new_el; }REFERENCES udi_dequeue, udi_queue_t
NAME udi_dequeue
Dequeue a queue element
#include <udi.h>ARGUMENTS element is a pointer to a queue element
DESCRIPTION udi_dequeue removes element from its queue and returns it in the function return. The specified element must be linked into a UDI queue at the time udi_dequeue is called, and must not be the list head.
The next and prev fields of element are not modified.
udi_dequeue shall be equivalent to the following implementation:
udi_queue_t *udi_dequeue( udi_queue_t *element) { element->next->prev = element->prev; element->prev->next = element->next; return element; }RETURN VALUES The element passed in is returned.
REFERENCES udi_enqueue, udi_queue_t
21.2.3 Queuing Macros
The macros defined in this section are general queue management macros used for the queuing of arbitrary structures linked together via embedded udi_queue_t structures. The behavior is indeterminate if the listhead passed to any of these macros other than UDI_QUEUE_INIT has not been previously initialized with UDI_QUEUE_INIT, or if the element or old_el parameter passed to any of the macros other than UDI_ENQUEUE_HEAD/TAIL and UDI_QUEUE_FOREACH is not currently linked into a UDI queue.
NAME UDI_QUEUE_INIT,
Initialize queue; check if it's empty
UDI_QUEUE_EMPTY
#include <udi.h>#define UDI_QUEUE_INIT(listhead) \ ((listhead)->next = (listhead)->prev =(listhead)) #define UDI_QUEUE_EMPTY(listhead) \ ((listhead)->next == (listhead))ARGUMENTS listhead is a pointer to a list head element.
DESCRIPTION UDI_QUEUE_INIT initializes the queue's list head and must be called before any other operations are performed on the queue.
UDI_QUEUE_EMPTY is used to determine if the queue specified by listhead is empty, based on the boolean return value (non-zero if empty; zero if non-empty).
These macros must be called as if they, respectively, had the following functional interfaces:
void UDI_QUEUE_INIT ( udi_queue_t *listhead ); udi_boolean_t UDI_QUEUE_EMPTY ( udi_queue_t *listhead );NAME UDI_ENQUEUE_XXX,
Insert an element into a queue
UDI_QUEUE_INSERT_XXX
#include <udi.h>#define UDI_ENQUEUE_HEAD(listhead, element) \ udi_enqueue(element, listhead) #define UDI_ENQUEUE_TAIL(listhead, element) \ udi_enqueue(element, (listhead)->prev) #define UDI_QUEUE_INSERT_AFTER(old_el, new_el) \ udi_enqueue(new_el, old_el) #define UDI_QUEUE_INSERT_BEFORE(old_el, new_el) \ udi_enqueue(new_el, (old_el)->prev)ARGUMENTS listhead is a pointer to a list head element.
element is a pointer to a queue element.
old_el is a pointer to a queue element that is currently linked into a UDI queue.
new_el is a pointer to a queue element that is not currently linked into a UDI queue.
DESCRIPTION UDI_ENQUEUE_HEAD inserts element at the head of the queue specified by listhead. This macro is equivalent to the udi_enqueue function.
UDI_ENQUEUE_TAIL appends element to the tail of the queue specified by listhead.
UDI_QUEUE_INSERT_AFTER inserts the queue element new_el after the element old_el.
UDI_QUEUE_INSERT_BEFORE inserts the queue element new_el in front of the element old_el.
These macros must be called as if they, respectively, had the following functional interfaces:
void UDI_ENQUEUE_HEAD ( udi_queue_t *listhead, udi_queue_t *element ); void UDI_ENQUEUE_TAIL ( udi_queue_t *listhead, udi_queue_t *element ); void UDI_QUEUE_INSERT_AFTER ( udi_queue_t *old_el, udi_queue_t *new_el ); void UDI_QUEUE_INSERT_BEFORE ( udi_queue_t *old_el, udi_queue_t *new_el );NAME UDI_DEQUEUE_XXX,
Remove an element from a queue
UDI_QUEUE_REMOVE
#include <udi.h>#define UDI_DEQUEUE_HEAD(listhead) \ udi_dequeue((listhead)->next) #define UDI_DEQUEUE_TAIL(listhead) \ udi_dequeue((listhead)->prev) #define UDI_QUEUE_REMOVE(element) \ ((void)udi_dequeue(element))ARGUMENTS listhead is a pointer to a list head element.
element is a pointer to a queue element.
DESCRIPTION UDI_DEQUEUE_HEAD removes the element at the head of the queue specified by listhead, and returns it to the caller.
UDI_DEQUEUE_TAIL removes the element at the tail of the queue specified by listhead, and returns it to the caller.
UDI_QUEUE_REMOVE removes element from its queue. With the exception that there is no return value, this macro is equivalent to the udi_dequeue function. Since the caller is specifying the element to remove, it is expected that normal usage would be to call this macro without expecting a return value, so the function return is voided out.
These macros must be called as if they, respectively, had the following functional interfaces:
udi_queue_t *UDI_DEQUEUE_HEAD ( udi_queue_t *listhead ); udi_queue_t *UDI_DEQUEUE_TAIL ( udi_queue_t *listhead ); void UDI_QUEUE_REMOVE ( udi_queue_t *element );NAME UDI_FIRST/ LAST/
Get first/last/next/previous element in queue
NEXT/ PREV_ELEMENT
#include <udi.h>#define UDI_FIRST_ELEMENT(listhead) \ ((listhead)->next) #define UDI_LAST_ELEMENT(listhead) \ ((listhead)->prev) #define UDI_NEXT_ELEMENT(element) \ ((element)->next) #define UDI_PREV_ELEMENT(element) \ ((element)->prev)ARGUMENTS listhead is a pointer to a list head element.
element is a pointer to a queue element.
DESCRIPTION UDI_FIRST_ELEMENT returns a pointer to the first element in the queue specified by listhead.
UDI_LAST_ELEMENT returns a pointer to the last element in the queue specified by listhead.
UDI_NEXT_ELEMENT returns a pointer to the next queue element immediately after element.
UDI_PREV_ELEMENT returns a pointer to the queue element immediately preceding element.
These macros must be called as if they, respectively, had the following functional interface:
udi_queue_t *UDI_FIRST_ELEMENT ( udi_queue_t *listhead ); udi_queue_t *UDI_LAST_ELEMENT ( udi_queue_t *listhead ); udi_queue_t *UDI_NEXT_ELEMENT ( udi_queue_t *element ); udi_queue_t *UDI_PREV_ELEMENT ( udi_queue_t *element );NAME UDI_QUEUE_FOREACH
Safe mechanism to walk a queue
#include <udi.h>#define UDI_QUEUE_FOREACH(listhead, element, tmp) \ for ((element) = UDI_FIRST_ELEMENT(listhead); \ ((tmp) = UDI_NEXT_ELEMENT(element)), \ ((element) != (listhead)); \ (element) = (tmp)))ARGUMENTS listhead is a pointer to a list head element.
element is a queue element pointer variable that may be uninitialized on entry, and is set successively to each element in the queue.
tmp is a queue element pointer variable for temporary storage in the loop.
DESCRIPTION UDI_QUEUE_FOREACH walks through the elements in the queue specified by listhead, setting element successively to each element in the queue, beginning at the head and continuing to the tail of the queue. This provides a safe mechanism to walk through each element in a queue, and do operations on each element (including removing it from the queue and re-queuing it in another queue) without affecting the traversal to the next element in the queue.
The UDI_QUEUE_FOREACH macro produces an iteration (loop) statement and hence must be followed by a C statement which is the action to take for each iteration through the loop (e.g., an action on each element in the queue). The parameters to this macro must have the following type definitions:
UDI_QUEUE_FOREACH ( udi_queue_t *listhead, udi_queue_t *element, udi_queue_t *tmp );EXAMPLES The following code reverses the elements in a queue:
{ udi_queue_t *elem, *tmp; udi_queue_t *head = ®ion_data->my_queue; UDI_QUEUE_FOREACH(head,elem,tmp) { UDI_ENQUEUE_HEAD(udi_dequeue(elem)) } }NAME UDI_BASE_STRUCT
Find base of structure from pointer to member
#include <udi.h>#define UDI_BASE_STRUCT( \ memberp, struct_type, member_name) \ ((struct_type *)((char *)(memberp) - \ offsetof(struct_type, member_name)))ARGUMENTS memberp is a pointer to a member of a structure.
struct_type is the ISO C data type of the structure.
member_name is the name of the member within the structure.
DESCRIPTION UDI_BASE_STRUCT takes a pointer to a structure member, memberp, and returns a point to the base of the structure.
This has general utility beyond queueing, but is particularly useful with the queueing utilities, when a udi_queue_t is embedded beyond the first member of a structure.
return value This macro returns a pointer to the base of the structure, of type (struct_type *).
| |
|
|
|