1 /*
2 * Copyright (c) 1983 The Regents of the University of California.
3 * All rights reserved.
4 *
5 * %sccs.include.redist.c%
6 */
7
8 #ifndef lint
9 static char sccsid[] = "@(#)lists.c 5.3 (Berkeley) 06/01/90";
10 #endif /* not lint */
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
list_alloc()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
generic_list_item(element)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
list_insert(item,after,list)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
list_append(item,before,list)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
list_delete(item,list)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
list_concat(first,second)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 }
229