| 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) %G%"; |
| 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 | } |