1 /* 2 * Copyright (c) 1988, 1989, 1990, 1993 3 * The Regents of the University of California. All rights reserved. 4 * Copyright (c) 1989 by Berkeley Softworks 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * Adam de Boor. 9 * 10 * %sccs.include.redist.c% 11 * 12 * @(#)list.h 8.2 (Berkeley) 04/28/95 13 */ 14 15 /* 16 * list.h -- 17 * 18 * Structures, macros, and routines exported by the List module. 19 */ 20 21 #ifndef _LIST 22 #define _LIST 23 24 #ifndef _SPRITE 25 #include "sprite.h" 26 #endif _SPRITE 27 28 /* 29 * This module defines the list abstraction, which enables one to link 30 * together arbitrary data structures. Lists are doubly-linked and 31 * circular. A list contains a header followed by its real members, if 32 * any. (An empty list therefore consists of a single element, the 33 * header, whose nextPtr and prevPtr fields point to itself). To refer 34 * to a list as a whole, the user keeps a pointer to the header; that 35 * header is initialized by a call to List_Init(), which creates an empty 36 * list given a pointer to a List_Links structure (described below). 37 * 38 * The links are contained in a two-element structure called List_Links. 39 * A list joins List_Links records (that is, each List_Links structure 40 * points to other List_Links structures), but if the List_Links is the 41 * first field within a larger structure, then the larger structures are 42 * effectively linked together as follows: 43 * 44 * header 45 * (List_Links) first elt. second elt. 46 * ----------------- ----------------- ----------------- 47 * ..-> | nextPtr | ----> | List_Links | ----> | List_Links |----.. 48 * | - - - - - - - | | | | | 49 * ..-- | prevPtr | <---- | | <---- | |<---.. 50 * ----------------- - --- --- --- - - --- --- --- - 51 * | rest of | | rest of | 52 * | structure | | structure | 53 * | | | | 54 * | ... | | ... | 55 * ----------------- ----------------- 56 * 57 * It is possible to link structures through List_Links fields that are 58 * not at the beginning of the larger structure, but it is then necessary 59 * to perform pointer arithmetic to find the beginning of the larger 60 * structure, given a pointer to some point within it. 61 * 62 * A typical structure might be something like: 63 * 64 * typedef struct { 65 * List_Links links; 66 * char ch; 67 * integer flags; 68 * } EditChar; 69 * 70 * Before an element is inserted in a list for the first time, it must 71 * be initialized by calling the macro List_InitElement(). 72 */ 73 74 75 /* 76 * data structure for lists 77 */ 78 79 typedef struct List_Links { 80 struct List_Links *prevPtr; 81 struct List_Links *nextPtr; 82 } List_Links; 83 84 /* 85 * procedures 86 */ 87 88 void List_Init(); /* initialize a header to a list */ 89 void List_Insert(); /* insert an element into a list */ 90 void List_Remove(); /* remove an element from a list */ 91 void List_Move(); /* move an element elsewhere in a list */ 92 93 /* 94 * ---------------------------------------------------------------------------- 95 * 96 * List_InitElement -- 97 * 98 * Initialize a list element. Must be called before an element is first 99 * inserted into a list. 100 * 101 * ---------------------------------------------------------------------------- 102 */ 103 #define List_InitElement(elementPtr) \ 104 (elementPtr)->prevPtr = (List_Links *) NIL; \ 105 (elementPtr)->nextPtr = (List_Links *) NIL; 106 107 /* 108 * Macros for stepping through or selecting parts of lists 109 */ 110 111 /* 112 * ---------------------------------------------------------------------------- 113 * 114 * LIST_FORALL -- 115 * 116 * Macro to loop through a list and perform an operation on each member. 117 * 118 * Usage: LIST_FORALL(headerPtr, itemPtr) { 119 * / * 120 * * operation on itemPtr, which points to successive members 121 * * of the list 122 * * 123 * * It may be appropriate to first assign 124 * * foobarPtr = (Foobar *) itemPtr; 125 * * to refer to the entire Foobar structure. 126 * * / 127 * } 128 * 129 * Note: itemPtr must be a List_Links pointer variable, and headerPtr 130 * must evaluate to a pointer to a List_Links structure. 131 * 132 * ---------------------------------------------------------------------------- 133 */ 134 135 #define LIST_FORALL(headerPtr, itemPtr) \ 136 for (itemPtr = List_First(headerPtr); \ 137 !List_IsAtEnd((headerPtr),itemPtr); \ 138 itemPtr = List_Next(itemPtr)) 139 140 /* 141 * ---------------------------------------------------------------------------- 142 * 143 * List_IsEmpty -- 144 * 145 * Macro: Boolean value, TRUE if the given list does not contain any 146 * members. 147 * 148 * Usage: if (List_IsEmpty(headerPtr)) ... 149 * 150 * ---------------------------------------------------------------------------- 151 */ 152 153 #define List_IsEmpty(headerPtr) \ 154 ((headerPtr) == (headerPtr)->nextPtr) 155 156 /* 157 * ---------------------------------------------------------------------------- 158 * 159 * List_IsAtEnd -- 160 * 161 * Macro: Boolean value, TRUE if itemPtr is after the end of headerPtr 162 * (i.e., itemPtr is the header of the list). 163 * 164 * Usage: if (List_IsAtEnd(headerPtr, itemPtr)) ... 165 * 166 * ---------------------------------------------------------------------------- 167 */ 168 169 170 #define List_IsAtEnd(headerPtr, itemPtr) \ 171 ((itemPtr) == (headerPtr)) 172 173 174 /* 175 * ---------------------------------------------------------------------------- 176 * 177 * List_First -- 178 * 179 * Macro to return the first member in a list, which is the header if 180 * the list is empty. 181 * 182 * Usage: firstPtr = List_First(headerPtr); 183 * 184 * ---------------------------------------------------------------------------- 185 */ 186 187 #define List_First(headerPtr) ((headerPtr)->nextPtr) 188 189 /* 190 * ---------------------------------------------------------------------------- 191 * 192 * List_Last -- 193 * 194 * Macro to return the last member in a list, which is the header if 195 * the list is empty. 196 * 197 * Usage: lastPtr = List_Last(headerPtr); 198 * 199 * ---------------------------------------------------------------------------- 200 */ 201 202 #define List_Last(headerPtr) ((headerPtr)->prevPtr) 203 204 /* 205 * ---------------------------------------------------------------------------- 206 * 207 * List_Prev -- 208 * 209 * Macro to return the member preceding the given member in its list. 210 * If the given list member is the first element in the list, List_Prev 211 * returns the list header. 212 * 213 * Usage: prevPtr = List_Prev(itemPtr); 214 * 215 * ---------------------------------------------------------------------------- 216 */ 217 218 #define List_Prev(itemPtr) ((itemPtr)->prevPtr) 219 220 /* 221 * ---------------------------------------------------------------------------- 222 * 223 * List_Next -- 224 * 225 * Macro to return the member following the given member in its list. 226 * If the given list member is the last element in the list, List_Next 227 * returns the list header. 228 * 229 * Usage: nextPtr = List_Next(itemPtr); 230 * 231 * ---------------------------------------------------------------------------- 232 */ 233 234 #define List_Next(itemPtr) ((itemPtr)->nextPtr) 235 236 237 /* 238 * ---------------------------------------------------------------------------- 239 * The List_Insert procedure takes two arguments. The first argument 240 * is a pointer to the structure to be inserted into a list, and 241 * the second argument is a pointer to the list member after which 242 * the new element is to be inserted. Macros are used to determine 243 * which existing member will precede the new one. 244 * 245 * The List_Move procedure takes a destination argument with the same 246 * semantics as List_Insert. 247 * 248 * The following macros define where to insert the new element 249 * in the list: 250 * 251 * LIST_AFTER(itemPtr) -- insert after itemPtr 252 * LIST_BEFORE(itemPtr) -- insert before itemPtr 253 * LIST_ATFRONT(headerPtr) -- insert at front of list 254 * LIST_ATREAR(headerPtr) -- insert at end of list 255 * 256 * For example, 257 * 258 * List_Insert(itemPtr, LIST_AFTER(otherPtr)); 259 * 260 * will insert itemPtr following otherPtr in the list containing otherPtr. 261 * ---------------------------------------------------------------------------- 262 */ 263 264 #define LIST_AFTER(itemPtr) ((List_Links *) itemPtr) 265 266 #define LIST_BEFORE(itemPtr) (((List_Links *) itemPtr)->prevPtr) 267 268 #define LIST_ATFRONT(headerPtr) ((List_Links *) headerPtr) 269 270 #define LIST_ATREAR(headerPtr) (((List_Links *) headerPtr)->prevPtr) 271 272 #endif /* _LIST */ 273