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