VirtualBox

source: vbox/trunk/src/VBox/Additions/WINNT/Graphics/Video/mp/wddm/VBoxMPSa.cpp@ 98103

Last change on this file since 98103 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: 9.9 KB
Line 
1/* $Id: VBoxMPSa.cpp 98103 2023-01-17 14:15:46Z vboxsync $ */
2
3/** @file
4 * Sorted array impl
5 */
6
7/*
8 * Copyright (C) 2014-2023 Oracle and/or its affiliates.
9 *
10 * This file is part of VirtualBox base platform packages, as
11 * available from https://www.virtualbox.org.
12 *
13 * This program is free software; you can redistribute it and/or
14 * modify it under the terms of the GNU General Public License
15 * as published by the Free Software Foundation, in version 3 of the
16 * License.
17 *
18 * This program is distributed in the hope that it will be useful, but
19 * WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
21 * General Public License for more details.
22 *
23 * You should have received a copy of the GNU General Public License
24 * along with this program; if not, see <https://www.gnu.org/licenses>.
25 *
26 * SPDX-License-Identifier: GPL-3.0-only
27 */
28
29#include "common/VBoxMPUtils.h"
30#include <iprt/err.h>
31#include <iprt/mem.h>
32
33#include <memory.h>
34
35#include "VBoxMPSa.h"
36
37VBOXSADECL(int) CrSaInit(CR_SORTARRAY *pArray, uint32_t cInitBuffer)
38{
39 pArray->cBufferSize = cInitBuffer;
40 pArray->cSize = 0;
41 if (cInitBuffer)
42 {
43 pArray->pElements = (uint64_t*)RTMemAlloc(cInitBuffer * sizeof (pArray->pElements[0]));
44 if (!pArray->pElements)
45 {
46 WARN(("no memory"));
47 /* sanity */
48 pArray->cBufferSize = 0;
49 return VERR_NO_MEMORY;
50 }
51 }
52 else
53 pArray->pElements = NULL;
54
55 return VINF_SUCCESS;
56}
57
58VBOXSADECL(void) CrSaCleanup(CR_SORTARRAY *pArray)
59{
60 if (pArray->pElements)
61 RTMemFree(pArray->pElements);
62
63 CrSaInit(pArray, 0);
64}
65
66static int crSaSearch(const CR_SORTARRAY *pArray, uint64_t element)
67{
68 int iMin = 0;
69 int iMax = pArray->cSize;
70 int i = 0;
71
72 while (iMin < iMax)
73 {
74 i = (iMax + iMin) / 2;
75
76 uint64_t el = pArray->pElements[i];
77 if (el == element)
78 return i;
79 else if (el < element)
80 iMin = i + 1;
81 else
82 iMax = i;
83 }
84
85 return -1;
86}
87
88static void crSaDbgValidate(const CR_SORTARRAY *pArray)
89{
90 Assert(pArray->cSize <= pArray->cBufferSize);
91 Assert(!pArray->pElements == !pArray->cBufferSize);
92 if (!pArray->cSize)
93 return;
94 uint64_t cur = pArray->pElements[0];
95 for (uint32_t i = 1; i < pArray->cSize; ++i)
96 {
97 Assert(pArray->pElements[i] > cur);
98 cur = pArray->pElements[i];
99 }
100}
101
102#ifdef DEBUG
103# define crSaValidate crSaDbgValidate
104#else
105# define crSaValidate(_a) do {} while (0)
106#endif
107
108static int crSaInsAt(CR_SORTARRAY *pArray, uint32_t iPos, uint64_t element)
109{
110 if (pArray->cSize == pArray->cBufferSize)
111 {
112 uint32_t cNewBufferSize = pArray->cBufferSize + 16;
113 uint64_t *pNew;
114 if (pArray->pElements)
115 pNew = (uint64_t*)RTMemRealloc(pArray->pElements, cNewBufferSize * sizeof (pArray->pElements[0]));
116 else
117 pNew = (uint64_t*)RTMemAlloc(cNewBufferSize * sizeof (pArray->pElements[0]));
118 if (!pNew)
119 {
120 WARN(("no memory"));
121 return VERR_NO_MEMORY;
122 }
123
124 pArray->pElements = pNew;
125 pArray->cBufferSize = cNewBufferSize;
126 crSaValidate(pArray);
127 }
128
129 for (int32_t i = (int32_t)pArray->cSize - 1; i >= (int32_t)iPos; --i)
130 {
131 pArray->pElements[i+1] = pArray->pElements[i];
132 }
133
134 pArray->pElements[iPos] = element;
135 ++pArray->cSize;
136
137 crSaValidate(pArray);
138
139 return VINF_SUCCESS;
140}
141
142static void crSaDelAt(CR_SORTARRAY *pArray, uint32_t iPos)
143{
144 Assert(pArray->cSize > iPos);
145
146 for (uint32_t i = iPos; i < pArray->cSize - 1; ++i)
147 {
148 pArray->pElements[i] = pArray->pElements[i+1];
149 }
150
151 --pArray->cSize;
152}
153
154static int crSaAdd(CR_SORTARRAY *pArray, uint64_t element)
155{
156 int iMin = 0;
157 int iMax = pArray->cSize;
158 int i = 0;
159 uint64_t el;
160
161 if (!iMax)
162 return crSaInsAt(pArray, 0, element);
163
164 el = element; /* Shup up MSC. */
165 while (iMin < iMax)
166 {
167 i = (iMax + iMin) / 2;
168
169 el = pArray->pElements[i];
170 if (el == element)
171 return VINF_ALREADY_INITIALIZED;
172 else if (el < element)
173 iMin = i + 1;
174 else
175 iMax = i;
176 }
177
178 if (el < element)
179 return crSaInsAt(pArray, i+1, element);
180 return crSaInsAt(pArray, i, element);
181}
182
183static int crSaRemove(CR_SORTARRAY *pArray, uint64_t element)
184{
185 int i = crSaSearch(pArray, element);
186 if (i >= 0)
187 {
188 crSaDelAt(pArray, i);
189 return VINF_SUCCESS;
190 }
191 return VINF_ALREADY_INITIALIZED;
192}
193
194/*
195 * * @return true if element is found */
196VBOXSADECL(bool) CrSaContains(const CR_SORTARRAY *pArray, uint64_t element)
197{
198 return crSaSearch(pArray, element) >= 0;
199}
200
201VBOXSADECL(int) CrSaAdd(CR_SORTARRAY *pArray, uint64_t element)
202{
203 return crSaAdd(pArray, element);
204}
205
206VBOXSADECL(int) CrSaRemove(CR_SORTARRAY *pArray, uint64_t element)
207{
208 return crSaRemove(pArray, element);
209}
210
211static int crSaIntersected(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2, CR_SORTARRAY *pResult)
212{
213 int rc = VINF_SUCCESS;
214 CrSaClear(pResult);
215
216 for (uint32_t i = 0, j = 0; i < pArray1->cSize && j < pArray2->cSize; )
217 {
218 if (pArray1->pElements[i] == pArray2->pElements[j])
219 {
220 rc = CrSaAdd(pResult, pArray1->pElements[i]);
221 if (rc < 0)
222 {
223 WARN(("CrSaAdd failed"));
224 return rc;
225 }
226
227 ++i;
228 ++j;
229 }
230 else if (pArray1->pElements[i] < pArray2->pElements[j])
231 {
232 ++i;
233 }
234 else
235 {
236 ++j;
237 }
238 }
239
240 return VINF_SUCCESS;
241}
242
243static void crSaIntersect(CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
244{
245 for (uint32_t i = 0, j = 0; i < pArray1->cSize && j < pArray2->cSize; )
246 {
247 if (pArray1->pElements[i] == pArray2->pElements[j])
248 {
249 ++i;
250 ++j;
251 }
252 else if (pArray1->pElements[i] < pArray2->pElements[j])
253 crSaDelAt(pArray1, i);
254 else
255 ++j;
256 }
257}
258
259/*
260 * @return >= 0 success
261 * < 0 - no memory
262 * */
263VBOXSADECL(void) CrSaIntersect(CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
264{
265 crSaIntersect(pArray1, pArray2);
266}
267
268VBOXSADECL(int) CrSaIntersected(CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2, CR_SORTARRAY *pResult)
269{
270 return crSaIntersected(pArray1, pArray2, pResult);
271}
272
273static int crSaUnited(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2, CR_SORTARRAY *pResult)
274{
275 int rc = VINF_SUCCESS;
276 CrSaClear(pResult);
277
278 uint32_t i = 0, j = 0;
279 uint32_t cResult = 0;
280 while (i < pArray1->cSize && j < pArray2->cSize)
281 {
282 uint64_t element;
283 if (pArray1->pElements[i] == pArray2->pElements[j])
284 {
285 element = pArray1->pElements[i];
286 ++i;
287 ++j;
288 }
289 else if (pArray1->pElements[i] < pArray2->pElements[j])
290 {
291 element = pArray1->pElements[i];
292 ++i;
293 }
294 else
295 {
296 element = pArray1->pElements[j];
297 ++j;
298 }
299
300 rc = crSaInsAt(pResult, cResult++, element);
301 if (rc < 0)
302 {
303 WARN(("crSaInsAt failed"));
304 return rc;
305 }
306 }
307
308 uint32_t iTail;
309 const CR_SORTARRAY *pTail;
310
311 if (i < pArray1->cSize)
312 {
313 iTail = i;
314 pTail = pArray1;
315 }
316 else if (j < pArray2->cSize)
317 {
318 iTail = j;
319 pTail = pArray2;
320 }
321 else
322 {
323 iTail = 0;
324 pTail = 0;
325 }
326
327 if (pTail)
328 {
329 for (;iTail < pTail->cSize; ++iTail)
330 {
331 rc = crSaInsAt(pResult, cResult++, pTail->pElements[iTail]);
332 if (rc < 0)
333 {
334 WARN(("crSaInsAt failed"));
335 return rc;
336 }
337 }
338 }
339
340 return VINF_SUCCESS;
341}
342
343VBOXSADECL(int) CrSaUnited(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2, CR_SORTARRAY *pResult)
344{
345 return crSaUnited(pArray1, pArray2, pResult);
346}
347
348static int crSaClone(const CR_SORTARRAY *pArray1, CR_SORTARRAY *pResult)
349{
350 CrSaClear(pResult);
351
352 if (pArray1->cSize > pResult->cBufferSize)
353 {
354 CrSaCleanup(pResult);
355 uint32_t cNewBufferSize = pArray1->cSize;
356 uint64_t *pNew = (uint64_t*)RTMemAlloc(cNewBufferSize * sizeof (pResult->pElements[0]));
357 if (!pNew)
358 {
359 WARN(("no memory"));
360 return VERR_NO_MEMORY;
361 }
362
363 pResult->pElements = pNew;
364 pResult->cBufferSize = cNewBufferSize;
365 crSaValidate(pResult);
366 }
367
368 pResult->cSize = pArray1->cSize;
369 memcpy(pResult->pElements, pArray1->pElements, pArray1->cSize * sizeof (pArray1->pElements[0]));
370 return VINF_SUCCESS;
371}
372
373/*
374 * @return VINF_SUCCESS on success
375 * VERR_NO_MEMORY - no memory
376 * */
377VBOXSADECL(int) CrSaClone(const CR_SORTARRAY *pArray1, CR_SORTARRAY *pResult)
378{
379 return crSaClone(pArray1, pResult);
380}
381
382static int crSaCmp(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
383{
384 int diff = CrSaGetSize(pArray1) - CrSaGetSize(pArray2);
385 if (diff)
386 return diff;
387
388 return memcmp(pArray1->pElements, pArray2->pElements, pArray1->cSize * sizeof (pArray1->pElements[0]));
389}
390
391VBOXSADECL(int) CrSaCmp(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
392{
393 return crSaCmp(pArray1, pArray2);
394}
395
396static bool crSaCovers(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
397{
398 if (CrSaGetSize(pArray1) < CrSaGetSize(pArray2))
399 return false;
400
401 uint32_t i = 0, j = 0;
402 while (j < pArray2->cSize)
403 {
404 if (i == pArray1->cSize)
405 return false;
406
407 if (pArray1->pElements[i] == pArray2->pElements[j])
408 {
409 ++i;
410 ++j;
411 }
412 else if (pArray1->pElements[i] < pArray2->pElements[j])
413 ++i;
414 else
415 return false;
416 }
417
418 return true;
419}
420
421VBOXSADECL(bool) CrSaCovers(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
422{
423 return crSaCovers(pArray1, pArray2);
424}
425
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