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