reactos/lib/rtl/avltable.c

   1 /*
   2 * PROJECT:         ReactOS Runtime Library
   3 * LICENSE:         BSD - See COPYING.ARM in the top level directory
   4 * FILE:            lib/rtl/avltable.c
   5 * PURPOSE:         AVL Tree Generic Table Implementation
   6 * PROGRAMMERS:     ReactOS Portable Systems Group
   7 */
   8
   9 /* INCLUDES ******************************************************************/
  10
  11 #include <rtl.h>
  12 #define NDEBUG
  13 #include <debug.h>
  14
  15 /* Include RTL version of AVL support */
  16 #include "rtlavl.h"
  17 #include "avlsupp.c"
  18
  19 /* AVL FUNCTIONS *************************************************************/
  20
  21 /*
  22  * @implemented
  23  */
  24 VOID
  25 NTAPI
  26 RtlInitializeGenericTableAvl(IN OUT PRTL_AVL_TABLE Table,
  27                              IN PRTL_AVL_COMPARE_ROUTINE CompareRoutine,
  28                              IN PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine,
  29                              IN PRTL_AVL_FREE_ROUTINE FreeRoutine,
  30                              IN PVOID TableContext)
  31 {
  32     /* Setup the table */
  33     RtlZeroMemory(Table, sizeof(RTL_AVL_TABLE));
  34     Table->BalancedRoot.Parent = &Table->BalancedRoot;
  35     Table->CompareRoutine = CompareRoutine;
  36     Table->AllocateRoutine = AllocateRoutine;
  37     Table->FreeRoutine = FreeRoutine;
  38     Table->TableContext = TableContext;
  39 }
  40
  41 /*
  42  * @implemented
  43  */
  44 PVOID
  45 NTAPI
  46 RtlInsertElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table,
  47                                     IN PVOID Buffer,
  48                                     IN ULONG BufferSize,
  49                                     OUT PBOOLEAN NewElement OPTIONAL,
  50                                     IN OUT PVOID NodeOrParent,
  51                                     IN OUT TABLE_SEARCH_RESULT SearchResult)
  52 {
  53     PRTL_BALANCED_LINKS NewNode;
  54     PVOID UserData;
  55
  56     /* Check if the entry wasn't already found */
  57     if (SearchResult != TableFoundNode)
  58     {
  59         /* We're doing an allocation, sanity check */
  60         ASSERT(Table->NumberGenericTableElements != (MAXULONG - 1));
  61
  62         /* Allocate a node */
  63         NewNode = Table->AllocateRoutine(Table,
  64                                          BufferSize +
  65                                          FIELD_OFFSET(TABLE_ENTRY_HEADER,
  66                                                       UserData));
  67         if (!NewNode)
  68         {
  69             /* No memory or other allocation error, fail */
  70             if (NewElement) *NewElement = FALSE;
  71             return NULL;
  72         }
  73
  74         /* Data to return to user */
  75         UserData = &((PTABLE_ENTRY_HEADER)NewNode)->UserData;
  76
  77         /* Insert the node in the tree */
  78         RtlpInsertAvlTreeNode(Table, NewNode, NodeOrParent, SearchResult);
  79
  80         /* Copy user buffer */
  81         RtlCopyMemory(UserData, Buffer, BufferSize);
  82     }
  83     else
  84     {
  85         /* Return the node we already found */
  86         NewNode = NodeOrParent;
  87         UserData = &((PTABLE_ENTRY_HEADER)NewNode)->UserData;
  88     }
  89
  90     /* Return status */
  91     if (NewElement) *NewElement = (SearchResult == TableFoundNode);
  92
  93     /* Return pointer to user data */
  94     return UserData;
  95 }
  96
  97 /*
  98  * @implemented
  99  */
 100 PVOID
 101 NTAPI
 102 RtlInsertElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
 103                                 IN PVOID Buffer,
 104                                 IN ULONG BufferSize,
 105                                 OUT PBOOLEAN NewElement OPTIONAL)
 106 {
 107     PRTL_BALANCED_LINKS NodeOrParent = NULL;
 108     TABLE_SEARCH_RESULT Result;
 109
 110     /* Get the balanced links and table search result immediately */
 111     Result = RtlpFindAvlTableNodeOrParent(Table, Buffer, &NodeOrParent);
 112
 113     /* Now call the routine to do the full insert */
 114     return RtlInsertElementGenericTableFullAvl(Table,
 115                                                Buffer,
 116                                                BufferSize,
 117                                                NewElement,
 118                                                NodeOrParent,
 119                                                Result);
 120 }
 121
 122 /*
 123  * @implemented
 124  */
 125 BOOLEAN
 126 NTAPI
 127 RtlIsGenericTableEmptyAvl(IN PRTL_AVL_TABLE Table)
 128 {
 129     /* If there's no elements, the table is empty */
 130     return Table->NumberGenericTableElements == 0;
 131 }
 132
 133 /*
 134  * @implemented
 135  */
 136 ULONG
 137 NTAPI
 138 RtlNumberGenericTableElementsAvl(IN PRTL_AVL_TABLE Table)
 139 {
 140     /* Return the element count */
 141     return Table->NumberGenericTableElements;
 142 }
 143
 144 /*
 145  * @implemented
 146  */
 147 PVOID
 148 NTAPI
 149 RtlLookupElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table,
 150                                     IN PVOID Buffer,
 151                                     IN OUT PVOID *NodeOrParent,
 152                                     IN OUT TABLE_SEARCH_RESULT *SearchResult)
 153 {
 154     /* Find the node */
 155     *SearchResult = RtlpFindAvlTableNodeOrParent(Table,
 156                                                  Buffer,
 157                                                  (PRTL_BALANCED_LINKS*)NodeOrParent);
 158     if (*SearchResult != TableFoundNode) return NULL;
 159
 160     /* Node found, return the user data */
 161     return &((PTABLE_ENTRY_HEADER)*NodeOrParent)->UserData;
 162 }
 163
 164 /*
 165  * @implemented
 166  */
 167 PVOID
 168 NTAPI
 169 RtlLookupElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
 170                                 IN PVOID Buffer)
 171 {
 172     PRTL_BALANCED_LINKS NodeOrParent;
 173     TABLE_SEARCH_RESULT Lookup;
 174
 175     /* Call the full function */
 176     return RtlLookupElementGenericTableFullAvl(Table,
 177                                                Buffer,
 178                                                (PVOID*)&NodeOrParent,
 179                                                &Lookup);
 180 }
 181
 182 /*
 183  * @implemented
 184  */
 185 PVOID
 186 NTAPI
 187 RtlEnumerateGenericTableAvl(IN PRTL_AVL_TABLE Table,
 188                             IN BOOLEAN Restart)
 189 {
 190     /* Reset the restart key if needed */
 191     if (Restart) Table->RestartKey = NULL;
 192
 193     /* Call the full function */
 194     return RtlEnumerateGenericTableWithoutSplayingAvl(Table,
 195                                                       (PVOID*)&Table->RestartKey);
 196 }
 197
 198 /*
 199 * @implemented
 200 */
 201 PVOID
 202 NTAPI
 203 RtlLookupFirstMatchingElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
 204                                              IN PVOID Buffer,
 205                                              OUT PVOID *RestartKey)
 206 {
 207     PRTL_BALANCED_LINKS Node, PreviousNode;
 208     TABLE_SEARCH_RESULT SearchResult;
 209     RTL_GENERIC_COMPARE_RESULTS Result = GenericEqual;
 210
 211     /* Assume failure */
 212     *RestartKey = NULL;
 213
 214     /* Find the node */
 215     SearchResult = RtlpFindAvlTableNodeOrParent(Table, Buffer, &Node);
 216     if (SearchResult != TableFoundNode) return NULL;
 217
 218     /* Scan each predecessor until a match is found */
 219     PreviousNode = Node;
 220     while (Result == GenericEqual)
 221     {
 222         /* Save the node */
 223         Node = PreviousNode;
 224
 225         /* Get the predecessor */
 226         PreviousNode = RtlRealPredecessorAvl(Node);
 227         if ((!PreviousNode) || (RtlParentAvl(PreviousNode) == PreviousNode)) break;
 228
 229         /* Check if this node matches */
 230         Result = RtlpAvlCompareRoutine(Table,
 231                                        Buffer,
 232                                        &((PTABLE_ENTRY_HEADER)PreviousNode)->
 233                                        UserData);
 234     }
 235
 236     /* Save the node as the restart key, and return its data */
 237     *RestartKey = Node;
 238     return &((PTABLE_ENTRY_HEADER)Node)->UserData;
 239 }
 240
 241 /*
 242  * @unimplemented
 243  */
 244 PVOID
 245 NTAPI
 246 RtlEnumerateGenericTableWithoutSplayingAvl(IN PRTL_AVL_TABLE Table,
 247                                            IN OUT PVOID *RestartKey)
 248 {
 249     PRTL_BALANCED_LINKS CurrentNode;
 250
 251     /* Skip an empty tree */
 252     if (RtlIsGenericTableEmptyAvl(Table)) return NULL;
 253
 254     /* Check if we have a starting point */
 255     if (!*RestartKey)
 256     {
 257         /* We'll have to find it, keep going until the leftmost child */
 258         for (CurrentNode = RtlRightChildAvl(&Table->BalancedRoot);
 259              RtlLeftChildAvl(CurrentNode);
 260              CurrentNode = RtlLeftChildAvl(CurrentNode));
 261
 262         /* Found it */
 263         *RestartKey = CurrentNode;
 264     }
 265     else
 266     {
 267         /* We already had a child, keep going by getting its successor */
 268         CurrentNode = RtlRealSuccessorAvl(*RestartKey);
 269
 270         /* If there was one, update the restart key */
 271         if (CurrentNode) *RestartKey = CurrentNode;
 272     }
 273
 274     /* Return the node's data if it was found, otherwise return NULL */
 275     if (CurrentNode) return &((PTABLE_ENTRY_HEADER)CurrentNode)->UserData;
 276     return NULL;
 277 }
 278
 279 /*
 280  * @unimplemented
 281  */
 282 PVOID
 283 NTAPI
 284 RtlGetElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
 285                              IN ULONG I)
 286 {
 287     UNIMPLEMENTED;
 288         return NULL;
 289 }
 290
 291 /*
 292  * @implemented
 293  */
 294 BOOLEAN
 295 NTAPI
 296 RtlDeleteElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
 297                                 IN PVOID Buffer)
 298 {
 299     PRTL_BALANCED_LINKS Node;
 300     TABLE_SEARCH_RESULT SearchResult;
 301
 302     /* Find the node */
 303     SearchResult = RtlpFindAvlTableNodeOrParent(Table, Buffer, &Node);
 304     if (SearchResult != TableFoundNode) return FALSE;
 305
 306     /* If this node was the key, update it */
 307     if (Node == Table->RestartKey) Table->RestartKey = RtlRealPredecessorAvl(Node);
 308
 309     /* Do the delete */
 310     Table->DeleteCount++;
 311     RtlpDeleteAvlTreeNode(Table, Node);
 312     Table->NumberGenericTableElements--;
 313
 314     /* Reset accounting */
 315     Table->WhichOrderedElement = 0;
 316     Table->OrderedPointer = NULL;
 317
 318     /* Free the node's data */
 319     Table->FreeRoutine(Table, Node);
 320
 321     /* It's done */
 322     return TRUE;
 323 }
 324
 325 /* EOF */