4.3BSD - /usr/src/ucb/dbx/lists.c

   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) 5/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: }

Defined functions

Defined variables

Defined struct's

Defined typedef's

Defined macros