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