tstRTAvl.cpp@ 79325

Last change on this file since 79325 was 76553, checked in by vboxsync, 6 years ago
scm --update-copyright-year
Property svn:eol-style set to `native` Property svn:keywords set to `Id Revision`
File size: 29.8 KB

Line
1	/* $Id: tstRTAvl.cpp 76553 2019-01-01 01:45:53Z vboxsync $ */
2	/** @file
3	* IPRT Testcase - AVL trees.
4	*/
5
6	/*
7	* Copyright (C) 2006-2019 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
33	#include <iprt/asm.h>
34	#include <iprt/initterm.h>
35	#include <iprt/mem.h>
36	#include <iprt/rand.h>
37	#include <iprt/stdarg.h>
38	#include <iprt/string.h>
39	#include <iprt/test.h>
40
41
42	/*********************************************************************************************************************************
43	* Structures and Typedefs *
44	*********************************************************************************************************************************/
45	typedef struct TRACKER
46	{
47	/** The max key value (exclusive). */
48	uint32_t MaxKey;
49	/** The last allocated key. */
50	uint32_t LastAllocatedKey;
51	/** The number of set bits in the bitmap. */
52	uint32_t cSetBits;
53	/** The bitmap size. */
54	uint32_t cbBitmap;
55	/** Bitmap containing the allocated nodes. */
56	uint8_t abBitmap[1];
57	} TRACKER, *PTRACKER;
58
59
60	/*********************************************************************************************************************************
61	* Global Variables *
62	*********************************************************************************************************************************/
63	static RTTEST g_hTest;
64	static RTRAND g_hRand;
65
66
67	/**
68	* Creates a new tracker.
69	*
70	* @returns Pointer to the new tracker.
71	* @param MaxKey The max key value for the tracker. (exclusive)
72	*/
73	static PTRACKER TrackerCreate(uint32_t MaxKey)
74	{
75	uint32_t cbBitmap = (MaxKey + sizeof(uint32_t) * sizeof(uint8_t) - 1) / sizeof(uint8_t);
76	PTRACKER pTracker = (PTRACKER)RTMemAllocZ(RT_UOFFSETOF_DYN(TRACKER, abBitmap[cbBitmap]));
77	if (pTracker)
78	{
79	pTracker->MaxKey = MaxKey;
80	pTracker->LastAllocatedKey = MaxKey;
81	pTracker->cbBitmap = cbBitmap;
82	Assert(pTracker->cSetBits == 0);
83	}
84	return pTracker;
85	}
86
87
88	/**
89	* Destroys a tracker.
90	*
91	* @param pTracker The tracker.
92	*/
93	static void TrackerDestroy(PTRACKER pTracker)
94	{
95	RTMemFree(pTracker);
96	}
97
98
99	/**
100	* Inserts a key range into the tracker.
101	*
102	* @returns success indicator.
103	* @param pTracker The tracker.
104	* @param Key The first key in the range.
105	* @param KeyLast The last key in the range. (inclusive)
106	*/
107	static bool TrackerInsert(PTRACKER pTracker, uint32_t Key, uint32_t KeyLast)
108	{
109	bool fRc = !ASMBitTestAndSet(pTracker->abBitmap, Key);
110	if (fRc)
111	pTracker->cSetBits++;
112	while (KeyLast != Key)
113	{
114	if (!ASMBitTestAndSet(pTracker->abBitmap, KeyLast))
115	pTracker->cSetBits++;
116	else
117	fRc = false;
118	KeyLast--;
119	}
120	return fRc;
121	}
122
123
124	/**
125	* Removes a key range from the tracker.
126	*
127	* @returns success indicator.
128	* @param pTracker The tracker.
129	* @param Key The first key in the range.
130	* @param KeyLast The last key in the range. (inclusive)
131	*/
132	static bool TrackerRemove(PTRACKER pTracker, uint32_t Key, uint32_t KeyLast)
133	{
134	bool fRc = ASMBitTestAndClear(pTracker->abBitmap, Key);
135	if (fRc)
136	pTracker->cSetBits--;
137	while (KeyLast != Key)
138	{
139	if (ASMBitTestAndClear(pTracker->abBitmap, KeyLast))
140	pTracker->cSetBits--;
141	else
142	fRc = false;
143	KeyLast--;
144	}
145	return fRc;
146	}
147
148
149	/**
150	* Random key range allocation.
151	*
152	* @returns success indicator.
153	* @param pTracker The tracker.
154	* @param pKey Where to store the first key in the allocated range.
155	* @param pKeyLast Where to store the first key in the allocated range.
156	* @param cMaxKey The max range length.
157	* @remark The caller has to call TrackerInsert.
158	*/
159	static bool TrackerNewRandomEx(PTRACKER pTracker, uint32_t pKey, uint32_t pKeyLast, uint32_t cMaxKeys)
160	{
161	/*
162	* Find a key.
163	*/
164	uint32_t Key = RTRandAdvU32Ex(g_hRand, 0, pTracker->MaxKey - 1);
165	if (ASMBitTest(pTracker->abBitmap, Key))
166	{
167	if (pTracker->cSetBits >= pTracker->MaxKey)
168	return false;
169
170	int Key2 = ASMBitNextClear(pTracker->abBitmap, pTracker->MaxKey, Key);
171	if (Key2 > 0)
172	Key = Key2;
173	else
174	{
175	/* we're missing a ASMBitPrevClear function, so just try another, lower, value.*/
176	for (;;)
177	{
178	const uint32_t KeyPrev = Key;
179	Key = RTRandAdvU32Ex(g_hRand, 0, KeyPrev - 1);
180	if (!ASMBitTest(pTracker->abBitmap, Key))
181	break;
182	Key2 = ASMBitNextClear(pTracker->abBitmap, RT_ALIGN_32(KeyPrev, 32), Key);
183	if (Key2 > 0)
184	{
185	Key = Key2;
186	break;
187	}
188	}
189	}
190	}
191
192	/*
193	* Determine the range.
194	*/
195	uint32_t KeyLast;
196	if (cMaxKeys == 1 \|\| !pKeyLast)
197	KeyLast = Key;
198	else
199	{
200	uint32_t cKeys = RTRandAdvU32Ex(g_hRand, 0, RT_MIN(pTracker->MaxKey - Key, cMaxKeys - 1));
201	KeyLast = Key + cKeys;
202	int Key2 = ASMBitNextSet(pTracker->abBitmap, RT_ALIGN_32(KeyLast, 32), Key);
203	if ( Key2 > 0
204	&& (unsigned)Key2 <= KeyLast)
205	KeyLast = Key2 - 1;
206	}
207
208	/*
209	* Return.
210	*/
211	*pKey = Key;
212	if (pKeyLast)
213	*pKeyLast = KeyLast;
214	return true;
215	}
216
217
218	/**
219	* Random single key allocation.
220	*
221	* @returns success indicator.
222	* @param pTracker The tracker.
223	* @param pKey Where to store the allocated key.
224	* @remark The caller has to call TrackerInsert.
225	*/
226	static bool TrackerNewRandom(PTRACKER pTracker, uint32_t *pKey)
227	{
228	return TrackerNewRandomEx(pTracker, pKey, NULL, 1);
229	}
230
231
232	/**
233	* Random single key 'lookup'.
234	*
235	* @returns success indicator.
236	* @param pTracker The tracker.
237	* @param pKey Where to store the allocated key.
238	* @remark The caller has to call TrackerRemove.
239	*/
240	static bool TrackerFindRandom(PTRACKER pTracker, uint32_t *pKey)
241	{
242	uint32_t Key = RTRandAdvU32Ex(g_hRand, 0, pTracker->MaxKey - 1);
243	if (!ASMBitTest(pTracker->abBitmap, Key))
244	{
245	if (!pTracker->cSetBits)
246	return false;
247
248	int Key2 = ASMBitNextSet(pTracker->abBitmap, pTracker->MaxKey, Key);
249	if (Key2 > 0)
250	Key = Key2;
251	else
252	{
253	/* we're missing a ASMBitPrevSet function, so here's a quick replacement hack. */
254	uint32_t pu32Start = (uint32_t )&pTracker->abBitmap[0];
255	uint32_t pu32Cur = (uint32_t )&pTracker->abBitmap[Key >> 8];
256	while (pu32Cur >= pu32Start)
257	{
258	if (*pu32Cur)
259	{
260	pKey = ASMBitLastSetU32(pu32Cur) - 1 + (uint32_t)((pu32Cur - pu32Start) * 32);
261	return true;
262	}
263	pu32Cur--;
264	}
265	Key2 = ASMBitFirstSet(pTracker->abBitmap, pTracker->MaxKey);
266	if (Key2 == -1)
267	{
268	RTTestIFailed("cSetBits=%u - but ASMBitFirstSet failed to find any", pTracker->cSetBits);
269	return false;
270	}
271	Key = Key2;
272	}
273	}
274
275	*pKey = Key;
276	return true;
277	}
278
279
280	/*
281	bool TrackerAllocSeq(PTRACKER pTracker, uint32_t pKey, uint32_t pKeyLast, uint32_t cMaxKeys)
282	{
283	return false;
284	}*/
285
286
287	/**
288	* Prints an unbuffered char.
289	* @param ch The char.
290	*/
291	static void ProgressChar(char ch)
292	{
293	//RTTestIPrintf(RTTESTLVL_INFO, "%c", ch);
294	RTTestIPrintf(RTTESTLVL_SUB_TEST, "%c", ch);
295	}
296
297	/**
298	* Prints a progress indicator label.
299	* @param cMax The max number of operations (exclusive).
300	* @param pszFormat The format string.
301	* @param ... The arguments to the format string.
302	*/
303	DECLINLINE(void) ProgressPrintf(unsigned cMax, const char *pszFormat, ...)
304	{
305	if (cMax < 10000)
306	return;
307
308	va_list va;
309	va_start(va, pszFormat);
310	//RTTestIPrintfV(RTTESTLVL_INFO, pszFormat, va);
311	RTTestIPrintfV(RTTESTLVL_SUB_TEST, pszFormat, va);
312	va_end(va);
313	}
314
315
316	/**
317	* Prints a progress indicator dot.
318	* @param iCur The current operation. (can be descending too)
319	* @param cMax The max number of operations (exclusive).
320	*/
321	DECLINLINE(void) Progress(unsigned iCur, unsigned cMax)
322	{
323	if (cMax < 10000)
324	return;
325	if (!(iCur % (cMax / 20)))
326	ProgressChar('.');
327	}
328
329
330	static int avlogcphys(unsigned cMax)
331	{
332	/*
333	* Simple linear insert and remove.
334	*/
335	if (cMax >= 10000)
336	RTTestISubF("oGCPhys(%d): linear left", cMax);
337	PAVLOGCPHYSTREE pTree = (PAVLOGCPHYSTREE)RTMemAllocZ(sizeof(*pTree));
338	unsigned i;
339	for (i = 0; i < cMax; i++)
340	{
341	Progress(i, cMax);
342	PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
343	pNode->Key = i;
344	if (!RTAvloGCPhysInsert(pTree, pNode))
345	{
346	RTTestIFailed("linear left insert i=%d\n", i);
347	return 1;
348	}
349	/* negative. */
350	AVLOGCPHYSNODECORE Node = *pNode;
351	if (RTAvloGCPhysInsert(pTree, &Node))
352	{
353	RTTestIFailed("linear left negative insert i=%d\n", i);
354	return 1;
355	}
356	}
357
358	ProgressPrintf(cMax, "~");
359	for (i = 0; i < cMax; i++)
360	{
361	Progress(i, cMax);
362	PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemove(pTree, i);
363	if (!pNode)
364	{
365	RTTestIFailed("linear left remove i=%d\n", i);
366	return 1;
367	}
368	memset(pNode, 0xcc, sizeof(*pNode));
369	RTMemFree(pNode);
370
371	/* negative */
372	pNode = RTAvloGCPhysRemove(pTree, i);
373	if (pNode)
374	{
375	RTTestIFailed("linear left negative remove i=%d\n", i);
376	return 1;
377	}
378	}
379
380	/*
381	* Simple linear insert and remove from the right.
382	*/
383	if (cMax >= 10000)
384	RTTestISubF("oGCPhys(%d): linear right", cMax);
385	for (i = 0; i < cMax; i++)
386	{
387	Progress(i, cMax);
388	PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
389	pNode->Key = i;
390	if (!RTAvloGCPhysInsert(pTree, pNode))
391	{
392	RTTestIFailed("linear right insert i=%d\n", i);
393	return 1;
394	}
395	/* negative. */
396	AVLOGCPHYSNODECORE Node = *pNode;
397	if (RTAvloGCPhysInsert(pTree, &Node))
398	{
399	RTTestIFailed("linear right negative insert i=%d\n", i);
400	return 1;
401	}
402	}
403
404	ProgressPrintf(cMax, "~");
405	while (i-- > 0)
406	{
407	Progress(i, cMax);
408	PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemove(pTree, i);
409	if (!pNode)
410	{
411	RTTestIFailed("linear right remove i=%d\n", i);
412	return 1;
413	}
414	memset(pNode, 0xcc, sizeof(*pNode));
415	RTMemFree(pNode);
416
417	/* negative */
418	pNode = RTAvloGCPhysRemove(pTree, i);
419	if (pNode)
420	{
421	RTTestIFailed("linear right negative remove i=%d\n", i);
422	return 1;
423	}
424	}
425
426	/*
427	* Linear insert but root based removal.
428	*/
429	if (cMax >= 10000)
430	RTTestISubF("oGCPhys(%d): linear root", cMax);
431	for (i = 0; i < cMax; i++)
432	{
433	Progress(i, cMax);
434	PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
435	pNode->Key = i;
436	if (!RTAvloGCPhysInsert(pTree, pNode))
437	{
438	RTTestIFailed("linear root insert i=%d\n", i);
439	return 1;
440	}
441	/* negative. */
442	AVLOGCPHYSNODECORE Node = *pNode;
443	if (RTAvloGCPhysInsert(pTree, &Node))
444	{
445	RTTestIFailed("linear root negative insert i=%d\n", i);
446	return 1;
447	}
448	}
449
450	ProgressPrintf(cMax, "~");
451	while (i-- > 0)
452	{
453	Progress(i, cMax);
454	PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)((intptr_t)pTree + *pTree);
455	RTGCPHYS Key = pNode->Key;
456	pNode = RTAvloGCPhysRemove(pTree, Key);
457	if (!pNode)
458	{
459	RTTestIFailed("linear root remove i=%d Key=%d\n", i, (unsigned)Key);
460	return 1;
461	}
462	memset(pNode, 0xcc, sizeof(*pNode));
463	RTMemFree(pNode);
464
465	/* negative */
466	pNode = RTAvloGCPhysRemove(pTree, Key);
467	if (pNode)
468	{
469	RTTestIFailed("linear root negative remove i=%d Key=%d\n", i, (unsigned)Key);
470	return 1;
471	}
472	}
473	if (*pTree)
474	{
475	RTTestIFailed("sparse remove didn't remove it all!\n");
476	return 1;
477	}
478
479	/*
480	* Make a sparsely populated tree and remove the nodes using best fit in 5 cycles.
481	*/
482	const unsigned cMaxSparse = RT_ALIGN(cMax, 32);
483	if (cMaxSparse >= 10000)
484	RTTestISubF("oGCPhys(%d): sparse", cMax);
485	for (i = 0; i < cMaxSparse; i += 8)
486	{
487	Progress(i, cMaxSparse);
488	PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
489	pNode->Key = i;
490	if (!RTAvloGCPhysInsert(pTree, pNode))
491	{
492	RTTestIFailed("sparse insert i=%d\n", i);
493	return 1;
494	}
495	/* negative. */
496	AVLOGCPHYSNODECORE Node = *pNode;
497	if (RTAvloGCPhysInsert(pTree, &Node))
498	{
499	RTTestIFailed("sparse negative insert i=%d\n", i);
500	return 1;
501	}
502	}
503
504	/* Remove using best fit in 5 cycles. */
505	ProgressPrintf(cMaxSparse, "~");
506	unsigned j;
507	for (j = 0; j < 4; j++)
508	{
509	for (i = 0; i < cMaxSparse; i += 8 * 4)
510	{
511	Progress(i, cMax); // good enough
512	PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemoveBestFit(pTree, i, true);
513	if (!pNode)
514	{
515	RTTestIFailed("sparse remove i=%d j=%d\n", i, j);
516	return 1;
517	}
518	if (pNode->Key - (unsigned long)i >= 8 * 4)
519	{
520	RTTestIFailed("sparse remove i=%d j=%d Key=%d\n", i, j, (unsigned)pNode->Key);
521	return 1;
522	}
523	memset(pNode, 0xdd, sizeof(*pNode));
524	RTMemFree(pNode);
525	}
526	}
527	if (*pTree)
528	{
529	RTTestIFailed("sparse remove didn't remove it all!\n");
530	return 1;
531	}
532	RTMemFree(pTree);
533	ProgressPrintf(cMaxSparse, "\n");
534	return 0;
535	}
536
537
538	int avlogcphysRand(unsigned cMax, unsigned cMax2)
539	{
540	PAVLOGCPHYSTREE pTree = (PAVLOGCPHYSTREE)RTMemAllocZ(sizeof(*pTree));
541	unsigned i;
542
543	/*
544	* Random tree.
545	*/
546	if (cMax >= 10000)
547	RTTestISubF("oGCPhys(%d, %d): random", cMax, cMax2);
548	PTRACKER pTracker = TrackerCreate(cMax2);
549	if (!pTracker)
550	{
551	RTTestIFailed("failed to create %d tracker!\n", cMax2);
552	return 1;
553	}
554
555	/* Insert a number of nodes in random order. */
556	for (i = 0; i < cMax; i++)
557	{
558	Progress(i, cMax);
559	uint32_t Key;
560	if (!TrackerNewRandom(pTracker, &Key))
561	{
562	RTTestIFailed("failed to allocate node no. %d\n", i);
563	TrackerDestroy(pTracker);
564	return 1;
565	}
566	PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
567	pNode->Key = Key;
568	if (!RTAvloGCPhysInsert(pTree, pNode))
569	{
570	RTTestIFailed("random insert i=%d Key=%#x\n", i, Key);
571	return 1;
572	}
573	/* negative. */
574	AVLOGCPHYSNODECORE Node = *pNode;
575	if (RTAvloGCPhysInsert(pTree, &Node))
576	{
577	RTTestIFailed("linear negative insert i=%d Key=%#x\n", i, Key);
578	return 1;
579	}
580	TrackerInsert(pTracker, Key, Key);
581	}
582
583
584	/* delete the nodes in random order. */
585	ProgressPrintf(cMax, "~");
586	while (i-- > 0)
587	{
588	Progress(i, cMax);
589	uint32_t Key;
590	if (!TrackerFindRandom(pTracker, &Key))
591	{
592	RTTestIFailed("failed to find free node no. %d\n", i);
593	TrackerDestroy(pTracker);
594	return 1;
595	}
596
597	PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemove(pTree, Key);
598	if (!pNode)
599	{
600	RTTestIFailed("random remove i=%d Key=%#x\n", i, Key);
601	return 1;
602	}
603	if (pNode->Key != Key)
604	{
605	RTTestIFailed("random remove i=%d Key=%#x pNode->Key=%#x\n", i, Key, (unsigned)pNode->Key);
606	return 1;
607	}
608	TrackerRemove(pTracker, Key, Key);
609	memset(pNode, 0xdd, sizeof(*pNode));
610	RTMemFree(pNode);
611	}
612	if (*pTree)
613	{
614	RTTestIFailed("random remove didn't remove it all!\n");
615	return 1;
616	}
617	ProgressPrintf(cMax, "\n");
618	TrackerDestroy(pTracker);
619	RTMemFree(pTree);
620	return 0;
621	}
622
623
624
625	int avlrogcphys(void)
626	{
627	unsigned i;
628	unsigned j;
629	unsigned k;
630	PAVLROGCPHYSTREE pTree = (PAVLROGCPHYSTREE)RTMemAllocZ(sizeof(*pTree));
631
632	AssertCompileSize(AVLOGCPHYSNODECORE, 24);
633	AssertCompileSize(AVLROGCPHYSNODECORE, 32);
634
635	RTTestISubF("RTAvlroGCPhys");
636
637	/*
638	* Simple linear insert, get and remove.
639	*/
640	/* insert */
641	for (i = 0; i < 65536; i += 4)
642	{
643	PAVLROGCPHYSNODECORE pNode = (PAVLROGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
644	pNode->Key = i;
645	pNode->KeyLast = i + 3;
646	if (!RTAvlroGCPhysInsert(pTree, pNode))
647	{
648	RTTestIFailed("linear insert i=%d\n", (unsigned)i);
649	return 1;
650	}
651
652	/* negative. */
653	AVLROGCPHYSNODECORE Node = *pNode;
654	for (j = i + 3; j > i - 32; j--)
655	{
656	for (k = i; k < i + 32; k++)
657	{
658	Node.Key = RT_MIN(j, k);
659	Node.KeyLast = RT_MAX(k, j);
660	if (RTAvlroGCPhysInsert(pTree, &Node))
661	{
662	RTTestIFailed("linear negative insert i=%d j=%d k=%d\n", i, j, k);
663	return 1;
664	}
665	}
666	}
667	}
668
669	/* do gets. */
670	for (i = 0; i < 65536; i += 4)
671	{
672	PAVLROGCPHYSNODECORE pNode = RTAvlroGCPhysGet(pTree, i);
673	if (!pNode)
674	{
675	RTTestIFailed("linear get i=%d\n", i);
676	return 1;
677	}
678	if (pNode->Key > i \|\| pNode->KeyLast < i)
679	{
680	RTTestIFailed("linear get i=%d Key=%d KeyLast=%d\n", i, (unsigned)pNode->Key, (unsigned)pNode->KeyLast);
681	return 1;
682	}
683
684	for (j = 0; j < 4; j++)
685	{
686	if (RTAvlroGCPhysRangeGet(pTree, i + j) != pNode)
687	{
688	RTTestIFailed("linear range get i=%d j=%d\n", i, j);
689	return 1;
690	}
691	}
692
693	/* negative. */
694	if ( RTAvlroGCPhysGet(pTree, i + 1)
695	\|\| RTAvlroGCPhysGet(pTree, i + 2)
696	\|\| RTAvlroGCPhysGet(pTree, i + 3))
697	{
698	RTTestIFailed("linear negative get i=%d + n\n", i);
699	return 1;
700	}
701
702	}
703
704	/* remove */
705	for (i = 0; i < 65536; i += 4)
706	{
707	PAVLROGCPHYSNODECORE pNode = RTAvlroGCPhysRemove(pTree, i);
708	if (!pNode)
709	{
710	RTTestIFailed("linear remove i=%d\n", i);
711	return 1;
712	}
713	memset(pNode, 0xcc, sizeof(*pNode));
714	RTMemFree(pNode);
715
716	/* negative */
717	if ( RTAvlroGCPhysRemove(pTree, i)
718	\|\| RTAvlroGCPhysRemove(pTree, i + 1)
719	\|\| RTAvlroGCPhysRemove(pTree, i + 2)
720	\|\| RTAvlroGCPhysRemove(pTree, i + 3))
721	{
722	RTTestIFailed("linear negative remove i=%d + n\n", i);
723	return 1;
724	}
725	}
726
727	/*
728	* Make a sparsely populated tree.
729	*/
730	for (i = 0; i < 65536; i += 8)
731	{
732	PAVLROGCPHYSNODECORE pNode = (PAVLROGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
733	pNode->Key = i;
734	pNode->KeyLast = i + 3;
735	if (!RTAvlroGCPhysInsert(pTree, pNode))
736	{
737	RTTestIFailed("sparse insert i=%d\n", i);
738	return 1;
739	}
740	/* negative. */
741	AVLROGCPHYSNODECORE Node = *pNode;
742	const RTGCPHYS jMin = i > 32 ? i - 32 : 1;
743	const RTGCPHYS kMax = i + 32;
744	for (j = pNode->KeyLast; j >= jMin; j--)
745	{
746	for (k = pNode->Key; k < kMax; k++)
747	{
748	Node.Key = RT_MIN(j, k);
749	Node.KeyLast = RT_MAX(k, j);
750	if (RTAvlroGCPhysInsert(pTree, &Node))
751	{
752	RTTestIFailed("sparse negative insert i=%d j=%d k=%d\n", i, j, k);
753	return 1;
754	}
755	}
756	}
757	}
758
759	/*
760	* Get and Remove using range matching in 5 cycles.
761	*/
762	for (j = 0; j < 4; j++)
763	{
764	for (i = 0; i < 65536; i += 8 * 4)
765	{
766	/* gets */
767	RTGCPHYS KeyBase = i + j * 8;
768	PAVLROGCPHYSNODECORE pNode = RTAvlroGCPhysGet(pTree, KeyBase);
769	if (!pNode)
770	{
771	RTTestIFailed("sparse get i=%d j=%d KeyBase=%d\n", i, j, (unsigned)KeyBase);
772	return 1;
773	}
774	if (pNode->Key > KeyBase \|\| pNode->KeyLast < KeyBase)
775	{
776	RTTestIFailed("sparse get i=%d j=%d KeyBase=%d pNode->Key=%d\n", i, j, (unsigned)KeyBase, (unsigned)pNode->Key);
777	return 1;
778	}
779	for (k = KeyBase; k < KeyBase + 4; k++)
780	{
781	if (RTAvlroGCPhysRangeGet(pTree, k) != pNode)
782	{
783	RTTestIFailed("sparse range get i=%d j=%d k=%d\n", i, j, k);
784	return 1;
785	}
786	}
787
788	/* negative gets */
789	for (k = i + j; k < KeyBase + 8; k++)
790	{
791	if ( k != KeyBase
792	&& RTAvlroGCPhysGet(pTree, k))
793	{
794	RTTestIFailed("sparse negative get i=%d j=%d k=%d\n", i, j, k);
795	return 1;
796	}
797	}
798	for (k = i + j; k < KeyBase; k++)
799	{
800	if (RTAvlroGCPhysRangeGet(pTree, k))
801	{
802	RTTestIFailed("sparse negative range get i=%d j=%d k=%d\n", i, j, k);
803	return 1;
804	}
805	}
806	for (k = KeyBase + 4; k < KeyBase + 8; k++)
807	{
808	if (RTAvlroGCPhysRangeGet(pTree, k))
809	{
810	RTTestIFailed("sparse negative range get i=%d j=%d k=%d\n", i, j, k);
811	return 1;
812	}
813	}
814
815	/* remove */
816	RTGCPHYS Key = KeyBase + ((i / 19) % 4);
817	if (RTAvlroGCPhysRangeRemove(pTree, Key) != pNode)
818	{
819	RTTestIFailed("sparse remove i=%d j=%d Key=%d\n", i, j, (unsigned)Key);
820	return 1;
821	}
822	memset(pNode, 0xdd, sizeof(*pNode));
823	RTMemFree(pNode);
824	}
825	}
826	if (*pTree)
827	{
828	RTTestIFailed("sparse remove didn't remove it all!\n");
829	return 1;
830	}
831
832
833	/*
834	* Realworld testcase.
835	*/
836	struct
837	{
838	AVLROGCPHYSTREE Tree;
839	AVLROGCPHYSNODECORE aNode[4];
840	} s1, s2, s3;
841	RT_ZERO(s1);
842	RT_ZERO(s2);
843	RT_ZERO(s3);
844
845	s1.aNode[0].Key = 0x00030000;
846	s1.aNode[0].KeyLast = 0x00030fff;
847	s1.aNode[1].Key = 0x000a0000;
848	s1.aNode[1].KeyLast = 0x000bffff;
849	s1.aNode[2].Key = 0xe0000000;
850	s1.aNode[2].KeyLast = 0xe03fffff;
851	s1.aNode[3].Key = 0xfffe0000;
852	s1.aNode[3].KeyLast = 0xfffe0ffe;
853	for (i = 0; i < RT_ELEMENTS(s1.aNode); i++)
854	{
855	PAVLROGCPHYSNODECORE pNode = &s1.aNode[i];
856	if (!RTAvlroGCPhysInsert(&s1.Tree, pNode))
857	{
858	RTTestIFailed("real insert i=%d\n", i);
859	return 1;
860	}
861	if (RTAvlroGCPhysInsert(&s1.Tree, pNode))
862	{
863	RTTestIFailed("real negative insert i=%d\n", i);
864	return 1;
865	}
866	if (RTAvlroGCPhysGet(&s1.Tree, pNode->Key) != pNode)
867	{
868	RTTestIFailed("real get (1) i=%d\n", i);
869	return 1;
870	}
871	if (RTAvlroGCPhysGet(&s1.Tree, pNode->KeyLast) != NULL)
872	{
873	RTTestIFailed("real negative get (2) i=%d\n", i);
874	return 1;
875	}
876	if (RTAvlroGCPhysRangeGet(&s1.Tree, pNode->Key) != pNode)
877	{
878	RTTestIFailed("real range get (1) i=%d\n", i);
879	return 1;
880	}
881	if (RTAvlroGCPhysRangeGet(&s1.Tree, pNode->Key + 1) != pNode)
882	{
883	RTTestIFailed("real range get (2) i=%d\n", i);
884	return 1;
885	}
886	if (RTAvlroGCPhysRangeGet(&s1.Tree, pNode->KeyLast) != pNode)
887	{
888	RTTestIFailed("real range get (3) i=%d\n", i);
889	return 1;
890	}
891	}
892
893	s3 = s1;
894	s1 = s2;
895	for (i = 0; i < RT_ELEMENTS(s3.aNode); i++)
896	{
897	PAVLROGCPHYSNODECORE pNode = &s3.aNode[i];
898	if (RTAvlroGCPhysGet(&s3.Tree, pNode->Key) != pNode)
899	{
900	RTTestIFailed("real get (10) i=%d\n", i);
901	return 1;
902	}
903	if (RTAvlroGCPhysRangeGet(&s3.Tree, pNode->Key) != pNode)
904	{
905	RTTestIFailed("real range get (10) i=%d\n", i);
906	return 1;
907	}
908
909	j = pNode->Key + 1;
910	do
911	{
912	if (RTAvlroGCPhysGet(&s3.Tree, j) != NULL)
913	{
914	RTTestIFailed("real negative get (11) i=%d j=%#x\n", i, j);
915	return 1;
916	}
917	if (RTAvlroGCPhysRangeGet(&s3.Tree, j) != pNode)
918	{
919	RTTestIFailed("real range get (11) i=%d j=%#x\n", i, j);
920	return 1;
921	}
922	} while (j++ < pNode->KeyLast);
923	}
924
925	return 0;
926	}
927
928
929	int avlul(void)
930	{
931	RTTestISubF("RTAvlUL");
932
933	/*
934	* Simple linear insert and remove.
935	*/
936	PAVLULNODECORE pTree = 0;
937	unsigned i;
938	/* insert */
939	for (i = 0; i < 65536; i++)
940	{
941	PAVLULNODECORE pNode = (PAVLULNODECORE)RTMemAlloc(sizeof(*pNode));
942	pNode->Key = i;
943	if (!RTAvlULInsert(&pTree, pNode))
944	{
945	RTTestIFailed("linear insert i=%d\n", i);
946	return 1;
947	}
948	/* negative. */
949	AVLULNODECORE Node = *pNode;
950	if (RTAvlULInsert(&pTree, &Node))
951	{
952	RTTestIFailed("linear negative insert i=%d\n", i);
953	return 1;
954	}
955	}
956
957	for (i = 0; i < 65536; i++)
958	{
959	PAVLULNODECORE pNode = RTAvlULRemove(&pTree, i);
960	if (!pNode)
961	{
962	RTTestIFailed("linear remove i=%d\n", i);
963	return 1;
964	}
965	pNode->pLeft = (PAVLULNODECORE)(uintptr_t)0xaaaaaaaa;
966	pNode->pRight = (PAVLULNODECORE)(uintptr_t)0xbbbbbbbb;
967	pNode->uchHeight = 'e';
968	RTMemFree(pNode);
969
970	/* negative */
971	pNode = RTAvlULRemove(&pTree, i);
972	if (pNode)
973	{
974	RTTestIFailed("linear negative remove i=%d\n", i);
975	return 1;
976	}
977	}
978
979	/*
980	* Make a sparsely populated tree.
981	*/
982	for (i = 0; i < 65536; i += 8)
983	{
984	PAVLULNODECORE pNode = (PAVLULNODECORE)RTMemAlloc(sizeof(*pNode));
985	pNode->Key = i;
986	if (!RTAvlULInsert(&pTree, pNode))
987	{
988	RTTestIFailed("linear insert i=%d\n", i);
989	return 1;
990	}
991	/* negative. */
992	AVLULNODECORE Node = *pNode;
993	if (RTAvlULInsert(&pTree, &Node))
994	{
995	RTTestIFailed("linear negative insert i=%d\n", i);
996	return 1;
997	}
998	}
999
1000	/*
1001	* Remove using best fit in 5 cycles.
1002	*/
1003	unsigned j;
1004	for (j = 0; j < 4; j++)
1005	{
1006	for (i = 0; i < 65536; i += 8 * 4)
1007	{
1008	PAVLULNODECORE pNode = RTAvlULRemoveBestFit(&pTree, i, true);
1009	//PAVLULNODECORE pNode = RTAvlULRemove(&pTree, i + j * 8);
1010	if (!pNode)
1011	{
1012	RTTestIFailed("sparse remove i=%d j=%d\n", i, j);
1013	return 1;
1014	}
1015	pNode->pLeft = (PAVLULNODECORE)(uintptr_t)0xdddddddd;
1016	pNode->pRight = (PAVLULNODECORE)(uintptr_t)0xcccccccc;
1017	pNode->uchHeight = 'E';
1018	RTMemFree(pNode);
1019	}
1020	}
1021
1022	return 0;
1023	}
1024
1025
1026	int main()
1027	{
1028	/*
1029	* Init.
1030	*/
1031	RTTEST hTest;
1032	int rc = RTTestInitAndCreate("tstRTAvl", &hTest);
1033	if (rc)
1034	return rc;
1035	RTTestBanner(hTest);
1036	g_hTest = hTest;
1037
1038	rc = RTRandAdvCreateParkMiller(&g_hRand);
1039	if (RT_FAILURE(rc))
1040	{
1041	RTTestIFailed("RTRandAdvCreateParkMiller -> %Rrc", rc);
1042	return RTTestSummaryAndDestroy(hTest);
1043	}
1044
1045	/*
1046	* Testing.
1047	*/
1048	unsigned i;
1049	RTTestSub(hTest, "oGCPhys(32..2048)");
1050	for (i = 32; i < 2048; i++)
1051	if (avlogcphys(i))
1052	break;
1053
1054	avlogcphys(_64K);
1055	avlogcphys(_512K);
1056	avlogcphys(_4M);
1057
1058	RTTestISubF("oGCPhys(32..2048, *1K)");
1059	for (i = 32; i < 4096; i++)
1060	if (avlogcphysRand(i, i + _1K))
1061	break;
1062	for (; i <= _4M; i *= 2)
1063	if (avlogcphysRand(i, i * 8))
1064	break;
1065
1066	avlrogcphys();
1067	avlul();
1068
1069	/*
1070	* Done.
1071	*/
1072	return RTTestSummaryAndDestroy(hTest);
1073	}
1074

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

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

Download in other formats: