tstRTAvl.cpp@ 93694

Last change on this file since 93694 was 93694, checked in by vboxsync, 3 years ago
IPRT/tstRTAvl: report some performance values at the end of the hardAvlRangTreeGCPhys test. bugref:10093
Property svn:eol-style set to `native` Property svn:keywords set to `Id Revision`
File size: 50.2 KB

Line
1	/* $Id: tstRTAvl.cpp 93694 2022-02-11 12:06:18Z 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;
1110	RTGCPHYS KeyLast;
1111	uint32_t idxLeft;
1112	uint32_t idxRight;
1113	uint8_t cHeight;
1114	} MYTESTNODE;
1115
1116	static DECLCALLBACK(int) hardAvlRangeTreeGCPhysEnumCallbackAscBy4(TESTNODE pNode, void pvUser)
1117	{
1118	PRTGCPHYS pExpect = (PRTGCPHYS)pvUser;
1119	if (pNode->Key != *pExpect)
1120	RTTestIFailed("Key=%RGp, expected %RGp\n", pNode->Key, *pExpect);
1121	*pExpect = pNode->Key + 4;
1122	return VINF_SUCCESS;
1123	}
1124
1125
1126	static DECLCALLBACK(int) hardAvlRangeTreeGCPhysEnumCallbackCount(TESTNODE pNode, void pvUser)
1127	{
1128	(uint32_t )pvUser += 1;
1129	RT_NOREF(pNode);
1130	return VINF_SUCCESS;
1131	}
1132
1133
1134	static uint32_t PickClearBit(uint64_t *pbm, uint32_t cItems)
1135	{
1136	uint32_t idx = RTRandAdvU32Ex(g_hRand, 0, cItems - 1);
1137	if (ASMBitTest(pbm, idx) == 0)
1138	return idx;
1139
1140	/* Scan forward as we've got code for that already: */
1141	uint32_t const idxOrg = idx;
1142	idx = ASMBitNextClear(pbm, cItems, idx);
1143	if ((int32_t)idx >= 0)
1144	return idx;
1145
1146	/* Scan backwards bit-by-bit because we don't have code for this: */
1147	for (idx = idxOrg - 1; idx < cItems; idx--)
1148	if (ASMBitTest(pbm, idx) == 0)
1149	return idx;
1150
1151	AssertFailed();
1152	RTTestIFailed("no clear bit in bitmap!\n");
1153	return 0;
1154	}
1155
1156
1157	static uint32_t PickClearBitAndSetIt(uint64_t *pbm, uint32_t cItems)
1158	{
1159	uint32_t idx = PickClearBit(pbm, cItems);
1160	RTTESTI_CHECK(ASMBitTestAndSet(pbm, idx) == false);
1161	return idx;
1162	}
1163
1164
1165	static uint32_t PickSetBit(uint64_t *pbm, uint32_t cItems)
1166	{
1167	uint32_t idx = RTRandAdvU32Ex(g_hRand, 0, cItems - 1);
1168	if (ASMBitTest(pbm, idx) == 1)
1169	return idx;
1170
1171	/* Scan forward as we've got code for that already: */
1172	uint32_t const idxOrg = idx;
1173	idx = ASMBitNextSet(pbm, cItems, idx);
1174	if ((int32_t)idx >= 0)
1175	return idx;
1176
1177	/* Scan backwards bit-by-bit because we don't have code for this: */
1178	for (idx = idxOrg - 1; idx < cItems; idx--)
1179	if (ASMBitTest(pbm, idx) == 1)
1180	return idx;
1181
1182	AssertFailed();
1183	RTTestIFailed("no set bit in bitmap!\n");
1184	return 0;
1185	}
1186
1187
1188	static uint32_t PickSetBitAndClearIt(uint64_t *pbm, uint32_t cItems)
1189	{
1190	uint32_t idx = PickSetBit(pbm, cItems);
1191	RTTESTI_CHECK(ASMBitTestAndClear(pbm, idx) == true);
1192	return idx;
1193	}
1194
1195
1196	/**
1197	* @return meaningless value, just for shortening 'return RTTestIFailed();'.
1198	*/
1199	int hardAvlRangeTreeGCPhys(RTTEST hTest)
1200	{
1201	RTTestISubF("RTCHardAvlRangeTreeGCPhys");
1202
1203	/*
1204	* Tree and allocator variables.
1205	*/
1206	RTCHardAvlTreeSlabAllocator<MYTESTNODE> Allocator;
1207	RTCHardAvlRangeTree<MYTESTNODE, RTGCPHYS> Tree(&Allocator);
1208	AssertCompileSize(Tree, sizeof(uint32_t) * 2);
1209	AssertCompileSize(Allocator, sizeof(void ) 2 + sizeof(uint32_t) * 4);
1210
1211	/* Initialize the allocator with a decent slab of memory. */
1212	const uint32_t cItems = 8192;
1213	void *pvItems;
1214	RTTESTI_CHECK_RC_RET(RTTestGuardedAlloc(hTest, sizeof(MYTESTNODE) * cItems,
1215	sizeof(uint64_t), false, &pvItems), VINF_SUCCESS, 1);
1216	void *pbmBitmap;
1217	RTTESTI_CHECK_RC_RET(RTTestGuardedAlloc(hTest, RT_ALIGN_32(cItems, 64) / 64 * 8,
1218	sizeof(uint64_t), false, &pbmBitmap), VINF_SUCCESS, 1);
1219	Allocator.initSlabAllocator(cItems, (TESTNODE )pvItems, (uint64_t )pbmBitmap);
1220
1221	uint32_t cInserted = 0;
1222
1223	/*
1224	* Simple linear insert, get and remove.
1225	*/
1226	/* insert */
1227	for (unsigned i = 0; i < cItems * 4; i += 4, cInserted++)
1228	{
1229	MYTESTNODE *pNode = Allocator.allocateNode();
1230	if (!pNode)
1231	return RTTestIFailed("out of nodes: i=%#x", i);
1232	pNode->Key = i;
1233	pNode->KeyLast = i + 3;
1234	int rc = Tree.insert(&Allocator, pNode);
1235	if (rc != VINF_SUCCESS)
1236	RTTestIFailed("linear insert i=%#x failed: %Rrc", i, rc);
1237
1238	/* look it up again immediately */
1239	for (unsigned j = 0; j < 4; j++)
1240	{
1241	MYTESTNODE *pNode2;
1242	rc = Tree.lookup(&Allocator, i + j, &pNode2);
1243	if (rc != VINF_SUCCESS \|\| pNode2 != pNode)
1244	return RTTestIFailed("get after insert i=%#x j=%#x: %Rrc pNode=%p pNode2=%p", i, j, rc, pNode, pNode2);
1245	}
1246
1247	/* Do negative inserts if we've got more free nodes. */
1248	if (i / 4 + 1 < cItems)
1249	{
1250	MYTESTNODE *pNode2 = Allocator.allocateNode();
1251	if (!pNode2)
1252	return RTTestIFailed("out of nodes: i=%#x (#2)", i);
1253	RTTESTI_CHECK(pNode2 != pNode);
1254
1255	pNode2 = pNode;
1256	for (unsigned j = i >= 32 ? i - 32 : 0; j <= i + 3; j++)
1257	{
1258	for (unsigned k = i; k < i + 32; k++)
1259	{
1260	pNode2->Key = RT_MIN(j, k);
1261	pNode2->KeyLast = RT_MAX(k, j);
1262	rc = Tree.insert(&Allocator, pNode2);
1263	if (rc != VERR_ALREADY_EXISTS)
1264	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",
1265	rc, i, j, k, pNode2->Key, pNode2->KeyLast, pNode->Key, pNode->KeyLast);
1266	}
1267	if (j == 0)
1268	break;
1269	}
1270
1271	rc = Allocator.freeNode(pNode2);
1272	if (rc != VINF_SUCCESS)
1273	return RTTestIFailed("freeNode(pNode2=%p) failed: %Rrc (i=%#x)", pNode2, rc, i);
1274	}
1275
1276	/* check the height */
1277	uint8_t const cHeight = Tree.getHeight(&Allocator);
1278	uint32_t const cMax = RT_BIT_32(cHeight);
1279	if (cInserted > cMax \|\| cInserted < (cMax >> 4))
1280	RTTestIFailed("wrong tree height after linear insert i=%#x: cMax=%#x, cInserted=%#x, cHeight=%u\n",
1281	i, cMax, cInserted, cHeight);
1282	}
1283
1284	/* do gets. */
1285	for (unsigned i = 0; i < cItems * 4; i += 4)
1286	{
1287	MYTESTNODE *pNode;
1288	int rc = Tree.lookup(&Allocator, i, &pNode);
1289	if (rc != VINF_SUCCESS \|\| pNode == NULL)
1290	return RTTestIFailed("linear get i=%#x: %Rrc pNode=%p", i, rc, pNode);
1291	if (i < pNode->Key \|\| i > pNode->KeyLast)
1292	return RTTestIFailed("linear get i=%#x Key=%RGp KeyLast=%RGp\n", i, pNode->Key, pNode->KeyLast);
1293
1294	for (unsigned j = 1; j < 4; j++)
1295	{
1296	MYTESTNODE *pNode2;
1297	rc = Tree.lookup(&Allocator, i + j, &pNode2);
1298	if (rc != VINF_SUCCESS \|\| pNode2 != pNode)
1299	return RTTestIFailed("linear get i=%#x j=%#x: %Rrc pNode=%p pNode2=%p", i, j, rc, pNode, pNode2);
1300	}
1301	}
1302
1303	/* negative get */
1304	for (unsigned i = cItems * 4; i < cItems * 4 * 2; i += 1)
1305	{
1306	MYTESTNODE pNode = (MYTESTNODE )(uintptr_t)i;
1307	int rc = Tree.lookup(&Allocator, i, &pNode);
1308	if (rc != VERR_NOT_FOUND \|\| pNode != NULL)
1309	return RTTestIFailed("linear negative get i=%#x: %Rrc pNode=%p, expected VERR_NOT_FOUND and NULL", i, rc, pNode);
1310	}
1311
1312	/* enumerate */
1313	{
1314	RTGCPHYS Expect = 0;
1315	int rc = Tree.doWithAllFromLeft(&Allocator, hardAvlRangeTreeGCPhysEnumCallbackAscBy4, &Expect);
1316	if (rc != VINF_SUCCESS)
1317	RTTestIFailed("enumeration after linear insert failed: %Rrc", rc);
1318	}
1319
1320	/* remove */
1321	for (unsigned i = 0, j = 0; i < cItems * 4; i += 4, j += 3, cInserted--)
1322	{
1323	MYTESTNODE *pNode;
1324	int rc = Tree.remove(&Allocator, i + (j % 4), &pNode);
1325	if (rc != VINF_SUCCESS \|\| pNode == NULL)
1326	return RTTestIFailed("linear remove(%#x): %Rrc pNode=%p", i + (j % 4), rc, pNode);
1327	if (i < pNode->Key \|\| i > pNode->KeyLast)
1328	return RTTestIFailed("linear remove i=%#x Key=%RGp KeyLast=%RGp\n", i, pNode->Key, pNode->KeyLast);
1329
1330	memset(pNode, 0xcc, sizeof(*pNode));
1331	Allocator.freeNode(pNode);
1332
1333	/* negative */
1334	for (unsigned k = i; k < i + 4; k++)
1335	{
1336	pNode = (MYTESTNODE *)(uintptr_t)k;
1337	rc = Tree.remove(&Allocator, k, &pNode);
1338	if (rc != VERR_NOT_FOUND \|\| pNode != NULL)
1339	return RTTestIFailed("linear negative remove(%#x): %Rrc pNode=%p", k, rc, pNode);
1340	}
1341
1342	/* check the height */
1343	uint8_t const cHeight = Tree.getHeight(&Allocator);
1344	uint32_t const cMax = RT_BIT_32(cHeight);
1345	if (cInserted > cMax \|\| cInserted < (cMax >> 4))
1346	RTTestIFailed("wrong tree height after linear remove i=%#x: cMax=%#x, cInserted=%#x cHeight=%d\n",
1347	i, cMax, cInserted, cHeight);
1348	}
1349
1350	/*
1351	* Randomized stuff.
1352	*/
1353	uint64_t uSeed = RTRandU64();
1354	RTRandAdvSeed(g_hRand, uSeed);
1355	RTTestIPrintf(RTTESTLVL_ALWAYS, "Random seed #1: %#RX64\n", uSeed);
1356
1357	RTGCPHYS const cbStep = RTGCPHYS_MAX / cItems + 1;
1358	uint64_t * const pbmPresent = (uint64_t )RTMemAllocZ(RT_ALIGN_32(cItems, 64) / 64 8);
1359	RTTESTI_CHECK_RET(pbmPresent, 1);
1360
1361	/* insert all in random order */
1362	cInserted = 0;
1363	for (unsigned i = 0; i < cItems; i++)
1364	{
1365	MYTESTNODE *pNode = Allocator.allocateNode();
1366	if (!pNode)
1367	return RTTestIFailed("out of nodes: i=%#x #3", i);
1368
1369	uint32_t const idx = PickClearBitAndSetIt(pbmPresent, cItems);
1370	pNode->Key = idx * cbStep;
1371	pNode->KeyLast = pNode->Key + cbStep - 1;
1372	int rc = Tree.insert(&Allocator, pNode);
1373	if (rc == VINF_SUCCESS)
1374	cInserted++;
1375	else
1376	RTTestIFailed("random insert failed: %Rrc, i=%#x, idx=%#x (%RGp ... %RGp)", rc, i, idx, pNode->Key, pNode->KeyLast);
1377
1378	MYTESTNODE pNode2 = (MYTESTNODE )(intptr_t)i;
1379	rc = Tree.lookup(&Allocator, pNode->Key, &pNode2);
1380	if (rc != VINF_SUCCESS \|\| pNode2 != pNode)
1381	return RTTestIFailed("lookup after random insert %#x: %Rrc pNode=%p pNode2=%p idx=%#x", i, rc, pNode, pNode2, idx);
1382
1383	uint32_t cCount = 0;
1384	rc = Tree.doWithAllFromLeft(&Allocator, hardAvlRangeTreeGCPhysEnumCallbackCount, &cCount);
1385	if (rc != VINF_SUCCESS)
1386	RTTestIFailed("enum after random insert %#x: %Rrc idx=%#x", i, rc, idx);
1387	else if (cCount != cInserted)
1388	RTTestIFailed("wrong count after random removal %#x: %#x, expected %#x", i, cCount, cInserted);
1389
1390	/* check the height */
1391	uint8_t const cHeight = Tree.getHeight(&Allocator);
1392	uint32_t const cMax = RT_BIT_32(cHeight);
1393	if (cInserted > cMax \|\| cInserted < (cMax >> 4))
1394	RTTestIFailed("wrong tree height after random insert %#x: cMax=%#x, cInserted=%#x, cHeight=%u\n",
1395	i, cMax, cInserted, cHeight);
1396	}
1397
1398	/* remove all in random order. */
1399	for (unsigned i = 0; i < cItems; i++)
1400	{
1401	uint32_t const idx = PickSetBitAndClearIt(pbmPresent, cItems);
1402
1403	MYTESTNODE pNode = (MYTESTNODE )(intptr_t)i;
1404	int rc = Tree.remove(&Allocator, idx * cbStep, &pNode);
1405	if (rc != VINF_SUCCESS)
1406	RTTestIFailed("random remove failed: %Rrc, i=%#x, idx=%#x (%RGp ... %RGp)",
1407	rc, i, idx, idx * cbStep, idx * cbStep + cbStep - 1);
1408	else
1409	{
1410	cInserted--;
1411	if ( pNode->Key != idx * cbStep
1412	\|\| pNode->KeyLast != idx * cbStep + cbStep - 1)
1413	RTTestIFailed("random remove returned wrong node: %RGp ... %RGp, expected %RGp ... %RGp (i=%#x, idx=%#x)",
1414	pNode->Key, pNode->KeyLast, idx * cbStep, idx * cbStep + cbStep - 1, i, idx);
1415	else
1416	{
1417	MYTESTNODE pNode2 = (MYTESTNODE )(intptr_t)i;
1418	rc = Tree.lookup(&Allocator, idx * cbStep, &pNode2);
1419	if (rc != VERR_NOT_FOUND)
1420	RTTestIFailed("lookup after random removal %#x: %Rrc pNode=%p pNode2=%p idx=%#x", i, rc, pNode, pNode2, idx);
1421
1422	uint32_t cCount = 0;
1423	rc = Tree.doWithAllFromLeft(&Allocator, hardAvlRangeTreeGCPhysEnumCallbackCount, &cCount);
1424	if (rc != VINF_SUCCESS)
1425	RTTestIFailed("enum after random removal %#x: %Rrc idx=%#x", i, rc, idx);
1426	else if (cCount != cInserted)
1427	RTTestIFailed("wrong count after random removal %#x: %#x, expected %#x", i, cCount, cInserted);
1428	}
1429
1430	rc = Allocator.freeNode(pNode);
1431	if (rc != VINF_SUCCESS)
1432	RTTestIFailed("free after random removal %#x failed: %Rrc pNode=%p idx=%#x", i, rc, pNode, idx);
1433	}
1434
1435	/* check the height */
1436	uint8_t const cHeight = Tree.getHeight(&Allocator);
1437	uint32_t const cMax = RT_BIT_32(cHeight);
1438	if (cInserted > cMax \|\| cInserted < (cMax >> 4))
1439	RTTestIFailed("wrong tree height after random removal %#x: cMax=%#x, cInserted=%#x, cHeight=%u\n",
1440	i, cMax, cInserted, cHeight);
1441	}
1442
1443	/*
1444	* Randomized operation.
1445	*/
1446	uSeed = RTRandU64();
1447	RTRandAdvSeed(g_hRand, uSeed);
1448	RTTestIPrintf(RTTESTLVL_ALWAYS, "Random seed #2: %#RX64\n", uSeed);
1449	uint64_t cItemsEnumed = 0;
1450	bool fAdding = true;
1451	uint64_t const nsStart = RTTimeNanoTS();
1452	unsigned i;
1453	for (i = 0, cInserted = 0; i < _64M; i++)
1454	{
1455	/* The operation. */
1456	bool fDelete;
1457	if (cInserted == cItems)
1458	{
1459	fDelete = true;
1460	fAdding = false;
1461	}
1462	else if (cInserted == 0)
1463	{
1464	fDelete = false;
1465	fAdding = true;
1466	}
1467	else
1468	fDelete = fAdding ? RTRandU32Ex(0, 3) == 1 : RTRandU32Ex(0, 3) != 0;
1469
1470	if (!fDelete)
1471	{
1472	uint32_t const idxInsert = PickClearBitAndSetIt(pbmPresent, cItems);
1473
1474	MYTESTNODE *pNode = Allocator.allocateNode();
1475	if (!pNode)
1476	return RTTestIFailed("out of nodes: cInserted=%#x cItems=%#x i=%#x", cInserted, cItems, i);
1477	pNode->Key = idxInsert * cbStep;
1478	pNode->KeyLast = pNode->Key + cbStep - 1;
1479	int rc = Tree.insert(&Allocator, pNode);
1480	if (rc == VINF_SUCCESS)
1481	cInserted += 1;
1482	else
1483	{
1484	RTTestIFailed("random insert failed: %Rrc - %RGp ... %RGp cInserted=%#x cItems=%#x i=%#x",
1485	rc, pNode->Key, pNode->KeyLast, cInserted, cItems, i);
1486	Allocator.freeNode(pNode);
1487	}
1488	}
1489	else
1490	{
1491	uint32_t const idxDelete = PickSetBitAndClearIt(pbmPresent, cItems);
1492
1493	MYTESTNODE pNode = (MYTESTNODE )(intptr_t)idxDelete;
1494	int rc = Tree.remove(&Allocator, idxDelete * cbStep, &pNode);
1495	if (rc == VINF_SUCCESS)
1496	{
1497	if ( pNode->Key != idxDelete * cbStep
1498	\|\| pNode->KeyLast != idxDelete * cbStep + cbStep - 1)
1499	RTTestIFailed("random remove returned wrong node: %RGp ... %RGp, expected %RGp ... %RGp (cInserted=%#x cItems=%#x i=%#x)",
1500	pNode->Key, pNode->KeyLast, idxDelete * cbStep, idxDelete * cbStep + cbStep - 1,
1501	cInserted, cItems, i);
1502
1503	cInserted -= 1;
1504	rc = Allocator.freeNode(pNode);
1505	if (rc != VINF_SUCCESS)
1506	RTTestIFailed("free after random removal failed: %Rrc - pNode=%p i=%#x", rc, pNode, i);
1507	}
1508	else
1509	RTTestIFailed("random remove failed: %Rrc - %RGp ... %RGp cInserted=%#x cItems=%#x i=%#x",
1510	rc, idxDelete * cbStep, idxDelete * cbStep + cbStep - 1, cInserted, cItems, i);
1511	}
1512
1513	/* Count the tree items. This will make sure the tree is balanced in strict builds. */
1514	uint32_t cCount = 0;
1515	int rc = Tree.doWithAllFromLeft(&Allocator, hardAvlRangeTreeGCPhysEnumCallbackCount, &cCount);
1516	if (rc != VINF_SUCCESS)
1517	RTTestIFailed("enum after random %s failed: %Rrc - i=%#x", fDelete ? "removal" : "insert", rc, i);
1518	else if (cCount != cInserted)
1519	RTTestIFailed("wrong count after random %s: %#x, expected %#x - i=%#x",
1520	fDelete ? "removal" : "insert", cCount, cInserted, i);
1521	cItemsEnumed += cCount;
1522
1523	/* check the height */
1524	uint8_t const cHeight = Tree.getHeight(&Allocator);
1525	uint32_t const cMax = RT_BIT_32(cHeight);
1526	if (cInserted > cMax \|\| cInserted < (cMax >> 4))
1527	RTTestIFailed("wrong tree height after random %s: cMax=%#x, cInserted=%#x, cHeight=%u - i=%#x\n",
1528	fDelete ? "removal" : "insert", cMax, cInserted, cHeight, i);
1529
1530	/* Check for timeout. */
1531	if ( (i & 0xffff) == 0
1532	&& RTTimeNanoTS() - nsStart >= RT_NS_15SEC)
1533	break;
1534	}
1535	uint64_t cNsElapsed = RTTimeNanoTS() - nsStart;
1536	RTTestIPrintf(RTTESTLVL_ALWAYS, "Performed %'u operations and enumerated %'RU64 nodes in %'RU64 ns\n",
1537	i, cItemsEnumed, cNsElapsed);
1538
1539	RTTestIValue("Operations rate", (uint64_t)i * RT_NS_1SEC / RT_MAX(cNsElapsed, 1), RTTESTUNIT_OCCURRENCES_PER_SEC);
1540	RTTestIValue("Nodes enumeration rate",
1541	(uint64_t)((double)cItemsEnumed * (double)RT_NS_1SEC / (double)RT_MAX(cNsElapsed, 1)),
1542	RTTESTUNIT_OCCURRENCES_PER_SEC);
1543
1544	return 0;
1545	}
1546
1547
1548	int main()
1549	{
1550	/*
1551	* Init.
1552	*/
1553	RTTEST hTest;
1554	int rc = RTTestInitAndCreate("tstRTAvl", &hTest);
1555	if (rc)
1556	return rc;
1557	RTTestBanner(hTest);
1558	g_hTest = hTest;
1559
1560	rc = RTRandAdvCreateParkMiller(&g_hRand);
1561	if (RT_FAILURE(rc))
1562	{
1563	RTTestIFailed("RTRandAdvCreateParkMiller -> %Rrc", rc);
1564	return RTTestSummaryAndDestroy(hTest);
1565	}
1566
1567	/*
1568	* Testing.
1569	*/
1570	unsigned i;
1571	RTTestSub(hTest, "oGCPhys(32..2048)");
1572	for (i = 32; i < 2048; i++)
1573	if (avlogcphys(i))
1574	break;
1575
1576	avlogcphys(_64K);
1577	avlogcphys(_512K);
1578	avlogcphys(_4M);
1579
1580	RTTestISubF("oGCPhys(32..2048, *1K)");
1581	for (i = 32; i < 4096; i++)
1582	if (avlogcphysRand(i, i + _1K, 0xff))
1583	break;
1584	for (; i <= _4M; i *= 2)
1585	if (avlogcphysRand(i, i * 8, i * 2 - 1))
1586	break;
1587
1588	avlrogcphys();
1589	avlul();
1590
1591	hardAvlRangeTreeGCPhys(hTest);
1592
1593	/*
1594	* Done.
1595	*/
1596	return RTTestSummaryAndDestroy(hTest);
1597	}
1598

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

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

Download in other formats: