tstRTAvl.cpp@ 39419

Last change on this file since 39419 was 33540, checked in by vboxsync, 14 years ago
*: spelling fixes, thanks Timeless!
Property svn:eol-style set to `native` Property svn:keywords set to `Id`
File size: 29.3 KB

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

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

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

Download in other formats: