VirtualBox

source: vbox/trunk/src/VBox/GuestHost/OpenGL/util/sortarray.cpp@ 69989

Last change on this file since 69989 was 69500, checked in by vboxsync, 7 years ago

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

© 2023 Oracle
Contact – Privacy policy – Terms of Use