VirtualBox

source: vbox/trunk/src/VBox/Runtime/testcase/tstRTList.cpp@ 65892

Last change on this file since 65892 was 62477, checked in by vboxsync, 8 years ago

(C) 2016
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 8.1 KB
Line 
1/* $Id: tstRTList.cpp 62477 2016-07-22 18:27:37Z vboxsync $ */
2/** @file
3 * IPRT Testcase - List interface.
4 */
5
6/*
7 * Copyright (C) 2010-2016 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/list.h>
32
33#include <iprt/err.h>
34#include <iprt/mem.h>
35#include <iprt/string.h>
36#include <iprt/test.h>
37
38
39/*********************************************************************************************************************************
40* Structures and Typedefs *
41*********************************************************************************************************************************/
42typedef struct LISTELEM
43{
44 /** Test data */
45 unsigned idx;
46 /** Node */
47 RTLISTNODE Node;
48} LISTELEM, *PLISTELEM;
49
50
51static void tstRTListOrder(RTTEST hTest, PRTLISTNODE pList, unsigned cElements,
52 unsigned idxFirst, unsigned idxLast, unsigned idxStep)
53{
54 RTTEST_CHECK(hTest, RTListIsEmpty(pList) == false);
55 RTTEST_CHECK(hTest, RTListGetFirst(pList, LISTELEM, Node) != NULL);
56 RTTEST_CHECK(hTest, RTListGetLast(pList, LISTELEM, Node) != NULL);
57 if (cElements > 1)
58 RTTEST_CHECK(hTest, RTListGetLast(pList, LISTELEM, Node) != RTListGetFirst(pList, LISTELEM, Node));
59 else
60 RTTEST_CHECK(hTest, RTListGetLast(pList, LISTELEM, Node) == RTListGetFirst(pList, LISTELEM, Node));
61
62 /* Check that the order is right. */
63 PLISTELEM pNode = RTListGetFirst(pList, LISTELEM, Node);
64 for (unsigned i = idxFirst; i < idxLast; i += idxStep)
65 {
66 RTTEST_CHECK(hTest, pNode->idx == i);
67 pNode = RTListNodeGetNext(&pNode->Node, LISTELEM, Node);
68 }
69
70 RTTEST_CHECK(hTest, pNode->idx == idxLast);
71 RTTEST_CHECK(hTest, RTListGetLast(pList, LISTELEM, Node) == pNode);
72 RTTEST_CHECK(hTest, RTListNodeIsLast(pList, &pNode->Node) == true);
73
74 /* Check reverse order */
75 pNode = RTListGetLast(pList, LISTELEM, Node);
76 for (unsigned i = idxLast; i > idxFirst; i -= idxStep)
77 {
78 RTTEST_CHECK(hTest, pNode->idx == i);
79 pNode = RTListNodeGetPrev(&pNode->Node, LISTELEM, Node);
80 }
81
82 RTTEST_CHECK(hTest, pNode->idx == idxFirst);
83 RTTEST_CHECK(hTest, RTListGetFirst(pList, LISTELEM, Node) == pNode);
84 RTTEST_CHECK(hTest, RTListNodeIsFirst(pList, &pNode->Node) == true);
85
86 /* The list enumeration. */
87 unsigned idx = idxFirst;
88 RTListForEach(pList, pNode, LISTELEM, Node)
89 {
90 RTTEST_CHECK_RETV(hTest, idx == pNode->idx);
91 idx += idxStep;
92 }
93 RTTEST_CHECK_MSG_RETV(hTest, idx == idxLast + idxStep || (idx == idxFirst && idxFirst == idxLast),
94 (hTest, "idx=%u idxFirst=%u idxLast=%u idxStep=%u\n", idx, idxFirst, idxLast, idxStep));
95
96 idx = idxLast;
97 RTListForEachReverse(pList, pNode, LISTELEM, Node)
98 {
99 RTTEST_CHECK_RETV(hTest, idx == pNode->idx);
100 idx -= idxStep;
101 }
102 RTTEST_CHECK_MSG_RETV(hTest, idx == idxFirst - idxStep || (idx == idxLast && idxFirst == idxLast),
103 (hTest, "idx=%u idxFirst=%u idxLast=%u idxStep=%u\n", idx, idxFirst, idxLast, idxStep));
104}
105
106static void tstRTListCreate(RTTEST hTest, unsigned cElements)
107{
108 RTTestISubF("Creating and moving - %u elements", cElements);
109 Assert(cElements > 0);
110
111 RTLISTANCHOR ListHead;
112
113 RTListInit(&ListHead);
114 RTTEST_CHECK(hTest, RTListIsEmpty(&ListHead) == true);
115 RTTEST_CHECK(hTest, RTListGetFirst(&ListHead, LISTELEM, Node) == NULL);
116 RTTEST_CHECK(hTest, RTListGetLast(&ListHead, LISTELEM, Node) == NULL);
117
118 /* Create the list */
119 for (unsigned i = 0; i< cElements; i++)
120 {
121 PLISTELEM pNode = (PLISTELEM)RTMemAlloc(sizeof(LISTELEM));
122
123 pNode->idx = i;
124 pNode->Node.pPrev = NULL;
125 pNode->Node.pNext = NULL;
126 RTListAppend(&ListHead, &pNode->Node);
127 }
128
129 tstRTListOrder(hTest, &ListHead, cElements, 0, cElements-1, 1);
130
131 /* Move the list to a new one. */
132 RTLISTANCHOR ListHeadNew;
133
134 RTListInit(&ListHeadNew);
135 RTListMove(&ListHeadNew, &ListHead);
136
137 RTTEST_CHECK(hTest, RTListIsEmpty(&ListHead) == true);
138 RTTEST_CHECK(hTest, RTListGetFirst(&ListHead, LISTELEM, Node) == NULL);
139 RTTEST_CHECK(hTest, RTListGetLast(&ListHead, LISTELEM, Node) == NULL);
140
141 tstRTListOrder(hTest, &ListHeadNew, cElements, 0, cElements-1, 1);
142
143 /*
144 * Safe iteration w/ removal.
145 */
146 RTTestISubF("Safe iteration w/ removal - %u elements", cElements);
147
148 /* Move it element by element. */
149 PLISTELEM pNode, pSafe;
150 RTListForEachSafe(&ListHeadNew, pNode, pSafe, LISTELEM, Node)
151 {
152 RTListNodeRemove(&pNode->Node);
153 RTListAppend(&ListHead, &pNode->Node);
154 }
155 RTTESTI_CHECK(RTListIsEmpty(&ListHeadNew) == true);
156 tstRTListOrder(hTest, &ListHead, cElements, 0, cElements-1, 1);
157
158 /* And the other way. */
159 RTListForEachReverseSafe(&ListHead, pNode, pSafe, LISTELEM, Node)
160 {
161 RTListNodeRemove(&pNode->Node);
162 RTListPrepend(&ListHeadNew, &pNode->Node);
163 }
164 RTTESTI_CHECK(RTListIsEmpty(&ListHead) == true);
165 tstRTListOrder(hTest, &ListHeadNew, cElements, 0, cElements-1, 1);
166
167 /*
168 * Remove elements now.
169 */
170 if (cElements > 1)
171 {
172 /* Remove every second */
173 RTTestISubF("Remove every second node - %u elements", cElements);
174
175 pNode = RTListGetFirst(&ListHeadNew, LISTELEM, Node);
176 for (unsigned i = 0; i < cElements; i++)
177 {
178 PLISTELEM pNext = RTListNodeGetNext(&pNode->Node, LISTELEM, Node);
179
180 if (!(pNode->idx % 2))
181 {
182 RTListNodeRemove(&pNode->Node);
183 RTMemFree(pNode);
184 }
185
186 pNode = pNext;
187 }
188
189 bool fElementsEven = (cElements % 2) == 0;
190 unsigned idxEnd = fElementsEven ? cElements - 1 : cElements - 2;
191
192 cElements /= 2;
193 tstRTListOrder(hTest, &ListHeadNew, cElements, 1, idxEnd, 2);
194 }
195
196 /* Remove the rest now. */
197 RTTestISubF("Remove all nodes - %u elements", cElements);
198 pNode = RTListGetFirst(&ListHeadNew, LISTELEM, Node);
199 for (unsigned i = 0; i < cElements; i++)
200 {
201 PLISTELEM pNext = RTListNodeGetNext(&pNode->Node, LISTELEM, Node);
202
203 RTListNodeRemove(&pNode->Node);
204 RTMemFree(pNode);
205 pNode = pNext;
206 }
207
208 /* List should be empty again */
209 RTTEST_CHECK(hTest, RTListIsEmpty(&ListHeadNew) == true);
210 RTTEST_CHECK(hTest, RTListGetFirst(&ListHeadNew, LISTELEM, Node) == NULL);
211 RTTEST_CHECK(hTest, RTListGetLast(&ListHeadNew, LISTELEM, Node) == NULL);
212}
213
214int main()
215{
216 RTTEST hTest;
217 int rc = RTTestInitAndCreate("tstRTList", &hTest);
218 if (rc)
219 return rc;
220 RTTestBanner(hTest);
221
222 tstRTListCreate(hTest, 1);
223 tstRTListCreate(hTest, 2);
224 tstRTListCreate(hTest, 3);
225 tstRTListCreate(hTest, 99);
226 tstRTListCreate(hTest, 100);
227 tstRTListCreate(hTest, 101);
228
229 /*
230 * Summary.
231 */
232 return RTTestSummaryAndDestroy(hTest);
233}
234
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette