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_HEADERPTABLE_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 }


Generated on Sat May 15 19:43:51 2004 for test by doxygen 1.3.7