tstRTAvl.cpp@ 102792

Last change on this file since 102792 was 99775, checked in by vboxsync, 18 months ago
*: Mark functions as static if not used outside of a given compilation unit. Enables the compiler to optimize inlining, reduces the symbol tables, exposes unused functions and in some rare cases exposes mismtaches between function declarations and definitions, but most importantly reduces the number of parfait reports for the extern-function-no-forward-declaration category. This should not result in any functional changes, bugref:3409
Property svn:eol-style set to `native` Property svn:keywords set to `Id Revision`
File size: 54.3 KB

Line
1	/* $Id: tstRTAvl.cpp 99775 2023-05-12 12:21:58Z vboxsync $ */
2	/** @file
3	* IPRT Testcase - AVL trees.
4	*/
5
6	/*
7	* Copyright (C) 2006-2023 Oracle and/or its affiliates.
8	*
9	* This file is part of VirtualBox base platform packages, as
10	* available from https://www.virtualbox.org.
11	*
12	* This program is free software; you can redistribute it and/or
13	* modify it under the terms of the GNU General Public License
14	* as published by the Free Software Foundation, in version 3 of the
15	* License.
16	*
17	* This program is distributed in the hope that it will be useful, but
18	* WITHOUT ANY WARRANTY; without even the implied warranty of
19	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
20	* General Public License for more details.
21	*
22	* You should have received a copy of the GNU General Public License
23	* along with this program; if not, see <https://www.gnu.org/licenses>.
24	*
25	* The contents of this file may alternatively be used under the terms
26	* of the Common Development and Distribution License Version 1.0
27	* (CDDL), a copy of it is provided in the "COPYING.CDDL" file included
28	* in the VirtualBox distribution, in which case the provisions of the
29	* CDDL are applicable instead of those of the GPL.
30	*
31	* You may elect to license modified versions of this file under the
32	* terms and conditions of either the GPL or the CDDL or both.
33	*
34	* SPDX-License-Identifier: GPL-3.0-only OR CDDL-1.0
35	*/
36
37
38	/*********************************************************************************************************************************
39	* Header Files *
40	*********************************************************************************************************************************/
41	#include <iprt/avl.h>
42	#include <iprt/cpp/hardavlrange.h>
43
44	#include <iprt/asm.h>
45	#include <iprt/initterm.h>
46	#include <iprt/mem.h>
47	#include <iprt/rand.h>
48	#include <iprt/stdarg.h>
49	#include <iprt/stream.h>
50	#include <iprt/string.h>
51	#include <iprt/test.h>
52	#include <iprt/time.h>
53
54
55	/*********************************************************************************************************************************
56	* Structures and Typedefs *
57	*********************************************************************************************************************************/
58	typedef struct TRACKER
59	{
60	/** The max key value (exclusive). */
61	uint32_t MaxKey;
62	/** The last allocated key. */
63	uint32_t LastAllocatedKey;
64	/** The number of set bits in the bitmap. */
65	uint32_t cSetBits;
66	/** The bitmap size. */
67	uint32_t cbBitmap;
68	/** Bitmap containing the allocated nodes. */
69	uint8_t abBitmap[1];
70	} TRACKER, *PTRACKER;
71
72
73	/*********************************************************************************************************************************
74	* Global Variables *
75	*********************************************************************************************************************************/
76	static RTTEST g_hTest;
77	static RTRAND g_hRand;
78
79
80	/**
81	* Creates a new tracker.
82	*
83	* @returns Pointer to the new tracker.
84	* @param MaxKey The max key value for the tracker. (exclusive)
85	*/
86	static PTRACKER TrackerCreate(uint32_t MaxKey)
87	{
88	uint32_t cbBitmap = RT_ALIGN_32(MaxKey, 64) / 8;
89	PTRACKER pTracker = (PTRACKER)RTMemAllocZ(RT_UOFFSETOF_DYN(TRACKER, abBitmap[cbBitmap]));
90	if (pTracker)
91	{
92	pTracker->MaxKey = MaxKey;
93	pTracker->LastAllocatedKey = MaxKey;
94	pTracker->cbBitmap = cbBitmap;
95	Assert(pTracker->cSetBits == 0);
96	}
97	return pTracker;
98	}
99
100
101	/**
102	* Destroys a tracker.
103	*
104	* @param pTracker The tracker.
105	*/
106	static void TrackerDestroy(PTRACKER pTracker)
107	{
108	RTMemFree(pTracker);
109	}
110
111
112	/**
113	* Inserts a key range into the tracker.
114	*
115	* @returns success indicator.
116	* @param pTracker The tracker.
117	* @param Key The first key in the range.
118	* @param KeyLast The last key in the range. (inclusive)
119	*/
120	static bool TrackerInsert(PTRACKER pTracker, uint32_t Key, uint32_t KeyLast)
121	{
122	bool fRc = !ASMBitTestAndSet(pTracker->abBitmap, Key);
123	if (fRc)
124	pTracker->cSetBits++;
125	while (KeyLast != Key)
126	{
127	if (!ASMBitTestAndSet(pTracker->abBitmap, KeyLast))
128	pTracker->cSetBits++;
129	else
130	fRc = false;
131	KeyLast--;
132	}
133	return fRc;
134	}
135
136
137	/**
138	* Removes a key range from the tracker.
139	*
140	* @returns success indicator.
141	* @param pTracker The tracker.
142	* @param Key The first key in the range.
143	* @param KeyLast The last key in the range. (inclusive)
144	*/
145	static bool TrackerRemove(PTRACKER pTracker, uint32_t Key, uint32_t KeyLast)
146	{
147	bool fRc = ASMBitTestAndClear(pTracker->abBitmap, Key);
148	if (fRc)
149	pTracker->cSetBits--;
150	while (KeyLast != Key)
151	{
152	if (ASMBitTestAndClear(pTracker->abBitmap, KeyLast))
153	pTracker->cSetBits--;
154	else
155	fRc = false;
156	KeyLast--;
157	}
158	return fRc;
159	}
160
161
162	/**
163	* Random key range allocation.
164	*
165	* @returns success indicator.
166	* @param pTracker The tracker.
167	* @param pKey Where to store the first key in the allocated range.
168	* @param pKeyLast Where to store the first key in the allocated range.
169	* @param cMaxKey The max range length.
170	* @remark The caller has to call TrackerInsert.
171	*/
172	static bool TrackerNewRandomEx(PTRACKER pTracker, uint32_t pKey, uint32_t pKeyLast, uint32_t cMaxKeys)
173	{
174	/*
175	* Find a key.
176	*/
177	uint32_t Key = RTRandAdvU32Ex(g_hRand, 0, pTracker->MaxKey - 1);
178	if (ASMBitTest(pTracker->abBitmap, Key))
179	{
180	if (pTracker->cSetBits >= pTracker->MaxKey)
181	return false;
182
183	int Key2 = ASMBitNextClear(pTracker->abBitmap, pTracker->MaxKey, Key);
184	if (Key2 > 0)
185	Key = Key2;
186	else
187	{
188	/* we're missing a ASMBitPrevClear function, so just try another, lower, value.*/
189	for (;;)
190	{
191	const uint32_t KeyPrev = Key;
192	Key = RTRandAdvU32Ex(g_hRand, 0, KeyPrev - 1);
193	if (!ASMBitTest(pTracker->abBitmap, Key))
194	break;
195	Key2 = ASMBitNextClear(pTracker->abBitmap, RT_ALIGN_32(KeyPrev, 32), Key);
196	if (Key2 > 0)
197	{
198	Key = Key2;
199	break;
200	}
201	}
202	}
203	}
204
205	/*
206	* Determine the range.
207	*/
208	uint32_t KeyLast;
209	if (cMaxKeys == 1 \|\| !pKeyLast)
210	KeyLast = Key;
211	else
212	{
213	uint32_t cKeys = RTRandAdvU32Ex(g_hRand, 0, RT_MIN(pTracker->MaxKey - Key, cMaxKeys - 1));
214	KeyLast = Key + cKeys;
215	int Key2 = ASMBitNextSet(pTracker->abBitmap, RT_ALIGN_32(KeyLast, 32), Key);
216	if ( Key2 > 0
217	&& (unsigned)Key2 <= KeyLast)
218	KeyLast = Key2 - 1;
219	}
220
221	/*
222	* Return.
223	*/
224	*pKey = Key;
225	if (pKeyLast)
226	*pKeyLast = KeyLast;
227	return true;
228	}
229
230
231	/**
232	* Random single key allocation.
233	*
234	* @returns success indicator.
235	* @param pTracker The tracker.
236	* @param pKey Where to store the allocated key.
237	* @remark The caller has to call TrackerInsert.
238	*/
239	static bool TrackerNewRandom(PTRACKER pTracker, uint32_t *pKey)
240	{
241	return TrackerNewRandomEx(pTracker, pKey, NULL, 1);
242	}
243
244
245	/**
246	* Random single key 'lookup'.
247	*
248	* @returns success indicator.
249	* @param pTracker The tracker.
250	* @param pKey Where to store the allocated key.
251	* @remark The caller has to call TrackerRemove.
252	*/
253	static bool TrackerFindRandom(PTRACKER pTracker, uint32_t *pKey)
254	{
255	uint32_t Key = RTRandAdvU32Ex(g_hRand, 0, pTracker->MaxKey - 1);
256	if (!ASMBitTest(pTracker->abBitmap, Key))
257	{
258	if (!pTracker->cSetBits)
259	return false;
260
261	int Key2 = ASMBitNextSet(pTracker->abBitmap, pTracker->MaxKey, Key);
262	if (Key2 > 0)
263	Key = Key2;
264	else
265	{
266	/* we're missing a ASMBitPrevSet function, so here's a quick replacement hack. */
267	uint32_t const pu32Bitmap = (uint32_t const )&pTracker->abBitmap[0];
268	Key >>= 5;
269	do
270	{
271	uint32_t u32;
272	if ((u32 = pu32Bitmap[Key]) != 0)
273	{
274	*pKey = ASMBitLastSetU32(u32) - 1 + (Key << 5);
275	return true;
276	}
277	} while (Key-- > 0);
278
279	Key2 = ASMBitFirstSet(pTracker->abBitmap, pTracker->MaxKey);
280	if (Key2 == -1)
281	{
282	RTTestIFailed("cSetBits=%u - but ASMBitFirstSet failed to find any", pTracker->cSetBits);
283	return false;
284	}
285	Key = Key2;
286	}
287	}
288
289	*pKey = Key;
290	return true;
291	}
292
293
294	/**
295	* Gets the number of keys in the tree.
296	*/
297	static uint32_t TrackerGetCount(PTRACKER pTracker)
298	{
299	return pTracker->cSetBits;
300	}
301
302
303	/*
304	bool TrackerAllocSeq(PTRACKER pTracker, uint32_t pKey, uint32_t pKeyLast, uint32_t cMaxKeys)
305	{
306	return false;
307	}*/
308
309
310	/**
311	* Prints an unbuffered char.
312	* @param ch The char.
313	*/
314	static void ProgressChar(char ch)
315	{
316	//RTTestIPrintf(RTTESTLVL_INFO, "%c", ch);
317	RTTestIPrintf(RTTESTLVL_SUB_TEST, "%c", ch);
318	}
319
320	/**
321	* Prints a progress indicator label.
322	* @param cMax The max number of operations (exclusive).
323	* @param pszFormat The format string.
324	* @param ... The arguments to the format string.
325	*/
326	DECLINLINE(void) ProgressPrintf(unsigned cMax, const char *pszFormat, ...)
327	{
328	if (cMax < 10000)
329	return;
330
331	va_list va;
332	va_start(va, pszFormat);
333	//RTTestIPrintfV(RTTESTLVL_INFO, pszFormat, va);
334	RTTestIPrintfV(RTTESTLVL_SUB_TEST, pszFormat, va);
335	va_end(va);
336	}
337
338
339	/**
340	* Prints a progress indicator dot.
341	* @param iCur The current operation. (can be descending too)
342	* @param cMax The max number of operations (exclusive).
343	*/
344	DECLINLINE(void) Progress(unsigned iCur, unsigned cMax)
345	{
346	if (cMax < 10000)
347	return;
348	if (!(iCur % (cMax / 20)))
349	ProgressChar('.');
350	}
351
352
353	static int avlogcphys(unsigned cMax)
354	{
355	/*
356	* Simple linear insert and remove.
357	*/
358	if (cMax >= 10000)
359	RTTestISubF("oGCPhys(%d): linear left", cMax);
360	PAVLOGCPHYSTREE pTree = (PAVLOGCPHYSTREE)RTMemAllocZ(sizeof(*pTree));
361	unsigned i;
362	for (i = 0; i < cMax; i++)
363	{
364	Progress(i, cMax);
365	PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
366	pNode->Key = i;
367	if (!RTAvloGCPhysInsert(pTree, pNode))
368	{
369	RTTestIFailed("linear left insert i=%d\n", i);
370	return 1;
371	}
372	/* negative. */
373	AVLOGCPHYSNODECORE Node = *pNode;
374	if (RTAvloGCPhysInsert(pTree, &Node))
375	{
376	RTTestIFailed("linear left negative insert i=%d\n", i);
377	return 1;
378	}
379	}
380
381	ProgressPrintf(cMax, "~");
382	for (i = 0; i < cMax; i++)
383	{
384	Progress(i, cMax);
385	PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemove(pTree, i);
386	if (!pNode)
387	{
388	RTTestIFailed("linear left remove i=%d\n", i);
389	return 1;
390	}
391	memset(pNode, 0xcc, sizeof(*pNode));
392	RTMemFree(pNode);
393
394	/* negative */
395	pNode = RTAvloGCPhysRemove(pTree, i);
396	if (pNode)
397	{
398	RTTestIFailed("linear left negative remove i=%d\n", i);
399	return 1;
400	}
401	}
402
403	/*
404	* Simple linear insert and remove from the right.
405	*/
406	if (cMax >= 10000)
407	RTTestISubF("oGCPhys(%d): linear right", cMax);
408	for (i = 0; i < cMax; i++)
409	{
410	Progress(i, cMax);
411	PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
412	pNode->Key = i;
413	if (!RTAvloGCPhysInsert(pTree, pNode))
414	{
415	RTTestIFailed("linear right insert i=%d\n", i);
416	return 1;
417	}
418	/* negative. */
419	AVLOGCPHYSNODECORE Node = *pNode;
420	if (RTAvloGCPhysInsert(pTree, &Node))
421	{
422	RTTestIFailed("linear right negative insert i=%d\n", i);
423	return 1;
424	}
425	}
426
427	ProgressPrintf(cMax, "~");
428	while (i-- > 0)
429	{
430	Progress(i, cMax);
431	PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemove(pTree, i);
432	if (!pNode)
433	{
434	RTTestIFailed("linear right remove i=%d\n", i);
435	return 1;
436	}
437	memset(pNode, 0xcc, sizeof(*pNode));
438	RTMemFree(pNode);
439
440	/* negative */
441	pNode = RTAvloGCPhysRemove(pTree, i);
442	if (pNode)
443	{
444	RTTestIFailed("linear right negative remove i=%d\n", i);
445	return 1;
446	}
447	}
448
449	/*
450	* Linear insert but root based removal.
451	*/
452	if (cMax >= 10000)
453	RTTestISubF("oGCPhys(%d): linear root", cMax);
454	for (i = 0; i < cMax; i++)
455	{
456	Progress(i, cMax);
457	PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
458	pNode->Key = i;
459	if (!RTAvloGCPhysInsert(pTree, pNode))
460	{
461	RTTestIFailed("linear root insert i=%d\n", i);
462	return 1;
463	}
464	/* negative. */
465	AVLOGCPHYSNODECORE Node = *pNode;
466	if (RTAvloGCPhysInsert(pTree, &Node))
467	{
468	RTTestIFailed("linear root negative insert i=%d\n", i);
469	return 1;
470	}
471	}
472
473	ProgressPrintf(cMax, "~");
474	while (i-- > 0)
475	{
476	Progress(i, cMax);
477	PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)((intptr_t)pTree + *pTree);
478	RTGCPHYS Key = pNode->Key;
479	pNode = RTAvloGCPhysRemove(pTree, Key);
480	if (!pNode)
481	{
482	RTTestIFailed("linear root remove i=%d Key=%d\n", i, (unsigned)Key);
483	return 1;
484	}
485	memset(pNode, 0xcc, sizeof(*pNode));
486	RTMemFree(pNode);
487
488	/* negative */
489	pNode = RTAvloGCPhysRemove(pTree, Key);
490	if (pNode)
491	{
492	RTTestIFailed("linear root negative remove i=%d Key=%d\n", i, (unsigned)Key);
493	return 1;
494	}
495	}
496	if (*pTree)
497	{
498	RTTestIFailed("sparse remove didn't remove it all!\n");
499	return 1;
500	}
501
502	/*
503	* Make a sparsely populated tree and remove the nodes using best fit in 5 cycles.
504	*/
505	const unsigned cMaxSparse = RT_ALIGN(cMax, 32);
506	if (cMaxSparse >= 10000)
507	RTTestISubF("oGCPhys(%d): sparse", cMax);
508	for (i = 0; i < cMaxSparse; i += 8)
509	{
510	Progress(i, cMaxSparse);
511	PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
512	pNode->Key = i;
513	if (!RTAvloGCPhysInsert(pTree, pNode))
514	{
515	RTTestIFailed("sparse insert i=%d\n", i);
516	return 1;
517	}
518	/* negative. */
519	AVLOGCPHYSNODECORE Node = *pNode;
520	if (RTAvloGCPhysInsert(pTree, &Node))
521	{
522	RTTestIFailed("sparse negative insert i=%d\n", i);
523	return 1;
524	}
525	}
526
527	/* Remove using best fit in 5 cycles. */
528	ProgressPrintf(cMaxSparse, "~");
529	unsigned j;
530	for (j = 0; j < 4; j++)
531	{
532	for (i = 0; i < cMaxSparse; i += 8 * 4)
533	{
534	Progress(i, cMax); // good enough
535	PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemoveBestFit(pTree, i, true);
536	if (!pNode)
537	{
538	RTTestIFailed("sparse remove i=%d j=%d\n", i, j);
539	return 1;
540	}
541	if (pNode->Key - (unsigned long)i >= 8 * 4)
542	{
543	RTTestIFailed("sparse remove i=%d j=%d Key=%d\n", i, j, (unsigned)pNode->Key);
544	return 1;
545	}
546	memset(pNode, 0xdd, sizeof(*pNode));
547	RTMemFree(pNode);
548	}
549	}
550	if (*pTree)
551	{
552	RTTestIFailed("sparse remove didn't remove it all!\n");
553	return 1;
554	}
555	RTMemFree(pTree);
556	ProgressPrintf(cMaxSparse, "\n");
557	return 0;
558	}
559
560
561	static DECLCALLBACK(int) avlogcphysCallbackCounter(PAVLOGCPHYSNODECORE pNode, void *pvUser)
562	{
563	RT_NOREF(pNode);
564	(uint32_t )pvUser += 1;
565	return 0;
566	}
567
568	static int avlogcphysRand(unsigned cMax, unsigned cMax2, uint32_t fCountMask)
569	{
570	PAVLOGCPHYSTREE pTree = (PAVLOGCPHYSTREE)RTMemAllocZ(sizeof(*pTree));
571	unsigned i;
572
573	/*
574	* Random tree.
575	*/
576	if (cMax >= 10000)
577	RTTestISubF("oGCPhys(%d, %d): random", cMax, cMax2);
578	PTRACKER pTracker = TrackerCreate(cMax2);
579	if (!pTracker)
580	{
581	RTTestIFailed("failed to create %d tracker!\n", cMax2);
582	return 1;
583	}
584
585	/* Insert a number of nodes in random order. */
586	for (i = 0; i < cMax; i++)
587	{
588	Progress(i, cMax);
589	uint32_t Key;
590	if (!TrackerNewRandom(pTracker, &Key))
591	{
592	RTTestIFailed("failed to allocate node no. %d\n", i);
593	TrackerDestroy(pTracker);
594	return 1;
595	}
596	PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
597	pNode->Key = Key;
598	if (!RTAvloGCPhysInsert(pTree, pNode))
599	{
600	RTTestIFailed("random insert i=%d Key=%#x\n", i, Key);
601	return 1;
602	}
603	/* negative. */
604	AVLOGCPHYSNODECORE Node = *pNode;
605	if (RTAvloGCPhysInsert(pTree, &Node))
606	{
607	RTTestIFailed("linear negative insert i=%d Key=%#x\n", i, Key);
608	return 1;
609	}
610	TrackerInsert(pTracker, Key, Key);
611
612	if (!(i & fCountMask))
613	{
614	uint32_t cCount = 0;
615	RTAvloGCPhysDoWithAll(pTree, i & 1, avlogcphysCallbackCounter, &cCount);
616	if (cCount != TrackerGetCount(pTracker))
617	RTTestIFailed("wrong tree count after random insert i=%d: %u, expected %u", i, cCount, TrackerGetCount(pTracker));
618	}
619	}
620
621	{
622	uint32_t cCount = 0;
623	RTAvloGCPhysDoWithAll(pTree, i & 1, avlogcphysCallbackCounter, &cCount);
624	if (cCount != TrackerGetCount(pTracker))
625	RTTestIFailed("wrong tree count after random insert i=%d: %u, expected %u", i, cCount, TrackerGetCount(pTracker));
626	}
627
628
629	/* delete the nodes in random order. */
630	ProgressPrintf(cMax, "~");
631	while (i-- > 0)
632	{
633	Progress(i, cMax);
634	uint32_t Key;
635	if (!TrackerFindRandom(pTracker, &Key))
636	{
637	RTTestIFailed("failed to find free node no. %d\n", i);
638	TrackerDestroy(pTracker);
639	return 1;
640	}
641
642	PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemove(pTree, Key);
643	if (!pNode)
644	{
645	RTTestIFailed("random remove i=%d Key=%#x\n", i, Key);
646	return 1;
647	}
648	if (pNode->Key != Key)
649	{
650	RTTestIFailed("random remove i=%d Key=%#x pNode->Key=%#x\n", i, Key, (unsigned)pNode->Key);
651	return 1;
652	}
653	TrackerRemove(pTracker, Key, Key);
654	memset(pNode, 0xdd, sizeof(*pNode));
655	RTMemFree(pNode);
656
657	if (!(i & fCountMask))
658	{
659	uint32_t cCount = 0;
660	RTAvloGCPhysDoWithAll(pTree, i & 1, avlogcphysCallbackCounter, &cCount);
661	if (cCount != TrackerGetCount(pTracker))
662	RTTestIFailed("wrong tree count after random remove i=%d: %u, expected %u", i, cCount, TrackerGetCount(pTracker));
663	}
664	}
665	{
666	uint32_t cCount = 0;
667	RTAvloGCPhysDoWithAll(pTree, i & 1, avlogcphysCallbackCounter, &cCount);
668	if (cCount != TrackerGetCount(pTracker))
669	RTTestIFailed("wrong tree count after random insert i=%d: %u, expected %u", i, cCount, TrackerGetCount(pTracker));
670	}
671	if (*pTree)
672	{
673	RTTestIFailed("random remove didn't remove it all!\n");
674	return 1;
675	}
676	ProgressPrintf(cMax, "\n");
677	TrackerDestroy(pTracker);
678	RTMemFree(pTree);
679	return 0;
680	}
681
682
683
684	static int avlrogcphys(void)
685	{
686	unsigned i;
687	unsigned j;
688	unsigned k;
689	PAVLROGCPHYSTREE pTree = (PAVLROGCPHYSTREE)RTMemAllocZ(sizeof(*pTree));
690
691	AssertCompileSize(AVLOGCPHYSNODECORE, 24);
692	AssertCompileSize(AVLROGCPHYSNODECORE, 32);
693
694	RTTestISubF("RTAvlroGCPhys");
695
696	/*
697	* Simple linear insert, get and remove.
698	*/
699	/* insert */
700	for (i = 0; i < 65536; i += 4)
701	{
702	PAVLROGCPHYSNODECORE pNode = (PAVLROGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
703	pNode->Key = i;
704	pNode->KeyLast = i + 3;
705	if (!RTAvlroGCPhysInsert(pTree, pNode))
706	{
707	RTTestIFailed("linear insert i=%d\n", (unsigned)i);
708	return 1;
709	}
710
711	/* negative. */
712	AVLROGCPHYSNODECORE Node = *pNode;
713	for (j = i + 3; j > i - 32; j--)
714	{
715	for (k = i; k < i + 32; k++)
716	{
717	Node.Key = RT_MIN(j, k);
718	Node.KeyLast = RT_MAX(k, j);
719	if (RTAvlroGCPhysInsert(pTree, &Node))
720	{
721	RTTestIFailed("linear negative insert i=%d j=%d k=%d\n", i, j, k);
722	return 1;
723	}
724	}
725	}
726	}
727
728	/* do gets. */
729	for (i = 0; i < 65536; i += 4)
730	{
731	PAVLROGCPHYSNODECORE pNode = RTAvlroGCPhysGet(pTree, i);
732	if (!pNode)
733	{
734	RTTestIFailed("linear get i=%d\n", i);
735	return 1;
736	}
737	if (pNode->Key > i \|\| pNode->KeyLast < i)
738	{
739	RTTestIFailed("linear get i=%d Key=%d KeyLast=%d\n", i, (unsigned)pNode->Key, (unsigned)pNode->KeyLast);
740	return 1;
741	}
742
743	for (j = 0; j < 4; j++)
744	{
745	if (RTAvlroGCPhysRangeGet(pTree, i + j) != pNode)
746	{
747	RTTestIFailed("linear range get i=%d j=%d\n", i, j);
748	return 1;
749	}
750	}
751
752	/* negative. */
753	if ( RTAvlroGCPhysGet(pTree, i + 1)
754	\|\| RTAvlroGCPhysGet(pTree, i + 2)
755	\|\| RTAvlroGCPhysGet(pTree, i + 3))
756	{
757	RTTestIFailed("linear negative get i=%d + n\n", i);
758	return 1;
759	}
760
761	}
762
763	/* remove */
764	for (i = 0; i < 65536; i += 4)
765	{
766	PAVLROGCPHYSNODECORE pNode = RTAvlroGCPhysRemove(pTree, i);
767	if (!pNode)
768	{
769	RTTestIFailed("linear remove i=%d\n", i);
770	return 1;
771	}
772	memset(pNode, 0xcc, sizeof(*pNode));
773	RTMemFree(pNode);
774
775	/* negative */
776	if ( RTAvlroGCPhysRemove(pTree, i)
777	\|\| RTAvlroGCPhysRemove(pTree, i + 1)
778	\|\| RTAvlroGCPhysRemove(pTree, i + 2)
779	\|\| RTAvlroGCPhysRemove(pTree, i + 3))
780	{
781	RTTestIFailed("linear negative remove i=%d + n\n", i);
782	return 1;
783	}
784	}
785
786	/*
787	* Make a sparsely populated tree.
788	*/
789	for (i = 0; i < 65536; i += 8)
790	{
791	PAVLROGCPHYSNODECORE pNode = (PAVLROGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
792	pNode->Key = i;
793	pNode->KeyLast = i + 3;
794	if (!RTAvlroGCPhysInsert(pTree, pNode))
795	{
796	RTTestIFailed("sparse insert i=%d\n", i);
797	return 1;
798	}
799	/* negative. */
800	AVLROGCPHYSNODECORE Node = *pNode;
801	const RTGCPHYS jMin = i > 32 ? i - 32 : 1;
802	const RTGCPHYS kMax = i + 32;
803	for (j = pNode->KeyLast; j >= jMin; j--)
804	{
805	for (k = pNode->Key; k < kMax; k++)
806	{
807	Node.Key = RT_MIN(j, k);
808	Node.KeyLast = RT_MAX(k, j);
809	if (RTAvlroGCPhysInsert(pTree, &Node))
810	{
811	RTTestIFailed("sparse negative insert i=%d j=%d k=%d\n", i, j, k);
812	return 1;
813	}
814	}
815	}
816	}
817
818	/*
819	* Get and Remove using range matching in 5 cycles.
820	*/
821	for (j = 0; j < 4; j++)
822	{
823	for (i = 0; i < 65536; i += 8 * 4)
824	{
825	/* gets */
826	RTGCPHYS KeyBase = i + j * 8;
827	PAVLROGCPHYSNODECORE pNode = RTAvlroGCPhysGet(pTree, KeyBase);
828	if (!pNode)
829	{
830	RTTestIFailed("sparse get i=%d j=%d KeyBase=%d\n", i, j, (unsigned)KeyBase);
831	return 1;
832	}
833	if (pNode->Key > KeyBase \|\| pNode->KeyLast < KeyBase)
834	{
835	RTTestIFailed("sparse get i=%d j=%d KeyBase=%d pNode->Key=%d\n", i, j, (unsigned)KeyBase, (unsigned)pNode->Key);
836	return 1;
837	}
838	for (k = KeyBase; k < KeyBase + 4; k++)
839	{
840	if (RTAvlroGCPhysRangeGet(pTree, k) != pNode)
841	{
842	RTTestIFailed("sparse range get i=%d j=%d k=%d\n", i, j, k);
843	return 1;
844	}
845	}
846
847	/* negative gets */
848	for (k = i + j; k < KeyBase + 8; k++)
849	{
850	if ( k != KeyBase
851	&& RTAvlroGCPhysGet(pTree, k))
852	{
853	RTTestIFailed("sparse negative get i=%d j=%d k=%d\n", i, j, k);
854	return 1;
855	}
856	}
857	for (k = i + j; k < KeyBase; k++)
858	{
859	if (RTAvlroGCPhysRangeGet(pTree, k))
860	{
861	RTTestIFailed("sparse negative range get i=%d j=%d k=%d\n", i, j, k);
862	return 1;
863	}
864	}
865	for (k = KeyBase + 4; k < KeyBase + 8; k++)
866	{
867	if (RTAvlroGCPhysRangeGet(pTree, k))
868	{
869	RTTestIFailed("sparse negative range get i=%d j=%d k=%d\n", i, j, k);
870	return 1;
871	}
872	}
873
874	/* remove */
875	RTGCPHYS Key = KeyBase + ((i / 19) % 4);
876	if (RTAvlroGCPhysRangeRemove(pTree, Key) != pNode)
877	{
878	RTTestIFailed("sparse remove i=%d j=%d Key=%d\n", i, j, (unsigned)Key);
879	return 1;
880	}
881	memset(pNode, 0xdd, sizeof(*pNode));
882	RTMemFree(pNode);
883	}
884	}
885	if (*pTree)
886	{
887	RTTestIFailed("sparse remove didn't remove it all!\n");
888	return 1;
889	}
890
891
892	/*
893	* Realworld testcase.
894	*/
895	struct
896	{
897	AVLROGCPHYSTREE Tree;
898	AVLROGCPHYSNODECORE aNode[4];
899	} s1, s2, s3;
900	RT_ZERO(s1);
901	RT_ZERO(s2);
902	RT_ZERO(s3);
903
904	s1.aNode[0].Key = 0x00030000;
905	s1.aNode[0].KeyLast = 0x00030fff;
906	s1.aNode[1].Key = 0x000a0000;
907	s1.aNode[1].KeyLast = 0x000bffff;
908	s1.aNode[2].Key = 0xe0000000;
909	s1.aNode[2].KeyLast = 0xe03fffff;
910	s1.aNode[3].Key = 0xfffe0000;
911	s1.aNode[3].KeyLast = 0xfffe0ffe;
912	for (i = 0; i < RT_ELEMENTS(s1.aNode); i++)
913	{
914	PAVLROGCPHYSNODECORE pNode = &s1.aNode[i];
915	if (!RTAvlroGCPhysInsert(&s1.Tree, pNode))
916	{
917	RTTestIFailed("real insert i=%d\n", i);
918	return 1;
919	}
920	if (RTAvlroGCPhysInsert(&s1.Tree, pNode))
921	{
922	RTTestIFailed("real negative insert i=%d\n", i);
923	return 1;
924	}
925	if (RTAvlroGCPhysGet(&s1.Tree, pNode->Key) != pNode)
926	{
927	RTTestIFailed("real get (1) i=%d\n", i);
928	return 1;
929	}
930	if (RTAvlroGCPhysGet(&s1.Tree, pNode->KeyLast) != NULL)
931	{
932	RTTestIFailed("real negative get (2) i=%d\n", i);
933	return 1;
934	}
935	if (RTAvlroGCPhysRangeGet(&s1.Tree, pNode->Key) != pNode)
936	{
937	RTTestIFailed("real range get (1) i=%d\n", i);
938	return 1;
939	}
940	if (RTAvlroGCPhysRangeGet(&s1.Tree, pNode->Key + 1) != pNode)
941	{
942	RTTestIFailed("real range get (2) i=%d\n", i);
943	return 1;
944	}
945	if (RTAvlroGCPhysRangeGet(&s1.Tree, pNode->KeyLast) != pNode)
946	{
947	RTTestIFailed("real range get (3) i=%d\n", i);
948	return 1;
949	}
950	}
951
952	s3 = s1;
953	s1 = s2;
954	for (i = 0; i < RT_ELEMENTS(s3.aNode); i++)
955	{
956	PAVLROGCPHYSNODECORE pNode = &s3.aNode[i];
957	if (RTAvlroGCPhysGet(&s3.Tree, pNode->Key) != pNode)
958	{
959	RTTestIFailed("real get (10) i=%d\n", i);
960	return 1;
961	}
962	if (RTAvlroGCPhysRangeGet(&s3.Tree, pNode->Key) != pNode)
963	{
964	RTTestIFailed("real range get (10) i=%d\n", i);
965	return 1;
966	}
967
968	j = pNode->Key + 1;
969	do
970	{
971	if (RTAvlroGCPhysGet(&s3.Tree, j) != NULL)
972	{
973	RTTestIFailed("real negative get (11) i=%d j=%#x\n", i, j);
974	return 1;
975	}
976	if (RTAvlroGCPhysRangeGet(&s3.Tree, j) != pNode)
977	{
978	RTTestIFailed("real range get (11) i=%d j=%#x\n", i, j);
979	return 1;
980	}
981	} while (j++ < pNode->KeyLast);
982	}
983
984	return 0;
985	}
986
987
988	static int avlul(void)
989	{
990	RTTestISubF("RTAvlUL");
991
992	/*
993	* Simple linear insert and remove.
994	*/
995	PAVLULNODECORE pTree = 0;
996	unsigned cInserted = 0;
997	unsigned i;
998
999	/* insert */
1000	for (i = 0; i < 65536; i++, cInserted++)
1001	{
1002	PAVLULNODECORE pNode = (PAVLULNODECORE)RTMemAlloc(sizeof(*pNode));
1003	pNode->Key = i;
1004	if (!RTAvlULInsert(&pTree, pNode))
1005	{
1006	RTTestIFailed("linear insert i=%d\n", i);
1007	return 1;
1008	}
1009
1010	/* negative. */
1011	AVLULNODECORE Node = *pNode;
1012	if (RTAvlULInsert(&pTree, &Node))
1013	{
1014	RTTestIFailed("linear negative insert i=%d\n", i);
1015	return 1;
1016	}
1017
1018	/* check height */
1019	uint8_t const cHeight = pTree ? pTree->uchHeight : 0;
1020	uint32_t const cMax = cHeight > 0 ? RT_BIT_32(cHeight) : 1;
1021	if (cInserted > cMax \|\| cInserted < (cMax >> 2))
1022	RTTestIFailed("bad tree height after linear insert i=%d: cMax=%#x, cInserted=%#x\n", i, cMax, cInserted);
1023	}
1024
1025	for (i = 0; i < 65536; i++, cInserted--)
1026	{
1027	PAVLULNODECORE pNode = RTAvlULRemove(&pTree, i);
1028	if (!pNode)
1029	{
1030	RTTestIFailed("linear remove i=%d\n", i);
1031	return 1;
1032	}
1033	pNode->pLeft = (PAVLULNODECORE)(uintptr_t)0xaaaaaaaa;
1034	pNode->pRight = (PAVLULNODECORE)(uintptr_t)0xbbbbbbbb;
1035	pNode->uchHeight = 'e';
1036	RTMemFree(pNode);
1037
1038	/* negative */
1039	pNode = RTAvlULRemove(&pTree, i);
1040	if (pNode)
1041	{
1042	RTTestIFailed("linear negative remove i=%d\n", i);
1043	return 1;
1044	}
1045
1046	/* check height */
1047	uint8_t const cHeight = pTree ? pTree->uchHeight : 0;
1048	uint32_t const cMax = cHeight > 0 ? RT_BIT_32(cHeight) : 1;
1049	if (cInserted > cMax \|\| cInserted < (cMax >> 2))
1050	RTTestIFailed("bad tree height after linear removal i=%d: cMax=%#x, cInserted=%#x\n", i, cMax, cInserted);
1051	}
1052
1053	/*
1054	* Make a sparsely populated tree.
1055	*/
1056	for (i = 0; i < 65536; i += 8, cInserted++)
1057	{
1058	PAVLULNODECORE pNode = (PAVLULNODECORE)RTMemAlloc(sizeof(*pNode));
1059	pNode->Key = i;
1060	if (!RTAvlULInsert(&pTree, pNode))
1061	{
1062	RTTestIFailed("linear insert i=%d\n", i);
1063	return 1;
1064	}
1065
1066	/* negative. */
1067	AVLULNODECORE Node = *pNode;
1068	if (RTAvlULInsert(&pTree, &Node))
1069	{
1070	RTTestIFailed("linear negative insert i=%d\n", i);
1071	return 1;
1072	}
1073
1074	/* check height */
1075	uint8_t const cHeight = pTree ? pTree->uchHeight : 0;
1076	uint32_t const cMax = cHeight > 0 ? RT_BIT_32(cHeight) : 1;
1077	if (cInserted > cMax \|\| cInserted < (cMax >> 2))
1078	RTTestIFailed("bad tree height after sparse insert i=%d: cMax=%#x, cInserted=%#x\n", i, cMax, cInserted);
1079	}
1080
1081	/*
1082	* Remove using best fit in 5 cycles.
1083	*/
1084	unsigned j;
1085	for (j = 0; j < 4; j++)
1086	{
1087	for (i = 0; i < 65536; i += 8 * 4, cInserted--)
1088	{
1089	PAVLULNODECORE pNode = RTAvlULRemoveBestFit(&pTree, i, true);
1090	//PAVLULNODECORE pNode = RTAvlULRemove(&pTree, i + j * 8);
1091	if (!pNode)
1092	{
1093	RTTestIFailed("sparse remove i=%d j=%d\n", i, j);
1094	return 1;
1095	}
1096	pNode->pLeft = (PAVLULNODECORE)(uintptr_t)0xdddddddd;
1097	pNode->pRight = (PAVLULNODECORE)(uintptr_t)0xcccccccc;
1098	pNode->uchHeight = 'E';
1099	RTMemFree(pNode);
1100
1101	/* check height */
1102	uint8_t const cHeight = pTree ? pTree->uchHeight : 0;
1103	uint32_t const cMax = cHeight > 0 ? RT_BIT_32(cHeight) : 1;
1104	if (cInserted > cMax \|\| cInserted < (cMax >> 2))
1105	RTTestIFailed("bad tree height after sparse removal i=%d: cMax=%#x, cInserted=%#x\n", i, cMax, cInserted);
1106	}
1107	}
1108
1109	return 0;
1110	}
1111
1112
1113	/*********************************************************************************************************************************
1114	* RTCHardAvlRangeTreeGCPhys *
1115	*********************************************************************************************************************************/
1116
1117	typedef struct TESTNODE
1118	{
1119	RTGCPHYS Key;
1120	RTGCPHYS KeyLast;
1121	uint32_t idxLeft;
1122	uint32_t idxRight;
1123	uint8_t cHeight;
1124	} MYTESTNODE;
1125
1126	static DECLCALLBACK(int) hardAvlRangeTreeGCPhysEnumCallbackAscBy4(TESTNODE pNode, void pvUser)
1127	{
1128	PRTGCPHYS pExpect = (PRTGCPHYS)pvUser;
1129	if (pNode->Key != *pExpect)
1130	RTTestIFailed("Key=%RGp, expected %RGp\n", pNode->Key, *pExpect);
1131	*pExpect = pNode->Key + 4;
1132	return VINF_SUCCESS;
1133	}
1134
1135
1136	static DECLCALLBACK(int) hardAvlRangeTreeGCPhysEnumCallbackDescBy4(TESTNODE pNode, void pvUser)
1137	{
1138	PRTGCPHYS pExpect = (PRTGCPHYS)pvUser;
1139	if (pNode->Key != *pExpect)
1140	RTTestIFailed("Key=%RGp, expected %RGp\n", pNode->Key, *pExpect);
1141	*pExpect = pNode->Key - 4;
1142	return VINF_SUCCESS;
1143	}
1144
1145
1146	static DECLCALLBACK(int) hardAvlRangeTreeGCPhysEnumCallbackCount(TESTNODE pNode, void pvUser)
1147	{
1148	(uint32_t )pvUser += 1;
1149	RT_NOREF(pNode);
1150	return VINF_SUCCESS;
1151	}
1152
1153
1154	static uint32_t PickClearBit(uint64_t *pbm, uint32_t cItems)
1155	{
1156	uint32_t idx = RTRandAdvU32Ex(g_hRand, 0, cItems - 1);
1157	if (ASMBitTest(pbm, idx) == 0)
1158	return idx;
1159
1160	/* Scan forward as we've got code for that already: */
1161	uint32_t const idxOrg = idx;
1162	idx = ASMBitNextClear(pbm, cItems, idx);
1163	if ((int32_t)idx >= 0)
1164	return idx;
1165
1166	/* Scan backwards bit-by-bit because we don't have code for this: */
1167	for (idx = idxOrg - 1; idx < cItems; idx--)
1168	if (ASMBitTest(pbm, idx) == 0)
1169	return idx;
1170
1171	AssertFailed();
1172	RTTestIFailed("no clear bit in bitmap!\n");
1173	return 0;
1174	}
1175
1176
1177	static uint32_t PickClearBitAndSetIt(uint64_t *pbm, uint32_t cItems)
1178	{
1179	uint32_t idx = PickClearBit(pbm, cItems);
1180	RTTESTI_CHECK(ASMBitTestAndSet(pbm, idx) == false);
1181	return idx;
1182	}
1183
1184
1185	static uint32_t PickSetBit(uint64_t *pbm, uint32_t cItems)
1186	{
1187	uint32_t idx = RTRandAdvU32Ex(g_hRand, 0, cItems - 1);
1188	if (ASMBitTest(pbm, idx) == 1)
1189	return idx;
1190
1191	/* Scan forward as we've got code for that already: */
1192	uint32_t const idxOrg = idx;
1193	idx = ASMBitNextSet(pbm, cItems, idx);
1194	if ((int32_t)idx >= 0)
1195	return idx;
1196
1197	/* Scan backwards bit-by-bit because we don't have code for this: */
1198	for (idx = idxOrg - 1; idx < cItems; idx--)
1199	if (ASMBitTest(pbm, idx) == 1)
1200	return idx;
1201
1202	AssertFailed();
1203	RTTestIFailed("no set bit in bitmap!\n");
1204	return 0;
1205	}
1206
1207
1208	static uint32_t PickSetBitAndClearIt(uint64_t *pbm, uint32_t cItems)
1209	{
1210	uint32_t idx = PickSetBit(pbm, cItems);
1211	RTTESTI_CHECK(ASMBitTestAndClear(pbm, idx) == true);
1212	return idx;
1213	}
1214
1215
1216	/**
1217	* @return meaningless value, just for shortening 'return RTTestIFailed();'.
1218	*/
1219	static int hardAvlRangeTreeGCPhys(RTTEST hTest)
1220	{
1221	RTTestISubF("RTCHardAvlRangeTreeGCPhys");
1222
1223	/*
1224	* Tree and allocator variables.
1225	*/
1226	RTCHardAvlTreeSlabAllocator<MYTESTNODE> Allocator;
1227	RTCHardAvlRangeTree<MYTESTNODE, RTGCPHYS> Tree(&Allocator);
1228	AssertCompileSize(Tree, sizeof(uint32_t) * 2 + sizeof(uint64_t) * 3);
1229	AssertCompileSize(Allocator, sizeof(void ) 2 + sizeof(uint32_t) * 4);
1230
1231	/* Initialize the allocator with a decent slab of memory. */
1232	const uint32_t cItems = 8192;
1233	void *pvItems;
1234	RTTESTI_CHECK_RC_RET(RTTestGuardedAlloc(hTest, sizeof(MYTESTNODE) * cItems,
1235	sizeof(uint64_t), false, &pvItems), VINF_SUCCESS, 1);
1236	void *pbmBitmap;
1237	RTTESTI_CHECK_RC_RET(RTTestGuardedAlloc(hTest, RT_ALIGN_32(cItems, 64) / 64 * 8,
1238	sizeof(uint64_t), false, &pbmBitmap), VINF_SUCCESS, 1);
1239	Allocator.initSlabAllocator(cItems, (TESTNODE )pvItems, (uint64_t )pbmBitmap);
1240
1241	uint32_t cInserted = 0;
1242
1243	/*
1244	* Simple linear insert, get and remove.
1245	*/
1246	/* insert */
1247	for (unsigned i = 0; i < cItems * 4; i += 4, cInserted++)
1248	{
1249	MYTESTNODE *pNode = Allocator.allocateNode();
1250	if (!pNode)
1251	return RTTestIFailed("out of nodes: i=%#x", i);
1252	pNode->Key = i;
1253	pNode->KeyLast = i + 3;
1254	int rc = Tree.insert(&Allocator, pNode);
1255	if (rc != VINF_SUCCESS)
1256	RTTestIFailed("linear insert i=%#x failed: %Rrc", i, rc);
1257
1258	/* look it up again immediately */
1259	for (unsigned j = 0; j < 4; j++)
1260	{
1261	MYTESTNODE *pNode2;
1262	rc = Tree.lookup(&Allocator, i + j, &pNode2);
1263	if (rc != VINF_SUCCESS \|\| pNode2 != pNode)
1264	return RTTestIFailed("get after insert i=%#x j=%#x: %Rrc pNode=%p pNode2=%p", i, j, rc, pNode, pNode2);
1265	}
1266
1267	/* Do negative inserts if we've got more free nodes. */
1268	if (i / 4 + 1 < cItems)
1269	{
1270	MYTESTNODE *pNode2 = Allocator.allocateNode();
1271	if (!pNode2)
1272	return RTTestIFailed("out of nodes: i=%#x (#2)", i);
1273	RTTESTI_CHECK(pNode2 != pNode);
1274
1275	pNode2 = pNode;
1276	for (unsigned j = i >= 32 ? i - 32 : 0; j <= i + 3; j++)
1277	{
1278	for (unsigned k = i; k < i + 32; k++)
1279	{
1280	pNode2->Key = RT_MIN(j, k);
1281	pNode2->KeyLast = RT_MAX(k, j);
1282	rc = Tree.insert(&Allocator, pNode2);
1283	if (rc != VERR_ALREADY_EXISTS)
1284	return RTTestIFailed("linear negative insert: %Rrc, expected VERR_ALREADY_EXISTS; i=%#x j=%#x k=%#x; Key2=%RGp KeyLast2=%RGp vs Key=%RGp KeyLast=%RGp",
1285	rc, i, j, k, pNode2->Key, pNode2->KeyLast, pNode->Key, pNode->KeyLast);
1286	}
1287	if (j == 0)
1288	break;
1289	}
1290
1291	rc = Allocator.freeNode(pNode2);
1292	if (rc != VINF_SUCCESS)
1293	return RTTestIFailed("freeNode(pNode2=%p) failed: %Rrc (i=%#x)", pNode2, rc, i);
1294	}
1295
1296	/* check the height */
1297	uint8_t const cHeight = Tree.getHeight(&Allocator);
1298	uint32_t const cMax = RT_BIT_32(cHeight);
1299	if (cInserted > cMax \|\| cInserted < (cMax >> 4))
1300	RTTestIFailed("wrong tree height after linear insert i=%#x: cMax=%#x, cInserted=%#x, cHeight=%u\n",
1301	i, cMax, cInserted, cHeight);
1302	}
1303
1304	/* do gets. */
1305	for (unsigned i = 0; i < cItems * 4; i += 4)
1306	{
1307	MYTESTNODE *pNode;
1308	int rc = Tree.lookup(&Allocator, i, &pNode);
1309	if (rc != VINF_SUCCESS \|\| pNode == NULL)
1310	return RTTestIFailed("linear get i=%#x: %Rrc pNode=%p", i, rc, pNode);
1311	if (i < pNode->Key \|\| i > pNode->KeyLast)
1312	return RTTestIFailed("linear get i=%#x Key=%RGp KeyLast=%RGp\n", i, pNode->Key, pNode->KeyLast);
1313
1314	for (unsigned j = 1; j < 4; j++)
1315	{
1316	MYTESTNODE *pNode2;
1317	rc = Tree.lookup(&Allocator, i + j, &pNode2);
1318	if (rc != VINF_SUCCESS \|\| pNode2 != pNode)
1319	return RTTestIFailed("linear get i=%#x j=%#x: %Rrc pNode=%p pNode2=%p", i, j, rc, pNode, pNode2);
1320	}
1321	}
1322
1323	/* negative get */
1324	for (unsigned i = cItems * 4; i < cItems * 4 * 2; i += 1)
1325	{
1326	MYTESTNODE pNode = (MYTESTNODE )(uintptr_t)i;
1327	int rc = Tree.lookup(&Allocator, i, &pNode);
1328	if (rc != VERR_NOT_FOUND \|\| pNode != NULL)
1329	return RTTestIFailed("linear negative get i=%#x: %Rrc pNode=%p, expected VERR_NOT_FOUND and NULL", i, rc, pNode);
1330	}
1331
1332	/* enumerate */
1333	{
1334	RTGCPHYS Expect = 0;
1335	int rc = Tree.doWithAllFromLeft(&Allocator, hardAvlRangeTreeGCPhysEnumCallbackAscBy4, &Expect);
1336	if (rc != VINF_SUCCESS)
1337	RTTestIFailed("enumeration after linear insert failed: %Rrc", rc);
1338
1339	Expect -= 4;
1340	rc = Tree.doWithAllFromRight(&Allocator, hardAvlRangeTreeGCPhysEnumCallbackDescBy4, &Expect);
1341	if (rc != VINF_SUCCESS)
1342	RTTestIFailed("enumeration after linear insert failed: %Rrc", rc);
1343	}
1344
1345	/* remove */
1346	for (unsigned i = 0, j = 0; i < cItems * 4; i += 4, j += 3, cInserted--)
1347	{
1348	MYTESTNODE *pNode;
1349	int rc = Tree.remove(&Allocator, i + (j % 4), &pNode);
1350	if (rc != VINF_SUCCESS \|\| pNode == NULL)
1351	return RTTestIFailed("linear remove(%#x): %Rrc pNode=%p", i + (j % 4), rc, pNode);
1352	if (i < pNode->Key \|\| i > pNode->KeyLast)
1353	return RTTestIFailed("linear remove i=%#x Key=%RGp KeyLast=%RGp\n", i, pNode->Key, pNode->KeyLast);
1354
1355	memset(pNode, 0xcc, sizeof(*pNode));
1356	Allocator.freeNode(pNode);
1357
1358	/* negative */
1359	for (unsigned k = i; k < i + 4; k++)
1360	{
1361	pNode = (MYTESTNODE *)(uintptr_t)k;
1362	rc = Tree.remove(&Allocator, k, &pNode);
1363	if (rc != VERR_NOT_FOUND \|\| pNode != NULL)
1364	return RTTestIFailed("linear negative remove(%#x): %Rrc pNode=%p", k, rc, pNode);
1365	}
1366
1367	/* check the height */
1368	uint8_t const cHeight = Tree.getHeight(&Allocator);
1369	uint32_t const cMax = RT_BIT_32(cHeight);
1370	if (cInserted > cMax \|\| cInserted < (cMax >> 4))
1371	RTTestIFailed("wrong tree height after linear remove i=%#x: cMax=%#x, cInserted=%#x cHeight=%d\n",
1372	i, cMax, cInserted, cHeight);
1373	}
1374
1375	/*
1376	* Randomized stuff.
1377	*/
1378	uint64_t uSeed = RTRandU64();
1379	RTRandAdvSeed(g_hRand, uSeed);
1380	RTTestIPrintf(RTTESTLVL_ALWAYS, "Random seed #1: %#RX64\n", uSeed);
1381
1382	RTGCPHYS const cbStep = RTGCPHYS_MAX / cItems + 1;
1383	uint64_t * const pbmPresent = (uint64_t )RTMemAllocZ(RT_ALIGN_32(cItems, 64) / 64 8);
1384	RTTESTI_CHECK_RET(pbmPresent, 1);
1385
1386	/* insert all in random order */
1387	cInserted = 0;
1388	for (unsigned i = 0; i < cItems; i++)
1389	{
1390	MYTESTNODE *pNode = Allocator.allocateNode();
1391	if (!pNode)
1392	return RTTestIFailed("out of nodes: i=%#x #3", i);
1393
1394	uint32_t const idx = PickClearBitAndSetIt(pbmPresent, cItems);
1395	pNode->Key = idx * cbStep;
1396	pNode->KeyLast = pNode->Key + cbStep - 1;
1397	int rc = Tree.insert(&Allocator, pNode);
1398	if (rc == VINF_SUCCESS)
1399	cInserted++;
1400	else
1401	RTTestIFailed("random insert failed: %Rrc, i=%#x, idx=%#x (%RGp ... %RGp)", rc, i, idx, pNode->Key, pNode->KeyLast);
1402
1403	MYTESTNODE pNode2 = (MYTESTNODE )(intptr_t)i;
1404	rc = Tree.lookup(&Allocator, pNode->Key, &pNode2);
1405	if (rc != VINF_SUCCESS \|\| pNode2 != pNode)
1406	return RTTestIFailed("lookup after random insert %#x: %Rrc pNode=%p pNode2=%p idx=%#x", i, rc, pNode, pNode2, idx);
1407
1408	uint32_t cCount = 0;
1409	rc = Tree.doWithAllFromLeft(&Allocator, hardAvlRangeTreeGCPhysEnumCallbackCount, &cCount);
1410	if (rc != VINF_SUCCESS)
1411	RTTestIFailed("enum after random insert %#x: %Rrc idx=%#x", i, rc, idx);
1412	else if (cCount != cInserted)
1413	RTTestIFailed("wrong count after random removal %#x: %#x, expected %#x", i, cCount, cInserted);
1414
1415	/* check the height */
1416	uint8_t const cHeight = Tree.getHeight(&Allocator);
1417	uint32_t const cMax = RT_BIT_32(cHeight);
1418	if (cInserted > cMax \|\| cInserted < (cMax >> 4))
1419	RTTestIFailed("wrong tree height after random insert %#x: cMax=%#x, cInserted=%#x, cHeight=%u\n",
1420	i, cMax, cInserted, cHeight);
1421	}
1422
1423	/* remove all in random order, doing adjacent lookups while at it. */
1424	for (unsigned i = 0; i < cItems; i++)
1425	{
1426	uint32_t const idx = PickSetBitAndClearIt(pbmPresent, cItems);
1427	RTGCPHYS const Key = idx * cbStep;
1428
1429	/* pre-removal lookup tests */
1430	MYTESTNODE pNode = (MYTESTNODE )(intptr_t)i;
1431	int rc = Tree.lookupMatchingOrBelow(&Allocator, Key, &pNode);
1432	if (rc != VINF_SUCCESS)
1433	RTTestIFailed("pre-remove lookupMatchingOrBelow failed: %Rrc, i=%#x, idx=%#x (%RGp ... %RGp)",
1434	rc, i, idx, Key, Key + cbStep - 1);
1435	else if (pNode->Key != Key)
1436	RTTestIFailed("pre-remove lookupMatchingOrBelow returned the wrong node: Key=%RGp, expected %RGp", pNode->Key, Key);
1437
1438	pNode = (MYTESTNODE *)(intptr_t)i;
1439	rc = Tree.lookupMatchingOrAbove(&Allocator, Key, &pNode);
1440	if (rc != VINF_SUCCESS)
1441	RTTestIFailed("pre-remove lookupMatchingOrAbove failed: %Rrc, i=%#x, idx=%#x (%RGp ... %RGp)",
1442	rc, i, idx, Key, Key + cbStep - 1);
1443	else if (pNode->Key != Key)
1444	RTTestIFailed("pre-remove lookupMatchingOrAbove returned the wrong node: Key=%RGp, expected %RGp", pNode->Key, Key);
1445
1446	/* remove */
1447	pNode = (MYTESTNODE *)(intptr_t)i;
1448	rc = Tree.remove(&Allocator, Key, &pNode);
1449	if (rc != VINF_SUCCESS)
1450	RTTestIFailed("random remove failed: %Rrc, i=%#x, idx=%#x (%RGp ... %RGp)",
1451	rc, i, idx, Key, Key + cbStep - 1);
1452	else
1453	{
1454	cInserted--;
1455	if ( pNode->Key != Key
1456	\|\| pNode->KeyLast != Key + cbStep - 1)
1457	RTTestIFailed("random remove returned wrong node: %RGp ... %RGp, expected %RGp ... %RGp (i=%#x, idx=%#x)",
1458	pNode->Key, pNode->KeyLast, Key, Key + cbStep - 1, i, idx);
1459	else
1460	{
1461	MYTESTNODE pNode2 = (MYTESTNODE )(intptr_t)i;
1462	rc = Tree.lookup(&Allocator, Key, &pNode2);
1463	if (rc != VERR_NOT_FOUND)
1464	RTTestIFailed("lookup after random removal %#x: %Rrc pNode=%p pNode2=%p idx=%#x", i, rc, pNode, pNode2, idx);
1465
1466	uint32_t cCount = 0;
1467	rc = Tree.doWithAllFromLeft(&Allocator, hardAvlRangeTreeGCPhysEnumCallbackCount, &cCount);
1468	if (rc != VINF_SUCCESS)
1469	RTTestIFailed("enum after random removal %#x: %Rrc idx=%#x", i, rc, idx);
1470	else if (cCount != cInserted)
1471	RTTestIFailed("wrong count after random removal %#x: %#x, expected %#x", i, cCount, cInserted);
1472	}
1473
1474	rc = Allocator.freeNode(pNode);
1475	if (rc != VINF_SUCCESS)
1476	RTTestIFailed("free after random removal %#x failed: %Rrc pNode=%p idx=%#x", i, rc, pNode, idx);
1477
1478	/* post-removal lookup tests */
1479	pNode = (MYTESTNODE *)(intptr_t)i;
1480	rc = Tree.lookupMatchingOrBelow(&Allocator, Key, &pNode);
1481	uint32_t idxAbove;
1482	if (rc == VINF_SUCCESS)
1483	{
1484	uint32_t idxRet = pNode->Key / cbStep;
1485	RTTESTI_CHECK(ASMBitTest(pbmPresent, idxRet) == true);
1486	idxAbove = (uint32_t)ASMBitNextSet(pbmPresent, cItems, idxRet);
1487	if (idxAbove <= idx)
1488	RTTestIFailed("post-remove lookupMatchingOrBelow wrong: idxRet=%#x idx=%#x idxAbove=%#x",
1489	idxRet, idx, idxAbove);
1490	}
1491	else if (rc == VERR_NOT_FOUND)
1492	{
1493	idxAbove = (uint32_t)ASMBitFirstSet(pbmPresent, cItems);
1494	if (idxAbove <= idx)
1495	RTTestIFailed("post-remove lookupMatchingOrBelow wrong: VERR_NOT_FOUND idx=%#x idxAbove=%#x", idx, idxAbove);
1496	}
1497	else
1498	{
1499	RTTestIFailed("post-remove lookupMatchingOrBelow failed: %Rrc, i=%#x, idx=%#x (%RGp ... %RGp)",
1500	rc, i, idx, Key, Key + cbStep - 1);
1501	idxAbove = (uint32_t)ASMBitNextSet(pbmPresent, cItems, idx);
1502	}
1503
1504	pNode = (MYTESTNODE *)(intptr_t)i;
1505	rc = Tree.lookupMatchingOrAbove(&Allocator, Key, &pNode);
1506	if (rc == VINF_SUCCESS)
1507	{
1508	uint32_t idxRet = pNode->Key / cbStep;
1509	if (idxRet != idxAbove)
1510	RTTestIFailed("post-remove lookupMatchingOrAbove wrong: idxRet=%#x idxAbove=%#x idx=%#x",
1511	idxRet, idxAbove, idx);
1512	}
1513	else if (rc == VERR_NOT_FOUND)
1514	{
1515	if (idxAbove != UINT32_MAX)
1516	RTTestIFailed("post-remove lookupMatchingOrAbove wrong: VERR_NOT_FOUND idxAbove=%#x idx=%#x", idxAbove, idx);
1517	}
1518	else
1519	{
1520	RTTestIFailed("post-remove lookupMatchingOrAbove failed: %Rrc, i=%#x, idx=%#x (%RGp ... %RGp) idxAbove=%#x",
1521	rc, i, idx, Key, Key + cbStep - 1, idxAbove);
1522	}
1523	}
1524
1525	/* check the height */
1526	uint8_t const cHeight = Tree.getHeight(&Allocator);
1527	uint32_t const cMax = RT_BIT_32(cHeight);
1528	if (cInserted > cMax \|\| cInserted < (cMax >> 4))
1529	RTTestIFailed("wrong tree height after random removal %#x: cMax=%#x, cInserted=%#x, cHeight=%u\n",
1530	i, cMax, cInserted, cHeight);
1531	}
1532
1533	/*
1534	* Randomized operation.
1535	*/
1536	uSeed = RTRandU64();
1537	RTRandAdvSeed(g_hRand, uSeed);
1538	RTTestIPrintf(RTTESTLVL_ALWAYS, "Random seed #2: %#RX64\n", uSeed);
1539	uint64_t cItemsEnumed = 0;
1540	bool fAdding = true;
1541	uint64_t const nsStart = RTTimeNanoTS();
1542	unsigned i;
1543	for (i = 0, cInserted = 0; i < _64M; i++)
1544	{
1545	/* The operation. */
1546	bool fDelete;
1547	if (cInserted == cItems)
1548	{
1549	fDelete = true;
1550	fAdding = false;
1551	}
1552	else if (cInserted == 0)
1553	{
1554	fDelete = false;
1555	fAdding = true;
1556	}
1557	else
1558	fDelete = fAdding ? RTRandU32Ex(0, 3) == 1 : RTRandU32Ex(0, 3) != 0;
1559
1560	if (!fDelete)
1561	{
1562	uint32_t const idxInsert = PickClearBitAndSetIt(pbmPresent, cItems);
1563
1564	MYTESTNODE *pNode = Allocator.allocateNode();
1565	if (!pNode)
1566	return RTTestIFailed("out of nodes: cInserted=%#x cItems=%#x i=%#x", cInserted, cItems, i);
1567	pNode->Key = idxInsert * cbStep;
1568	pNode->KeyLast = pNode->Key + cbStep - 1;
1569	int rc = Tree.insert(&Allocator, pNode);
1570	if (rc == VINF_SUCCESS)
1571	cInserted += 1;
1572	else
1573	{
1574	RTTestIFailed("random insert failed: %Rrc - %RGp ... %RGp cInserted=%#x cItems=%#x i=%#x",
1575	rc, pNode->Key, pNode->KeyLast, cInserted, cItems, i);
1576	Allocator.freeNode(pNode);
1577	}
1578	}
1579	else
1580	{
1581	uint32_t const idxDelete = PickSetBitAndClearIt(pbmPresent, cItems);
1582
1583	MYTESTNODE pNode = (MYTESTNODE )(intptr_t)idxDelete;
1584	int rc = Tree.remove(&Allocator, idxDelete * cbStep, &pNode);
1585	if (rc == VINF_SUCCESS)
1586	{
1587	if ( pNode->Key != idxDelete * cbStep
1588	\|\| pNode->KeyLast != idxDelete * cbStep + cbStep - 1)
1589	RTTestIFailed("random remove returned wrong node: %RGp ... %RGp, expected %RGp ... %RGp (cInserted=%#x cItems=%#x i=%#x)",
1590	pNode->Key, pNode->KeyLast, idxDelete * cbStep, idxDelete * cbStep + cbStep - 1,
1591	cInserted, cItems, i);
1592
1593	cInserted -= 1;
1594	rc = Allocator.freeNode(pNode);
1595	if (rc != VINF_SUCCESS)
1596	RTTestIFailed("free after random removal failed: %Rrc - pNode=%p i=%#x", rc, pNode, i);
1597	}
1598	else
1599	RTTestIFailed("random remove failed: %Rrc - %RGp ... %RGp cInserted=%#x cItems=%#x i=%#x",
1600	rc, idxDelete * cbStep, idxDelete * cbStep + cbStep - 1, cInserted, cItems, i);
1601	}
1602
1603	/* Count the tree items. This will make sure the tree is balanced in strict builds. */
1604	uint32_t cCount = 0;
1605	int rc = Tree.doWithAllFromLeft(&Allocator, hardAvlRangeTreeGCPhysEnumCallbackCount, &cCount);
1606	if (rc != VINF_SUCCESS)
1607	RTTestIFailed("enum after random %s failed: %Rrc - i=%#x", fDelete ? "removal" : "insert", rc, i);
1608	else if (cCount != cInserted)
1609	RTTestIFailed("wrong count after random %s: %#x, expected %#x - i=%#x",
1610	fDelete ? "removal" : "insert", cCount, cInserted, i);
1611	cItemsEnumed += cCount;
1612
1613	/* check the height */
1614	uint8_t const cHeight = Tree.getHeight(&Allocator);
1615	uint32_t const cMax = RT_BIT_32(cHeight);
1616	if (cInserted > cMax \|\| cInserted < (cMax >> 4))
1617	RTTestIFailed("wrong tree height after random %s: cMax=%#x, cInserted=%#x, cHeight=%u - i=%#x\n",
1618	fDelete ? "removal" : "insert", cMax, cInserted, cHeight, i);
1619
1620	/* Check for timeout. */
1621	if ( (i & 0xffff) == 0
1622	&& RTTimeNanoTS() - nsStart >= RT_NS_15SEC)
1623	break;
1624	}
1625	uint64_t cNsElapsed = RTTimeNanoTS() - nsStart;
1626	RTTestIPrintf(RTTESTLVL_ALWAYS, "Performed %'u operations and enumerated %'RU64 nodes in %'RU64 ns\n",
1627	i, cItemsEnumed, cNsElapsed);
1628
1629	RTTestIValue("Operations rate", (uint64_t)i * RT_NS_1SEC / RT_MAX(cNsElapsed, 1), RTTESTUNIT_OCCURRENCES_PER_SEC);
1630	RTTestIValue("Nodes enumeration rate",
1631	(uint64_t)((double)cItemsEnumed * (double)RT_NS_1SEC / (double)RT_MAX(cNsElapsed, 1)),
1632	RTTESTUNIT_OCCURRENCES_PER_SEC);
1633
1634	return 0;
1635	}
1636
1637
1638	int main()
1639	{
1640	/*
1641	* Init.
1642	*/
1643	RTTEST hTest;
1644	int rc = RTTestInitAndCreate("tstRTAvl", &hTest);
1645	if (rc)
1646	return rc;
1647	RTTestBanner(hTest);
1648	g_hTest = hTest;
1649
1650	rc = RTRandAdvCreateParkMiller(&g_hRand);
1651	if (RT_FAILURE(rc))
1652	{
1653	RTTestIFailed("RTRandAdvCreateParkMiller -> %Rrc", rc);
1654	return RTTestSummaryAndDestroy(hTest);
1655	}
1656
1657	/*
1658	* Testing.
1659	*/
1660	unsigned i;
1661	RTTestSub(hTest, "oGCPhys(32..2048)");
1662	for (i = 32; i < 2048; i++)
1663	if (avlogcphys(i))
1664	break;
1665
1666	avlogcphys(_64K);
1667	avlogcphys(_512K);
1668	avlogcphys(_4M);
1669
1670	RTTestISubF("oGCPhys(32..2048, *1K)");
1671	for (i = 32; i < 4096; i++)
1672	if (avlogcphysRand(i, i + _1K, 0xff))
1673	break;
1674	for (; i <= _4M; i *= 2)
1675	if (avlogcphysRand(i, i * 8, i * 2 - 1))
1676	break;
1677
1678	avlrogcphys();
1679	avlul();
1680
1681	hardAvlRangeTreeGCPhys(hTest);
1682
1683	/*
1684	* Done.
1685	*/
1686	return RTTestSummaryAndDestroy(hTest);
1687	}
1688

Note: See TracBrowser for help on using the repository browser.

source: vbox/trunk/src/VBox/Runtime/testcase/tstRTAvl.cpp@ 102792

Download in other formats: