a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync/* $Id$ */
96ceb3a26c92d45834d00c86eca5c2e7adbde009vboxsync
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync/** @file
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync * Sorted array impl
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync */
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync/*
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync * Copyright (C) 2014 Oracle Corporation
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync *
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync * This file is part of VirtualBox Open Source Edition (OSE), as
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync * available from http://www.virtualbox.org. This file is free software;
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync * you can redistribute it and/or modify it under the terms of the GNU
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync * General Public License (GPL) as published by the Free Software
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync * Foundation, in version 2 as it comes in the "COPYING" file of the
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync */
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync#include <cr_sortarray.h>
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync#include <cr_error.h>
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync#include <iprt/err.h>
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync#include <iprt/mem.h>
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync#include <memory.h>
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsyncVBOXSADECL(int) CrSaInit(CR_SORTARRAY *pArray, uint32_t cInitBuffer)
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync{
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync pArray->cBufferSize = cInitBuffer;
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync pArray->cSize = 0;
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync if (cInitBuffer)
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync {
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync pArray->pElements = (uint64_t*)RTMemAlloc(cInitBuffer * sizeof (pArray->pElements[0]));
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync if (!pArray->pElements)
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync {
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync WARN(("no memory"));
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync /* sanity */
96ceb3a26c92d45834d00c86eca5c2e7adbde009vboxsync pArray->cBufferSize = 0;
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync return VERR_NO_MEMORY;
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync }
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync }
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync else
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync pArray->pElements = NULL;
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync return VINF_SUCCESS;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync}
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsyncVBOXSADECL(void) CrSaCleanup(CR_SORTARRAY *pArray)
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync{
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync if (pArray->pElements)
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync RTMemFree(pArray->pElements);
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync CrSaInit(pArray, 0);
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync}
137af3daace06f18fa5d5c74f281d90f3884b277vboxsync
137af3daace06f18fa5d5c74f281d90f3884b277vboxsyncstatic int crSaSearch(const CR_SORTARRAY *pArray, uint64_t element)
137af3daace06f18fa5d5c74f281d90f3884b277vboxsync{
137af3daace06f18fa5d5c74f281d90f3884b277vboxsync int iMin = 0;
137af3daace06f18fa5d5c74f281d90f3884b277vboxsync int iMax = pArray->cSize;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync int i = 0;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync while (iMin < iMax)
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync {
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync i = (iMax + iMin) / 2;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync uint64_t el = pArray->pElements[i];
137af3daace06f18fa5d5c74f281d90f3884b277vboxsync if (el == element)
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync return i;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync else if (el < element)
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync iMin = i + 1;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync else
c55bf74b54ecdfb5ebc4e5d90b620d0fee31737evboxsync iMax = i;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync }
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync return -1;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync}
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsyncstatic void crSaDbgValidate(const CR_SORTARRAY *pArray)
137af3daace06f18fa5d5c74f281d90f3884b277vboxsync{
137af3daace06f18fa5d5c74f281d90f3884b277vboxsync Assert(pArray->cSize <= pArray->cBufferSize);
137af3daace06f18fa5d5c74f281d90f3884b277vboxsync Assert(!pArray->pElements == !pArray->cBufferSize);
137af3daace06f18fa5d5c74f281d90f3884b277vboxsync if (!pArray->cSize)
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync return;
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsync uint64_t cur = pArray->pElements[0];
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsync for (uint32_t i = 1; i < pArray->cSize; ++i)
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsync {
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsync Assert(pArray->pElements[i] > cur);
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsync cur = pArray->pElements[i];
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsync }
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsync}
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsync
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsync#ifdef DEBUG
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsync# define crSaValidate crSaDbgValidate
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsync#else
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsync# define crSaValidate(_a) do {} while (0)
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsync#endif
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsync
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsyncstatic int crSaInsAt(CR_SORTARRAY *pArray, uint32_t iPos, uint64_t element)
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsync{
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsync if (pArray->cSize == pArray->cBufferSize)
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsync {
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsync uint32_t cNewBufferSize = pArray->cBufferSize + 16;
fbea89d3b3ffed0adfb4c2c031bbd631baf783ccvboxsync uint64_t *pNew;
859d0408dbaebc06a6a82b0eeeb81e84f9af7c44vboxsync if (pArray->pElements)
859d0408dbaebc06a6a82b0eeeb81e84f9af7c44vboxsync pNew = (uint64_t*)RTMemRealloc(pArray->pElements, cNewBufferSize * sizeof (pArray->pElements[0]));
859d0408dbaebc06a6a82b0eeeb81e84f9af7c44vboxsync else
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsync pNew = (uint64_t*)RTMemAlloc(cNewBufferSize * sizeof (pArray->pElements[0]));
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsync if (!pNew)
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsync {
c31578d36637d7ab03bf8d8e9db2ab056ca7e692vboxsync WARN(("no memory"));
c31578d36637d7ab03bf8d8e9db2ab056ca7e692vboxsync return VERR_NO_MEMORY;
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsync }
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsync
5f2b03bf7695dabd71222dba123532a3f76828c1vboxsync pArray->pElements = pNew;
5f2b03bf7695dabd71222dba123532a3f76828c1vboxsync pArray->cBufferSize = cNewBufferSize;
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsync crSaValidate(pArray);
22866e6b8e8304e8604724f7509c33253e7eedcfvboxsync }
3fb3de312d1ff675e0f7cc62a7d46cbb1d5d9353vboxsync
3fb3de312d1ff675e0f7cc62a7d46cbb1d5d9353vboxsync for (int32_t i = (int32_t)pArray->cSize - 1; i >= (int32_t)iPos; --i)
3fb3de312d1ff675e0f7cc62a7d46cbb1d5d9353vboxsync {
3fb3de312d1ff675e0f7cc62a7d46cbb1d5d9353vboxsync pArray->pElements[i+1] = pArray->pElements[i];
3fb3de312d1ff675e0f7cc62a7d46cbb1d5d9353vboxsync }
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync pArray->pElements[iPos] = element;
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync ++pArray->cSize;
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync crSaValidate(pArray);
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync return VINF_SUCCESS;
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync}
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsyncstatic void crSaDelAt(CR_SORTARRAY *pArray, uint32_t iPos)
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync{
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync Assert(pArray->cSize > iPos);
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync
3fb3de312d1ff675e0f7cc62a7d46cbb1d5d9353vboxsync for (uint32_t i = iPos; i < pArray->cSize - 1; ++i)
3fb3de312d1ff675e0f7cc62a7d46cbb1d5d9353vboxsync {
89b03b736ab7dd4eac1d820aad87826e2d527253vboxsync pArray->pElements[i] = pArray->pElements[i+1];
22866e6b8e8304e8604724f7509c33253e7eedcfvboxsync }
22866e6b8e8304e8604724f7509c33253e7eedcfvboxsync
db4f765965f7fdbb7411d7589ba3b5b1d6f62136vboxsync --pArray->cSize;
db4f765965f7fdbb7411d7589ba3b5b1d6f62136vboxsync}
22866e6b8e8304e8604724f7509c33253e7eedcfvboxsync
22866e6b8e8304e8604724f7509c33253e7eedcfvboxsyncstatic int crSaAdd(CR_SORTARRAY *pArray, uint64_t element)
22866e6b8e8304e8604724f7509c33253e7eedcfvboxsync{
22866e6b8e8304e8604724f7509c33253e7eedcfvboxsync int iMin = 0;
89b03b736ab7dd4eac1d820aad87826e2d527253vboxsync int iMax = pArray->cSize;
22866e6b8e8304e8604724f7509c33253e7eedcfvboxsync int i = 0;
599104d38a98f53d08be0aa687444c6099983c38vboxsync uint64_t el;
599104d38a98f53d08be0aa687444c6099983c38vboxsync
599104d38a98f53d08be0aa687444c6099983c38vboxsync if (!iMax)
599104d38a98f53d08be0aa687444c6099983c38vboxsync return crSaInsAt(pArray, 0, element);
c48ee3740edf0a5855aa9bfdb4cb9bf2a4921c2avboxsync
c48ee3740edf0a5855aa9bfdb4cb9bf2a4921c2avboxsync while (iMin < iMax)
c48ee3740edf0a5855aa9bfdb4cb9bf2a4921c2avboxsync {
599104d38a98f53d08be0aa687444c6099983c38vboxsync i = (iMax + iMin) / 2;
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync el = pArray->pElements[i];
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync if (el == element)
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync return VINF_ALREADY_INITIALIZED;
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync else if (el < element)
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync iMin = i + 1;
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync else
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync iMax = i;
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync }
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync if (el < element)
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync return crSaInsAt(pArray, i+1, element);
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync return crSaInsAt(pArray, i, element);
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync}
862ba4401c9fa66fbb0264053634d47d0718ed74vboxsync
862ba4401c9fa66fbb0264053634d47d0718ed74vboxsyncstatic int crSaRemove(CR_SORTARRAY *pArray, uint64_t element)
862ba4401c9fa66fbb0264053634d47d0718ed74vboxsync{
862ba4401c9fa66fbb0264053634d47d0718ed74vboxsync int i = crSaSearch(pArray, element);
862ba4401c9fa66fbb0264053634d47d0718ed74vboxsync if (i >= 0)
862ba4401c9fa66fbb0264053634d47d0718ed74vboxsync {
862ba4401c9fa66fbb0264053634d47d0718ed74vboxsync crSaDelAt(pArray, i);
862ba4401c9fa66fbb0264053634d47d0718ed74vboxsync return VINF_SUCCESS;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync }
862ba4401c9fa66fbb0264053634d47d0718ed74vboxsync return VINF_ALREADY_INITIALIZED;
96ceb3a26c92d45834d00c86eca5c2e7adbde009vboxsync}
96ceb3a26c92d45834d00c86eca5c2e7adbde009vboxsync
96ceb3a26c92d45834d00c86eca5c2e7adbde009vboxsync/*
2beb20cf9bf27df36f1704b083f93dff72af736evboxsync * * @return true if element is found */
2beb20cf9bf27df36f1704b083f93dff72af736evboxsyncVBOXSADECL(bool) CrSaContains(const CR_SORTARRAY *pArray, uint64_t element)
8782e654b5a355600d165b6e0bb761b8f4e769fdvboxsync{
be3d0bd25a476139fdeea1971e4356cbd149cb69vboxsync return crSaSearch(pArray, element) >= 0;
0ee97b0f64f8fc25aec648b0fd38cacbbbe9ff69vboxsync}
99472aa3482be8de024b8ea7aa5f22cba5053216vboxsync
8782e654b5a355600d165b6e0bb761b8f4e769fdvboxsyncVBOXSADECL(int) CrSaAdd(CR_SORTARRAY *pArray, uint64_t element)
96ceb3a26c92d45834d00c86eca5c2e7adbde009vboxsync{
2beb20cf9bf27df36f1704b083f93dff72af736evboxsync return crSaAdd(pArray, element);
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsync}
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsync
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsyncVBOXSADECL(int) CrSaRemove(CR_SORTARRAY *pArray, uint64_t element)
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsync{
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsync return crSaRemove(pArray, element);
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsync}
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsync
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsyncstatic int crSaIntersected(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2, CR_SORTARRAY *pResult)
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsync{
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsync int rc = VINF_SUCCESS;
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsync CrSaClear(pResult);
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsync
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsync for (uint32_t i = 0, j = 0; i < pArray1->cSize && j < pArray2->cSize; )
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsync {
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsync if (pArray1->pElements[i] == pArray2->pElements[j])
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsync {
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsync rc = CrSaAdd(pResult, pArray1->pElements[i]);
96ceb3a26c92d45834d00c86eca5c2e7adbde009vboxsync if (rc < 0)
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync {
96ceb3a26c92d45834d00c86eca5c2e7adbde009vboxsync WARN(("CrSaAdd failed"));
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync return rc;
68e97031354932600728a42c3d454abf04f8c8d1vboxsync }
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync ++i;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync ++j;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync }
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync else if (pArray1->pElements[i] < pArray2->pElements[j])
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync {
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync ++i;
68e97031354932600728a42c3d454abf04f8c8d1vboxsync }
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync else
9d4498106267e3834edc3a37bca5ca660153525cvboxsync {
04dc6a47e0d4c6fffb1192998c068d3e8f00a495vboxsync ++j;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync }
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync }
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync
04dc6a47e0d4c6fffb1192998c068d3e8f00a495vboxsync return VINF_SUCCESS;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync}
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync
04dc6a47e0d4c6fffb1192998c068d3e8f00a495vboxsyncstatic void crSaIntersect(CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync{
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync for (uint32_t i = 0, j = 0; i < pArray1->cSize && j < pArray2->cSize; )
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync {
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync if (pArray1->pElements[i] == pArray2->pElements[j])
0344ece581e48aa2858e00b768ce69eef7bff02avboxsync {
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync ++i;
5a1e5c163993c3b463dd41e71fab26c499dfa44bvboxsync ++j;
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync }
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync else if (pArray1->pElements[i] < pArray2->pElements[j])
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync crSaDelAt(pArray1, i);
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync else
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync ++j;
9eea21d61089fe62b80ef3f4549600091c2b1967vboxsync }
9eea21d61089fe62b80ef3f4549600091c2b1967vboxsync}
9eea21d61089fe62b80ef3f4549600091c2b1967vboxsync
9eea21d61089fe62b80ef3f4549600091c2b1967vboxsync/*
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync * @return >= 0 success
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync * < 0 - no memory
9d4498106267e3834edc3a37bca5ca660153525cvboxsync * */
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsyncVBOXSADECL(void) CrSaIntersect(CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync{
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync crSaIntersect(pArray1, pArray2);
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync}
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsyncVBOXSADECL(int) CrSaIntersected(CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2, CR_SORTARRAY *pResult)
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync{
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync return crSaIntersected(pArray1, pArray2, pResult);
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync}
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync
4d8251400411b4dcf2c86b5b0376a326ff45938cvboxsyncstatic int crSaUnited(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2, CR_SORTARRAY *pResult)
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync{
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync int rc = VINF_SUCCESS;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync CrSaClear(pResult);
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync
4d8251400411b4dcf2c86b5b0376a326ff45938cvboxsync uint32_t i = 0, j = 0;
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync uint32_t cResult = 0;
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync while (i < pArray1->cSize && j < pArray2->cSize)
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync {
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync uint64_t element;
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync if (pArray1->pElements[i] == pArray2->pElements[j])
f9ce005e61f0fbb51a2cabc53d58c3485151faa9vboxsync {
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync element = pArray1->pElements[i];
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync ++i;
f9ce005e61f0fbb51a2cabc53d58c3485151faa9vboxsync ++j;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync }
f9ce005e61f0fbb51a2cabc53d58c3485151faa9vboxsync else if (pArray1->pElements[i] < pArray2->pElements[j])
f9ce005e61f0fbb51a2cabc53d58c3485151faa9vboxsync {
f9ce005e61f0fbb51a2cabc53d58c3485151faa9vboxsync element = pArray1->pElements[i];
f9ce005e61f0fbb51a2cabc53d58c3485151faa9vboxsync ++i;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync }
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync else
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync {
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync element = pArray1->pElements[j];
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync ++j;
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync }
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync rc = crSaInsAt(pResult, cResult++, element);
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync if (rc < 0)
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync {
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync WARN(("crSaInsAt failed"));
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync return rc;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync }
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync }
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync uint32_t iTail;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync const CR_SORTARRAY *pTail;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync if (i < pArray1->cSize)
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync {
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync iTail = i;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync pTail = pArray1;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync }
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync else if (j < pArray2->cSize)
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync {
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync iTail = j;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync pTail = pArray2;
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync }
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync else
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync {
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync iTail = 0;
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync pTail = 0;
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync }
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync if (pTail)
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync {
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync for (;iTail < pTail->cSize; ++iTail)
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync {
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync rc = crSaInsAt(pResult, cResult++, pTail->pElements[iTail]);
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync if (rc < 0)
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync {
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync WARN(("crSaInsAt failed"));
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync return rc;
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync }
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync }
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync }
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync return VINF_SUCCESS;
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync}
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsyncVBOXSADECL(int) CrSaUnited(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2, CR_SORTARRAY *pResult)
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync{
4d8251400411b4dcf2c86b5b0376a326ff45938cvboxsync return crSaUnited(pArray1, pArray2, pResult);
4d8251400411b4dcf2c86b5b0376a326ff45938cvboxsync}
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsyncstatic int crSaClone(const CR_SORTARRAY *pArray1, CR_SORTARRAY *pResult)
4d8251400411b4dcf2c86b5b0376a326ff45938cvboxsync{
0344ece581e48aa2858e00b768ce69eef7bff02avboxsync int rc = 0;
4d8251400411b4dcf2c86b5b0376a326ff45938cvboxsync CrSaClear(pResult);
4d8251400411b4dcf2c86b5b0376a326ff45938cvboxsync
4d8251400411b4dcf2c86b5b0376a326ff45938cvboxsync if (pArray1->cSize > pResult->cBufferSize)
4d8251400411b4dcf2c86b5b0376a326ff45938cvboxsync {
0344ece581e48aa2858e00b768ce69eef7bff02avboxsync CrSaCleanup(pResult);
0344ece581e48aa2858e00b768ce69eef7bff02avboxsync uint32_t cNewBufferSize = pArray1->cSize;
760446f710619a9daa6cedc7f0601f49e4ea3442vboxsync uint64_t *pNew = (uint64_t*)RTMemAlloc(cNewBufferSize * sizeof (pResult->pElements[0]));
0344ece581e48aa2858e00b768ce69eef7bff02avboxsync if (!pNew)
0344ece581e48aa2858e00b768ce69eef7bff02avboxsync {
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync WARN(("no memory"));
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync return VERR_NO_MEMORY;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync }
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync
9d4498106267e3834edc3a37bca5ca660153525cvboxsync pResult->pElements = pNew;
d528a04fa09ef242ac61f49472a5f1027b6b33e5vboxsync pResult->cBufferSize = cNewBufferSize;
d528a04fa09ef242ac61f49472a5f1027b6b33e5vboxsync crSaValidate(pResult);
d528a04fa09ef242ac61f49472a5f1027b6b33e5vboxsync }
d528a04fa09ef242ac61f49472a5f1027b6b33e5vboxsync
d528a04fa09ef242ac61f49472a5f1027b6b33e5vboxsync pResult->cSize = pArray1->cSize;
c55bf74b54ecdfb5ebc4e5d90b620d0fee31737evboxsync memcpy(pResult->pElements, pArray1->pElements, pArray1->cSize * sizeof (pArray1->pElements[0]));
c55bf74b54ecdfb5ebc4e5d90b620d0fee31737evboxsync return VINF_SUCCESS;
c55bf74b54ecdfb5ebc4e5d90b620d0fee31737evboxsync}
c55bf74b54ecdfb5ebc4e5d90b620d0fee31737evboxsync
c55bf74b54ecdfb5ebc4e5d90b620d0fee31737evboxsync/*
d528a04fa09ef242ac61f49472a5f1027b6b33e5vboxsync * @return VINF_SUCCESS on success
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync * VERR_NO_MEMORY - no memory
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync * */
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsyncVBOXSADECL(int) CrSaClone(const CR_SORTARRAY *pArray1, CR_SORTARRAY *pResult)
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync{
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync return crSaClone(pArray1, pResult);
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync}
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsyncstatic int crSaCmp(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync{
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync int diff = CrSaGetSize(pArray1) - CrSaGetSize(pArray2);
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync if (diff)
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync return diff;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync return memcmp(pArray1->pElements, pArray2->pElements, pArray1->cSize * sizeof (pArray1->pElements[0]));
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync}
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsyncVBOXSADECL(int) CrSaCmp(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync{
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync return crSaCmp(pArray1, pArray2);
9eea21d61089fe62b80ef3f4549600091c2b1967vboxsync}
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsyncstatic bool crSaCovers(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync{
9eea21d61089fe62b80ef3f4549600091c2b1967vboxsync if (CrSaGetSize(pArray1) < CrSaGetSize(pArray2))
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync return false;
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync
817d003403ed9395143bd4ba88fbd9cb60e5eeebvboxsync uint32_t i = 0, j = 0;
9eea21d61089fe62b80ef3f4549600091c2b1967vboxsync while (j < pArray2->cSize)
817d003403ed9395143bd4ba88fbd9cb60e5eeebvboxsync {
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync if (i == pArray1->cSize)
f9ce005e61f0fbb51a2cabc53d58c3485151faa9vboxsync return false;
f9ce005e61f0fbb51a2cabc53d58c3485151faa9vboxsync
f9ce005e61f0fbb51a2cabc53d58c3485151faa9vboxsync if (pArray1->pElements[i] == pArray2->pElements[j])
f9ce005e61f0fbb51a2cabc53d58c3485151faa9vboxsync {
f9ce005e61f0fbb51a2cabc53d58c3485151faa9vboxsync ++i;
f9ce005e61f0fbb51a2cabc53d58c3485151faa9vboxsync ++j;
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync }
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync else if (pArray1->pElements[i] < pArray2->pElements[j])
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync ++i;
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync else
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync return false;
d8e12fa5dd1c35282b98cb165e42b6b395cf971bvboxsync }
d8e12fa5dd1c35282b98cb165e42b6b395cf971bvboxsync
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync return true;
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync}
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsyncVBOXSADECL(bool) CrSaCovers(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync{
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync return crSaCovers(pArray1, pArray2);
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync}
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync