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