next up previous contents
Next: Application-reserved ( app) Up: Data Structures Previous: Data Structures

Linked Lists

Prospero uses linked lists to structure all data structures allocated with xx alloc(). In all cases, these are doubly linked lists. As usual, the empty list is represented by a list whose head is the NULL pointer. When a doubly linked list has one or more items in it, then the previous field of the first item in the list points to the last item, and the next field of the last item is NULL. Therefore, when a list has only one item in it, then the next pointer of the last item is NULL and the previous points back to itself. In other words, if head is non-null, head -> previous will always be the TAIL of the list, and head ->previous ->next will always be NULL.

Macros for manipulating lists of these structures are in the list_macros.h include file. This file is included by pfs.h, but may be included again without problems.

APPEND_ITEM( new, head) appends the item new to the doubly linked list pointed to by head. The item new goes at the TAIL of the list. It must not already be present in the list. This macro modifies its second argument, head, which should be a variable.

EXTRACT_ITEM( item, head) removes item from a doubly-linked list headed by head. If item is not a member of the list, the results are not defined. The extracted item will NOT be freed.

APPEND_LISTS( list1,list2) performs an O(1) list appending operation. It sets list1 to point to a doubly-linked list consisting of list1 appended to list2. list2 must not already be a part of list1 or the results are unpredictable. list2 will be a garbage value at the end of this exercise, since it will no longer point to a valid doubly-linked list. list1 and list2 must already be valid doubly-linked lists.



next up previous contents
Next: Application-reserved ( app) Up: Data Structures Previous: Data Structures



Padma Indraganti
Wed Jun 19 18:04:04 PDT 1996