tstRTAvl.cpp@ 105589

Last change on this file since 105589 was 103005, checked in by vboxsync, 10 months ago
iprt/asm.h,: Split out the ASMMem and related stuff into a separate header, asm-mem.h, so that we can get the RT_ASM_PAGE_SIZE stuff out of the way.
Property svn:eol-style set to `native` Property svn:keywords set to `Id Revision`
File size: 54.3 KB

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

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

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

Download in other formats: