tstRTAvl.cpp@ 96407

Last change on this file since 96407 was 96407, checked in by vboxsync, 2 years ago
scm copyright and license note update
Property svn:eol-style set to `native` Property svn:keywords set to `Id Revision`
File size: 54.3 KB

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

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

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

Download in other formats: