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