doublylinkedlist.c

00001 // Copyright (c) Microsoft. All rights reserved.
00002 // Licensed under the MIT license. See LICENSE file in the project root for full license information.
00003 
00004 #include <stdlib.h>
00005 #ifdef _CRTDBG_MAP_ALLOC
00006 #include <crtdbg.h>
00007 #endif
00008 #include "azure_c_shared_utility/doublylinkedlist.h"
00009 
00010 void
00011 DList_InitializeListHead(
00012     PDLIST_ENTRY ListHead
00013 )
00014 {
00015     /* Codes_SRS_DLIST_06_005: [DList_InitializeListHead will initialize the Flink & Blink to the address of the DLIST_ENTRY.] */
00016     ListHead->Flink = ListHead->Blink = ListHead;
00017     return;
00018 }
00019 
00020 int
00021 DList_IsListEmpty(
00022     const PDLIST_ENTRY ListHead
00023 )
00024 {
00025     /* Codes_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.] */
00026     /* Codes_SRS_DLIST_06_004: [DList_IsListEmpty shall return 0 if there is one or more items in the list.] */
00027     return (ListHead->Flink == ListHead);
00028 }
00029 
00030 int
00031 DList_RemoveEntryList(
00032     PDLIST_ENTRY Entry
00033 )
00034 {
00035     /* Codes_SRS_DLIST_06_008: [DList_RemoveEntryList shall remove a listEntry from whatever list it is properly part of.] */
00036     /* Codes_SRS_DLIST_06_009: [The remaining list is properly formed.] */
00037     /* Codes_SRS_DLIST_06_010: [DList_RemoveEntryList shall return non-zero if the remaining list is empty.] */
00038     /* Codes_SRS_DLIST_06_011: [DList_RemoveEntryList shall return zero if the remaining list is NOT empty.] */
00039     PDLIST_ENTRY Blink;
00040     PDLIST_ENTRY Flink;
00041 
00042     Flink = Entry->Flink;
00043     Blink = Entry->Blink;
00044     Blink->Flink = Flink;
00045     Flink->Blink = Blink;
00046     return (Flink == Blink);
00047 }
00048 
00049 PDLIST_ENTRY
00050 DList_RemoveHeadList(
00051     PDLIST_ENTRY ListHead
00052 )
00053 {
00054     /* Codes_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.] */
00055     /* Codes_SRS_DLIST_06_013: [DList_RemoveHeadList shall return listHead if that's the only item in the list.] */
00056 
00057     PDLIST_ENTRY Flink;
00058     PDLIST_ENTRY Entry;
00059 
00060     Entry = ListHead->Flink;
00061     Flink = Entry->Flink;
00062     ListHead->Flink = Flink;
00063     Flink->Blink = ListHead;
00064     return Entry;
00065 }
00066 
00067 
00068 
00069 void
00070 DList_InsertTailList(
00071     PDLIST_ENTRY ListHead,
00072     PDLIST_ENTRY Entry
00073 )
00074 {
00075     PDLIST_ENTRY Blink;
00076 
00077     /* Codes_SRS_DLIST_06_006: [DListInsertTailList shall place the DLIST_ENTRY at the end of the list defined by the listHead parameter.] */
00078     Blink = ListHead->Blink;
00079     Entry->Flink = ListHead;
00080     Entry->Blink = Blink;
00081     Blink->Flink = Entry;
00082     ListHead->Blink = Entry;
00083     return;
00084 }
00085 
00086 
00087 void
00088 DList_AppendTailList(
00089     PDLIST_ENTRY ListHead,
00090     PDLIST_ENTRY ListToAppend
00091 )
00092 {
00093     /* Codes_SRS_DLIST_06_007: [DList_AppendTailList shall place the list defined by listToAppend at the end of the list defined by the listHead parameter.] */
00094     PDLIST_ENTRY ListEnd = ListHead->Blink;
00095 
00096     ListHead->Blink->Flink = ListToAppend;
00097     ListHead->Blink = ListToAppend->Blink;
00098     ListToAppend->Blink->Flink = ListHead;
00099     ListToAppend->Blink = ListEnd;
00100     return;
00101 }
00102 
00103 
00104 /*Codes_SRS_DLIST_02_002: [DList_InsertHeadList inserts a singular entry in the list having as head listHead after "head".]*/
00105 void DList_InsertHeadList(PDLIST_ENTRY listHead, PDLIST_ENTRY entry)
00106 {
00107     entry->Blink = listHead;
00108     entry->Flink = listHead->Flink;
00109     listHead->Flink->Blink = entry;
00110     listHead->Flink = entry;
00111 }