tstRTAvl.cpp@ 93693

Last change on this file since 93693 was 93693, checked in by vboxsync, 3 years ago
IPRT/hardavl: Added a getHeight() method for tstRTAvl and extended the testcase to check the tree height. bugref:10093
Property svn:eol-style set to `native` Property svn:keywords set to `Id Revision`
File size: 49.9 KB

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

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

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

Download in other formats: