VirtualBox

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

Last change on this file since 103075 was 98103, checked in by vboxsync, 2 years ago

Copyright year updates by scm.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 8.4 KB
Line 
1/* $Id: tstRTList.cpp 98103 2023-01-17 14:15:46Z vboxsync $ */
2/** @file
3 * IPRT Testcase - List interface.
4 */
5
6/*
7 * Copyright (C) 2010-2023 Oracle and/or its affiliates.
8 *
9 * This file is part of VirtualBox base platform packages, as
10 * available from https://www.virtualbox.org.
11 *
12 * This program is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU General Public License
14 * as published by the Free Software Foundation, in version 3 of the
15 * License.
16 *
17 * This program is distributed in the hope that it will be useful, but
18 * WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
20 * General Public License for more details.
21 *
22 * You should have received a copy of the GNU General Public License
23 * along with this program; if not, see <https://www.gnu.org/licenses>.
24 *
25 * The contents of this file may alternatively be used under the terms
26 * of the Common Development and Distribution License Version 1.0
27 * (CDDL), a copy of it is provided in the "COPYING.CDDL" file included
28 * in the VirtualBox distribution, in which case the provisions of the
29 * CDDL are applicable instead of those of the GPL.
30 *
31 * You may elect to license modified versions of this file under the
32 * terms and conditions of either the GPL or the CDDL or both.
33 *
34 * SPDX-License-Identifier: GPL-3.0-only OR CDDL-1.0
35 */
36
37
38/*********************************************************************************************************************************
39* Header Files *
40*********************************************************************************************************************************/
41#include <iprt/list.h>
42
43#include <iprt/errcore.h>
44#include <iprt/mem.h>
45#include <iprt/string.h>
46#include <iprt/test.h>
47
48
49/*********************************************************************************************************************************
50* Structures and Typedefs *
51*********************************************************************************************************************************/
52typedef struct LISTELEM
53{
54 /** Test data */
55 unsigned idx;
56 /** Node */
57 RTLISTNODE Node;
58} LISTELEM, *PLISTELEM;
59
60
61static void tstRTListOrder(RTTEST hTest, PRTLISTNODE pList, unsigned cElements,
62 unsigned idxFirst, unsigned idxLast, unsigned idxStep)
63{
64 RTTEST_CHECK(hTest, RTListIsEmpty(pList) == false);
65 RTTEST_CHECK(hTest, RTListGetFirst(pList, LISTELEM, Node) != NULL);
66 RTTEST_CHECK(hTest, RTListGetLast(pList, LISTELEM, Node) != NULL);
67 if (cElements > 1)
68 RTTEST_CHECK(hTest, RTListGetLast(pList, LISTELEM, Node) != RTListGetFirst(pList, LISTELEM, Node));
69 else
70 RTTEST_CHECK(hTest, RTListGetLast(pList, LISTELEM, Node) == RTListGetFirst(pList, LISTELEM, Node));
71
72 /* Check that the order is right. */
73 PLISTELEM pNode = RTListGetFirst(pList, LISTELEM, Node);
74 for (unsigned i = idxFirst; i < idxLast; i += idxStep)
75 {
76 RTTEST_CHECK(hTest, pNode->idx == i);
77 pNode = RTListNodeGetNext(&pNode->Node, LISTELEM, Node);
78 }
79
80 RTTEST_CHECK(hTest, pNode->idx == idxLast);
81 RTTEST_CHECK(hTest, RTListGetLast(pList, LISTELEM, Node) == pNode);
82 RTTEST_CHECK(hTest, RTListNodeIsLast(pList, &pNode->Node) == true);
83
84 /* Check reverse order */
85 pNode = RTListGetLast(pList, LISTELEM, Node);
86 for (unsigned i = idxLast; i > idxFirst; i -= idxStep)
87 {
88 RTTEST_CHECK(hTest, pNode->idx == i);
89 pNode = RTListNodeGetPrev(&pNode->Node, LISTELEM, Node);
90 }
91
92 RTTEST_CHECK(hTest, pNode->idx == idxFirst);
93 RTTEST_CHECK(hTest, RTListGetFirst(pList, LISTELEM, Node) == pNode);
94 RTTEST_CHECK(hTest, RTListNodeIsFirst(pList, &pNode->Node) == true);
95
96 /* The list enumeration. */
97 unsigned idx = idxFirst;
98 RTListForEach(pList, pNode, LISTELEM, Node)
99 {
100 RTTEST_CHECK_RETV(hTest, idx == pNode->idx);
101 idx += idxStep;
102 }
103 RTTEST_CHECK_MSG_RETV(hTest, idx == idxLast + idxStep || (idx == idxFirst && idxFirst == idxLast),
104 (hTest, "idx=%u idxFirst=%u idxLast=%u idxStep=%u\n", idx, idxFirst, idxLast, idxStep));
105
106 idx = idxLast;
107 RTListForEachReverse(pList, pNode, LISTELEM, Node)
108 {
109 RTTEST_CHECK_RETV(hTest, idx == pNode->idx);
110 idx -= idxStep;
111 }
112 RTTEST_CHECK_MSG_RETV(hTest, idx == idxFirst - idxStep || (idx == idxLast && idxFirst == idxLast),
113 (hTest, "idx=%u idxFirst=%u idxLast=%u idxStep=%u\n", idx, idxFirst, idxLast, idxStep));
114}
115
116static void tstRTListCreate(RTTEST hTest, unsigned cElements)
117{
118 RTTestISubF("Creating and moving - %u elements", cElements);
119 Assert(cElements > 0);
120
121 RTLISTANCHOR ListHead;
122
123 RTListInit(&ListHead);
124 RTTEST_CHECK(hTest, RTListIsEmpty(&ListHead) == true);
125 RTTEST_CHECK(hTest, RTListGetFirst(&ListHead, LISTELEM, Node) == NULL);
126 RTTEST_CHECK(hTest, RTListGetLast(&ListHead, LISTELEM, Node) == NULL);
127
128 /* Create the list */
129 for (unsigned i = 0; i< cElements; i++)
130 {
131 PLISTELEM pNode = (PLISTELEM)RTMemAlloc(sizeof(LISTELEM));
132
133 pNode->idx = i;
134 pNode->Node.pPrev = NULL;
135 pNode->Node.pNext = NULL;
136 RTListAppend(&ListHead, &pNode->Node);
137 }
138
139 tstRTListOrder(hTest, &ListHead, cElements, 0, cElements-1, 1);
140
141 /* Move the list to a new one. */
142 RTLISTANCHOR ListHeadNew;
143 RTListMove(&ListHeadNew, &ListHead);
144
145 RTTEST_CHECK(hTest, RTListIsEmpty(&ListHead) == true);
146 RTTEST_CHECK(hTest, RTListGetFirst(&ListHead, LISTELEM, Node) == NULL);
147 RTTEST_CHECK(hTest, RTListGetLast(&ListHead, LISTELEM, Node) == NULL);
148
149 tstRTListOrder(hTest, &ListHeadNew, cElements, 0, cElements-1, 1);
150
151 /*
152 * Safe iteration w/ removal.
153 */
154 RTTestISubF("Safe iteration w/ removal - %u elements", cElements);
155
156 /* Move it element by element. */
157 PLISTELEM pNode, pSafe;
158 RTListForEachSafe(&ListHeadNew, pNode, pSafe, LISTELEM, Node)
159 {
160 RTListNodeRemove(&pNode->Node);
161 RTListAppend(&ListHead, &pNode->Node);
162 }
163 RTTESTI_CHECK(RTListIsEmpty(&ListHeadNew) == true);
164 tstRTListOrder(hTest, &ListHead, cElements, 0, cElements-1, 1);
165
166 /* And the other way. */
167 RTListForEachReverseSafe(&ListHead, pNode, pSafe, LISTELEM, Node)
168 {
169 RTListNodeRemove(&pNode->Node);
170 RTListPrepend(&ListHeadNew, &pNode->Node);
171 }
172 RTTESTI_CHECK(RTListIsEmpty(&ListHead) == true);
173 tstRTListOrder(hTest, &ListHeadNew, cElements, 0, cElements-1, 1);
174
175 /*
176 * Remove elements now.
177 */
178 if (cElements > 1)
179 {
180 /* Remove every second */
181 RTTestISubF("Remove every second node - %u elements", cElements);
182
183 pNode = RTListGetFirst(&ListHeadNew, LISTELEM, Node);
184 for (unsigned i = 0; i < cElements; i++)
185 {
186 PLISTELEM pNext = RTListNodeGetNext(&pNode->Node, LISTELEM, Node);
187
188 if (!(pNode->idx % 2))
189 {
190 RTListNodeRemove(&pNode->Node);
191 RTMemFree(pNode);
192 }
193
194 pNode = pNext;
195 }
196
197 bool fElementsEven = (cElements % 2) == 0;
198 unsigned idxEnd = fElementsEven ? cElements - 1 : cElements - 2;
199
200 cElements /= 2;
201 tstRTListOrder(hTest, &ListHeadNew, cElements, 1, idxEnd, 2);
202 }
203
204 /* Remove the rest now. */
205 RTTestISubF("Remove all nodes - %u elements", cElements);
206 pNode = RTListGetFirst(&ListHeadNew, LISTELEM, Node);
207 for (unsigned i = 0; i < cElements; i++)
208 {
209 PLISTELEM pNext = RTListNodeGetNext(&pNode->Node, LISTELEM, Node);
210
211 RTListNodeRemove(&pNode->Node);
212 RTMemFree(pNode);
213 pNode = pNext;
214 }
215
216 /* List should be empty again */
217 RTTEST_CHECK(hTest, RTListIsEmpty(&ListHeadNew) == true);
218 RTTEST_CHECK(hTest, RTListGetFirst(&ListHeadNew, LISTELEM, Node) == NULL);
219 RTTEST_CHECK(hTest, RTListGetLast(&ListHeadNew, LISTELEM, Node) == NULL);
220}
221
222int main()
223{
224 RTTEST hTest;
225 int rc = RTTestInitAndCreate("tstRTList", &hTest);
226 if (rc)
227 return rc;
228 RTTestBanner(hTest);
229
230 tstRTListCreate(hTest, 1);
231 tstRTListCreate(hTest, 2);
232 tstRTListCreate(hTest, 3);
233 tstRTListCreate(hTest, 99);
234 tstRTListCreate(hTest, 100);
235 tstRTListCreate(hTest, 101);
236
237 /*
238 * Summary.
239 */
240 return RTTestSummaryAndDestroy(hTest);
241}
242
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