|
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 "Boolean.h" //rjf 6.2000 |
|
18 |
|
19 #include <cstdlib> |
|
20 #include <stddef.h> //rjf 6.2000 |
|
21 // This declares the type "VoidFunctionPtr" to be a "pointer to a |
|
22 // function taking an integer argument and returning nothing". With |
|
23 // such a function pointer (say it is "func"), we can call it like this: |
|
24 // |
|
25 // (*func) (17); |
|
26 // |
|
27 // Used by MapCar in list.h |
|
28 |
|
29 typedef void (*VoidFunctionPtr)(int arg); |
|
30 |
|
31 // The following class defines a "list element" -- which is |
|
32 // used to keep track of one item on a list. It is equivalent to a |
|
33 // LISP cell, with a "car" ("next") pointing to the next element on the list, |
|
34 // and a "cdr" ("item") pointing to the item on the list. |
|
35 // |
|
36 // Internal data structures kept public so that List operations can |
|
37 // access them directly. |
|
38 |
|
39 class ListElement { |
|
40 public: |
|
41 ListElement(void *itemPtr, int sortKey); // initialize a list element |
|
42 |
|
43 ListElement *next; // next element on list, |
|
44 // NULL if this is the last |
|
45 ListElement *previous; // previous element on the list |
|
46 // NULL if this is the first element |
|
47 // put types int before these guys 7/00 RJF |
|
48 int insertAfter(void *item); // insert a new item after this one |
|
49 int insertBefore(void *item); // insert a new item before this one |
|
50 int remove(void * item); // remove this item |
|
51 |
|
52 int key; // priority, for a sorted list |
|
53 void *item; // pointer to item on the list |
|
54 }; |
|
55 |
|
56 // The following class defines a "list" -- a singly linked list of |
|
57 // list elements, each of which points to a single item on the list. |
|
58 // |
|
59 // By using the "Sorted" functions, the list can be kept in sorted |
|
60 // in increasing order by "key" in ListElement. |
|
61 |
|
62 class List { |
|
63 public: |
|
64 List(); // initialize the list |
|
65 ~List(); // de-allocate the list |
|
66 |
|
67 void Prepend(void *item); // Put item at the beginning of the list |
|
68 void Append(void *item); // Put item at the end of the list |
|
69 void *Remove(); // Take item off the front of the list |
|
70 |
|
71 void Mapcar(VoidFunctionPtr func); // Apply "func" to every element |
|
72 // on the list |
|
73 bool IsEmpty(); // is the list empty? |
|
74 void insertAfter(ListElement * listEl, void *item); |
|
75 void insertBefore(ListElement * listEl, void *item); |
|
76 void removeAt(ListElement * listEl); |
|
77 |
|
78 // Routines to put/get items on/off list in order (sorted by key) |
|
79 void SortedInsert(void *item, int sortKey); // Put item into list |
|
80 void *SortedRemove(int *keyPtr); // Remove first item from list |
|
81 |
|
82 |
|
83 int length; // Length of list |
|
84 ListElement *first; // Head of the list, NULL if list is empty |
|
85 ListElement *last; // Last element of list |
|
86 |
|
87 }; |
|
88 |
|
89 #endif // LIST_H |
|
90 |
|
91 |
|
92 |
|
93 |