![[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] / 43BSD / ucb / dbx|
Return to lists.c CVS log | Up to [CSRG BSD Unix] / 43BSD / ucb / dbx |
1.1 root 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: */
6:
7: #ifndef lint
8: static char sccsid[] = "@(#)lists.c 5.1 (Berkeley) 5/31/85";
9: #endif not lint
10:
11: static char rcsid[] = "$Header: lists.c,v 1.5 84/12/26 10:40:00 linton Exp $";
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: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.