![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to lists.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 42BSD / ucb / dbx|
Return to lists.c CVS log | Up to [CSRG BSD Unix] / 42BSD / ucb / dbx |
1.1 root 1: /* Copyright (c) 1982 Regents of the University of California */
2:
3: static char sccsid[] = "@(#)lists.c 1.2 12/15/82";
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: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.