Commit | Line | Data |
---|---|---|
54e8b989 ML |
1 | /* Copyright (c) 1982 Regents of the University of California */ |
2 | ||
e1f4dbca | 3 | static char sccsid[] = "@(#)lists.c 1.3 (Berkeley) %G%"; |
54e8b989 ML |
4 | |
5 | /* | |
6 | * General list definitions. | |
7 | * | |
8 | * The assumption is that the elements in a list are words, | |
9 | * usually pointers to the actual information. | |
10 | */ | |
11 | ||
12 | #include "defs.h" | |
13 | #include "lists.h" | |
14 | ||
15 | #ifndef public | |
16 | ||
17 | typedef struct List *List; | |
18 | typedef struct ListItem *ListItem; | |
19 | typedef char *ListElement; | |
20 | ||
21 | #define list_item(element) generic_list_item((ListElement) (element)) | |
22 | #define list_element(type, item) ((type) (item == nil ? nil : (item)->element)) | |
23 | #define list_head(list) ((list == nil) ? nil : (list)->head) | |
24 | #define list_tail(list) ((list == nil) ? nil : (list)->tail) | |
25 | #define list_next(item) ((item == nil) ? nil : (item)->next) | |
26 | #define list_prev(item) ((item == nil) ? nil : (item)->prev) | |
27 | #define list_size(list) (((list) == nil) ? 0 : (list)->nitems) | |
28 | ||
29 | #define foreach(type, i, list) \ | |
30 | { \ | |
31 | register ListItem _item; \ | |
32 | \ | |
33 | _item = list_head(list); \ | |
34 | while (_item != nil) { \ | |
35 | i = list_element(type, _item); \ | |
36 | _item = list_next(_item); | |
37 | ||
38 | #define endfor \ | |
39 | } \ | |
40 | } | |
41 | ||
42 | /* | |
43 | * Iterate through two equal-sized lists. | |
44 | */ | |
45 | ||
46 | #define foreach2(type1, i, list1, type2, j, list2) \ | |
47 | { \ | |
48 | register ListItem _item1, _item2; \ | |
49 | \ | |
50 | _item1 = list_head(list1); \ | |
51 | _item2 = list_head(list2); \ | |
52 | while (_item1 != nil) { \ | |
53 | i = list_element(type1, _item1); \ | |
54 | j = list_element(type2, _item2); \ | |
55 | _item1 = list_next(_item1); \ | |
56 | _item2 = list_next(_item2); | |
57 | ||
58 | #define list_islast() (_item == nil) | |
59 | #define list_curitem(list) (_item == nil ? list_tail(list) : list_prev(_item)) | |
60 | ||
61 | /* | |
62 | * Representation should not be used outside except through macros. | |
63 | */ | |
64 | ||
65 | struct List { | |
66 | Integer nitems; | |
67 | ListItem head; | |
68 | ListItem tail; | |
69 | }; | |
70 | ||
71 | struct ListItem { | |
72 | ListElement element; | |
73 | ListItem next; | |
74 | ListItem prev; | |
75 | }; | |
76 | ||
77 | #endif | |
78 | ||
79 | /* | |
80 | * Allocate and initialize a list. | |
81 | */ | |
82 | ||
83 | public List list_alloc() | |
84 | { | |
85 | List list; | |
86 | ||
87 | list = new(List); | |
88 | list->nitems = 0; | |
89 | list->head = nil; | |
90 | list->tail = nil; | |
91 | return list; | |
92 | } | |
93 | ||
94 | /* | |
95 | * Create a list item from an object (represented as pointer or integer). | |
96 | */ | |
97 | ||
98 | public ListItem generic_list_item(element) | |
99 | ListElement element; | |
100 | { | |
101 | ListItem i; | |
102 | ||
103 | i = new(ListItem); | |
104 | i->element = element; | |
105 | i->next = nil; | |
106 | i->prev = nil; | |
107 | return i; | |
108 | } | |
109 | ||
110 | /* | |
111 | * Insert an item before the item in a list. | |
112 | */ | |
113 | ||
114 | public list_insert(item, after, list) | |
115 | ListItem item; | |
116 | ListItem after; | |
117 | List list; | |
118 | { | |
119 | ListItem a; | |
120 | ||
121 | checkref(list); | |
122 | list->nitems = list->nitems + 1; | |
123 | if (list->head == nil) { | |
124 | list->head = item; | |
125 | list->tail = item; | |
126 | } else { | |
127 | if (after == nil) { | |
128 | a = list->head; | |
129 | } else { | |
130 | a = after; | |
131 | } | |
132 | item->next = a; | |
133 | item->prev = a->prev; | |
134 | if (a->prev != nil) { | |
135 | a->prev->next = item; | |
136 | } else { | |
137 | list->head = item; | |
138 | } | |
139 | a->prev = item; | |
140 | } | |
141 | } | |
142 | ||
143 | /* | |
144 | * Append an item after the given item in a list. | |
145 | */ | |
146 | ||
147 | public list_append(item, before, list) | |
148 | ListItem item; | |
149 | ListItem before; | |
150 | List list; | |
151 | { | |
152 | ListItem b; | |
153 | ||
154 | checkref(list); | |
155 | list->nitems = list->nitems + 1; | |
156 | if (list->head == nil) { | |
157 | list->head = item; | |
158 | list->tail = item; | |
159 | } else { | |
160 | if (before == nil) { | |
161 | b = list->tail; | |
162 | } else { | |
163 | b = before; | |
164 | } | |
165 | item->next = b->next; | |
166 | item->prev = b; | |
167 | if (b->next != nil) { | |
168 | b->next->prev = item; | |
169 | } else { | |
170 | list->tail = item; | |
171 | } | |
172 | b->next = item; | |
173 | } | |
174 | } | |
175 | ||
176 | /* | |
177 | * Delete an item from a list. | |
178 | */ | |
179 | ||
180 | public list_delete(item, list) | |
181 | ListItem item; | |
182 | List list; | |
183 | { | |
184 | checkref(item); | |
185 | checkref(list); | |
186 | assert(list->nitems > 0); | |
187 | if (item->next == nil) { | |
188 | list->tail = item->prev; | |
189 | } else { | |
190 | item->next->prev = item->prev; | |
191 | } | |
192 | if (item->prev == nil) { | |
193 | list->head = item->next; | |
194 | } else { | |
195 | item->prev->next = item->next; | |
196 | } | |
197 | list->nitems = list->nitems - 1; | |
198 | } | |
199 | ||
200 | /* | |
201 | * Concatenate one list onto the end of another. | |
202 | */ | |
203 | ||
204 | public List list_concat(first, second) | |
205 | List first, second; | |
206 | { | |
207 | List r; | |
208 | ||
209 | if (first == nil) { | |
210 | r = second; | |
211 | } else if (second == nil) { | |
212 | r = first; | |
213 | } else { | |
214 | second->head->prev = first->tail; | |
215 | first->tail->next = second->head; | |
216 | first->tail = second->tail; | |
217 | first->nitems = first->nitems + second->nitems; | |
218 | r = first; | |
219 | } | |
220 | return r; | |
221 | } |