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 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 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 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 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 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 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