XINU List Manipulation Routines

The usual list manipulation routines exist in XINU including:

• isempty() // checks if the list is empty
• nonempty() // true if not empty
• firstkey() // key value of first element (one at head of list)
• firstid() // PID in first element
• lastkey() // key value of last element (one at tail)

In XINU if the list is being used as a FIFO list, then elements are added at the tail, and removed from the head. The routines to do this are:

• enqueue() // adds to the tail
• dequeue() // removes item from anywhere in list

If this list is being used as a priority list, this means that list elements are ordered according to the value of their keys. This is used, for example, for the ready list (ready processes are ordered by process priority - the priority is kept in the key field of the list elements).

The routine insert() adds an element to the list in order of key value. Note that the implementation is simplified by the fact that the key value for the HEAD dummy node is minint (-1 I think) and the key value for the TAIL dummy node is maxint. Thus insert never needs to worry about checking for end of list - it will always be inserting into the middle of a list.

The routines getfirst() and getlast() remove and return the first (head) item and last (tail) item in the list, respectively.

Note that the arrangement of the ready queues (a single, ordered ready Q) has its advantages and disadvantages. The advantage is that process priorities can take the entire integer range. The disadvantage is that the list must be searched during additions to the list. Pthreads has a fixed set of priorities (only three) but no searching is necessary when adding to, or deleting from lists.

Finally, there is a routine to create a new list. It is newqueue(). There is no routine to delete a list (there is never a need to delete process lists in XINU). Never having to delete a list makes list creation easy. We simply start allocating at NPROC, and for each allocation add two to the next free list head position.