![[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] / 43BSDReno / pgrm / dbx|
Return to lists.c CVS log | Up to [CSRG BSD Unix] / 43BSDReno / pgrm / dbx |
1.1 root 1: /*
2: * Copyright (c) 1983 The Regents of the University of California.
3: * All rights reserved.
4: *
5: * Redistribution and use in source and binary forms are permitted
6: * provided that: (1) source distributions retain this entire copyright
7: * notice and comment, and (2) distributions including binaries display
8: * the following acknowledgement: ``This product includes software
9: * developed by the University of California, Berkeley and its contributors''
10: * in the documentation or other materials provided with the distribution
11: * and in all advertising materials mentioning features or use of this
12: * software. Neither the name of the University nor the names of its
13: * contributors may be used to endorse or promote products derived
14: * from this software without specific prior written permission.
15: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
16: * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
17: * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
18: */
19:
20: #ifndef lint
21: static char sccsid[] = "@(#)lists.c 5.3 (Berkeley) 6/1/90";
22: #endif /* not lint */
23:
24: /*
25: * General list definitions.
26: *
27: * The assumption is that the elements in a list are words,
28: * usually pointers to the actual information.
29: */
30:
31: #include "defs.h"
32: #include "lists.h"
33:
34: #ifndef public
35:
36: typedef struct List *List;
37: typedef struct ListItem *ListItem;
38: typedef char *ListElement;
39:
40: #define list_item(element) generic_list_item((ListElement) (element))
41: #define list_element(type, item) ((type) (item == nil ? nil : (item)->element))
42: #define list_head(list) ((list == nil) ? nil : (list)->head)
43: #define list_tail(list) ((list == nil) ? nil : (list)->tail)
44: #define list_next(item) ((item == nil) ? nil : (item)->next)
45: #define list_prev(item) ((item == nil) ? nil : (item)->prev)
46: #define list_size(list) (((list) == nil) ? 0 : (list)->nitems)
47:
48: #define foreach(type, i, list) \
49: { \
50: register ListItem _item; \
51: \
52: _item = list_head(list); \
53: while (_item != nil) { \
54: i = list_element(type, _item); \
55: _item = list_next(_item);
56:
57: #define endfor \
58: } \
59: }
60:
61: /*
62: * Iterate through two equal-sized lists.
63: */
64:
65: #define foreach2(type1, i, list1, type2, j, list2) \
66: { \
67: register ListItem _item1, _item2; \
68: \
69: _item1 = list_head(list1); \
70: _item2 = list_head(list2); \
71: while (_item1 != nil) { \
72: i = list_element(type1, _item1); \
73: j = list_element(type2, _item2); \
74: _item1 = list_next(_item1); \
75: _item2 = list_next(_item2);
76:
77: #define list_islast() (_item == nil)
78: #define list_curitem(list) (_item == nil ? list_tail(list) : list_prev(_item))
79:
80: /*
81: * Representation should not be used outside except through macros.
82: */
83:
84: struct List {
85: Integer nitems;
86: ListItem head;
87: ListItem tail;
88: };
89:
90: struct ListItem {
91: ListElement element;
92: ListItem next;
93: ListItem prev;
94: };
95:
96: #endif
97:
98: /*
99: * Allocate and initialize a list.
100: */
101:
102: public List list_alloc()
103: {
104: List list;
105:
106: list = new(List);
107: list->nitems = 0;
108: list->head = nil;
109: list->tail = nil;
110: return list;
111: }
112:
113: /*
114: * Create a list item from an object (represented as pointer or integer).
115: */
116:
117: public ListItem generic_list_item(element)
118: ListElement element;
119: {
120: ListItem i;
121:
122: i = new(ListItem);
123: i->element = element;
124: i->next = nil;
125: i->prev = nil;
126: return i;
127: }
128:
129: /*
130: * Insert an item before the item in a list.
131: */
132:
133: public list_insert(item, after, list)
134: ListItem item;
135: ListItem after;
136: List list;
137: {
138: ListItem a;
139:
140: checkref(list);
141: list->nitems = list->nitems + 1;
142: if (list->head == nil) {
143: list->head = item;
144: list->tail = item;
145: } else {
146: if (after == nil) {
147: a = list->head;
148: } else {
149: a = after;
150: }
151: item->next = a;
152: item->prev = a->prev;
153: if (a->prev != nil) {
154: a->prev->next = item;
155: } else {
156: list->head = item;
157: }
158: a->prev = item;
159: }
160: }
161:
162: /*
163: * Append an item after the given item in a list.
164: */
165:
166: public list_append(item, before, list)
167: ListItem item;
168: ListItem before;
169: List list;
170: {
171: ListItem b;
172:
173: checkref(list);
174: list->nitems = list->nitems + 1;
175: if (list->head == nil) {
176: list->head = item;
177: list->tail = item;
178: } else {
179: if (before == nil) {
180: b = list->tail;
181: } else {
182: b = before;
183: }
184: item->next = b->next;
185: item->prev = b;
186: if (b->next != nil) {
187: b->next->prev = item;
188: } else {
189: list->tail = item;
190: }
191: b->next = item;
192: }
193: }
194:
195: /*
196: * Delete an item from a list.
197: */
198:
199: public list_delete(item, list)
200: ListItem item;
201: List list;
202: {
203: checkref(item);
204: checkref(list);
205: assert(list->nitems > 0);
206: if (item->next == nil) {
207: list->tail = item->prev;
208: } else {
209: item->next->prev = item->prev;
210: }
211: if (item->prev == nil) {
212: list->head = item->next;
213: } else {
214: item->prev->next = item->next;
215: }
216: list->nitems = list->nitems - 1;
217: }
218:
219: /*
220: * Concatenate one list onto the end of another.
221: */
222:
223: public List list_concat(first, second)
224: List first, second;
225: {
226: List r;
227:
228: if (first == nil) {
229: r = second;
230: } else if (second == nil) {
231: r = first;
232: } else {
233: second->head->prev = first->tail;
234: first->tail->next = second->head;
235: first->tail = second->tail;
236: first->nitems = first->nitems + second->nitems;
237: r = first;
238: }
239: return r;
240: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.