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