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