lib/rtl/generictable.c

   1 /*
   2 * PROJECT:         ReactOS Runtime Library
   3 * LICENSE:         GPL - See COPYING in the top level directory
   4 * FILE:            lib/rtl/generictable.c
   5 * PURPOSE:         Splay Tree Generic Table Implementation
   6 * PROGRAMMERS:     Alex Ionescu (alex.ionescu@reactos.org)
   7 */
   8
   9 /* INCLUDES ******************************************************************/
  10
  11 #include <rtl.h>
  12 #define NDEBUG
  13 #include <debug.h>
  14
  15 /* Internal header for table entries */
  16 typedef struct _TABLE_ENTRY_HEADER
  17 {
  18     RTL_SPLAY_LINKS SplayLinks;
  19     LIST_ENTRY ListEntry;
  20     LONGLONG UserData;
  21 } TABLE_ENTRY_HEADER, *PTABLE_ENTRY_HEADER;
  22
  23 /* PRIVATE FUNCTIONS *********************************************************/
  24
  25 TABLE_SEARCH_RESULT
  26 NTAPI
  27 RtlpFindGenericTableNodeOrParent(IN PRTL_GENERIC_TABLE Table,
  28                                  IN PVOID Buffer,
  29                                  OUT PRTL_SPLAY_LINKS *NodeOrParent)
  30 {
  31     PRTL_SPLAY_LINKS CurrentNode, ChildNode;
  32     RTL_GENERIC_COMPARE_RESULTS Result;
  33
  34     /* Quick check to see if the table is empty */
  35     if (RtlIsGenericTableEmpty(Table))
  36     {
  37         *NodeOrParent = NULL;
  38         return TableEmptyTree;
  39     }
  40
  41     /* Set the current node */
  42     CurrentNode = Table->TableRoot;
  43
  44     /* Start compare loop */
  45     while (TRUE)
  46     {
  47         /* Do the compare */
  48         Result = Table->CompareRoutine(Table,
  49                                        Buffer,
  50                                        &((PTABLE_ENTRY_HEADER)CurrentNode)->
  51                                        UserData);
  52         if (Result == GenericLessThan)
  53         {
  54             /* We're less, check if this is the left child */
  55             if ((ChildNode = RtlLeftChild(CurrentNode)))
  56             {
  57                 /* Continue searching from this node */
  58                 CurrentNode = ChildNode;
  59             }
  60             else
  61             {
  62                 /* Otherwise, the element isn't in this tree */
  63                 *NodeOrParent = CurrentNode;
  64                 return TableInsertAsLeft;
  65             }
  66         }
  67         else if (Result == GenericGreaterThan)
  68         {
  69             /* We're more, check if this is the right child */
  70             if ((ChildNode = RtlRightChild(CurrentNode)))
  71             {
  72                 /* Continue searching from this node */
  73                 CurrentNode = ChildNode;
  74             }
  75             else
  76             {
  77                 /* Otherwise, the element isn't in this tree */
  78                 *NodeOrParent = CurrentNode;
  79                 return TableInsertAsRight;
  80             }
  81         }
  82         else
  83         {
  84             /* We should've found the node */
  85             ASSERT(Result == GenericEqual);
  86
  87             /* Return node found */
  88             *NodeOrParent = CurrentNode;
  89             return TableFoundNode;
  90         }
  91     }
  92 }
  93
  94 /* SPLAY FUNCTIONS ***********************************************************/
  95
  96 /*
  97  * @implemented
  98  */
  99 VOID
 100 NTAPI
 101 RtlInitializeGenericTable(IN PRTL_GENERIC_TABLE Table,
 102                           IN PRTL_GENERIC_COMPARE_ROUTINE CompareRoutine,
 103                           IN PRTL_GENERIC_ALLOCATE_ROUTINE AllocateRoutine,
 104                           IN PRTL_GENERIC_FREE_ROUTINE FreeRoutine,
 105                           IN PVOID TableContext)
 106 {
 107     /* Initialize the table to default and passed values */
 108     InitializeListHead(&Table->InsertOrderList);
 109     Table->TableRoot = NULL;
 110     Table->NumberGenericTableElements = 0;
 111     Table->WhichOrderedElement = 0;
 112     Table->OrderedPointer = &Table->InsertOrderList;
 113     Table->CompareRoutine = CompareRoutine;
 114     Table->AllocateRoutine = AllocateRoutine;
 115     Table->FreeRoutine = FreeRoutine;
 116     Table->TableContext = TableContext;
 117 }
 118
 119 /*
 120  * @implemented
 121  */
 122 PVOID
 123 NTAPI
 124 RtlInsertElementGenericTable(IN PRTL_GENERIC_TABLE Table,
 125                              IN PVOID Buffer,
 126                              IN ULONG BufferSize,
 127                              OUT PBOOLEAN NewElement OPTIONAL)
 128 {
 129     PRTL_SPLAY_LINKS NodeOrParent;
 130     TABLE_SEARCH_RESULT Result;
 131
 132     /* Get the splay links and table search result immediately */
 133     Result = RtlpFindGenericTableNodeOrParent(Table, Buffer, &NodeOrParent);
 134
 135     /* Now call the routine to do the full insert */
 136     return RtlInsertElementGenericTableFull(Table,
 137                                             Buffer,
 138                                             BufferSize,
 139                                             NewElement,
 140                                             NodeOrParent,
 141                                             Result);
 142 }
 143
 144 /*
 145  * @implemented
 146  */
 147 PVOID
 148 NTAPI
 149 RtlInsertElementGenericTableFull(IN PRTL_GENERIC_TABLE Table,
 150                                  IN PVOID Buffer,
 151                                  IN ULONG BufferSize,
 152                                  OUT PBOOLEAN NewElement OPTIONAL,
 153                                  IN PVOID NodeOrParent,
 154                                  IN TABLE_SEARCH_RESULT SearchResult)
 155 {
 156     PRTL_SPLAY_LINKS NewNode;
 157
 158     /* Check if the entry wasn't already found */
 159     if (SearchResult != TableFoundNode)
 160     {
 161         /* We're doing an allocation, sanity check */
 162         ASSERT(Table->NumberGenericTableElements != (MAXULONG - 1));
 163
 164         /* Allocate a node */
 165         NewNode = Table->AllocateRoutine(Table,
 166                                          BufferSize +
 167                                          FIELD_OFFSET(TABLE_ENTRY_HEADER,
 168                                                       UserData));
 169         if (!NewNode)
 170         {
 171             /* No memory or other allocation error, fail */
 172             if (NewElement) *NewElement = FALSE;
 173             return NULL;
 174         }
 175
 176         /* Initialize the new inserted element */
 177         RtlInitializeSplayLinks(NewNode);
 178         InsertTailList(&Table->InsertOrderList,
 179                        &((PTABLE_ENTRY_HEADER)NewNode)->ListEntry);
 180
 181         /* Increase element count */
 182         Table->NumberGenericTableElements++;
 183
 184         /* Check where we should insert the entry */
 185         if (SearchResult == TableEmptyTree)
 186         {
 187             /* This is the new root node */
 188             Table->TableRoot = NewNode;
 189         }
 190         else if (SearchResult == TableInsertAsLeft)
 191         {
 192             /* Insert it left */
 193             RtlInsertAsLeftChild(NodeOrParent, NewNode);
 194         }
 195         else
 196         {
 197             /* Right node */
 198             RtlInsertAsRightChild(NodeOrParent, NewNode);
 199         }
 200
 201         /* Copy user buffer */
 202         RtlCopyMemory(&((PTABLE_ENTRY_HEADER)NewNode)->UserData,
 203                       Buffer,
 204                       BufferSize);
 205     }
 206     else
 207     {
 208         /* Return the node we already found */
 209         NewNode = NodeOrParent;
 210     }
 211
 212     /* Splay the tree */
 213     Table->TableRoot = RtlSplay(NewNode);
 214
 215     /* Return status */
 216     if (NewElement) *NewElement = (SearchResult == TableFoundNode);
 217
 218     /* Return pointer to user data */
 219     return &((PTABLE_ENTRY_HEADER)NewNode)->UserData;
 220 }
 221
 222 /*
 223  * @implemented
 224  */
 225 BOOLEAN
 226 NTAPI
 227 RtlIsGenericTableEmpty(IN PRTL_GENERIC_TABLE Table)
 228 {
 229     /* Check if the table root is empty */
 230     return (Table->TableRoot) ? FALSE: TRUE;
 231 }
 232
 233 /*
 234  * @implemented
 235  */
 236 ULONG
 237 NTAPI
 238 RtlNumberGenericTableElements(IN PRTL_GENERIC_TABLE Table)
 239 {
 240     /* Return the number of elements */
 241     return Table->NumberGenericTableElements;
 242 }
 243
 244 /*
 245  * @implemented
 246  */
 247 PVOID
 248 NTAPI
 249 RtlLookupElementGenericTable(IN PRTL_GENERIC_TABLE Table,
 250                              IN PVOID Buffer)
 251 {
 252     PRTL_SPLAY_LINKS NodeOrParent;
 253     TABLE_SEARCH_RESULT Result;
 254
 255     /* Call the full version */
 256     return RtlLookupElementGenericTableFull(Table,
 257                                             Buffer,
 258                                             (PVOID)&NodeOrParent,
 259                                             &Result);
 260 }
 261
 262 /*
 263  * @implemented
 264  */
 265 PVOID
 266 NTAPI
 267 RtlLookupElementGenericTableFull(IN PRTL_GENERIC_TABLE Table,
 268                                  IN PVOID Buffer,
 269                                  OUT PVOID *NodeOrParent,
 270                                  OUT TABLE_SEARCH_RESULT *SearchResult)
 271 {
 272     /* Do the initial lookup */
 273     *SearchResult = RtlpFindGenericTableNodeOrParent(Table,
 274                                                      Buffer,
 275                                                      (PRTL_SPLAY_LINKS *)
 276                                                      NodeOrParent);
 277
 278     /* Check if we found anything */
 279     if ((*SearchResult == TableEmptyTree) || (*SearchResult != TableFoundNode))
 280     {
 281         /* Nothing found */
 282         return NULL;
 283     }
 284
 285     /* Otherwise, splay the tree and return this entry */
 286     Table->TableRoot = RtlSplay(*NodeOrParent);
 287     return &((PTABLE_ENTRY_HEADER)*NodeOrParent)->UserData;
 288 }
 289
 290 /*
 291  * @implemented
 292  */
 293 BOOLEAN
 294 NTAPI
 295 RtlDeleteElementGenericTable(IN PRTL_GENERIC_TABLE Table,
 296                              IN PVOID Buffer)
 297 {
 298     PRTL_SPLAY_LINKS NodeOrParent;
 299     TABLE_SEARCH_RESULT Result;
 300
 301     /* Get the splay links and table search result immediately */
 302     Result = RtlpFindGenericTableNodeOrParent(Table, Buffer, &NodeOrParent);
 303     if ((Result == TableEmptyTree) || (Result != TableFoundNode))
 304     {
 305         /* Nothing to delete */
 306         return FALSE;
 307     }
 308
 309     /* Delete the entry */
 310     Table->TableRoot = RtlDelete(NodeOrParent);
 311     RemoveEntryList(&((PTABLE_ENTRY_HEADER)NodeOrParent)->ListEntry);
 312
 313     /* Update accounting data */
 314     Table->NumberGenericTableElements--;
 315     Table->WhichOrderedElement = 0;
 316     Table->OrderedPointer = &Table->InsertOrderList;
 317
 318     /* Free the entry */
 319     Table->FreeRoutine(Table, NodeOrParent);
 320     return TRUE;
 321 }
 322
 323 /*
 324  * @implemented
 325  */
 326 PVOID
 327 NTAPI
 328 RtlEnumerateGenericTable(IN PRTL_GENERIC_TABLE Table,
 329                          IN BOOLEAN Restart)
 330 {
 331     PRTL_SPLAY_LINKS FoundNode;
 332
 333     /* Check if the table is empty */
 334     if (RtlIsGenericTableEmpty(Table)) return NULL;
 335
 336     /* Check if we have to restart */
 337     if (Restart)
 338     {
 339         /* Then find the leftmost element */
 340         FoundNode = Table->TableRoot;
 341         do
 342         {
 343             /* Get the left child */
 344             FoundNode = RtlLeftChild(FoundNode);
 345         } while(RtlLeftChild(FoundNode));
 346
 347         /* Splay it */
 348         Table->TableRoot = RtlSplay(FoundNode);
 349     }
 350     else
 351     {
 352         /* Otherwise, try using the real successor */
 353         FoundNode = RtlRealSuccessor(Table->TableRoot);
 354         if (FoundNode) Table->TableRoot = RtlSplay(FoundNode);
 355     }
 356
 357     /* Check if we found the node and return it */
 358     return FoundNode ? &((PTABLE_ENTRY_HEADER)FoundNode)->UserData : NULL;
 359 }
 360
 361 /*
 362  * @implemented
 363  */
 364 PVOID
 365 NTAPI
 366 RtlEnumerateGenericTableWithoutSplaying(IN PRTL_GENERIC_TABLE Table,
 367                                         IN OUT PVOID *RestartKey)
 368 {
 369     PRTL_SPLAY_LINKS FoundNode;
 370
 371     /* Check if the table is empty */
 372     if (RtlIsGenericTableEmpty(Table)) return NULL;
 373
 374     /* Check if we have to restart */
 375     if (!(*RestartKey))
 376     {
 377         /* Then find the leftmost element */
 378         FoundNode = Table->TableRoot;
 379         do
 380         {
 381             /* Get the left child */
 382             FoundNode = RtlLeftChild(FoundNode);
 383         } while(RtlLeftChild(FoundNode));
 384
 385         /* Splay it */
 386         *RestartKey = FoundNode;
 387     }
 388     else
 389     {
 390         /* Otherwise, try using the real successor */
 391         FoundNode = RtlRealSuccessor(*RestartKey);
 392         if (FoundNode) *RestartKey = FoundNode;
 393     }
 394
 395     /* Check if we found the node and return it */
 396     return FoundNode ? &((PTABLE_ENTRY_HEADER)FoundNode)->UserData : NULL;
 397 }
 398
 399 /*
 400  * @unimplemented
 401  */
 402 PVOID
 403 NTAPI
 404 RtlEnumerateGenericTableLikeADirectory(IN PRTL_AVL_TABLE Table,
 405                                        IN PRTL_AVL_MATCH_FUNCTION MatchFunction,
 406                                        IN PVOID MatchData,
 407                                        IN ULONG NextFlag,
 408                                        IN OUT PVOID *RestartKey,
 409                                        IN OUT PULONG DeleteCount,
 410                                        IN OUT PVOID Buffer)
 411 {
 412     UNIMPLEMENTED;
 413     return 0;
 414 }
 415
 416 /*
 417  * @implemented
 418  */
 419 PVOID
 420 NTAPI
 421 RtlGetElementGenericTable(IN PRTL_GENERIC_TABLE Table,
 422                           IN ULONG I)
 423 {
 424     ULONG OrderedElement, ElementCount;
 425     PLIST_ENTRY OrderedNode;
 426     ULONG DeltaUp, DeltaDown;
 427     ULONG NextI = I + 1;
 428
 429     /* Setup current accounting data */
 430     OrderedNode = Table->OrderedPointer;
 431     OrderedElement = Table->WhichOrderedElement;
 432     ElementCount = Table->NumberGenericTableElements;
 433
 434     /* Sanity checks */
 435     if ((I == MAXULONG) || (NextI > ElementCount)) return NULL;
 436
 437     /* Check if we already found the entry */
 438     if (NextI == OrderedElement)
 439     {
 440         /* Return it */
 441         return &((PTABLE_ENTRY_HEADER)CONTAINING_RECORD(OrderedNode,
 442                                                         TABLE_ENTRY_HEADER,
 443                                                         ListEntry))->UserData;
 444     }
 445
 446     /* Now check if we're farther behind */
 447     if (OrderedElement > NextI)
 448     {
 449         /* Find out if the distance is more then the half-way point */
 450         if (NextI > (OrderedElement / 2))
 451         {
 452             /* Do the search backwards, since this takes less iterations */
 453             DeltaDown = OrderedElement - NextI;
 454             do
 455             {
 456                 /* Get next node */
 457                 OrderedNode = OrderedNode->Blink;
 458             } while (--DeltaDown);
 459         }
 460         else
 461         {
 462             /* Follow the list directly instead */
 463             OrderedNode = &Table->InsertOrderList;
 464             do
 465             {
 466                 /* Get next node */
 467                 OrderedNode = OrderedNode->Flink;
 468             } while (--NextI);
 469         }
 470     }
 471     else
 472     {
 473         /* We are farther ahead, calculate distances */
 474         DeltaUp = NextI - OrderedElement;
 475         DeltaDown = (ElementCount - NextI) + 1;
 476
 477         /* Check if the up distance is smaller then the down distance */
 478         if (DeltaUp <= DeltaDown)
 479         {
 480             /* Do the search forwards, since this takes less iterations */
 481             do
 482             {
 483                 /* Get next node */
 484                 OrderedNode = OrderedNode->Blink;
 485             } while (--DeltaUp);
 486         }
 487         else
 488         {
 489             /* Do the search downwards, since this takes less iterations */
 490             OrderedNode = &Table->InsertOrderList;
 491             do
 492             {
 493                 /* Get next node */
 494                 OrderedNode = OrderedNode->Blink;
 495             } while (--DeltaDown);
 496         }
 497     }
 498
 499     /* Got the element, save it */
 500     Table->OrderedPointer = OrderedNode;
 501     Table->WhichOrderedElement = NextI;
 502
 503     /* Return the element */
 504     return &((PTABLE_ENTRY_HEADER)CONTAINING_RECORD(OrderedNode,
 505                                                     TABLE_ENTRY_HEADER,
 506                                                     ListEntry))->UserData;
 507 }
 508
 509 /* EOF */