sdk/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         RtlZeroMemory(NewNode, sizeof(RTL_BALANCED_LINKS));
  79         RtlpInsertAvlTreeNode(Table, NewNode, NodeOrParent, SearchResult);
  80
  81         /* Copy user buffer */
  82         RtlCopyMemory(UserData, Buffer, BufferSize);
  83     }
  84     else
  85     {
  86         /* Return the node we already found */
  87         NewNode = NodeOrParent;
  88         UserData = &((PTABLE_ENTRY_HEADER)NewNode)->UserData;
  89     }
  90
  91     /* Return status */
  92     if (NewElement) *NewElement = (SearchResult != TableFoundNode);
  93
  94     /* Return pointer to user data */
  95     return UserData;
  96 }
  97
  98 /*
  99  * @implemented
 100  */
 101 PVOID
 102 NTAPI
 103 RtlInsertElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
 104                                 IN PVOID Buffer,
 105                                 IN ULONG BufferSize,
 106                                 OUT PBOOLEAN NewElement OPTIONAL)
 107 {
 108     PRTL_BALANCED_LINKS NodeOrParent = NULL;
 109     TABLE_SEARCH_RESULT Result;
 110
 111     /* Get the balanced links and table search result immediately */
 112     Result = RtlpFindAvlTableNodeOrParent(Table, Buffer, &NodeOrParent);
 113
 114     /* Now call the routine to do the full insert */
 115     return RtlInsertElementGenericTableFullAvl(Table,
 116                                                Buffer,
 117                                                BufferSize,
 118                                                NewElement,
 119                                                NodeOrParent,
 120                                                Result);
 121 }
 122
 123 /*
 124  * @implemented
 125  */
 126 BOOLEAN
 127 NTAPI
 128 RtlIsGenericTableEmptyAvl(IN PRTL_AVL_TABLE Table)
 129 {
 130     /* If there's no elements, the table is empty */
 131     return Table->NumberGenericTableElements == 0;
 132 }
 133
 134 /*
 135  * @implemented
 136  */
 137 ULONG
 138 NTAPI
 139 RtlNumberGenericTableElementsAvl(IN PRTL_AVL_TABLE Table)
 140 {
 141     /* Return the element count */
 142     return Table->NumberGenericTableElements;
 143 }
 144
 145 /*
 146  * @implemented
 147  */
 148 PVOID
 149 NTAPI
 150 RtlLookupElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table,
 151                                     IN PVOID Buffer,
 152                                     IN OUT PVOID *NodeOrParent,
 153                                     IN OUT TABLE_SEARCH_RESULT *SearchResult)
 154 {
 155     /* Find the node */
 156     *SearchResult = RtlpFindAvlTableNodeOrParent(Table,
 157                                                  Buffer,
 158                                                  (PRTL_BALANCED_LINKS*)NodeOrParent);
 159     if (*SearchResult != TableFoundNode) return NULL;
 160
 161     /* Node found, return the user data */
 162     return &((PTABLE_ENTRY_HEADER)*NodeOrParent)->UserData;
 163 }
 164
 165 /*
 166  * @implemented
 167  */
 168 PVOID
 169 NTAPI
 170 RtlLookupElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
 171                                 IN PVOID Buffer)
 172 {
 173     PRTL_BALANCED_LINKS NodeOrParent;
 174     TABLE_SEARCH_RESULT Lookup;
 175
 176     /* Call the full function */
 177     return RtlLookupElementGenericTableFullAvl(Table,
 178                                                Buffer,
 179                                                (PVOID*)&NodeOrParent,
 180                                                &Lookup);
 181 }
 182
 183 /*
 184  * @implemented
 185  */
 186 PVOID
 187 NTAPI
 188 RtlEnumerateGenericTableAvl(IN PRTL_AVL_TABLE Table,
 189                             IN BOOLEAN Restart)
 190 {
 191     /* Reset the restart key if needed */
 192     if (Restart) Table->RestartKey = NULL;
 193
 194     /* Call the full function */
 195     return RtlEnumerateGenericTableWithoutSplayingAvl(Table,
 196                                                       (PVOID*)&Table->RestartKey);
 197 }
 198
 199 /*
 200 * @implemented
 201 */
 202 PVOID
 203 NTAPI
 204 RtlLookupFirstMatchingElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
 205                                              IN PVOID Buffer,
 206                                              OUT PVOID *RestartKey)
 207 {
 208     PRTL_BALANCED_LINKS Node, PreviousNode;
 209     TABLE_SEARCH_RESULT SearchResult;
 210     RTL_GENERIC_COMPARE_RESULTS Result = GenericEqual;
 211
 212     /* Assume failure */
 213     *RestartKey = NULL;
 214
 215     /* Find the node */
 216     SearchResult = RtlpFindAvlTableNodeOrParent(Table, Buffer, &Node);
 217     if (SearchResult != TableFoundNode) return NULL;
 218
 219     /* Scan each predecessor until a match is found */
 220     PreviousNode = Node;
 221     while (Result == GenericEqual)
 222     {
 223         /* Save the node */
 224         Node = PreviousNode;
 225
 226         /* Get the predecessor */
 227         PreviousNode = RtlRealPredecessorAvl(Node);
 228         if ((!PreviousNode) || (RtlParentAvl(PreviousNode) == PreviousNode)) break;
 229
 230         /* Check if this node matches */
 231         Result = RtlpAvlCompareRoutine(Table,
 232                                        Buffer,
 233                                        &((PTABLE_ENTRY_HEADER)PreviousNode)->
 234                                        UserData);
 235     }
 236
 237     /* Save the node as the restart key, and return its data */
 238     *RestartKey = Node;
 239     return &((PTABLE_ENTRY_HEADER)Node)->UserData;
 240 }
 241
 242 /*
 243  * @unimplemented
 244  */
 245 PVOID
 246 NTAPI
 247 RtlEnumerateGenericTableWithoutSplayingAvl(IN PRTL_AVL_TABLE Table,
 248                                            IN OUT PVOID *RestartKey)
 249 {
 250     PRTL_BALANCED_LINKS CurrentNode;
 251
 252     /* Skip an empty tree */
 253     if (RtlIsGenericTableEmptyAvl(Table)) return NULL;
 254
 255     /* Check if we have a starting point */
 256     if (!*RestartKey)
 257     {
 258         /* We'll have to find it, keep going until the leftmost child */
 259         for (CurrentNode = RtlRightChildAvl(&Table->BalancedRoot);
 260              RtlLeftChildAvl(CurrentNode);
 261              CurrentNode = RtlLeftChildAvl(CurrentNode));
 262
 263         /* Found it */
 264         *RestartKey = CurrentNode;
 265     }
 266     else
 267     {
 268         /* We already had a child, keep going by getting its successor */
 269         CurrentNode = RtlRealSuccessorAvl(*RestartKey);
 270
 271         /* If there was one, update the restart key */
 272         if (CurrentNode) *RestartKey = CurrentNode;
 273     }
 274
 275     /* Return the node's data if it was found, otherwise return NULL */
 276     if (CurrentNode) return &((PTABLE_ENTRY_HEADER)CurrentNode)->UserData;
 277     return NULL;
 278 }
 279
 280 /*
 281  * @unimplemented
 282  */
 283 PVOID
 284 NTAPI
 285 RtlGetElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
 286                              IN ULONG I)
 287 {
 288     UNIMPLEMENTED;
 289         return NULL;
 290 }
 291
 292 /*
 293  * @implemented
 294  */
 295 BOOLEAN
 296 NTAPI
 297 RtlDeleteElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
 298                                 IN PVOID Buffer)
 299 {
 300     PRTL_BALANCED_LINKS Node;
 301     TABLE_SEARCH_RESULT SearchResult;
 302
 303     /* Find the node */
 304     SearchResult = RtlpFindAvlTableNodeOrParent(Table, Buffer, &Node);
 305     if (SearchResult != TableFoundNode) return FALSE;
 306
 307     /* If this node was the key, update it */
 308     if (Node == Table->RestartKey) Table->RestartKey = RtlRealPredecessorAvl(Node);
 309
 310     /* Do the delete */
 311     Table->DeleteCount++;
 312     RtlpDeleteAvlTreeNode(Table, Node);
 313     Table->NumberGenericTableElements--;
 314
 315     /* Reset accounting */
 316     Table->WhichOrderedElement = 0;
 317     Table->OrderedPointer = NULL;
 318
 319     /* Free the node's data */
 320     Table->FreeRoutine(Table, Node);
 321
 322     /* It's done */
 323     return TRUE;
 324 }
 325
 326 /* EOF */