NAME

queue - q-structure predicates and list manipulation procedures

SYNOPSIS

#include <q.h>

int enqueue(proc, tail)
int dequeue(proc)
int firstid(head)
int firstkey(head)
int getfirst(head)
int getlast(tail)
int insert(proc, head, key)
int insertd(proc, head, key)
Bool isempty(head)
int lastkey(tail)
Bool nonempty(head)
int head, tail;
int proc;
int key;

DESCRIPTION

The q structure holds doubly-linked lists of processes, including lists of processes that are ready, sleeping, and waiting on a semaphore.  These routines manipulate lists in the q structure as follows. 

enqueue
Add a process to a FIFO list given the process id in argument proc and the q index of the tail of the list in argument tail.  Enqueue returns argument proc to its caller. 

dequeue
Remove a process from a list given the process id. The list on which the process is found need not be specified because it can be determined from the q structure.  Dequeue will remove a process from both FIFO and ordered lists.  It returns its argument to the caller. 

firstid
Return the process id of the first process on a list given the q index of the list head in argument head. 

firstkey
Return the integer key associated with the first entry on a list given the q index of the list in argument head. 

getfirst
Remove the first process from a list and return its process id given the q index of the head of the list in argument head.  Getfirst returns EMPTY if the list is empty, and a process id otherwise. 

getlast
Remove the last process on a list and return its process id given the q index of the tail of the list in argument tail.  Getlast returns EMPTY if the list is empty, and a process id otherwise. 

insert Insert a process into an ordered list given the process id in argument proc, the q index of the head of the list in argument head, and an integer key for the process in argument key.  Ordered lists are always ordered by increasing key values.  Insert returns OK. 

insertd
Insert a process in a delta list given the process id in argument proc, the q index of the head of the list in argument head, and an integer key in argument key.  Insertd returns OK. 

isempty
Return TRUE if there are no processes on a list, FALSE otherwise, given the q index of the head of the list in argument head. 

lastkey
Return the key of the last process in a list given the q index of the tail of the list in argument tail. 

nonempty
Return TRUE if there is at least one process on a list, FALSE otherwise, given the q index of the head of the list in argument head. 

BUGS

Most of these routines do not check for valid arguments or valid lists.  Also, they assume interrupts are disabled when called, and will corrupt the list structure if the caller fails to disable interrupts. 

December 01, 1986  —  Xinu Programmer’s Manual