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) 05/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 } 230