tstRTAvl.cpp@ 25000

Last change on this file since 25000 was 20606, checked in by vboxsync, 15 years ago
IPRT/testcase: Use RTTestInitAndCreate.
Property svn:eol-style set to `native` Property svn:keywords set to `Id`
File size: 29.4 KB

Line
1	/* $Id: tstRTAvl.cpp 20606 2009-06-15 23:49:07Z vboxsync $ */
2	/** @file
3	* IPRT Testcase - AVL trees.
4	*/
5
6	/*
7	* Copyright (C) 2006-2009 Sun Microsystems, Inc.
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	* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
27	* Clara, CA 95054 USA or visit http://www.sun.com if you need
28	* additional information or have any questions.
29	*/
30
31	/*******************************************************************************
32	* Header Files *
33	*******************************************************************************/
34	#include <iprt/avl.h>
35
36	#include <iprt/asm.h>
37	#include <iprt/initterm.h>
38	#include <iprt/mem.h>
39	#include <iprt/rand.h>
40	#include <iprt/stdarg.h>
41	#include <iprt/string.h>
42	#include <iprt/test.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 = (MaxKey + sizeof(uint32_t) * sizeof(uint8_t) - 1) / sizeof(uint8_t);
79	PTRACKER pTracker = (PTRACKER)RTMemAllocZ(RT_OFFSETOF(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	* Determin 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 pu32Start = (uint32_t )&pTracker->abBitmap[0];
258	uint32_t pu32Cur = (uint32_t )&pTracker->abBitmap[Key >> 8];
259	while (pu32Cur >= pu32Start)
260	{
261	if (*pu32Cur)
262	{
263	pKey = ASMBitLastSetU32(pu32Cur) - 1 + (uint32_t)((pu32Cur - pu32Start) * 32);
264	return true;
265	}
266	pu32Cur--;
267	}
268	Key2 = ASMBitFirstSet(pTracker->abBitmap, pTracker->MaxKey);
269	if (Key2 == -1)
270	{
271	RTTestIFailed("cSetBits=%u - but ASMBitFirstSet failed to find any", pTracker->cSetBits);
272	return false;
273	}
274	Key = Key2;
275	}
276	}
277
278	*pKey = Key;
279	return true;
280	}
281
282
283	/*
284	bool TrackerAllocSeq(PTRACKER pTracker, uint32_t pKey, uint32_t pKeyLast, uint32_t cMaxKeys)
285	{
286	return false;
287	}*/
288
289
290	/**
291	* Prints an unbuffered char.
292	* @param ch The char.
293	*/
294	static void ProgressChar(char ch)
295	{
296	//RTTestIPrintf(RTTESTLVL_INFO, "%c", ch);
297	RTTestIPrintf(RTTESTLVL_SUB_TEST, "%c", ch);
298	}
299
300	/**
301	* Prints a progress indicator label.
302	* @param cMax The max number of operations (exclusive).
303	* @param pszFormat The format string.
304	* @param ... The arguments to the format string.
305	*/
306	DECLINLINE(void) ProgressPrintf(unsigned cMax, const char *pszFormat, ...)
307	{
308	if (cMax < 10000)
309	return;
310
311	va_list va;
312	va_start(va, pszFormat);
313	//RTTestIPrintfV(RTTESTLVL_INFO, pszFormat, va);
314	RTTestIPrintfV(RTTESTLVL_SUB_TEST, pszFormat, va);
315	va_end(va);
316	}
317
318
319	/**
320	* Prints a progress indicator dot.
321	* @param iCur The current operation. (can be decending too)
322	* @param cMax The max number of operations (exclusive).
323	*/
324	DECLINLINE(void) Progress(unsigned iCur, unsigned cMax)
325	{
326	if (cMax < 10000)
327	return;
328	if (!(iCur % (cMax / 20)))
329	ProgressChar('.');
330	}
331
332
333	static int avlogcphys(unsigned cMax)
334	{
335	/*
336	* Simple linear insert and remove.
337	*/
338	if (cMax >= 10000)
339	RTTestISubF("oGCPhys(%d): linear left", cMax);
340	PAVLOGCPHYSTREE pTree = (PAVLOGCPHYSTREE)RTMemAllocZ(sizeof(*pTree));
341	unsigned i;
342	for (i = 0; i < cMax; i++)
343	{
344	Progress(i, cMax);
345	PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
346	pNode->Key = i;
347	if (!RTAvloGCPhysInsert(pTree, pNode))
348	{
349	RTTestIFailed("linear left insert i=%d\n", i);
350	return 1;
351	}
352	/* negative. */
353	AVLOGCPHYSNODECORE Node = *pNode;
354	if (RTAvloGCPhysInsert(pTree, &Node))
355	{
356	RTTestIFailed("linear left negative insert i=%d\n", i);
357	return 1;
358	}
359	}
360
361	ProgressPrintf(cMax, "~");
362	for (i = 0; i < cMax; i++)
363	{
364	Progress(i, cMax);
365	PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemove(pTree, i);
366	if (!pNode)
367	{
368	RTTestIFailed("linear left remove i=%d\n", i);
369	return 1;
370	}
371	memset(pNode, 0xcc, sizeof(*pNode));
372	RTMemFree(pNode);
373
374	/* negative */
375	pNode = RTAvloGCPhysRemove(pTree, i);
376	if (pNode)
377	{
378	RTTestIFailed("linear left negative remove i=%d\n", i);
379	return 1;
380	}
381	}
382
383	/*
384	* Simple linear insert and remove from the right.
385	*/
386	if (cMax >= 10000)
387	RTTestISubF("oGCPhys(%d): linear right", cMax);
388	for (i = 0; i < cMax; i++)
389	{
390	Progress(i, cMax);
391	PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
392	pNode->Key = i;
393	if (!RTAvloGCPhysInsert(pTree, pNode))
394	{
395	RTTestIFailed("linear right insert i=%d\n", i);
396	return 1;
397	}
398	/* negative. */
399	AVLOGCPHYSNODECORE Node = *pNode;
400	if (RTAvloGCPhysInsert(pTree, &Node))
401	{
402	RTTestIFailed("linear right negative insert i=%d\n", i);
403	return 1;
404	}
405	}
406
407	ProgressPrintf(cMax, "~");
408	while (i-- > 0)
409	{
410	Progress(i, cMax);
411	PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemove(pTree, i);
412	if (!pNode)
413	{
414	RTTestIFailed("linear right remove i=%d\n", i);
415	return 1;
416	}
417	memset(pNode, 0xcc, sizeof(*pNode));
418	RTMemFree(pNode);
419
420	/* negative */
421	pNode = RTAvloGCPhysRemove(pTree, i);
422	if (pNode)
423	{
424	RTTestIFailed("linear right negative remove i=%d\n", i);
425	return 1;
426	}
427	}
428
429	/*
430	* Linear insert but root based removal.
431	*/
432	if (cMax >= 10000)
433	RTTestISubF("oGCPhys(%d): linear root", cMax);
434	for (i = 0; i < cMax; i++)
435	{
436	Progress(i, cMax);
437	PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
438	pNode->Key = i;
439	if (!RTAvloGCPhysInsert(pTree, pNode))
440	{
441	RTTestIFailed("linear root insert i=%d\n", i);
442	return 1;
443	}
444	/* negative. */
445	AVLOGCPHYSNODECORE Node = *pNode;
446	if (RTAvloGCPhysInsert(pTree, &Node))
447	{
448	RTTestIFailed("linear root negative insert i=%d\n", i);
449	return 1;
450	}
451	}
452
453	ProgressPrintf(cMax, "~");
454	while (i-- > 0)
455	{
456	Progress(i, cMax);
457	PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)((intptr_t)pTree + *pTree);
458	RTGCPHYS Key = pNode->Key;
459	pNode = RTAvloGCPhysRemove(pTree, Key);
460	if (!pNode)
461	{
462	RTTestIFailed("linear root remove i=%d Key=%d\n", i, (unsigned)Key);
463	return 1;
464	}
465	memset(pNode, 0xcc, sizeof(*pNode));
466	RTMemFree(pNode);
467
468	/* negative */
469	pNode = RTAvloGCPhysRemove(pTree, Key);
470	if (pNode)
471	{
472	RTTestIFailed("linear root negative remove i=%d Key=%d\n", i, (unsigned)Key);
473	return 1;
474	}
475	}
476	if (*pTree)
477	{
478	RTTestIFailed("sparse remove didn't remove it all!\n");
479	return 1;
480	}
481
482	/*
483	* Make a sparsely populated tree and remove the nodes using best fit in 5 cycles.
484	*/
485	const unsigned cMaxSparse = RT_ALIGN(cMax, 32);
486	if (cMaxSparse >= 10000)
487	RTTestISubF("oGCPhys(%d): sparse", cMax);
488	for (i = 0; i < cMaxSparse; i += 8)
489	{
490	Progress(i, cMaxSparse);
491	PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
492	pNode->Key = i;
493	if (!RTAvloGCPhysInsert(pTree, pNode))
494	{
495	RTTestIFailed("sparse insert i=%d\n", i);
496	return 1;
497	}
498	/* negative. */
499	AVLOGCPHYSNODECORE Node = *pNode;
500	if (RTAvloGCPhysInsert(pTree, &Node))
501	{
502	RTTestIFailed("sparse negative insert i=%d\n", i);
503	return 1;
504	}
505	}
506
507	/* Remove using best fit in 5 cycles. */
508	ProgressPrintf(cMaxSparse, "~");
509	unsigned j;
510	for (j = 0; j < 4; j++)
511	{
512	for (i = 0; i < cMaxSparse; i += 8 * 4)
513	{
514	Progress(i, cMax); // good enough
515	PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemoveBestFit(pTree, i, true);
516	if (!pNode)
517	{
518	RTTestIFailed("sparse remove i=%d j=%d\n", i, j);
519	return 1;
520	}
521	if (pNode->Key - (unsigned long)i >= 8 * 4)
522	{
523	RTTestIFailed("sparse remove i=%d j=%d Key=%d\n", i, j, (unsigned)pNode->Key);
524	return 1;
525	}
526	memset(pNode, 0xdd, sizeof(*pNode));
527	RTMemFree(pNode);
528	}
529	}
530	if (*pTree)
531	{
532	RTTestIFailed("sparse remove didn't remove it all!\n");
533	return 1;
534	}
535	RTMemFree(pTree);
536	ProgressPrintf(cMaxSparse, "\n");
537	return 0;
538	}
539
540
541	int avlogcphysRand(unsigned cMax, unsigned cMax2)
542	{
543	PAVLOGCPHYSTREE pTree = (PAVLOGCPHYSTREE)RTMemAllocZ(sizeof(*pTree));
544	unsigned i;
545
546	/*
547	* Random tree.
548	*/
549	if (cMax >= 10000)
550	RTTestISubF("oGCPhys(%d, %d): random", cMax, cMax2);
551	PTRACKER pTracker = TrackerCreate(cMax2);
552	if (!pTracker)
553	{
554	RTTestIFailed("failed to create %d tracker!\n", cMax2);
555	return 1;
556	}
557
558	/* Insert a number of nodes in random order. */
559	for (i = 0; i < cMax; i++)
560	{
561	Progress(i, cMax);
562	uint32_t Key;
563	if (!TrackerNewRandom(pTracker, &Key))
564	{
565	RTTestIFailed("failed to allocate node no. %d\n", i);
566	TrackerDestroy(pTracker);
567	return 1;
568	}
569	PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
570	pNode->Key = Key;
571	if (!RTAvloGCPhysInsert(pTree, pNode))
572	{
573	RTTestIFailed("random insert i=%d Key=%#x\n", i, Key);
574	return 1;
575	}
576	/* negative. */
577	AVLOGCPHYSNODECORE Node = *pNode;
578	if (RTAvloGCPhysInsert(pTree, &Node))
579	{
580	RTTestIFailed("linear negative insert i=%d Key=%#x\n", i, Key);
581	return 1;
582	}
583	TrackerInsert(pTracker, Key, Key);
584	}
585
586
587	/* delete the nodes in random order. */
588	ProgressPrintf(cMax, "~");
589	while (i-- > 0)
590	{
591	Progress(i, cMax);
592	uint32_t Key;
593	if (!TrackerFindRandom(pTracker, &Key))
594	{
595	RTTestIFailed("failed to find free node no. %d\n", i);
596	TrackerDestroy(pTracker);
597	return 1;
598	}
599
600	PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemove(pTree, Key);
601	if (!pNode)
602	{
603	RTTestIFailed("random remove i=%d Key=%#x\n", i, Key);
604	return 1;
605	}
606	if (pNode->Key != Key)
607	{
608	RTTestIFailed("random remove i=%d Key=%#x pNode->Key=%#x\n", i, Key, (unsigned)pNode->Key);
609	return 1;
610	}
611	TrackerRemove(pTracker, Key, Key);
612	memset(pNode, 0xdd, sizeof(*pNode));
613	RTMemFree(pNode);
614	}
615	if (*pTree)
616	{
617	RTTestIFailed("random remove didn't remove it all!\n");
618	return 1;
619	}
620	ProgressPrintf(cMax, "\n");
621	TrackerDestroy(pTracker);
622	RTMemFree(pTree);
623	return 0;
624	}
625
626
627
628	int avlrogcphys(void)
629	{
630	unsigned i;
631	unsigned j;
632	unsigned k;
633	PAVLROGCPHYSTREE pTree = (PAVLROGCPHYSTREE)RTMemAllocZ(sizeof(*pTree));
634
635	AssertCompileSize(AVLOGCPHYSNODECORE, 24);
636	AssertCompileSize(AVLROGCPHYSNODECORE, 32);
637
638	RTTestISubF("RTAvlroGCPhys");
639
640	/*
641	* Simple linear insert, get and remove.
642	*/
643	/* insert */
644	for (i = 0; i < 65536; i += 4)
645	{
646	PAVLROGCPHYSNODECORE pNode = (PAVLROGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
647	pNode->Key = i;
648	pNode->KeyLast = i + 3;
649	if (!RTAvlroGCPhysInsert(pTree, pNode))
650	{
651	RTTestIFailed("linear insert i=%d\n", (unsigned)i);
652	return 1;
653	}
654
655	/* negative. */
656	AVLROGCPHYSNODECORE Node = *pNode;
657	for (j = i + 3; j > i - 32; j--)
658	{
659	for (k = i; k < i + 32; k++)
660	{
661	Node.Key = RT_MIN(j, k);
662	Node.KeyLast = RT_MAX(k, j);
663	if (RTAvlroGCPhysInsert(pTree, &Node))
664	{
665	RTTestIFailed("linear negative insert i=%d j=%d k=%d\n", i, j, k);
666	return 1;
667	}
668	}
669	}
670	}
671
672	/* do gets. */
673	for (i = 0; i < 65536; i += 4)
674	{
675	PAVLROGCPHYSNODECORE pNode = RTAvlroGCPhysGet(pTree, i);
676	if (!pNode)
677	{
678	RTTestIFailed("linear get i=%d\n", i);
679	return 1;
680	}
681	if (pNode->Key > i \|\| pNode->KeyLast < i)
682	{
683	RTTestIFailed("linear get i=%d Key=%d KeyLast=%d\n", i, (unsigned)pNode->Key, (unsigned)pNode->KeyLast);
684	return 1;
685	}
686
687	for (j = 0; j < 4; j++)
688	{
689	if (RTAvlroGCPhysRangeGet(pTree, i + j) != pNode)
690	{
691	RTTestIFailed("linear range get i=%d j=%d\n", i, j);
692	return 1;
693	}
694	}
695
696	/* negative. */
697	if ( RTAvlroGCPhysGet(pTree, i + 1)
698	\|\| RTAvlroGCPhysGet(pTree, i + 2)
699	\|\| RTAvlroGCPhysGet(pTree, i + 3))
700	{
701	RTTestIFailed("linear negative get i=%d + n\n", i);
702	return 1;
703	}
704
705	}
706
707	/* remove */
708	for (i = 0; i < 65536; i += 4)
709	{
710	PAVLROGCPHYSNODECORE pNode = RTAvlroGCPhysRemove(pTree, i);
711	if (!pNode)
712	{
713	RTTestIFailed("linear remove i=%d\n", i);
714	return 1;
715	}
716	memset(pNode, 0xcc, sizeof(*pNode));
717	RTMemFree(pNode);
718
719	/* negative */
720	if ( RTAvlroGCPhysRemove(pTree, i)
721	\|\| RTAvlroGCPhysRemove(pTree, i + 1)
722	\|\| RTAvlroGCPhysRemove(pTree, i + 2)
723	\|\| RTAvlroGCPhysRemove(pTree, i + 3))
724	{
725	RTTestIFailed("linear negative remove i=%d + n\n", i);
726	return 1;
727	}
728	}
729
730	/*
731	* Make a sparsely populated tree.
732	*/
733	for (i = 0; i < 65536; i += 8)
734	{
735	PAVLROGCPHYSNODECORE pNode = (PAVLROGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
736	pNode->Key = i;
737	pNode->KeyLast = i + 3;
738	if (!RTAvlroGCPhysInsert(pTree, pNode))
739	{
740	RTTestIFailed("sparse insert i=%d\n", i);
741	return 1;
742	}
743	/* negative. */
744	AVLROGCPHYSNODECORE Node = *pNode;
745	const RTGCPHYS jMin = i > 32 ? i - 32 : 1;
746	const RTGCPHYS kMax = i + 32;
747	for (j = pNode->KeyLast; j >= jMin; j--)
748	{
749	for (k = pNode->Key; k < kMax; k++)
750	{
751	Node.Key = RT_MIN(j, k);
752	Node.KeyLast = RT_MAX(k, j);
753	if (RTAvlroGCPhysInsert(pTree, &Node))
754	{
755	RTTestIFailed("sparse negative insert i=%d j=%d k=%d\n", i, j, k);
756	return 1;
757	}
758	}
759	}
760	}
761
762	/*
763	* Get and Remove using range matching in 5 cycles.
764	*/
765	for (j = 0; j < 4; j++)
766	{
767	for (i = 0; i < 65536; i += 8 * 4)
768	{
769	/* gets */
770	RTGCPHYS KeyBase = i + j * 8;
771	PAVLROGCPHYSNODECORE pNode = RTAvlroGCPhysGet(pTree, KeyBase);
772	if (!pNode)
773	{
774	RTTestIFailed("sparse get i=%d j=%d KeyBase=%d\n", i, j, (unsigned)KeyBase);
775	return 1;
776	}
777	if (pNode->Key > KeyBase \|\| pNode->KeyLast < KeyBase)
778	{
779	RTTestIFailed("sparse get i=%d j=%d KeyBase=%d pNode->Key=%d\n", i, j, (unsigned)KeyBase, (unsigned)pNode->Key);
780	return 1;
781	}
782	for (k = KeyBase; k < KeyBase + 4; k++)
783	{
784	if (RTAvlroGCPhysRangeGet(pTree, k) != pNode)
785	{
786	RTTestIFailed("sparse range get i=%d j=%d k=%d\n", i, j, k);
787	return 1;
788	}
789	}
790
791	/* negative gets */
792	for (k = i + j; k < KeyBase + 8; k++)
793	{
794	if ( k != KeyBase
795	&& RTAvlroGCPhysGet(pTree, k))
796	{
797	RTTestIFailed("sparse negative get i=%d j=%d k=%d\n", i, j, k);
798	return 1;
799	}
800	}
801	for (k = i + j; k < KeyBase; k++)
802	{
803	if (RTAvlroGCPhysRangeGet(pTree, k))
804	{
805	RTTestIFailed("sparse negative range get i=%d j=%d k=%d\n", i, j, k);
806	return 1;
807	}
808	}
809	for (k = KeyBase + 4; k < KeyBase + 8; k++)
810	{
811	if (RTAvlroGCPhysRangeGet(pTree, k))
812	{
813	RTTestIFailed("sparse negative range get i=%d j=%d k=%d\n", i, j, k);
814	return 1;
815	}
816	}
817
818	/* remove */
819	RTGCPHYS Key = KeyBase + ((i / 19) % 4);
820	if (RTAvlroGCPhysRangeRemove(pTree, Key) != pNode)
821	{
822	RTTestIFailed("sparse remove i=%d j=%d Key=%d\n", i, j, (unsigned)Key);
823	return 1;
824	}
825	memset(pNode, 0xdd, sizeof(*pNode));
826	RTMemFree(pNode);
827	}
828	}
829	if (*pTree)
830	{
831	RTTestIFailed("sparse remove didn't remove it all!\n");
832	return 1;
833	}
834
835
836	/*
837	* Realworld testcase.
838	*/
839	struct
840	{
841	AVLROGCPHYSTREE Tree;
842	AVLROGCPHYSNODECORE aNode[4];
843	} s1 = {0}, s2 = {0}, s3 = {0};
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)0xaaaaaaaa;
966	pNode->pRight = (PAVLULNODECORE)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)0xdddddddd;
1016	pNode->pRight = (PAVLULNODECORE)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@ 25000

Download in other formats: