1 /* LINKLIST.H (c) Copyright "Fish" (David B. Trout), 2001-2005 */ 2 /* Linked-list macros */ 3 4 #ifndef _LLIST_ 5 #define _LLIST_ 6 7 ////////////////////////////////////////////////////////////////////////////////////////// 8 /* 9 This module is a standalone collection of linked-list definition, 10 and manipulation macros originally defined for Windows NT development. 11 12 13 Samples: 14 15 16 // Define a list head. 17 18 LIST_ENTRY FooList; 19 20 21 // Define a structure that will be on the list. 22 23 // (NOTE: To make debugging easier, it's best to define the LIST_ENTRY field 24 // as the very first field in your structure, but it's not a requirement.) 25 26 typedef struct _FOO 27 { 28 LIST_ENTRY FooListEntry; 29 . 30 . 31 . 32 } 33 FOO, *PFOO; 34 35 36 // Initialize an empty list. 37 38 InitializeListHead(&FooList); 39 40 41 // Create an object, append it to the end of the list. 42 43 FOO* pFoo; 44 45 pFoo = ALLOC(sizeof(FOO)); 46 {check for errors, initialize FOO structure} 47 48 InsertListTail(&FooList,&pFoo->FooListEntry); 49 50 51 // Scan list and delete selected items. 52 53 LIST_ENTRY* pListEntry = FooList.Flink; 54 55 while (pListEntry != &FooList) 56 { 57 pFoo = CONTAINING_RECORD(pListEntry,FOO,FooListEntry); 58 pListEntry = pListEntry->Flink; 59 60 if (SomeFunction(pFoo)) 61 { 62 RemoveListEntry(&pFoo->FooListEntry); 63 FREE(pFoo); 64 } 65 } 66 67 68 // Purge all items from a list. 69 70 while (!IsListEmpty(&FooList)) 71 { 72 pListEntry = RemoveListHead(&FooList); 73 pFoo = CONTAINING_RECORD(pListEntry,FOO,FooListEntry); 74 FREE(pFoo); 75 } 76 */ 77 ////////////////////////////////////////////////////////////////////////////////////////// 78 79 #if !defined( WIN32 ) || \ 80 ( defined( _MSVC_ ) && !defined(_WINNT_) && !defined(_WINNT_H) ) 81 82 typedef struct _LIST_ENTRY 83 { 84 struct _LIST_ENTRY* Flink; // ptr to next link in chain 85 struct _LIST_ENTRY* Blink; // ptr to previous link in chain 86 } 87 LIST_ENTRY, *PLIST_ENTRY; 88 89 #endif // !defined(_WINNT_) 90 91 ////////////////////////////////////////////////////////////////////////////////////////// 92 // 93 // <typename>* CONTAINING_RECORD 94 // ( 95 // VOID* address, 96 // <typename> type, 97 // <fieldname> field 98 // ); 99 // 100 /* 101 Retrieves a typed pointer to a linked list item given the address of the 102 link storage structure embedded in the linked list item, the type of the 103 linked list item, and the field name of the embedded link storage structure. 104 105 NOTE: since this macro uses compile-time type knowledge, 106 there is no equivalent C procedure for this macro. 107 108 Arguments: 109 110 address - The address of a LIST_ENTRY structure embedded in an a linked list item. 111 type - The type name of the containing linked list item structure. 112 field - The field name of the LIST_ENTRY structure embedded within the linked list item structure. 113 114 Return Value: 115 116 Pointer to the linked list item. 117 118 119 For Example: 120 121 If your record looked like this: 122 123 typedef struct _MYRECORD 124 { 125 int alpha; 126 int beta; 127 LIST_ENTRY gamma; 128 int delta; 129 int epsilon; 130 } 131 MYRECORD, *PMYRECORD; 132 133 Then, given a variable called "pListEntry" that pointed to the LIST_ENTRY field 134 within your record (i.e. gamma), you can obtain a pointer to the beginning of your 135 record by coding the following CONTAINING_RECORD macro expression: 136 137 MYRECORD* pMyRecord; // the variable you wish to point to your record 138 // LIST_ENTRY* pListEntry; // already points to the LIST_ENTRY field within 139 // your record (i.e. points to field "gamma") 140 141 pMyRecord = CONTAINING_RECORD(pListEntry,MYRECORD,gamma); 142 --*/ 143 144 #ifndef CONTAINING_RECORD 145 #define CONTAINING_RECORD( address, type, field ) \ 146 \ 147 ( (type*) ((char*)(address) - (char*)(&((type*)0)->field)) ) 148 #endif 149 150 151 ////////////////////////////////////////////////////////////////////////////////////////// 152 ////////////////////////////////////////////////////////////////////////////////////////// 153 ////////////////////////////////////////////////////////////////////////////////////////// 154 // 155 // From NTRTL.H: Doubly-linked list manipulation routines. 156 // 157 // (NOTE: implemented as macros but logically these are procedures) 158 // 159 ////////////////////////////////////////////////////////////////////////////////////////// 160 ////////////////////////////////////////////////////////////////////////////////////////// 161 ////////////////////////////////////////////////////////////////////////////////////////// 162 163 164 165 ////////////////////////////////////////////////////////////////////////////////////////// 166 // 167 // void InitializeListHead 168 // ( 169 // LIST_ENTRY* head 170 // ); 171 // 172 /* 173 Initializes a LIST_ENTRY structure to be the head of an initially empty linked list. 174 175 Arguments: 176 177 head - Reference to the structure to be initialized. 178 179 Return Value: 180 181 None 182 */ 183 184 #define InitializeListHead(head) \ 185 \ 186 ( (head)->Flink = (head)->Blink = (head) ) 187 188 189 ////////////////////////////////////////////////////////////////////////////////////////// 190 // (I created this one myself -- Fish) 191 // 192 // void InitializeListLink 193 // ( 194 // LIST_ENTRY* link 195 // ); 196 // 197 /* 198 Initializes a LIST_ENTRY structure 199 to be an unlinked link. 200 201 Arguments: 202 203 link - Reference to the structure to be initialized. 204 205 Return Value: 206 207 None 208 */ 209 210 #define InitializeListLink(link) \ 211 \ 212 ( (link)->Flink = (link)->Blink = (NULL) ) 213 214 215 ////////////////////////////////////////////////////////////////////////////////////////// 216 // 217 // <boolean> IsListEmpty 218 // ( 219 // LIST_ENTRY* head 220 // ); 221 // 222 /* 223 Determines whether or not a list is empty. 224 225 Arguments: 226 227 head - Reference to the head of the linked list to be examined. 228 229 Return Value: 230 231 <true> - List is empty. 232 <false> - List contains at least one item. 233 --*/ 234 235 #define IsListEmpty(head) \ 236 \ 237 ( (head)->Flink == (head) ) 238 239 240 ////////////////////////////////////////////////////////////////////////////////////////// 241 // 242 // VOID InsertListHead 243 // ( 244 // LIST_ENTRY* head, 245 // LIST_ENTRY* entry 246 // ); 247 // 248 /* 249 Inserts a new item as the "head" (first) item of a linked list. 250 251 Arguments: 252 253 head - Reference to the head of the linked list to be operated upon. 254 entry - Reference to the linkage structure embedded in the linked list item 255 to be added to the linked list. 256 257 Return Value: 258 259 None 260 */ 261 262 #define InsertListHead(head,entry) \ 263 { \ 264 LIST_ENTRY* _EX_Head; \ 265 LIST_ENTRY* _EX_Next; \ 266 \ 267 _EX_Head = (head); \ 268 _EX_Next = _EX_Head->Flink; \ 269 \ 270 (entry)->Flink = _EX_Next; \ 271 (entry)->Blink = _EX_Head; \ 272 \ 273 _EX_Head->Flink = (entry); \ 274 _EX_Next->Blink = (entry); \ 275 } 276 277 278 ////////////////////////////////////////////////////////////////////////////////////////// 279 // 280 // VOID InsertListTail 281 // ( 282 // LIST_ENTRY* head, 283 // LIST_ENTRY* entry 284 // ); 285 // 286 /* 287 Inserts a new item as the "tail" (last) item of a linked list. 288 289 Arguments: 290 291 head - Reference to the head of the linked list to be operated upon. 292 entry - Reference to the linkage structure embedded in the linked list item 293 to be added to the linked list. 294 295 Return Value: 296 297 None 298 */ 299 300 #define InsertListTail(head,entry) \ 301 { \ 302 LIST_ENTRY* _EX_Head; \ 303 LIST_ENTRY* _EX_Tail; \ 304 \ 305 _EX_Head = (head); \ 306 _EX_Tail = _EX_Head->Blink; \ 307 \ 308 (entry)->Flink = _EX_Head; \ 309 (entry)->Blink = _EX_Tail; \ 310 \ 311 _EX_Tail->Flink = (entry); \ 312 _EX_Head->Blink = (entry); \ 313 } 314 315 316 ////////////////////////////////////////////////////////////////////////////////////////// 317 // 318 // LIST_ENTRY* RemoveListHead 319 // ( 320 // LIST_ENTRY* head 321 // ); 322 // 323 /* 324 Removes the "head" (first) item from a linked list, returning the pointer 325 to the removed entry's embedded linkage structure. Attempting to remove the 326 head item from a (properly initialized) linked list is a no-op and returns 327 the pointer to the head of the linked list. 328 329 The caller may use the CONTAINING_RECORD macro to amplify the returned 330 linkage structure pointer to the containing linked list item structure. 331 332 Arguments: 333 334 head - Reference to the head of the linked list to be operated upon. 335 336 Return Value: 337 338 Returns a pointer to the newly removed linked list item's embedded linkage structure, 339 or the linked list head in the case of an empty list. 340 */ 341 342 #define RemoveListHead(head) \ 343 \ 344 (head)->Flink; \ 345 \ 346 { \ 347 RemoveListEntry((head)->Flink) \ 348 } 349 350 351 ////////////////////////////////////////////////////////////////////////////////////////// 352 // 353 // LIST_ENTRY* RemoveListTail 354 // ( 355 // LIST_ENTRY* head 356 // ); 357 // 358 /* 359 Removes the "tail" (last) item from a linked list, returning the pointer to the 360 removed entry's embedded linkage structure. Attempting to remove the tail item 361 from a (properly initialized) linked list is a no-op and returns the pointer to 362 the head of the linked list. 363 364 The caller may use the CONTAINING_RECORD macro to amplify the returned 365 linkage structure pointer to the containing linked list item structure. 366 367 Arguments: 368 369 head - Reference to the head of the linked list to be operated upon. 370 371 Return Value: 372 373 Pointer to the newly removed linked list item's embedded linkage structure, 374 or the linked list head in the case of an empty list. 375 */ 376 377 #define RemoveListTail(head) \ 378 \ 379 (head)->Blink; \ 380 \ 381 { \ 382 RemoveListEntry((head)->Blink) \ 383 } 384 385 386 ////////////////////////////////////////////////////////////////////////////////////////// 387 // 388 // VOID RemoveListEntry 389 // ( 390 // LIST_ENTRY* entry 391 // ); 392 // 393 /* 394 Removes an item from a linked list. (Removing the head of an empty list is a no-op.) 395 396 Arguments: 397 398 entry - Reference to the linkage structure embedded in a linked list item structure. 399 400 Return Value: 401 402 None 403 */ 404 405 #define RemoveListEntry(entry) \ 406 { \ 407 LIST_ENTRY* _EX_Blink; \ 408 LIST_ENTRY* _EX_Flink; \ 409 \ 410 _EX_Flink = (entry)->Flink; \ 411 _EX_Blink = (entry)->Blink; \ 412 \ 413 _EX_Blink->Flink = _EX_Flink; \ 414 _EX_Flink->Blink = _EX_Blink; \ 415 } 416 417 ////////////////////////////////////////////////////////////////////////////////////////// 418 419 #endif // _LLIST_ 420