VirtualBox

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

Last change on this file since 73705 was 72054, checked in by vboxsync, 7 years ago

*: RTListMove no longer need the call to init the destination list to workaround buggy behavior when when the source is empty.
  • 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 72054 2018-04-27 09:18:51Z vboxsync $ */
2/** @file
3 * IPRT Testcase - List interface.
4 */
5
6/*
7 * Copyright (C) 2010-2017 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 RTListMove(&ListHeadNew, &ListHead);
134
135 RTTEST_CHECK(hTest, RTListIsEmpty(&ListHead) == true);
136 RTTEST_CHECK(hTest, RTListGetFirst(&ListHead, LISTELEM, Node) == NULL);
137 RTTEST_CHECK(hTest, RTListGetLast(&ListHead, LISTELEM, Node) == NULL);
138
139 tstRTListOrder(hTest, &ListHeadNew, cElements, 0, cElements-1, 1);
140
141 /*
142 * Safe iteration w/ removal.
143 */
144 RTTestISubF("Safe iteration w/ removal - %u elements", cElements);
145
146 /* Move it element by element. */
147 PLISTELEM pNode, pSafe;
148 RTListForEachSafe(&ListHeadNew, pNode, pSafe, LISTELEM, Node)
149 {
150 RTListNodeRemove(&pNode->Node);
151 RTListAppend(&ListHead, &pNode->Node);
152 }
153 RTTESTI_CHECK(RTListIsEmpty(&ListHeadNew) == true);
154 tstRTListOrder(hTest, &ListHead, cElements, 0, cElements-1, 1);
155
156 /* And the other way. */
157 RTListForEachReverseSafe(&ListHead, pNode, pSafe, LISTELEM, Node)
158 {
159 RTListNodeRemove(&pNode->Node);
160 RTListPrepend(&ListHeadNew, &pNode->Node);
161 }
162 RTTESTI_CHECK(RTListIsEmpty(&ListHead) == true);
163 tstRTListOrder(hTest, &ListHeadNew, cElements, 0, cElements-1, 1);
164
165 /*
166 * Remove elements now.
167 */
168 if (cElements > 1)
169 {
170 /* Remove every second */
171 RTTestISubF("Remove every second node - %u elements", cElements);
172
173 pNode = RTListGetFirst(&ListHeadNew, LISTELEM, Node);
174 for (unsigned i = 0; i < cElements; i++)
175 {
176 PLISTELEM pNext = RTListNodeGetNext(&pNode->Node, LISTELEM, Node);
177
178 if (!(pNode->idx % 2))
179 {
180 RTListNodeRemove(&pNode->Node);
181 RTMemFree(pNode);
182 }
183
184 pNode = pNext;
185 }
186
187 bool fElementsEven = (cElements % 2) == 0;
188 unsigned idxEnd = fElementsEven ? cElements - 1 : cElements - 2;
189
190 cElements /= 2;
191 tstRTListOrder(hTest, &ListHeadNew, cElements, 1, idxEnd, 2);
192 }
193
194 /* Remove the rest now. */
195 RTTestISubF("Remove all nodes - %u elements", cElements);
196 pNode = RTListGetFirst(&ListHeadNew, LISTELEM, Node);
197 for (unsigned i = 0; i < cElements; i++)
198 {
199 PLISTELEM pNext = RTListNodeGetNext(&pNode->Node, LISTELEM, Node);
200
201 RTListNodeRemove(&pNode->Node);
202 RTMemFree(pNode);
203 pNode = pNext;
204 }
205
206 /* List should be empty again */
207 RTTEST_CHECK(hTest, RTListIsEmpty(&ListHeadNew) == true);
208 RTTEST_CHECK(hTest, RTListGetFirst(&ListHeadNew, LISTELEM, Node) == NULL);
209 RTTEST_CHECK(hTest, RTListGetLast(&ListHeadNew, LISTELEM, Node) == NULL);
210}
211
212int main()
213{
214 RTTEST hTest;
215 int rc = RTTestInitAndCreate("tstRTList", &hTest);
216 if (rc)
217 return rc;
218 RTTestBanner(hTest);
219
220 tstRTListCreate(hTest, 1);
221 tstRTListCreate(hTest, 2);
222 tstRTListCreate(hTest, 3);
223 tstRTListCreate(hTest, 99);
224 tstRTListCreate(hTest, 100);
225 tstRTListCreate(hTest, 101);
226
227 /*
228 * Summary.
229 */
230 return RTTestSummaryAndDestroy(hTest);
231}
232
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