[fireball] 50686: [RTL/DPH] - Implement list manipulation routines: pool list, virtual list, unused list. - Implement node removal from an available list.

Author: fireball
Date: Sun Feb 13 21:39:26 2011
New Revision: 50686

URL: http://svn.reactos.org/svn/reactos?rev=50686&view=rev
Log:
[RTL/DPH]
- Implement list manipulation routines: pool list, virtual list, unused list.
- Implement node removal from an available list.

Modified:
    trunk/reactos/lib/rtl/heappage.c

Modified: trunk/reactos/lib/rtl/heappage.c
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/heappage.c?rev=506…
==============================================================================
--- trunk/reactos/lib/rtl/heappage.c [iso-8859-1] (original)
+++ trunk/reactos/lib/rtl/heappage.c [iso-8859-1] Sun Feb 13 21:39:26 2011
@@ -143,6 +143,11 @@
 /* Signatures */
 #define DPH_SIGNATURE 0xFFEEDDCC
 
+/* Biased pointer macros */
+#define IS_BIASED_POINTER(ptr) ((ULONG_PTR)(ptr) & 1)
+#define POINTER_REMOVE_BIAS(ptr) ((ULONG_PTR)(ptr) & ~(ULONG_PTR)1)
+#define POINTER_ADD_BIAS(ptr) ((ULONG_PTR)(ptr) & 1)
+
 /* FUNCTIONS ******************************************************************/
 
 NTSTATUS NTAPI
@@ -268,7 +273,99 @@
 }
 
 VOID NTAPI
-RtlpDphAddNewPool(PDPH_HEAP_ROOT DphRoot, PDPH_HEAP_BLOCK NodeBlock, PVOID Virtual,
SIZE_T Size, BOOLEAN Add)
+RtlpDphPlaceOnPoolList(PDPH_HEAP_ROOT DphRoot, PDPH_HEAP_BLOCK DphNode)
+{
+    /* DphNode is being added to the tail of the list */
+    DphNode->pNextAlloc = NULL;
+
+    /* Add it to the tail of the linked list */
+    if (DphRoot->pNodePoolListTail)
+        DphRoot->pNodePoolListTail->pNextAlloc = DphNode;
+    else
+        DphRoot->pNodePoolListHead = DphNode;
+    DphRoot->pNodePoolListTail = DphNode;
+
+    /* Update byte counts taking in account this new node */
+    DphRoot->nNodePools++;
+    DphRoot->nNodePoolBytes += DphNode->nVirtualBlockSize;
+}
+
+VOID NTAPI
+RtlpDphPlaceOnVirtualList(PDPH_HEAP_ROOT DphRoot, PDPH_HEAP_BLOCK DphNode)
+{
+    /* Add it to the head of the virtual list */
+    DphNode->pNextAlloc = DphRoot->pVirtualStorageListHead;
+    if (!DphRoot->pVirtualStorageListHead)
+        DphRoot->pVirtualStorageListTail = DphNode;
+    DphRoot->pVirtualStorageListHead = DphNode;
+
+    /* Update byte counts taking in account this new node */
+    DphRoot->nVirtualStorageRanges++;
+    DphRoot->nVirtualStorageBytes += DphNode->nVirtualBlockSize;
+}
+
+PDPH_HEAP_BLOCK NTAPI
+RtlpDphTakeNodeFromUnusedList(PDPH_HEAP_ROOT DphRoot)
+{
+    PDPH_HEAP_BLOCK Node = DphRoot->pUnusedNodeListHead;
+    PDPH_HEAP_BLOCK Next;
+
+    /* Take the first entry */
+    if (!Node) return NULL;
+
+    /* Remove that entry (Node) from the list */
+    Next = Node->pNextAlloc;
+    if (DphRoot->pUnusedNodeListHead == Node) DphRoot->pUnusedNodeListHead = Next;
+    if (DphRoot->pUnusedNodeListTail == Node) DphRoot->pUnusedNodeListTail = NULL;
+
+    /* Decrease amount of unused nodes */
+    DphRoot->nUnusedNodes--;
+
+    return Node;
+}
+
+VOID NTAPI
+RtlpDphReturnNodeToUnusedList(PDPH_HEAP_ROOT DphRoot,
+                              PDPH_HEAP_BLOCK Node)
+{
+    /* Add it back to the head of the unused list */
+    Node->pNextAlloc = DphRoot->pUnusedNodeListHead;
+    if (!DphRoot->pUnusedNodeListHead) DphRoot->pUnusedNodeListTail = Node;
+    DphRoot->pUnusedNodeListHead = Node;
+
+    /* Increase amount of unused nodes */
+    DphRoot->nUnusedNodes++;
+}
+
+VOID NTAPI
+RtlpDphRemoveFromAvailableList(PDPH_HEAP_ROOT DphRoot,
+                               PDPH_HEAP_BLOCK Node)
+{
+    /* Make sure Adjacency list pointers are biased */
+    ASSERT(IS_BIASED_POINTER(Node->AdjacencyEntry.Flink));
+    ASSERT(IS_BIASED_POINTER(Node->AdjacencyEntry.Blink));
+
+    /* Remove it from the list */
+    RemoveEntryList(&Node->AvailableEntry);
+
+    /* Decrease heap counters */
+    DphRoot->nAvailableAllocations--;
+    DphRoot->nAvailableAllocationBytesCommitted -= Node->nVirtualBlockSize;
+
+    /* Remove bias from the AdjacencyEntry pointer */
+    POINTER_REMOVE_BIAS(Node->AdjacencyEntry.Flink);
+    POINTER_REMOVE_BIAS(Node->AdjacencyEntry.Blink);
+}
+
+VOID NTAPI
+RtlpDphCoalesceNodeIntoAvailable(PDPH_HEAP_ROOT DphRoot,
+                                 PDPH_HEAP_BLOCK Node)
+{
+    UNIMPLEMENTED;
+}
+
+VOID NTAPI
+RtlpDphAddNewPool(PDPH_HEAP_ROOT DphRoot, PDPH_HEAP_BLOCK NodeBlock, PVOID Virtual,
SIZE_T Size, BOOLEAN PlaceOnPool)
 {
     PDPH_HEAP_BLOCK DphNode, DphStartNode;
     ULONG NodeCount;
@@ -294,9 +391,19 @@
     /* Increase counters */
     DphRoot->nUnusedNodes += NodeCount;
 
-    if (Add)
-    {
-        UNIMPLEMENTED;
+    /* Check if we need to place it on the pool list */
+    if (PlaceOnPool)
+    {
+        /* Get a node from the unused list */
+        DphNode = RtlpDphTakeNodeFromUnusedList(DphRoot);
+        ASSERT(DphNode);
+
+        /* Set its virtual block values */
+        DphNode->pVirtualBlock = Virtual;
+        DphNode->nVirtualBlockSize = Size;
+
+        /* Place it on the pool list */
+        RtlpDphPlaceOnPoolList(DphRoot, DphNode);
     }
 }
 
@@ -307,34 +414,6 @@
 {
     UNIMPLEMENTED;
     return NULL;
-}
-
-
-PDPH_HEAP_BLOCK NTAPI
-RtlpDphTakeNodeFromUnusedList(PDPH_HEAP_ROOT DphRoot)
-{
-    UNIMPLEMENTED;
-    return NULL;
-}
-
-VOID NTAPI
-RtlpDphReturnNodeToUnusedList(PDPH_HEAP_ROOT DphRoot,
-                               PDPH_HEAP_BLOCK Node)
-{
-}
-
-VOID NTAPI
-RtlpDphRemoveFromAvailableList(PDPH_HEAP_ROOT DphRoot,
-                               PDPH_HEAP_BLOCK Node)
-{
-    UNIMPLEMENTED;
-}
-
-VOID NTAPI
-RtlpDphCoalesceNodeIntoAvailable(PDPH_HEAP_ROOT DphRoot,
-                                 PDPH_HEAP_BLOCK Node)
-{
-    UNIMPLEMENTED;
 }
 
 PDPH_HEAP_BLOCK NTAPI
@@ -420,18 +499,6 @@
     }
 
     return RtlpDphTakeNodeFromUnusedList(DphRoot);
-}
-
-VOID NTAPI
-RtlpDphPlaceOnPoolList(PDPH_HEAP_ROOT DphRoot, PDPH_HEAP_BLOCK DphNode)
-{
-    UNIMPLEMENTED;
-}
-
-VOID NTAPI
-RtlpDphPlaceOnVirtualList(PDPH_HEAP_ROOT DphRoot, PDPH_HEAP_BLOCK DphNode)
-{
-    UNIMPLEMENTED;
 }
 
 RTL_GENERIC_COMPARE_RESULTS