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