reactos/lib/rtl/generictable.c

   1 /*
   2 * PROJECT:         ReactOS Kernel
   3 * LICENSE:         GPL - See COPYING in the top level directory
   4 * FILE:            lib/rtl/generictable.c
   5 * PURPOSE:         Splay Tree and AVL Tree Generic Table Implementation
   6 * PROGRAMMERS:     Alex Ionescu (alex.ionescu@reactos.org)
   7 *                  Art Yerks (ayerkes@speakeasy.net)
   8 */
   9
  10 /* INCLUDES ******************************************************************/
  11
  12 #include <rtl.h>
  13 #include "austin/avl.h"
  14 #define NDEBUG
  15 #include <debug.h>
  16
  17 /* Internal header for table entries */
  18 typedef struct _TABLE_ENTRY_HEADER
  19 {
  20     RTL_SPLAY_LINKS SplayLinks;
  21     LIST_ENTRY ListEntry;
  22     LONGLONG UserData;
  23 } TABLE_ENTRY_HEADER, *PTABLE_ENTRY_HEADER;
  24
  25 /* PRIVATE FUNCTIONS *********************************************************/
  26
  27 TABLE_SEARCH_RESULT
  28 NTAPI
  29 RtlpFindGenericTableNodeOrParent(IN PRTL_GENERIC_TABLE Table,
  30                                  IN PVOID Buffer,
  31                                  OUT PRTL_SPLAY_LINKS *NodeOrParent)
  32 {
  33     PRTL_SPLAY_LINKS CurrentNode, ChildNode;
  34     RTL_GENERIC_COMPARE_RESULTS Result;
  35
  36     /* Quick check to see if the table is empty */
  37     if (RtlIsGenericTableEmpty(Table))
  38     {
  39         *NodeOrParent = NULL;
  40         return TableEmptyTree;
  41     }
  42
  43     /* Set the current node */
  44     CurrentNode = Table->TableRoot;
  45
  46     /* Start compare loop */
  47     while (TRUE)
  48     {
  49         /* Do the compare */
  50         Result = Table->CompareRoutine(Table,
  51                                        Buffer,
  52                                        &((PTABLE_ENTRY_HEADER)CurrentNode)->
  53                                        UserData);
  54         if (Result == GenericLessThan)
  55         {
  56             /* We're less, check if this is the left child */
  57             if ((ChildNode = RtlLeftChild(CurrentNode)))
  58             {
  59                 /* Continue searching from this node */
  60                 CurrentNode = ChildNode;
  61             }
  62             else
  63             {
  64                 /* Otherwise, the element isn't in this tree */
  65                 *NodeOrParent = CurrentNode;
  66                 return TableInsertAsLeft;
  67             }
  68         }
  69         else if (Result == GenericGreaterThan)
  70         {
  71             /* We're more, check if this is the right child */
  72             if ((ChildNode = RtlRightChild(CurrentNode)))
  73             {
  74                 /* Continue searching from this node */
  75                 CurrentNode = ChildNode;
  76             }
  77             else
  78             {
  79                 /* Otherwise, the element isn't in this tree */
  80                 *NodeOrParent = CurrentNode;
  81                 return TableInsertAsRight;
  82             }
  83         }
  84         else
  85         {
  86             /* We should've found the node */
  87             ASSERT(Result == GenericEqual);
  88
  89             /* Return node found */
  90             *NodeOrParent = CurrentNode;
  91             return TableFoundNode;
  92         }
  93     }
  94 }
  95
  96 /* SPLAY FUNCTIONS ***********************************************************/
  97
  98 /*
  99  * @implemented
 100  */
 101 VOID
 102 NTAPI
 103 RtlInitializeGenericTable(IN PRTL_GENERIC_TABLE Table,
 104                           IN PRTL_GENERIC_COMPARE_ROUTINE CompareRoutine,
 105                           IN PRTL_GENERIC_ALLOCATE_ROUTINE AllocateRoutine,
 106                           IN PRTL_GENERIC_FREE_ROUTINE FreeRoutine,
 107                           IN PVOID TableContext)
 108 {
 109     /* Initialize the table to default and passed values */
 110     InitializeListHead(&Table->InsertOrderList);
 111     Table->TableRoot = NULL;
 112     Table->NumberGenericTableElements = 0;
 113     Table->WhichOrderedElement = 0;
 114     Table->OrderedPointer = &Table->InsertOrderList;
 115     Table->CompareRoutine = CompareRoutine;
 116     Table->AllocateRoutine = AllocateRoutine;
 117     Table->FreeRoutine = FreeRoutine;
 118     Table->TableContext = TableContext;
 119 }
 120
 121 /*
 122  * @implemented
 123  */
 124 PVOID
 125 NTAPI
 126 RtlInsertElementGenericTable(IN PRTL_GENERIC_TABLE Table,
 127                              IN PVOID Buffer,
 128                              IN ULONG BufferSize,
 129                              OUT PBOOLEAN NewElement OPTIONAL)
 130 {
 131     PRTL_SPLAY_LINKS NodeOrParent;
 132     TABLE_SEARCH_RESULT Result;
 133
 134     /* Get the splay links and table search result immediately */
 135     Result = RtlpFindGenericTableNodeOrParent(Table, Buffer, &NodeOrParent);
 136
 137     /* Now call the routine to do the full insert */
 138     return RtlInsertElementGenericTableFull(Table,
 139                                             Buffer,
 140                                             BufferSize,
 141                                             NewElement,
 142                                             NodeOrParent,
 143                                             Result);
 144 }
 145
 146 /*
 147  * @implemented
 148  */
 149 PVOID
 150 NTAPI
 151 RtlInsertElementGenericTableFull(IN PRTL_GENERIC_TABLE Table,
 152                                  IN PVOID Buffer,
 153                                  IN ULONG BufferSize,
 154                                  OUT PBOOLEAN NewElement OPTIONAL,
 155                                  IN PVOID NodeOrParent,
 156                                  IN TABLE_SEARCH_RESULT SearchResult)
 157 {
 158     PRTL_SPLAY_LINKS NewNode;
 159
 160     /* Check if the entry wasn't already found */
 161     if (SearchResult != TableFoundNode)
 162     {
 163         /* We're doing an allocation, sanity check */
 164         ASSERT(Table->NumberGenericTableElements != (MAXULONG - 1));
 165
 166         /* Allocate a node */
 167         NewNode = Table->AllocateRoutine(Table,
 168                                          BufferSize +
 169                                          FIELD_OFFSET(TABLE_ENTRY_HEADER,
 170                                                       UserData));
 171         if (!NewNode)
 172         {
 173             /* No memory or other allocation error, fail */
 174             if (NewElement) *NewElement = FALSE;
 175             return NULL;
 176         }
 177
 178         /* Initialize the new inserted element */
 179         RtlInitializeSplayLinks(NewNode);
 180         InsertTailList(&Table->InsertOrderList,
 181                        &((PTABLE_ENTRY_HEADER)NewNode)->ListEntry);
 182
 183         /* Increase element count */
 184         Table->NumberGenericTableElements++;
 185
 186         /* Check where we should insert the entry */
 187         if (SearchResult == TableEmptyTree)
 188         {
 189             /* This is the new root node */
 190             Table->TableRoot = NewNode;
 191         }
 192         else if (SearchResult == TableInsertAsLeft)
 193         {
 194             /* Insert it left */
 195             RtlInsertAsLeftChild(NodeOrParent, NewNode);
 196         }
 197         else
 198         {
 199             /* Right node */
 200             RtlInsertAsRightChild(NodeOrParent, NewNode);
 201         }
 202
 203         /* Copy user buffer */
 204         RtlCopyMemory(&((PTABLE_ENTRY_HEADER)NewNode)->UserData,
 205                       Buffer,
 206                       BufferSize);
 207     }
 208     else
 209     {
 210         /* Return the node we already found */
 211         NewNode = NodeOrParent;
 212     }
 213
 214     /* Splay the tree */
 215     Table->TableRoot = RtlSplay(NewNode);
 216
 217     /* Return status */
 218     if (NewElement) *NewElement = (SearchResult == TableFoundNode);
 219
 220     /* Return pointer to user data */
 221     return &((PTABLE_ENTRY_HEADER)NewNode)->UserData;
 222 }
 223
 224 /*
 225  * @implemented
 226  */
 227 BOOLEAN
 228 NTAPI
 229 RtlIsGenericTableEmpty(IN PRTL_GENERIC_TABLE Table)
 230 {
 231     /* Check if the table root is empty */
 232     return (Table->TableRoot) ? FALSE: TRUE;
 233 }
 234
 235 /*
 236  * @implemented
 237  */
 238 ULONG
 239 NTAPI
 240 RtlNumberGenericTableElements(IN PRTL_GENERIC_TABLE Table)
 241 {
 242     /* Return the number of elements */
 243     return Table->NumberGenericTableElements;
 244 }
 245
 246 /*
 247  * @implemented
 248  */
 249 PVOID
 250 NTAPI
 251 RtlLookupElementGenericTable(IN PRTL_GENERIC_TABLE Table,
 252                              IN PVOID Buffer)
 253 {
 254     PRTL_SPLAY_LINKS NodeOrParent;
 255     TABLE_SEARCH_RESULT Result;
 256
 257     /* Call the full version */
 258     return RtlLookupElementGenericTableFull(Table,
 259                                             Buffer,
 260                                             (PVOID)&NodeOrParent,
 261                                             &Result);
 262 }
 263
 264 /*
 265  * @implemented
 266  */
 267 PVOID
 268 NTAPI
 269 RtlLookupElementGenericTableFull(IN PRTL_GENERIC_TABLE Table,
 270                                  IN PVOID Buffer,
 271                                  OUT PVOID *NodeOrParent,
 272                                  OUT TABLE_SEARCH_RESULT *SearchResult)
 273 {
 274     /* Do the initial lookup */
 275     *SearchResult = RtlpFindGenericTableNodeOrParent(Table,
 276                                                      Buffer,
 277                                                      (PRTL_SPLAY_LINKS *)
 278                                                      NodeOrParent);
 279
 280     /* Check if we found anything */
 281     if ((*SearchResult == TableEmptyTree) || (*SearchResult != TableFoundNode))
 282     {
 283         /* Nothing found */
 284         return NULL;
 285     }
 286
 287     /* Otherwise, splay the tree and return this entry */
 288     Table->TableRoot = RtlSplay(*NodeOrParent);
 289     return &((PTABLE_ENTRY_HEADER)*NodeOrParent)->UserData;
 290 }
 291
 292 /*
 293  * @implemented
 294  */
 295 BOOLEAN
 296 NTAPI
 297 RtlDeleteElementGenericTable(IN PRTL_GENERIC_TABLE Table,
 298                              IN PVOID Buffer)
 299 {
 300     PRTL_SPLAY_LINKS NodeOrParent;
 301     TABLE_SEARCH_RESULT Result;
 302
 303     /* Get the splay links and table search result immediately */
 304     Result = RtlpFindGenericTableNodeOrParent(Table, Buffer, &NodeOrParent);
 305     if ((Result == TableEmptyTree) || (Result != TableFoundNode))
 306     {
 307         /* Nothing to delete */
 308         return FALSE;
 309     }
 310
 311     /* Delete the entry */
 312     Table->TableRoot = RtlDelete(NodeOrParent);
 313     RemoveEntryList(&((PTABLE_ENTRY_HEADER)NodeOrParent)->ListEntry);
 314
 315     /* Update accounting data */
 316     Table->NumberGenericTableElements--;
 317     Table->WhichOrderedElement = 0;
 318     Table->OrderedPointer = &Table->InsertOrderList;
 319
 320     /* Free the entry */
 321     Table->FreeRoutine(Table, NodeOrParent);
 322     return TRUE;
 323 }
 324
 325 /*
 326  * @implemented
 327  */
 328 PVOID
 329 NTAPI
 330 RtlEnumerateGenericTable(IN PRTL_GENERIC_TABLE Table,
 331                          IN BOOLEAN Restart)
 332 {
 333     PRTL_SPLAY_LINKS FoundNode;
 334
 335     /* Check if the table is empty */
 336     if (RtlIsGenericTableEmpty(Table)) return NULL;
 337
 338     /* Check if we have to restart */
 339     if (Restart)
 340     {
 341         /* Then find the leftmost element */
 342         FoundNode = Table->TableRoot;
 343         do
 344         {
 345             /* Get the left child */
 346             FoundNode = RtlLeftChild(FoundNode);
 347         } while(RtlLeftChild(FoundNode));
 348
 349         /* Splay it */
 350         Table->TableRoot = RtlSplay(FoundNode);
 351     }
 352     else
 353     {
 354         /* Otherwise, try using the real successor */
 355         FoundNode = RtlRealSuccessor(Table->TableRoot);
 356         if (FoundNode) Table->TableRoot = RtlSplay(FoundNode);
 357     }
 358
 359     /* Check if we found the node and return it */
 360     return FoundNode ? &((PTABLE_ENTRY_HEADER)FoundNode)->UserData : NULL;
 361 }
 362
 363 /*
 364  * @implemented
 365  */
 366 PVOID
 367 NTAPI
 368 RtlEnumerateGenericTableWithoutSplaying(IN PRTL_GENERIC_TABLE Table,
 369                                         IN OUT PVOID *RestartKey)
 370 {
 371     PRTL_SPLAY_LINKS FoundNode;
 372
 373     /* Check if the table is empty */
 374     if (RtlIsGenericTableEmpty(Table)) return NULL;
 375
 376     /* Check if we have to restart */
 377     if (!(*RestartKey))
 378     {
 379         /* Then find the leftmost element */
 380         FoundNode = Table->TableRoot;
 381         do
 382         {
 383             /* Get the left child */
 384             FoundNode = RtlLeftChild(FoundNode);
 385         } while(RtlLeftChild(FoundNode));
 386
 387         /* Splay it */
 388         *RestartKey = FoundNode;
 389     }
 390     else
 391     {
 392         /* Otherwise, try using the real successor */
 393         FoundNode = RtlRealSuccessor(*RestartKey);
 394         if (FoundNode) *RestartKey = FoundNode;
 395     }
 396
 397     /* Check if we found the node and return it */
 398     return FoundNode ? &((PTABLE_ENTRY_HEADER)FoundNode)->UserData : NULL;
 399 }
 400
 401 /*
 402  * @unimplemented
 403  */
 404 PVOID
 405 NTAPI
 406 RtlEnumerateGenericTableLikeADirectory(IN PRTL_AVL_TABLE Table,
 407                                        IN PRTL_AVL_MATCH_FUNCTION MatchFunction,
 408                                        IN PVOID MatchData,
 409                                        IN ULONG NextFlag,
 410                                        IN OUT PVOID *RestartKey,
 411                                        IN OUT PULONG DeleteCount,
 412                                        IN OUT PVOID Buffer)
 413 {
 414     UNIMPLEMENTED;
 415     return 0;
 416 }
 417
 418 /*
 419  * @implemented
 420  */
 421 PVOID
 422 NTAPI
 423 RtlGetElementGenericTable(IN PRTL_GENERIC_TABLE Table,
 424                           IN ULONG I)
 425 {
 426     ULONG OrderedElement, ElementCount;
 427     PLIST_ENTRY OrderedNode;
 428     ULONG DeltaUp, DeltaDown;
 429     ULONG NextI = I + 1;
 430
 431     /* Setup current accounting data */
 432     OrderedNode = Table->OrderedPointer;
 433     OrderedElement = Table->WhichOrderedElement;
 434     ElementCount = Table->NumberGenericTableElements;
 435
 436     /* Sanity checks */
 437     if ((I == MAXULONG) || (NextI > ElementCount)) return NULL;
 438
 439     /* Check if we already found the entry */
 440     if (NextI == OrderedElement)
 441     {
 442         /* Return it */
 443         return &((PTABLE_ENTRY_HEADER)CONTAINING_RECORD(OrderedNode,
 444                                                         TABLE_ENTRY_HEADER,
 445                                                         ListEntry))->UserData;
 446     }
 447
 448     /* Now check if we're farther behind */
 449     if (OrderedElement > NextI)
 450     {
 451         /* Find out if the distance is more then the half-way point */
 452         if (NextI > (OrderedElement / 2))
 453         {
 454             /* Do the search backwards, since this takes less iterations */
 455             DeltaDown = OrderedElement - NextI;
 456             do
 457             {
 458                 /* Get next node */
 459                 OrderedNode = OrderedNode->Blink;
 460             } while (--DeltaDown);
 461         }
 462         else
 463         {
 464             /* Follow the list directly instead */
 465             OrderedNode = &Table->InsertOrderList;
 466             do
 467             {
 468                 /* Get next node */
 469                 OrderedNode = OrderedNode->Flink;
 470             } while (--NextI);
 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             do
 484             {
 485                 /* Get next node */
 486                 OrderedNode = OrderedNode->Blink;
 487             } while (--DeltaUp);
 488         }
 489         else
 490         {
 491             /* Do the search downwards, since this takes less iterations */
 492             OrderedNode = &Table->InsertOrderList;
 493             do
 494             {
 495                 /* Get next node */
 496                 OrderedNode = OrderedNode->Blink;
 497             } while (--DeltaDown);
 498         }
 499     }
 500
 501     /* Got the element, save it */
 502     Table->OrderedPointer = OrderedNode;
 503     Table->WhichOrderedElement = NextI;
 504
 505     /* Return the element */
 506     return &((PTABLE_ENTRY_HEADER)CONTAINING_RECORD(OrderedNode,
 507                                                     TABLE_ENTRY_HEADER,
 508                                                     ListEntry))->UserData;
 509 }
 510
 511 /* AVL FUNCTIONS *************************************************************/
 512
 513 /*
 514  * @implemented
 515  */
 516 PVOID
 517 NTAPI
 518 RtlLookupElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table,
 519                                     IN PVOID Buffer,
 520                                     IN OUT PVOID *NodeOrParent,
 521                                     IN OUT TABLE_SEARCH_RESULT *SearchResult)
 522 {
 523         PRTL_BALANCED_LINKS OurNodeOrParent;
 524         TABLE_SEARCH_RESULT OurSearchResult;
 525
 526         if( !Table->NumberGenericTableElements )
 527         {
 528                 *SearchResult = TableEmptyTree;
 529                 *NodeOrParent = NULL;
 530                 return NULL;
 531         }
 532
 533         OurSearchResult = avl_search
 534                 (Table, Buffer,
 535                  Table->BalancedRoot.LeftChild, &OurNodeOrParent);
 536
 537         if(SearchResult) *SearchResult = OurSearchResult;
 538         if(NodeOrParent) *NodeOrParent = OurNodeOrParent;
 539
 540         if(OurSearchResult == TableFoundNode)
 541                 return avl_data(OurNodeOrParent);
 542         else
 543                 return NULL;
 544 }
 545
 546 /*
 547  * @implemented
 548  */
 549 PVOID
 550 NTAPI
 551 RtlLookupElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
 552                                 IN PVOID Buffer)
 553 {
 554         PRTL_BALANCED_LINKS OurNodeOrParent;
 555         TABLE_SEARCH_RESULT OurSearchResult;
 556         return RtlLookupElementGenericTableFullAvl
 557         (Table, Buffer, (PVOID *)&OurNodeOrParent, &OurSearchResult);
 558 }
 559
 560 /*
 561  * @implemented
 562  */
 563 BOOLEAN
 564 NTAPI
 565 RtlDeleteElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
 566                                 IN PVOID Buffer)
 567 {
 568         TABLE_SEARCH_RESULT Result;
 569         PRTL_BALANCED_LINKS Node;
 570
 571         RtlLookupElementGenericTableFullAvl
 572                 ( Table, Buffer, (PVOID *)&Node, &Result );
 573
 574         if( Result == TableFoundNode )
 575         {
 576                 avl_delete_node(Table, Node);
 577                 Table->FreeRoutine(Table, Node);
 578                 if( Table->NumberGenericTableElements == 0 )
 579                         avl_deinit(Table);
 580                 return TRUE;
 581         }
 582         else
 583         {
 584                 return FALSE;
 585         }
 586 }
 587
 588 /*
 589  * @implemented
 590  */
 591 PVOID
 592 NTAPI
 593 RtlEnumerateGenericTableAvl(IN PRTL_AVL_TABLE Table,
 594                             IN BOOLEAN Restart)
 595 {
 596         if( Table->NumberGenericTableElements == 0 )
 597                 return NULL;
 598
 599         if( Restart )
 600         {
 601                 Table->RestartKey = avl_first(Table);
 602         }
 603         else
 604         {
 605                 Table->RestartKey = avl_next(Table, Table->RestartKey);
 606         }
 607         if( !Table->RestartKey )
 608                 return NULL;
 609         else
 610                 return avl_data(Table->RestartKey);
 611 }
 612
 613 /*
 614  * @implemented
 615  */
 616 PVOID
 617 NTAPI
 618 RtlEnumerateGenericTableWithoutSplayingAvl(IN PRTL_AVL_TABLE Table,
 619                                            IN OUT PVOID *RestartKey)
 620 {
 621     /* FIXME! */
 622         return RtlEnumerateGenericTableWithoutSplayingAvl(Table, RestartKey);
 623 }
 624
 625 /*
 626  * @implemented
 627  */
 628 PVOID
 629 NTAPI
 630 RtlGetElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
 631                              IN ULONG I)
 632 {
 633         PRTL_BALANCED_LINKS Node;
 634
 635         if( I >= Table->NumberGenericTableElements ) return NULL;
 636         else
 637         {
 638                 Node = avl_first(Table);
 639                 while(I--) Node = avl_next(Table, Node);
 640                 return avl_data(Node);
 641         }
 642 }
 643
 644 /*
 645  * @implemented
 646  */
 647 VOID
 648 NTAPI
 649 RtlInitializeGenericTableAvl(IN OUT PRTL_AVL_TABLE Table,
 650                              IN PRTL_AVL_COMPARE_ROUTINE CompareRoutine,
 651                              IN PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine,
 652                              IN PRTL_AVL_FREE_ROUTINE FreeRoutine,
 653                              IN PVOID TableContext)
 654 {
 655     RtlZeroMemory(Table, sizeof(RTL_AVL_TABLE));
 656     Table->BalancedRoot.Parent = &Table->BalancedRoot;
 657     Table->CompareRoutine = CompareRoutine;
 658     Table->AllocateRoutine = AllocateRoutine;
 659     Table->FreeRoutine = FreeRoutine;
 660     Table->TableContext = TableContext;
 661 }
 662
 663 /*
 664  * @implemented
 665  */
 666 PVOID
 667 NTAPI
 668 RtlInsertElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table,
 669                                     IN PVOID Buffer,
 670                                     IN ULONG BufferSize,
 671                                     OUT PBOOLEAN NewElement OPTIONAL,
 672                                     IN OUT PVOID *NodeOrParent,
 673                                     IN OUT TABLE_SEARCH_RESULT *SearchResult)
 674 {
 675         PRTL_BALANCED_LINKS OurNodeOrParent;
 676         TABLE_SEARCH_RESULT OurSearchResult;
 677
 678         if(Table->NumberGenericTableElements == 0) {
 679                 avl_init(Table);
 680         }
 681
 682         if(NewElement)
 683                 *NewElement = FALSE;
 684
 685         OurSearchResult = avl_search
 686                 (Table, Buffer,
 687                  Table->BalancedRoot.LeftChild, &OurNodeOrParent);
 688
 689         if(NodeOrParent) *NodeOrParent = OurNodeOrParent;
 690         if(SearchResult) *SearchResult = OurSearchResult;
 691
 692         if(OurSearchResult == TableFoundNode)
 693         {
 694                 RtlDeleteElementGenericTableAvl(Table, Buffer);
 695                 return RtlInsertElementGenericTableFullAvl
 696                         (Table, Buffer, BufferSize,
 697                          NewElement, NodeOrParent, SearchResult);
 698         }
 699         else
 700         {
 701                 PRTL_BALANCED_LINKS NewNode =
 702                         Table->AllocateRoutine
 703                         (Table,
 704                          BufferSize + sizeof(RTL_BALANCED_LINKS) + BufferSize);
 705
 706                 if( !NewNode ) return NULL;
 707
 708                 NewNode->Balance = 0;
 709                 RtlCopyMemory(avl_data(NewNode), Buffer, BufferSize);
 710
 711                 OurNodeOrParent = NewNode;
 712
 713                 avl_insert_node(Table, NewNode);
 714                 return avl_data(NewNode);
 715         }
 716 }
 717
 718 /*
 719  * @implemented
 720  */
 721 PVOID
 722 NTAPI
 723 RtlInsertElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
 724                                 IN PVOID Buffer,
 725                                 IN ULONG BufferSize,
 726                                 OUT PBOOLEAN NewElement OPTIONAL)
 727 {
 728         PVOID NodeOrParent;
 729         TABLE_SEARCH_RESULT SearchResult;
 730
 731         return RtlInsertElementGenericTableFullAvl
 732         (Table, Buffer, BufferSize, NewElement, &NodeOrParent, &SearchResult);
 733 }
 734
 735 /*
 736  * @implemented
 737  */
 738 BOOLEAN
 739 NTAPI
 740 RtlIsGenericTableEmptyAvl(PRTL_AVL_TABLE Table)
 741 {
 742     return Table->NumberGenericTableElements == 0;
 743 }
 744
 745 /*
 746  * @implemented
 747  */
 748 ULONG
 749 NTAPI
 750 RtlNumberGenericTableElementsAvl(IN PRTL_AVL_TABLE Table)
 751 {
 752     return Table->NumberGenericTableElements;
 753 }
 754
 755 /*
 756 * @unimplemented
 757 */
 758 PVOID
 759 NTAPI
 760 RtlLookupFirstMatchingElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
 761                                              IN PVOID Buffer,
 762                                              OUT PVOID *RestartKey)
 763 {
 764     UNIMPLEMENTED;
 765     return NULL;
 766 }
 767
 768 /* EOF */