| 1 |
DoublyLinkedList Requirements |
| 2 |
================ |
| 3 |
|
| 4 |
## Overview |
| 5 |
|
| 6 |
These functions are the basic linking structures used throughout NT. |
| 7 |
They have been publicly available since 1992. |
| 8 |
Note that the lists do NOT store any data, by design. |
| 9 |
They simply provide a consistent mechanism for linking homogenous items. Also note that no input error checking is provided for this set of APIs. |
| 10 |
|
| 11 |
## References |
| 12 |
|
| 13 |
[http://www.dcl.hpi.uni-potsdam.de/research/WRK/2009/07/single_list_entry-containing_record/](http://www.dcl.hpi.uni-potsdam.de/research/WRK/2009/07/single_list_entry-containing_record/) |
| 14 |
|
| 15 |
## Exposed API |
| 16 |
```c |
| 17 |
typedef struct DLIST_ENTRY_TAG |
| 18 |
{ |
| 19 |
struct DLIST_ENTRY_TAG *Flink; |
| 20 |
struct DLIST_ENTRY_TAG *Blink; |
| 21 |
} DLIST_ENTRY, *PDLIST_ENTRY; |
| 22 |
|
| 23 |
extern void DList_InitializeListHead(PDLIST_ENTRY listHead); |
| 24 |
extern int DList_IsListEmpty(const PDLIST_ENTRY listHead); |
| 25 |
extern void DList_InsertTailList(PDLIST_ENTRY listHead, PDLIST_ENTRY listEntry); |
| 26 |
extern void DList_InsertHeadList(PDLIST_ENTRY listHead, PDLIST_ENTRY entry); |
| 27 |
extern void DList_AppendTailList(PDLIST_ENTRY listHead, PDLIST_ENTRY ListToAppend); |
| 28 |
extern int DList_RemoveEntryList(PDLIST_ENTRY listEntry); |
| 29 |
extern PDLIST_ENTRY DList_RemoveHeadList(PDLIST_ENTRY listHead); |
| 30 |
// |
| 31 |
// Calculate the address of the base of the structure given its type, and an |
| 32 |
// address of a field within the structure. |
| 33 |
// |
| 34 |
|
| 35 |
#define containingRecord(address, type, field) ((type *)((char *)(address) - offsetof(type,field))) |
| 36 |
``` |
| 37 |
|
| 38 |
### DList_InitializeListHead |
| 39 |
```c |
| 40 |
extern void DList_InitializeListHead(PDLIST_ENTRY listHead); |
| 41 |
``` |
| 42 |
**SRS_DLIST_06_005: [** DList_InitializeListHead will initialize the Flink & Blink to the address of the DLIST_ENTRY. **]** |
| 43 |
|
| 44 |
### DList_IsListEmpty |
| 45 |
```c |
| 46 |
extern int DList_IsListEmpty(const PDLIST_ENTRY listHead); |
| 47 |
``` |
| 48 |
|
| 49 |
**SRS_DLIST_06_003: [** DList_IsListEmpty shall return a non-zero value if there are no DLIST_ENTRY's on this list other than the list head. **]** |
| 50 |
|
| 51 |
**SRS_DLIST_06_004: [** DList_IsListEmpty shall return 0 if there is one or more items in the list. **]** |
| 52 |
|
| 53 |
Notes: |
| 54 |
1. DList_IsListEmpty shall be undefined if the DLIST_ENTRY is not currently part of a list. |
| 55 |
2. DList_IsListEmpty shall be undefined if the DLIST_ENTRY has not been initialized as with DList_InitializeListHead. |
| 56 |
|
| 57 |
### DList_InsertTailList |
| 58 |
```c |
| 59 |
extern void DList_InsertTailList(PDLIST_ENTRY listHead, PDLIST_ENTRY listEntry); |
| 60 |
``` |
| 61 |
|
| 62 |
**SRS_DLIST_06_006: [** DList_InsertTailList shall place the DLIST_ENTRY at the end of the list defined by the listHead parameter. **]** |
| 63 |
|
| 64 |
### DList_InsertHeadList |
| 65 |
```c |
| 66 |
extern void DList_InsertHeadList(PDLIST_ENTRY listHead, PDLIST_ENTRY entry); |
| 67 |
``` |
| 68 |
|
| 69 |
**SRS_DLIST_02_002: [** DList_InsertHeadList inserts a singular entry in the list having as head listHead after "head". **]** (see diagram below) |
| 70 |
|
| 71 |
DList_InsertHeadList shall assume listHead and listEntry non-NULL and pointing to existing DLIST_ENTRY structures. Calling DList_InsertHeadList with NULL parameters is undefined behavior. |
| 72 |
|
| 73 |
### DList_AppendTailList |
| 74 |
```c |
| 75 |
extern void DList_AppendTailList(PDLIST_ENTRY listHead, PDLIST_ENTRY ListToAppend); |
| 76 |
``` |
| 77 |
|
| 78 |
**SRS_DLIST_06_007: [** DList_AppendTailList shall place the list defined by listToAppend at the end of the list defined by the listHead parameter. **]** |
| 79 |
|
| 80 |
### DList_RemoveEntryList |
| 81 |
```c |
| 82 |
extern int DList_RemoveEntryList(PDLIST_ENTRY listEntry); |
| 83 |
``` |
| 84 |
|
| 85 |
**SRS_DLIST_06_008: [** DList_RemoveEntryList shall remove a listEntry from whatever list it is properly part of. **]** |
| 86 |
|
| 87 |
**SRS_DLIST_06_009: [** The remaining list is properly formed. **]** |
| 88 |
|
| 89 |
**SRS_DLIST_06_010: [** DList_RemoveEntryList shall return non-zero if the remaining list is empty. **]** |
| 90 |
|
| 91 |
**SRS_DLIST_06_011: [** DList_RemoveEntryList shall return zero if the remaining list is NOT empty. **]** |
| 92 |
|
| 93 |
Notes: |
| 94 |
1. If listEntry is NOT part of a list then the result of this function is undefined. Therefore, calling DList_RemoveEntryList twice on the same listEntry is undefined. |
| 95 |
2. The Flink & Blink of the listEntry parameter shall be undefined after calling this function |
| 96 |
|
| 97 |
### DList_RemoveHeadList |
| 98 |
```c |
| 99 |
extern PDLIST_ENTRY DList_RemoveHeadList(PDLIST_ENTRY listHead); |
| 100 |
``` |
| 101 |
|
| 102 |
**SRS_DLIST_06_012: [** DList_RemoveHeadList removes the oldest entry from the list defined by the listHead parameter and returns a pointer to that entry. **]** |
| 103 |
|
| 104 |
**SRS_DLIST_06_013: [** DList_RemoveHeadList shall return listHead if that's the only item in the list. **]** |
| 105 |
|
| 106 |
Note: The Flink & Blink of the returned PDLIST_ENTRY shall be undefined. |