test: gentable.c File Reference

Main Page | Class Hierarchy | Class List | File List | Class Members | File Members

# gentable.c File Reference

`#include <nt.h>`
`#include <ntrtl.h>`

Go to the source code of this file.

## Classes

struct | _TABLE_ENTRY_HEADER

## Typedefs

typedef _TABLE_ENTRY_HEADER | TABLE_ENTRY_HEADER
typedef _TABLE_ENTRY_HEADER * | PTABLE_ENTRY_HEADER

## Functions

TABLE_SEARCH_RESULT | FindNodeOrParent (IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer, OUT PRTL_SPLAY_LINKS *NodeOrParent)
VOID | RtlInitializeGenericTable (IN PRTL_GENERIC_TABLE Table, IN PRTL_GENERIC_COMPARE_ROUTINE CompareRoutine, IN PRTL_GENERIC_ALLOCATE_ROUTINE AllocateRoutine, IN PRTL_GENERIC_FREE_ROUTINE FreeRoutine, IN PVOID TableContext)
PVOID | RtlInsertElementGenericTable (IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer, IN CLONG BufferSize, OUT PBOOLEAN NewElement OPTIONAL)
PVOID | RtlInsertElementGenericTableFull (IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer, IN CLONG BufferSize, OUT PBOOLEAN NewElement OPTIONAL, PVOID NodeOrParent, TABLE_SEARCH_RESULT SearchResult)
BOOLEAN | RtlDeleteElementGenericTable (IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer)
PVOID | RtlLookupElementGenericTable (IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer)
PVOID NTAPI | RtlLookupElementGenericTableFull (PRTL_GENERIC_TABLE Table, PVOID Buffer, OUT PVOID *NodeOrParent, OUT TABLE_SEARCH_RESULT *SearchResult)
PVOID | RtlEnumerateGenericTable (IN PRTL_GENERIC_TABLE Table, IN BOOLEAN Restart)
BOOLEAN | RtlIsGenericTableEmpty (IN PRTL_GENERIC_TABLE Table)
PVOID | RtlGetElementGenericTable (IN PRTL_GENERIC_TABLE Table, IN ULONG I)
ULONG | RtlNumberGenericTableElements (IN PRTL_GENERIC_TABLE Table)
PVOID | RtlEnumerateGenericTableWithoutSplaying (IN PRTL_GENERIC_TABLE Table, IN PVOID *RestartKey)

## Typedef Documentation

typedef struct _TABLE_ENTRY_HEADER * PTABLE_ENTRY_HEADER

| Referenced by FindNodeOrParent(), RtlDeleteElementGenericTable(), RtlEnumerateGenericTable(), RtlEnumerateGenericTableWithoutSplaying(), RtlGetElementGenericTable(), RtlInsertElementGenericTableFull(), and RtlLookupElementGenericTableFull().

typedef struct _TABLE_ENTRY_HEADER TABLE_ENTRY_HEADER

## Function Documentation

TABLE_SEARCH_RESULT FindNodeOrParent | ( | IN PRTL_GENERIC_TABLE | Table,
|  | IN PVOID | Buffer,
|  | OUT PRTL_SPLAY_LINKS * | NodeOrParent
| ) | `[static]`

Definition at line 64 of file gentable.c.

References ASSERT, Buffer, PTABLE_ENTRY_HEADER, RtlIsGenericTableEmpty(), and TRUE.

Referenced by RtlDeleteElementGenericTable(), RtlInsertElementGenericTable(), and RtlLookupElementGenericTableFull().

    00072                    :
    00073
    00074     This routine is used by all of the routines of the generic
    00075     table package to locate the a node in the tree.  It will
    00076     find and return (via the NodeOrParent parameter) the node
    00077     with the given key, or if that node is not in the tree it
    00078     will return (via the NodeOrParent parameter) a pointer to
    00079     the parent.
    00080
    00081 Arguments:
    00082
    00083     Table - The generic table to search for the key.
    00084
    00085     Buffer - Pointer to a buffer holding the key.  The table
    00086              package doesn't examine the key itself.  It leaves
    00087              this up to the user supplied compare routine.
    00088
    00089     NodeOrParent - Will be set to point to the node containing the
    00090                    the key or what should be the parent of the node
    00091                    if it were in the tree.  Note that this will *NOT*
    00092                    be set if the search result is TableEmptyTree.
    00093
    00094 Return Value:
    00095
    00096     TABLE_SEARCH_RESULT - TableEmptyTree: The tree was empty.  NodeOrParent
    00097                                           is *not* altered.
    00098
    00099                           TableFoundNode: A node with the key is in the tree.
    00100                                           NodeOrParent points to that node.
    00101
    00102                           TableInsertAsLeft: Node with key was not found.
    00103                                              NodeOrParent points to what would be
    00104                                              parent.  The node would be the left
    00105                                              child.
    00106
    00107                           TableInsertAsRight: Node with key was not found.
    00108                                               NodeOrParent points to what would be
    00109                                               parent.  The node would be the right
    00110                                               child.
    00111
    00112 --*/
    00113
    00114
    00115
    00116 {
    00117
    00118     if (RtlIsGenericTableEmpty(Table)) {
    00119
    00120         return TableEmptyTree;
    00121
    00122     } else {
    00123
    00124         //
    00125         // Used as the iteration variable while stepping through
    00126         // the generic table.
    00127         //
    00128         PRTL_SPLAY_LINKS NodeToExamine = Table->TableRoot;
    00129
    00130         //
    00131         // Just a temporary.  Hopefully a good compiler will get
    00132         // rid of it.
    00133         //
    00134         PRTL_SPLAY_LINKS Child;
    00135
    00136         //
    00137         // Holds the value of the comparasion.
    00138         //
    00139         RTL_GENERIC_COMPARE_RESULTS Result;
    00140
    00141         while (TRUE) {
    00142
    00143             //
    00144             // Compare the buffer with the key in the tree element.
    00145             //
    00146
    00147             Result = Table->CompareRoutine(
    00148                          Table,
    00149                          Buffer,
    00150                          &((PTABLE_ENTRY_HEADER) NodeToExamine)->UserData
    00151                          );
    00152
    00153             if (Result == GenericLessThan) {
    00154
    00155                 if (Child = RtlLeftChild(NodeToExamine)) {
    00156
    00157                     NodeToExamine = Child;
    00158
    00159                 } else {
    00160
    00161                     //
    00162                     // Node is not in the tree.  Set the output
    00163                     // parameter to point to what would be its
    00164                     // parent and return which child it would be.
    00165                     //
    00166
    00167                     *NodeOrParent = NodeToExamine;
    00168                     return TableInsertAsLeft;
    00169
    00170                 }
    00171
    00172             } else if (Result == GenericGreaterThan) {
    00173
    00174                 if (Child = RtlRightChild(NodeToExamine)) {
    00175
    00176                     NodeToExamine = Child;
    00177
    00178                 } else {
    00179
    00180                     //
    00181                     // Node is not in the tree.  Set the output
    00182                     // parameter to point to what would be its
    00183                     // parent and return which child it would be.
    00184                     //
    00185
    00186                     *NodeOrParent = NodeToExamine;
    00187                     return TableInsertAsRight;
    00188
    00189                 }
    00190
    00191
    00192             } else {
    00193
    00194                 //
    00195                 // Node is in the tree (or it better be because of the
    00196                 // assert).  Set the output parameter to point to
    00197                 // the node and tell the caller that we found the node.
    00198                 //
    00199
    00200                 ASSERT(Result == GenericEqual);
    00201                 *NodeOrParent = NodeToExamine;
    00202                 return TableFoundNode;
    00203
    00204             }
    00205
    00206         }
    00207
    00208     }
    00209
    00210 }

BOOLEAN RtlDeleteElementGenericTable | ( | IN PRTL_GENERIC_TABLE | Table,
|  | IN PVOID | Buffer
| ) |

Definition at line 532 of file gentable.c.

References Buffer, FALSE, FindNodeOrParent(), PTABLE_ENTRY_HEADER, RtlDelete(), and TRUE.

    00539                    :
    00540
    00541     The function DeleteElementGenericTable will find and delete an element
    00542     from a generic table.  If the element is located and deleted the return
    00543     value is TRUE, otherwise if the element is not located the return value
    00544     is FALSE.  The user supplied input buffer is only used as a key in
    00545     locating the element in the table.
    00546
    00547 Arguments:
    00548
    00549     Table - Pointer to the table in which to (possibly) delete the
    00550             memory accessed by the key buffer.
    00551
    00552     Buffer - Passed to the user comparasion routine.  Its contents are
    00553              up to the user but one could imagine that it contains some
    00554              sort of key value.
    00555
    00556 Return Value:
    00557
    00558     BOOLEAN - If the table contained the key then true, otherwise false.
    00559
    00560 --*/
    00561
    00562 {
    00563
    00564     //
    00565     // Holds a pointer to the node in the table or what would be the
    00566     // parent of the node.
    00567     //
    00568     PRTL_SPLAY_LINKS NodeOrParent;
    00569
    00570     //
    00571     // Holds the result of the table lookup.
    00572     //
    00573     TABLE_SEARCH_RESULT Lookup;
    00574
    00575     Lookup = FindNodeOrParent(
    00576                  Table,
    00577                  Buffer,
    00578                  &NodeOrParent
    00579                  );
    00580
    00581     if ((Lookup == TableEmptyTree) || (Lookup != TableFoundNode)) {
    00582
    00583         return FALSE;
    00584
    00585     } else {
    00586
    00587         //
    00588         // Delete the node from the splay tree.
    00589         //
    00590
    00591         Table->TableRoot = RtlDelete(NodeOrParent);
    00592
    00593         //
    00594         // Delete the element from the linked list.
    00595         //
    00596
    00597         RemoveEntryList(&((PTABLE_ENTRY_HEADER) NodeOrParent)->ListEntry);
    00598         Table->NumberGenericTableElements--;
    00599         Table->WhichOrderedElement = 0;
    00600         Table->OrderedPointer = &Table->InsertOrderList;
    00601
    00602         //
    00603         // The node has been deleted from the splay table.
    00604         // Now give the node to the user deletion routine.
    00605         // NOTE: We are giving the deletion routine a pointer
    00606         // to the splay links rather then the user data.  It
    00607         // is assumed that the deallocation is rather stupid.
    00608         //
    00609
    00610         Table->FreeRoutine(Table,NodeOrParent);
    00611         return TRUE;
    00612
    00613     }
    00614
    00615 }

PVOID RtlEnumerateGenericTable | ( | IN PRTL_GENERIC_TABLE | Table,
|  | IN BOOLEAN | Restart
| ) |

Definition at line 738 of file gentable.c.

References NULL, PTABLE_ENTRY_HEADER, RtlIsGenericTableEmpty(), RtlRealSuccessor(), and RtlSplay().

    00745                    :
    00746
    00747     The function EnumerateGenericTable will return to the caller one-by-one
    00748     the elements of of a table.  The return value is a pointer to the user
    00749     defined structure associated with the element.  The input parameter
    00750     Restart indicates if the enumeration should start from the beginning
    00751     or should return the next element.  If the are no more new elements to
    00752     return the return value is NULL.  As an example of its use, to enumerate
    00753     all of the elements in a table the user would write:
    00754
    00755         for (ptr = EnumerateGenericTable(Table,TRUE);
    00756              ptr != NULL;
    00757              ptr = EnumerateGenericTable(Table, FALSE)) {
    00758                 :
    00759         }
    00760
    00761 Arguments:
    00762
    00763     Table - Pointer to the generic table to enumerate.
    00764
    00765     Restart - Flag that if true we should start with the least
    00766               element in the tree otherwise, return we return
    00767               a pointer to the user data for the root and make
    00768               the real successor to the root the new root.
    00769
    00770 Return Value:
    00771
    00772     PVOID - Pointer to the user data.
    00773
    00774 --*/
    00775
    00776 {
    00777
    00778     if (RtlIsGenericTableEmpty(Table)) {
    00779
    00780         //
    00781         // Nothing to do if the table is empty.
    00782         //
    00783
    00784         return NULL;
    00785
    00786     } else {
    00787
    00788         //
    00789         // Will be used as the "iteration" through the tree.
    00790         //
    00791         PRTL_SPLAY_LINKS NodeToReturn;
    00792
    00793         //
    00794         // If the restart flag is true then go to the least element
    00795         // in the tree.
    00796         //
    00797
    00798         if (Restart) {
    00799
    00800             //
    00801             // We just loop until we find the leftmost child of the root.
    00802             //
    00803
    00804             for (
    00805                 NodeToReturn = Table->TableRoot;
    00806                 RtlLeftChild(NodeToReturn);
    00807                 NodeToReturn = RtlLeftChild(NodeToReturn)
    00808                 ) {
    00809                 ;
    00810             }
    00811
    00812             Table->TableRoot = RtlSplay(NodeToReturn);
    00813
    00814         } else {
    00815
    00816             //
    00817             // The assumption here is that the root of the
    00818             // tree is the last node that we returned.  We
    00819             // find the real successor to the root and return
    00820             // it as next element of the enumeration.  The
    00821             // node that is to be returned is splayed (thereby
    00822             // making it the root of the tree).  Note that we
    00823             // need to take care when there are no more elements.
    00824             //
    00825
    00826             NodeToReturn = RtlRealSuccessor(Table->TableRoot);
    00827
    00828             if (NodeToReturn) {
    00829
    00830                 Table->TableRoot = RtlSplay(NodeToReturn);
    00831
    00832             }
    00833
    00834         }
    00835
    00836         //
    00837         // If there actually is a next element in the enumeration
    00838         // then the pointer to return is right after the list links.
    00839         //
    00840
    00841         return ((NodeToReturn)?
    00842                    ((PVOID)&((PTABLE_ENTRY_HEADER)NodeToReturn)->UserData)
    00843                   :((PVOID)(NULL)));
    00844
    00845     }
    00846
    00847 }

PVOID RtlEnumerateGenericTableWithoutSplaying | ( | IN PRTL_GENERIC_TABLE | Table,
|  | IN PVOID * | RestartKey
| ) |

Definition at line 1110 of file gentable.c.

References NULL, PTABLE_ENTRY_HEADER, RtlIsGenericTableEmpty(), and RtlRealSuccessor().

Referenced by UdfGetNextFcb().

    01117                    :
    01118
    01119     The function EnumerateGenericTableWithoutSplaying will return to the
    01120     caller one-by-one the elements of of a table.  The return value is a
    01121     pointer to the user defined structure associated with the element.
    01122     The input parameter RestartKey indicates if the enumeration should
    01123     start from the beginning or should return the next element.  If the
    01124     are no more new elements to return the return value is NULL.  As an
    01125     example of its use, to enumerate all of the elements in a table the
    01126     user would write:
    01127
    01128         *RestartKey = NULL;
    01129
    01130         for (ptr = EnumerateGenericTableWithoutSplaying(Table, &RestartKey);
    01131              ptr != NULL;
    01132              ptr = EnumerateGenericTableWithoutSplaying(Table, &RestartKey)) {
    01133                 :
    01134         }
    01135
    01136 Arguments:
    01137
    01138     Table - Pointer to the generic table to enumerate.
    01139
    01140     RestartKey - Pointer that indicates if we should restart or return the next
    01141                 element.  If the contents of RestartKey is NULL, the search
    01142                 will be started from the beginning.
    01143
    01144 Return Value:
    01145
    01146     PVOID - Pointer to the user data.
    01147
    01148 --*/
    01149
    01150 {
    01151
    01152     if (RtlIsGenericTableEmpty(Table)) {
    01153
    01154         //
    01155         // Nothing to do if the table is empty.
    01156         //
    01157
    01158         return NULL;
    01159
    01160     } else {
    01161
    01162         //
    01163         // Will be used as the "iteration" through the tree.
    01164         //
    01165         PRTL_SPLAY_LINKS NodeToReturn;
    01166
    01167         //
    01168         // If the restart flag is true then go to the least element
    01169         // in the tree.
    01170         //
    01171
    01172         if (*RestartKey == NULL) {
    01173
    01174             //
    01175             // We just loop until we find the leftmost child of the root.
    01176             //
    01177
    01178             for (
    01179                 NodeToReturn = Table->TableRoot;
    01180                 RtlLeftChild(NodeToReturn);
    01181                 NodeToReturn = RtlLeftChild(NodeToReturn)
    01182                 ) {
    01183                 ;
    01184             }
    01185
    01186             *RestartKey = NodeToReturn;
    01187
    01188         } else {
    01189
    01190             //
    01191             // The caller has passed in the previous entry found
    01192             // in the table to enable us to continue the search.  We call
    01193             // RtlRealSuccessor to step to the next element in the tree.
    01194             //
    01195
    01196             NodeToReturn = RtlRealSuccessor(*RestartKey);
    01197
    01198             if (NodeToReturn) {
    01199
    01200                 *RestartKey = NodeToReturn;
    01201
    01202             }
    01203
    01204         }
    01205
    01206         //
    01207         // If there actually is a next element in the enumeration
    01208         // then the pointer to return is right after the list links.
    01209         //
    01210
    01211         return ((NodeToReturn)?
    01212                    ((PVOID)&((PTABLE_ENTRY_HEADER)NodeToReturn)->UserData)
    01213                   :((PVOID)(NULL)));
    01214
    01215     }
    01216
    01217 }

PVOID RtlGetElementGenericTable | ( | IN PRTL_GENERIC_TABLE | Table,
|  | IN ULONG | I
| ) |

Definition at line 884 of file gentable.c.

References NULL, and PTABLE_ENTRY_HEADER.

    00891                    :
    00892
    00893
    00894     The function GetElementGenericTable will return the i'th element
    00895     inserted in the generic table.  I = 0 implies the first element,
    00896     I = (RtlNumberGenericTableElements(Table)-1) will return the last element
    00897     inserted into the generic table.  The type of I is ULONG.  Values
    00898     of I > than (NumberGenericTableElements(Table)-1) will return NULL.  If
    00899     an arbitrary element is deleted from the generic table it will cause
    00900     all elements inserted after the deleted element to "move up".
    00901
    00902 Arguments:
    00903
    00904     Table - Pointer to the generic table from which to get the ith element.
    00905
    00906     I - Which element to get.
    00907
    00908
    00909 Return Value:
    00910
    00911     PVOID - Pointer to the user data.
    00912
    00913 --*/
    00914
    00915 {
    00916
    00917     //
    00918     // Current location in the table.
    00919     //
    00920     ULONG CurrentLocation = Table->WhichOrderedElement;
    00921
    00922     //
    00923     // Hold the number of elements in the table.
    00924     //
    00925     ULONG NumberInTable = Table->NumberGenericTableElements;
    00926
    00927     //
    00928     // Holds the value of I+1.
    00929     //
    00930     // Note that we don't care if this value overflows.
    00931     // If we end up accessing it we know that it didn't.
    00932     //
    00933     ULONG NormalizedI = I + 1;
    00934
    00935     //
    00936     // Will hold distances to travel to the desired node;
    00937     //
    00938     ULONG ForwardDistance,BackwardDistance;
    00939
    00940     //
    00941     // Will point to the current element in the linked list.
    00942     //
    00943     PLIST_ENTRY CurrentNode = Table->OrderedPointer;
    00944
    00945
    00946     //
    00947     // If it's out of bounds get out quick.
    00948     //
    00949
    00950     if ((I == MAXULONG) || (NormalizedI > NumberInTable)) return NULL;
    00951
    00952     //
    00953     // If we're already at the node then return it.
    00954     //
    00955
    00956     if (NormalizedI == CurrentLocation) {
    00957
    00958         return &((PTABLE_ENTRY_HEADER) CONTAINING_RECORD(CurrentNode, TABLE_ENTRY_HEADER, ListEntry))->UserData;
    00959     }
    00960
    00961     //
    00962     // Calculate the forward and backward distance to the node.
    00963     //
    00964
    00965     if (CurrentLocation > NormalizedI) {
    00966
    00967         //
    00968         // When CurrentLocation is greater than where we want to go,
    00969         // if moving forward gets us there quicker than moving backward
    00970         // then it follows that moving forward from the listhead is
    00971         // going to take fewer steps. (This is because, moving forward
    00972         // in this case must move *through* the listhead.)
    00973         //
    00974         // The work here is to figure out if moving backward would be quicker.
    00975         //
    00976         // Moving backward would be quicker only if the location we wish  to
    00977         // go to is more than half way between the listhead and where we
    00978         // currently are.
    00979         //
    00980
    00981         if (NormalizedI > (CurrentLocation/2)) {
    00982
    00983             //
    00984             // Where we want to go is more than half way from the listhead
    00985             // We can traval backwards from our current location.
    00986             //
    00987
    00988             for (
    00989                 BackwardDistance = CurrentLocation - NormalizedI;
    00990                 BackwardDistance;
    00991                 BackwardDistance--
    00992                 ) {
    00993
    00994                 CurrentNode = CurrentNode->Blink;
    00995
    00996             }
    00997         } else {
    00998
    00999             //
    01000             // Where we want to go is less than halfway between the start
    01001             // and where we currently are.  Start from the listhead.
    01002             //
    01003
    01004             for (
    01005                 CurrentNode = &Table->InsertOrderList;
    01006                 NormalizedI;
    01007                 NormalizedI--
    01008                 ) {
    01009
    01010                 CurrentNode = CurrentNode->Flink;
    01011
    01012             }
    01013
    01014         }
    01015
    01016     } else {
    01017
    01018
    01019         //
    01020         // When CurrentLocation is less than where we want to go,
    01021         // if moving backwards gets us there quicker than moving forwards
    01022         // then it follows that moving backwards from the listhead is
    01023         // going to take fewer steps. (This is because, moving backwards
    01024         // in this case must move *through* the listhead.)
    01025         //
    01026
    01027         ForwardDistance = NormalizedI - CurrentLocation;
    01028
    01029         //
    01030         // Do the backwards calculation as if we are starting from the
    01031         // listhead.
    01032         //
    01033
    01034         BackwardDistance = (NumberInTable - NormalizedI) + 1;
    01035
    01036         if (ForwardDistance <= BackwardDistance) {
    01037
    01038             for (
    01039                 ;
    01040                 ForwardDistance;
    01041                 ForwardDistance--
    01042                 ) {
    01043
    01044                 CurrentNode = CurrentNode->Flink;
    01045
    01046             }
    01047
    01048
    01049         } else {
    01050
    01051             for (
    01052                 CurrentNode = &Table->InsertOrderList;
    01053                 BackwardDistance;
    01054                 BackwardDistance--
    01055                 ) {
    01056
    01057                 CurrentNode = CurrentNode->Blink;
    01058
    01059             }
    01060
    01061         }
    01062
    01063     }
    01064
    01065     //
    01066     // We're where we want to be.  Save our current location and return
    01067     // a pointer to the data to the user.
    01068     //
    01069
    01070     Table->OrderedPointer = CurrentNode;
    01071     Table->WhichOrderedElement = I+1;
    01072
    01073     return &((PTABLE_ENTRY_HEADER) CONTAINING_RECORD(CurrentNode, TABLE_ENTRY_HEADER, ListEntry))->UserData;
    01074
    01075 }

VOID RtlInitializeGenericTable | ( | IN PRTL_GENERIC_TABLE | Table,
|  | IN PRTL_GENERIC_COMPARE_ROUTINE | CompareRoutine,
|  | IN PRTL_GENERIC_ALLOCATE_ROUTINE | AllocateRoutine,
|  | IN PRTL_GENERIC_FREE_ROUTINE | FreeRoutine,
|  | IN PVOID | TableContext
| ) |

Definition at line 213 of file gentable.c.

References NULL.

Referenced by UdfInitializeVcb(), and UdfInitializeVmcb().

    00223                    :
    00224
    00225     The procedure InitializeGenericTable takes as input an uninitialized
    00226     generic table variable and pointers to the three user supplied routines.
    00227     This must be called for every individual generic table variable before
    00228     it can be used.
    00229
    00230 Arguments:
    00231
    00232     Table - Pointer to the generic table to be initialized.
    00233
    00234     CompareRoutine - User routine to be used to compare to keys in the
    00235                      table.
    00236
    00237     AllocateRoutine - User routine to call to allocate memory for a new
    00238                       node in the generic table.
    00239
    00240     FreeRoutine - User routine to call to deallocate memory for
    00241                         a node in the generic table.
    00242
    00243     TableContext - Supplies user supplied context for the table.
    00244
    00245 Return Value:
    00246
    00247     None.
    00248
    00249 --*/
    00250
    00251 {
    00252
    00253     //
    00254     // Initialize each field of the Table parameter.
    00255     //
    00256
    00257     Table->TableRoot = NULL;
    00258     InitializeListHead(&Table->InsertOrderList);
    00259     Table->NumberGenericTableElements = 0;
    00260     Table->OrderedPointer = &Table->InsertOrderList;
    00261     Table->WhichOrderedElement = 0;
    00262     Table->CompareRoutine = CompareRoutine;
    00263     Table->AllocateRoutine = AllocateRoutine;
    00264     Table->FreeRoutine = FreeRoutine;
    00265     Table->TableContext = TableContext;
    00266
    00267 }

PVOID RtlInsertElementGenericTable | ( | IN PRTL_GENERIC_TABLE | Table,
|  | IN PVOID | Buffer,
|  | IN CLONG | BufferSize,
|  | OUT PBOOLEAN NewElement | OPTIONAL
| ) |

Definition at line 271 of file gentable.c.

References Buffer, BufferSize, FindNodeOrParent(), and RtlInsertElementGenericTableFull().

    00280                    :
    00281
    00282     The function InsertElementGenericTable will insert a new element
    00283     in a table.  It does this by allocating space for the new element
    00284     (this includes splay links), inserting the element in the table, and
    00285     then returning to the user a pointer to the new element (which is
    00286     the first available space after the splay links).  If an element
    00287     with the same key already exists in the table the return value is a pointer
    00288     to the old element.  The optional output parameter NewElement is used
    00289     to indicate if the element previously existed in the table.  Note: the user
    00290     supplied Buffer is only used for searching the table, upon insertion its
    00291     contents are copied to the newly created element.  This means that
    00292     pointer to the input buffer will not point to the new element.
    00293
    00294 Arguments:
    00295
    00296     Table - Pointer to the table in which to (possibly) insert the
    00297             key buffer.
    00298
    00299     Buffer - Passed to the user comparasion routine.  Its contents are
    00300              up to the user but one could imagine that it contains some
    00301              sort of key value.
    00302
    00303     BufferSize - The amount of space to allocate when the (possible)
    00304                  insertion is made.  Note that if we actually do
    00305                  not find the node and we do allocate space then we
    00306                  will add the size of the SPLAY_LINKS to this buffer
    00307                  size.  The user should really take care not to depend
    00308                  on anything in the first sizeof(SPLAY_LINKS) bytes
    00309                  of the memory allocated via the memory allocation
    00310                  routine.
    00311
    00312     NewElement - Optional Flag.  If present then it will be set to
    00313                  TRUE if the buffer was not "found" in the generic
    00314                  table.
    00315
    00316 Return Value:
    00317
    00318     PVOID - Pointer to the user defined data.
    00319
    00320 --*/
    00321
    00322 {
    00323
    00324     //
    00325     // Holds a pointer to the node in the table or what would be the
    00326     // parent of the node.
    00327     //
    00328     PRTL_SPLAY_LINKS NodeOrParent;
    00329
    00330     //
    00331     // Holds the result of the table lookup.
    00332     //
    00333     TABLE_SEARCH_RESULT Lookup;
    00334
    00335     Lookup = FindNodeOrParent(
    00336                  Table,
    00337                  Buffer,
    00338                  &NodeOrParent
    00339                  );
    00340
    00341     //
    00342     //  Call the full routine to do the real work.
    00343     //
    00344
    00345     return RtlInsertElementGenericTableFull(
    00346                 Table,
    00347                 Buffer,
    00348                 BufferSize,
    00349                 NewElement,
    00350                 NodeOrParent,
    00351                 Lookup
    00352                 );
    00353 }

PVOID RtlInsertElementGenericTableFull | ( | IN PRTL_GENERIC_TABLE | Table,
|  | IN PVOID | Buffer,
|  | IN CLONG | BufferSize,
|  | OUT PBOOLEAN NewElement | OPTIONAL,
|  | PVOID | NodeOrParent,
|  | TABLE_SEARCH_RESULT | SearchResult
| ) |

Definition at line 357 of file gentable.c.

References ASSERT, Buffer, BufferSize, FALSE, NULL, PTABLE_ENTRY_HEADER, RtlSplay(), and TRUE.

Referenced by RtlInsertElementGenericTable().

    00368                    :
    00369
    00370     The function InsertElementGenericTableFull will insert a new element
    00371     in a table.  It does this by allocating space for the new element
    00372     (this includes splay links), inserting the element in the table, and
    00373     then returning to the user a pointer to the new element.  If an element
    00374     with the same key already exists in the table the return value is a pointer
    00375     to the old element.  The optional output parameter NewElement is used
    00376     to indicate if the element previously existed in the table.  Note: the user
    00377     supplied Buffer is only used for searching the table, upon insertion its
    00378     contents are copied to the newly created element.  This means that
    00379     pointer to the input buffer will not point to the new element.
    00380     This routine is passed the NodeOrParent and SearchResult from a
    00381     previous RtlLookupElementGenericTableFull.
    00382
    00383 Arguments:
    00384
    00385     Table - Pointer to the table in which to (possibly) insert the
    00386             key buffer.
    00387
    00388     Buffer - Passed to the user comparasion routine.  Its contents are
    00389              up to the user but one could imagine that it contains some
    00390              sort of key value.
    00391
    00392     BufferSize - The amount of space to allocate when the (possible)
    00393                  insertion is made.  Note that if we actually do
    00394                  not find the node and we do allocate space then we
    00395                  will add the size of the SPLAY_LINKS to this buffer
    00396                  size.  The user should really take care not to depend
    00397                  on anything in the first sizeof(SPLAY_LINKS) bytes
    00398                  of the memory allocated via the memory allocation
    00399                  routine.
    00400
    00401     NewElement - Optional Flag.  If present then it will be set to
    00402                  TRUE if the buffer was not "found" in the generic
    00403                  table.
    00404
    00405    NodeOrParent - Result of prior RtlLookupElementGenericTableFull.
    00406
    00407    SearchResult - Result of prior RtlLookupElementGenericTableFull.
    00408
    00409 Return Value:
    00410
    00411     PVOID - Pointer to the user defined data.
    00412
    00413 --*/
    00414
    00415 {
    00416     //
    00417     // Node will point to the splay links of what
    00418     // will be returned to the user.
    00419     //
    00420
    00421     PRTL_SPLAY_LINKS NodeToReturn;
    00422
    00423     if (SearchResult != TableFoundNode) {
    00424
    00425         //
    00426         // We just check that the table isn't getting
    00427         // too big.
    00428         //
    00429
    00430         ASSERT(Table->NumberGenericTableElements != (MAXULONG-1));
    00431
    00432         //
    00433         // The node wasn't in the (possibly empty) tree.
    00434         // Call the user allocation routine to get space
    00435         // for the new node.
    00436         //
    00437
    00438         NodeToReturn = Table->AllocateRoutine(
    00439                            Table,
    00440                            BufferSize+FIELD_OFFSET( TABLE_ENTRY_HEADER, UserData )
    00441                            );
    00442
    00443         //
    00444         // If the return is NULL, return NULL from here to indicate that
    00445         // the entry could not be added.
    00446         //
    00447
    00448         if (NodeToReturn == NULL) {
    00449
    00450             if (ARGUMENT_PRESENT(NewElement)) {
    00451
    00452                 *NewElement = FALSE;
    00453             }
    00454
    00455             return(NULL);
    00456         }
    00457
    00458         RtlInitializeSplayLinks(NodeToReturn);
    00459
    00460         //
    00461         // Insert the new node at the end of the ordered linked list.
    00462         //
    00463
    00464         InsertTailList(
    00465             &Table->InsertOrderList,
    00466             &((PTABLE_ENTRY_HEADER) NodeToReturn)->ListEntry
    00467             );
    00468
    00469         Table->NumberGenericTableElements++;
    00470
    00471         //
    00472         // Insert the new node in the tree.
    00473         //
    00474
    00475         if (SearchResult == TableEmptyTree) {
    00476
    00477             Table->TableRoot = NodeToReturn;
    00478
    00479         } else {
    00480
    00481             if (SearchResult == TableInsertAsLeft) {
    00482
    00483                 RtlInsertAsLeftChild(
    00484                     NodeOrParent,
    00485                     NodeToReturn
    00486                     );
    00487
    00488             } else {
    00489
    00490                 RtlInsertAsRightChild(
    00491                     NodeOrParent,
    00492                     NodeToReturn
    00493                     );
    00494             }
    00495         }
    00496
    00497         //
    00498         // Copy the users buffer into the user data area of the table.
    00499         //
    00500
    00501         RtlCopyMemory(
    00502             &((PTABLE_ENTRY_HEADER) NodeToReturn)->UserData,
    00503             Buffer,
    00504             BufferSize
    00505             );
    00506
    00507     } else {
    00508
    00509         NodeToReturn = NodeOrParent;
    00510     }
    00511
    00512     //
    00513     // Always splay the (possibly) new node.
    00514     //
    00515
    00516     Table->TableRoot = RtlSplay(NodeToReturn);
    00517
    00518     if (ARGUMENT_PRESENT(NewElement)) {
    00519
    00520         *NewElement = ((SearchResult == TableFoundNode)?(FALSE):(TRUE));
    00521     }
    00522
    00523     //
    00524     // Insert the element on the ordered list;
    00525     //
    00526
    00527     return &((PTABLE_ENTRY_HEADER) NodeToReturn)->UserData;
    00528 }

BOOLEAN RtlIsGenericTableEmpty | ( | IN PRTL_GENERIC_TABLE | Table | ) |

Definition at line 851 of file gentable.c.

References FALSE, and TRUE.

Referenced by FindNodeOrParent(), RtlEnumerateGenericTable(), and RtlEnumerateGenericTableWithoutSplaying().

    00857                    :
    00858
    00859     The function IsGenericTableEmpty will return to the caller TRUE if
    00860     the input table is empty (i.e., does not contain any elements) and
    00861     FALSE otherwise.
    00862
    00863 Arguments:
    00864
    00865     Table - Supplies a pointer to the Generic Table.
    00866
    00867 Return Value:
    00868
    00869     BOOLEAN - if enabled the tree is empty.
    00870
    00871 --*/
    00872
    00873 {
    00874
    00875     //
    00876     // Table is empty if the root pointer is null.
    00877     //
    00878
    00879     return ((Table->TableRoot)?(FALSE):(TRUE));
    00880
    00881 }

PVOID RtlLookupElementGenericTable | ( | IN PRTL_GENERIC_TABLE | Table,
|  | IN PVOID | Buffer
| ) |

Definition at line 619 of file gentable.c.

References Buffer, and RtlLookupElementGenericTableFull().

Referenced by UdfLookupFcbTable().

    00626                    :
    00627
    00628     The function LookupElementGenericTable will find an element in a generic
    00629     table.  If the element is located the return value is a pointer to
    00630     the user defined structure associated with the element, otherwise if
    00631     the element is not located the return value is NULL.  The user supplied
    00632     input buffer is only used as a key in locating the element in the table.
    00633
    00634 Arguments:
    00635
    00636     Table - Pointer to the users Generic table to search for the key.
    00637
    00638     Buffer - Used for the comparasion.
    00639
    00640 Return Value:
    00641
    00642     PVOID - returns a pointer to the user data.
    00643
    00644 --*/
    00645
    00646 {
    00647     //
    00648     // Holds a pointer to the node in the table or what would be the
    00649     // parent of the node.
    00650     //
    00651     PRTL_SPLAY_LINKS NodeOrParent;
    00652
    00653     //
    00654     // Holds the result of the table lookup.
    00655     //
    00656     TABLE_SEARCH_RESULT Lookup;
    00657
    00658     return RtlLookupElementGenericTableFull(
    00659                 Table,
    00660                 Buffer,
    00661                 &NodeOrParent,
    00662                 &Lookup
    00663                 );
    00664 }

PVOID NTAPI RtlLookupElementGenericTableFull | ( | PRTL_GENERIC_TABLE | Table,
|  | PVOID | Buffer,
|  | OUT PVOID * | NodeOrParent,
|  | OUT TABLE_SEARCH_RESULT * | SearchResult
| ) |

Definition at line 669 of file gentable.c.

References Buffer, FindNodeOrParent(), NULL, PTABLE_ENTRY_HEADER, and RtlSplay().

Referenced by RtlLookupElementGenericTable().

    00678                    :
    00679
    00680     The function LookupElementGenericTableFull will find an element in a generic
    00681     table.  If the element is located the return value is a pointer to
    00682     the user defined structure associated with the element.  If the element is not
    00683     located then a pointer to the parent for the insert location is returned.  The
    00684     user must look at the SearchResult value to determine which is being returned.
    00685     The user can use the SearchResult and parent for a subsequent FullInsertElement
    00686     call to optimize the insert.
    00687
    00688 Arguments:
    00689
    00690     Table - Pointer to the users Generic table to search for the key.
    00691
    00692     Buffer - Used for the comparasion.
    00693
    00694     NodeOrParent - Address to store the desired Node or parent of the desired node.
    00695
    00696     SearchResult - Describes the relationship of the NodeOrParent with the desired Node.
    00697
    00698 Return Value:
    00699
    00700     PVOID - returns a pointer to the user data.
    00701
    00702 --*/
    00703
    00704 {
    00705
    00706     //
    00707     //  Lookup the element and save the result.
    00708     //
    00709
    00710     *SearchResult = FindNodeOrParent(
    00711                         Table,
    00712                         Buffer,
    00713                         (PRTL_SPLAY_LINKS *)NodeOrParent
    00714                         );
    00715
    00716     if ((*SearchResult == TableEmptyTree) || (*SearchResult != TableFoundNode)) {
    00717
    00718         return NULL;
    00719
    00720     } else {
    00721
    00722         //
    00723         // Splay the tree with this node.
    00724         //
    00725
    00726         Table->TableRoot = RtlSplay(*NodeOrParent);
    00727
    00728         //
    00729         // Return a pointer to the user data.
    00730         //
    00731
    00732         return &((PTABLE_ENTRY_HEADER)*NodeOrParent)->UserData;
    00733     }
    00734 }

ULONG RtlNumberGenericTableElements | ( | IN PRTL_GENERIC_TABLE | Table | ) |

Definition at line 1079 of file gentable.c.

    01085                    :
    01086
    01087     The function NumberGenericTableElements returns a ULONG value
    01088     which is the number of generic table elements currently inserted
    01089     in the generic table.
    01090
    01091 Arguments:
    01092
    01093     Table - Pointer to the generic table from which to find out the number
    01094     of elements.
    01095
    01096
    01097 Return Value:
    01098
    01099     ULONG - The number of elements in the generic table.
    01100
    01101 --*/
    01102 {
    01103
    01104     return Table->NumberGenericTableElements;
    01105
    01106 }