reactos/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         return TableEmptyTree;
  38     }
  39
  40     /* Set the current node */
  41     CurrentNode = Table->TableRoot;
  42
  43     /* Start compare loop */
  44     while (TRUE)
  45     {
  46         /* Do the compare */
  47         Result = Table->CompareRoutine(Table,
  48                                        Buffer,
  49                                        &((PTABLE_ENTRY_HEADER)CurrentNode)->
  50                                        UserData);
  51         if (Result == GenericLessThan)
  52         {
  53             /* We're less, check if this is the left child */
  54             if ((ChildNode = RtlLeftChild(CurrentNode)))
  55             {
  56                 /* Continue searching from this node */
  57                 CurrentNode = ChildNode;
  58             }
  59             else
  60             {
  61                 /* Otherwise, the element isn't in this tree */
  62                 *NodeOrParent = CurrentNode;
  63                 return TableInsertAsLeft;
  64             }
  65         }
  66         else if (Result == GenericGreaterThan)
  67         {
  68             /* We're more, check if this is the right child */
  69             if ((ChildNode = RtlRightChild(CurrentNode)))
  70             {
  71                 /* Continue searching from this node */
  72                 CurrentNode = ChildNode;
  73             }
  74             else
  75             {
  76                 /* Otherwise, the element isn't in this tree */
  77                 *NodeOrParent = CurrentNode;
  78                 return TableInsertAsRight;
  79             }
  80         }
  81         else
  82         {
  83             /* We should've found the node */
  84             ASSERT(Result == GenericEqual);
  85
  86             /* Return node found */
  87             *NodeOrParent = CurrentNode;
  88             return TableFoundNode;
  89         }
  90     }
  91 }
  92
  93 /* SPLAY FUNCTIONS ***********************************************************/
  94
  95 /*
  96  * @implemented
  97  */
  98 VOID
  99 NTAPI
 100 RtlInitializeGenericTable(IN PRTL_GENERIC_TABLE Table,
 101                           IN PRTL_GENERIC_COMPARE_ROUTINE CompareRoutine,
 102                           IN PRTL_GENERIC_ALLOCATE_ROUTINE AllocateRoutine,
 103                           IN PRTL_GENERIC_FREE_ROUTINE FreeRoutine,
 104                           IN PVOID TableContext)
 105 {
 106     /* Initialize the table to default and passed values */
 107     InitializeListHead(&Table->InsertOrderList);
 108     Table->TableRoot = NULL;
 109     Table->NumberGenericTableElements = 0;
 110     Table->WhichOrderedElement = 0;
 111     Table->OrderedPointer = &Table->InsertOrderList;
 112     Table->CompareRoutine = CompareRoutine;
 113     Table->AllocateRoutine = AllocateRoutine;
 114     Table->FreeRoutine = FreeRoutine;
 115     Table->TableContext = TableContext;
 116 }
 117
 118 /*
 119  * @implemented
 120  */
 121 PVOID
 122 NTAPI
 123 RtlInsertElementGenericTable(IN PRTL_GENERIC_TABLE Table,
 124                              IN PVOID Buffer,
 125                              IN ULONG BufferSize,
 126                              OUT PBOOLEAN NewElement OPTIONAL)
 127 {
 128     PRTL_SPLAY_LINKS NodeOrParent;
 129     TABLE_SEARCH_RESULT Result;
 130
 131     /* Get the splay links and table search result immediately */
 132     Result = RtlpFindGenericTableNodeOrParent(Table, Buffer, &NodeOrParent);
 133
 134     /* Now call the routine to do the full insert */
 135     return RtlInsertElementGenericTableFull(Table,
 136                                             Buffer,
 137                                             BufferSize,
 138                                             NewElement,
 139                                             NodeOrParent,
 140                                             Result);
 141 }
 142
 143 /*
 144  * @implemented
 145  */
 146 PVOID
 147 NTAPI
 148 RtlInsertElementGenericTableFull(IN PRTL_GENERIC_TABLE Table,
 149                                  IN PVOID Buffer,
 150                                  IN ULONG BufferSize,
 151                                  OUT PBOOLEAN NewElement OPTIONAL,
 152                                  IN PVOID NodeOrParent,
 153                                  IN TABLE_SEARCH_RESULT SearchResult)
 154 {
 155     PRTL_SPLAY_LINKS NewNode;
 156
 157     /* Check if the entry wasn't already found */
 158     if (SearchResult != TableFoundNode)
 159     {
 160         /* We're doing an allocation, sanity check */
 161         ASSERT(Table->NumberGenericTableElements != (MAXULONG - 1));
 162
 163         /* Allocate a node */
 164         NewNode = Table->AllocateRoutine(Table,
 165                                          BufferSize +
 166                                          FIELD_OFFSET(TABLE_ENTRY_HEADER,
 167                                                       UserData));
 168         if (!NewNode)
 169         {
 170             /* No memory or other allocation error, fail */
 171             if (NewElement) *NewElement = FALSE;
 172             return NULL;
 173         }
 174
 175         /* Initialize the new inserted element */
 176         RtlInitializeSplayLinks(NewNode);
 177         InsertTailList(&Table->InsertOrderList,
 178                        &((PTABLE_ENTRY_HEADER)NewNode)->ListEntry);
 179
 180         /* Increase element count */
 181         Table->NumberGenericTableElements++;
 182
 183         /* Check where we should insert the entry */
 184         if (SearchResult == TableEmptyTree)
 185         {
 186             /* This is the new root node */
 187             Table->TableRoot = NewNode;
 188         }
 189         else if (SearchResult == TableInsertAsLeft)
 190         {
 191             /* Insert it left */
 192             RtlInsertAsLeftChild(NodeOrParent, NewNode);
 193         }
 194         else
 195         {
 196             /* Right node */
 197             RtlInsertAsRightChild(NodeOrParent, NewNode);
 198         }
 199
 200         /* Copy user buffer */
 201         RtlCopyMemory(&((PTABLE_ENTRY_HEADER)NewNode)->UserData,
 202                       Buffer,
 203                       BufferSize);
 204     }
 205     else
 206     {
 207         /* Return the node we already found */
 208         NewNode = NodeOrParent;
 209     }
 210
 211     /* Splay the tree */
 212     Table->TableRoot = RtlSplay(NewNode);
 213
 214     /* Return status */
 215     if (NewElement) *NewElement = (SearchResult != TableFoundNode);
 216
 217     /* Return pointer to user data */
 218     return &((PTABLE_ENTRY_HEADER)NewNode)->UserData;
 219 }
 220
 221 /*
 222  * @implemented
 223  */
 224 BOOLEAN
 225 NTAPI
 226 RtlIsGenericTableEmpty(IN PRTL_GENERIC_TABLE Table)
 227 {
 228     /* Check if the table root is empty */
 229     return (Table->TableRoot) ? FALSE: TRUE;
 230 }
 231
 232 /*
 233  * @implemented
 234  */
 235 ULONG
 236 NTAPI
 237 RtlNumberGenericTableElements(IN PRTL_GENERIC_TABLE Table)
 238 {
 239     /* Return the number of elements */
 240     return Table->NumberGenericTableElements;
 241 }
 242
 243 /*
 244  * @implemented
 245  */
 246 PVOID
 247 NTAPI
 248 RtlLookupElementGenericTable(IN PRTL_GENERIC_TABLE Table,
 249                              IN PVOID Buffer)
 250 {
 251     PRTL_SPLAY_LINKS NodeOrParent;
 252     TABLE_SEARCH_RESULT Result;
 253
 254     /* Call the full version */
 255     return RtlLookupElementGenericTableFull(Table,
 256                                             Buffer,
 257                                             (PVOID)&NodeOrParent,
 258                                             &Result);
 259 }
 260
 261 /*
 262  * @implemented
 263  */
 264 PVOID
 265 NTAPI
 266 RtlLookupElementGenericTableFull(IN PRTL_GENERIC_TABLE Table,
 267                                  IN PVOID Buffer,
 268                                  OUT PVOID *NodeOrParent,
 269                                  OUT TABLE_SEARCH_RESULT *SearchResult)
 270 {
 271     /* Do the initial lookup */
 272     *SearchResult = RtlpFindGenericTableNodeOrParent(Table,
 273                                                      Buffer,
 274                                                      (PRTL_SPLAY_LINKS *)
 275                                                      NodeOrParent);
 276
 277     /* Check if we found anything */
 278     if ((*SearchResult == TableEmptyTree) || (*SearchResult != TableFoundNode))
 279     {
 280         /* Nothing found */
 281         return NULL;
 282     }
 283
 284     /* Otherwise, splay the tree and return this entry */
 285     Table->TableRoot = RtlSplay(*NodeOrParent);
 286     return &((PTABLE_ENTRY_HEADER)*NodeOrParent)->UserData;
 287 }
 288
 289 /*
 290  * @implemented
 291  */
 292 BOOLEAN
 293 NTAPI
 294 RtlDeleteElementGenericTable(IN PRTL_GENERIC_TABLE Table,
 295                              IN PVOID Buffer)
 296 {
 297     PRTL_SPLAY_LINKS NodeOrParent;
 298     TABLE_SEARCH_RESULT Result;
 299
 300     /* Get the splay links and table search result immediately */
 301     Result = RtlpFindGenericTableNodeOrParent(Table, Buffer, &NodeOrParent);
 302     if (Result != TableFoundNode)
 303     {
 304         /* Nothing to delete */
 305         return FALSE;
 306     }
 307
 308     /* Delete the entry */
 309     Table->TableRoot = RtlDelete(NodeOrParent);
 310     RemoveEntryList(&((PTABLE_ENTRY_HEADER)NodeOrParent)->ListEntry);
 311
 312     /* Update accounting data */
 313     Table->NumberGenericTableElements--;
 314     Table->WhichOrderedElement = 0;
 315     Table->OrderedPointer = &Table->InsertOrderList;
 316
 317     /* Free the entry */
 318     Table->FreeRoutine(Table, NodeOrParent);
 319     return TRUE;
 320 }
 321
 322 /*
 323  * @implemented
 324  */
 325 PVOID
 326 NTAPI
 327 RtlEnumerateGenericTable(IN PRTL_GENERIC_TABLE Table,
 328                          IN BOOLEAN Restart)
 329 {
 330     PRTL_SPLAY_LINKS FoundNode;
 331
 332     /* Check if the table is empty */
 333     if (RtlIsGenericTableEmpty(Table)) return NULL;
 334
 335     /* Check if we have to restart */
 336     if (Restart)
 337     {
 338         /* Then find the leftmost element */
 339         FoundNode = Table->TableRoot;
 340         while(RtlLeftChild(FoundNode))
 341         {
 342             /* Get the left child */
 343             FoundNode = RtlLeftChild(FoundNode);
 344         }
 345
 346         /* Splay it */
 347         _Analysis_assume_(FoundNode != NULL);
 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         while(RtlLeftChild(FoundNode))
 380         {
 381             /* Get the left child */
 382             FoundNode = RtlLeftChild(FoundNode);
 383         }
 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             while (DeltaDown)
 455             {
 456                 /* Get next node */
 457                 OrderedNode = OrderedNode->Blink;
 458                 DeltaDown--;
 459             }
 460         }
 461         else
 462         {
 463             /* Follow the list directly instead */
 464             OrderedNode = &Table->InsertOrderList;
 465             while (NextI)
 466             {
 467                 /* Get next node */
 468                 OrderedNode = OrderedNode->Flink;
 469                 NextI--;
 470             }
 471         }
 472     }
 473     else
 474     {
 475         /* We are farther ahead, calculate distances */
 476         DeltaUp = NextI - OrderedElement;
 477         DeltaDown = (ElementCount - NextI) + 1;
 478
 479         /* Check if the up distance is smaller then the down distance */
 480         if (DeltaUp <= DeltaDown)
 481         {
 482             /* Do the search forwards, since this takes less iterations */
 483             while (DeltaUp)
 484             {
 485                 /* Get next node */
 486                 OrderedNode = OrderedNode->Blink;
 487                 DeltaUp--;
 488             }
 489         }
 490         else
 491         {
 492             /* Do the search downwards, since this takes less iterations */
 493             OrderedNode = &Table->InsertOrderList;
 494             while (DeltaDown)
 495             {
 496                 /* Get next node */
 497                 OrderedNode = OrderedNode->Blink;
 498                 DeltaDown--;
 499             }
 500         }
 501     }
 502
 503     /* Got the element, save it */
 504     Table->OrderedPointer = OrderedNode;
 505     Table->WhichOrderedElement = NextI;
 506
 507     /* Return the element */
 508     return &((PTABLE_ENTRY_HEADER)CONTAINING_RECORD(OrderedNode,
 509                                                     TABLE_ENTRY_HEADER,
 510                                                     ListEntry))->UserData;
 511 }
 512
 513 /* EOF */