Debian Codegraph @

src/vendor/azure-uamqp-c/deps/azure-c-shared-utility/devdoc/doublylinkedlist_requirements.md

raw
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.