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