tstRTAvl.cpp@ 93943

Last change on this file since 93943 was 93715, checked in by vboxsync, 3 years ago
IPRT/hardavl: Renamed lookupMatchingOrSmaller to lookupMatchingOrBelow and lookupMatchingOrLarger to lookupMatchingOrAbove. bugref:10093
Property svn:eol-style set to `native` Property svn:keywords set to `Id Revision`
File size: 54.0 KB

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

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

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

Download in other formats: