|
1 |
|
2 // list.h |
|
3 // Data structures to manage LISP-like lists. |
|
4 // |
|
5 // As in LISP, a list can contain any type of data structure |
|
6 // as an item on the list: thread control blocks, |
|
7 // pending interrupts, etc. That is why each item is a "void *", |
|
8 // or in other words, a "pointers to anything". |
|
9 // |
|
10 // Copyright (c) 1992-1993 The Regents of the University of California. |
|
11 // All rights reserved. See copyright.h for copyright notice and limitation |
|
12 // of liability and disclaimer of warranty provisions. |
|
13 |
|
14 #ifndef LIST_H |
|
15 #define LIST_H |
|
16 #include <bool.h> |
|
17 #include <stdlib.h> |
|
18 |
|
19 // This declares the type "VoidFunctionPtr" to be a "pointer to a |
|
20 // function taking an integer argument and returning nothing". With |
|
21 // such a function pointer (say it is "func"), we can call it like this: |
|
22 // |
|
23 // (*func) (17); |
|
24 // |
|
25 // Used by MapCar in list.h |
|
26 |
|
27 typedef void (*VoidFunctionPtr)(int arg); |
|
28 |
|
29 // The following class defines a "list element" -- which is |
|
30 // used to keep track of one item on a list. It is equivalent to a |
|
31 // LISP cell, with a "car" ("next") pointing to the next element on the list, |
|
32 // and a "cdr" ("item") pointing to the item on the list. |
|
33 // |
|
34 // Internal data structures kept public so that List operations can |
|
35 // access them directly. |
|
36 |
|
37 class ListElement { |
|
38 public: |
|
39 ListElement(void *itemPtr, int sortKey); // initialize a list element |
|
40 |
|
41 ListElement *next; // next element on list, |
|
42 // NULL if this is the last |
|
43 ListElement *previous; // previous element on the list |
|
44 // NULL if this is the first element |
|
45 |
|
46 insertAfter(void *item); // insert a new item after this one |
|
47 insertBefore(void *item); // insert a new item before this one |
|
48 remove(void * item); // remove item with this key |
|
49 |
|
50 int key; // priority, for a sorted list |
|
51 void *item; // pointer to item on the list |
|
52 }; |
|
53 |
|
54 // The following class defines a "list" -- a singly linked list of |
|
55 // list elements, each of which points to a single item on the list. |
|
56 // |
|
57 // By using the "Sorted" functions, the list can be kept in sorted |
|
58 // in increasing order by "key" in ListElement. |
|
59 |
|
60 class List { |
|
61 public: |
|
62 List(); // initialize the list |
|
63 ~List(); // de-allocate the list |
|
64 |
|
65 void Prepend(void *item); // Put item at the beginning of the list |
|
66 void Append(void *item); // Put item at the end of the list |
|
67 void *Remove(); // Take item off the front of the list |
|
68 |
|
69 void Mapcar(VoidFunctionPtr func); // Apply "func" to every element |
|
70 // on the list |
|
71 bool IsEmpty(); // is the list empty? |
|
72 void printList(); |
|
73 |
|
74 void insertAfter(ListElement * listEl, void *item); |
|
75 void insertBefore(ListElement * listEl, void *item); |
|
76 void removeAt(ListElement * listEl); |
|
77 void * removeElement(void * item); |
|
78 // find this item in list and remove it |
|
79 |
|
80 // Routines to put/get items on/off list in order (sorted by key) |
|
81 void Insert(void *item){SortedInsert(item,0);} |
|
82 void SortedInsert(void *item, int sortKey); // Put item into list |
|
83 void *SortedRemove(int *keyPtr); // Remove first item from list |
|
84 |
|
85 |
|
86 int length; // Length of list |
|
87 ListElement *first; // Head of the list, NULL if list is empty |
|
88 ListElement *last; // Last element of list |
|
89 |
|
90 }; |
|
91 |
|
92 #endif // LIST_H |
|
93 |
|
94 |
|
95 |
|
96 |