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