Queue Module (QU_)

    #include "queue.h"

    typedef struct QU_Elem {    
        Ptr next;  
        Ptr prev;
    } QU_Elem;

    typedef struct QU_Head {
        Ptr first;
        Ptr last;
    } QU_Head;

    QU_init(QU_Elem *q);

    QU_insert(QU_Elem *q1, QU_Elem *q2);

    QU_remove(QU_Elem *q);

    QU_move(QU_Elem *q1, QU_Elem *q2);

    QU_HEAD

    QU_ELEMENT

    QU_INIT(p)

    QU_INSERT(pInsertThisElement, pInFrontOfThisElement)

    QU_PREPEND(pInsertThisElement, pAtBeginOfThisQueue)

    QU_APPEND(pInsertThisElement, pAtEndOfThisQueue)

    QU_REMOVE(p)

    QU_MOVE(pMoveMe, pBeforeThisElement)

    QU_FIRST(p)

    QU_LAST(p)

    QU_NEXT(p)

    QU_PREV(p)

    QU_EQUAL(p1, p2)

QU_ facilities provide a uniform mechanism for manipulation of doubly linked circular lists. A queue is a circular doubly linked list. Queues are often used for implementation of sequences and sets. A queue entry is linked to the next by a pair of pointers. The first pointer (next) is the forward link. It specifies the location of the succeeding entry. The second pointer (prev) is the backward link, it specifies the location of the preceding entry.

A queue is specified by a queue header (QU_Head). Structure of queue header is same as queue element (two pointers). The forward link of the header (first) is called head of the queue. The backward link of the header (last) is called the tail of the queue.

IMPORTANT NOTE 1:

Make no assumptions about the structure of this type. It may change in the future. All manipulation of queue elements must be accomplished solely by the functions in this queue module.

(As an example, if this code is ever moved into a multi-threading environment, some elements may be added to the header, for mutual exclusion while manipulating the queue pointers.)

IMPORTANT NOTE 2:

Do not declare queue pointers in your own structures. Instead, declare the first element of your structures as either QU_ELEMENT or QU_HEAD. No variable name is necessary.

Two basic operations can be performed on queues: insertion of entries and removal of entries.

QU_ facilities are not protected against asynchronous preemption and should not be used when asynchronous preemption can result into inconsistencies. SF_quInsert and SF_quRemove are expected to be atomic (non-preemptable during the entire operation).

QU_init, QU_insert, QU_remove and QU_move all operate on an abstract data type "QU_Elem". Objects that queue management facilities manipulate are expected to be data types that allow for a QU_Elem to be casted over them.

QU_init initializes a QU_Elem so that it can be used in subsequent operations. A QU_Elem is initialized by having its "next" and "prev" field point to itself. An initialized QU_Elem is an empty circular list.

QU_insert(q1, q2) inserts linked list q1 before list q2. The result is a linked list that contains all members of q1 and q2.

It is interesting to note that the order of arguments is not important. The result of QU_insert(q1, q2) and QU_insert(q2, q1) is the same. Figure 6.3 illustrates this.

Figure 6.3: Queue Insertion

The facility QU_remove removes QU_Elem q from the list to which it belonged. QU_Elem q is initialized upon completion of QU_remove.

QU_move moves QU_Elem q1 to end of q2. This is equivalent to the commonly used coding sequence:

    QU_remove(q1);
    QU_insert(q2, q1);

QU_ Macros

QU_ also provides the following set of macros to simplify coding.

• Use one of these as the first element within a structure which is to be a queue head or queue element.

  QU_HEAD
  QU_ELEMENT
  

• Use this macro to statically initialize a queue head.

  QU_INITIALIZE(q)

• These macros may be used to initialize, insert, and remove queue elements. By using these macros, rather then direct calls to the functions, you assure future compatibility.

  QU_INIT(p)
  QU_INSERT(pInsertThisElement, pInFrontOfThisElement)
  QU_PREPEND(pInsertThisElement, pAtBeginOfThisQueue)
  QU_APPEND(pInsertThisElement, pAtEndOfThisQueue)
  QU_REMOVE(p)
  QU_MOVE(pMoveMe, pBeforeThisElement)
  

• Use these macros to find the first or last element on a queue.

  QU_FIRST(p)
  QU_LAST(p)
  

• Use these macros to find the next or previous element on a queue.

  QU_NEXT(p)
  QU_PREV(p)
  

• Use this macro to determine if two queue elements are equal. The following code may be used to iterate through a queue:

  QU_EQUAL(p1, p2)
  
  for (pElement = QU_FIRST(pHead);
       ! QU_EQUAL(pElement, pHead);
       pElement = QU_NEXT(pElement))
  {
     ...
  }
  

• If you want to free all elements on a queue, and each element was allocated with OS_alloc() and no element contains pointers to other dynamically allocated memory, you can use this function. Just pass it a pointer to the queue head.

  QU_FREE(pQHead){