a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync * Sorted array impl
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync * Copyright (C) 2014 Oracle Corporation
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.
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsyncVBOXSADECL(int) CrSaInit(CR_SORTARRAY *pArray, uint32_t cInitBuffer)
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync pArray->pElements = (uint64_t*)RTMemAlloc(cInitBuffer * sizeof (pArray->pElements[0]));
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync /* sanity */
137af3daace06f18fa5d5c74f281d90f3884b277vboxsyncstatic int crSaSearch(const CR_SORTARRAY *pArray, uint64_t element)
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsyncstatic void crSaDbgValidate(const CR_SORTARRAY *pArray)
137af3daace06f18fa5d5c74f281d90f3884b277vboxsync Assert(!pArray->pElements == !pArray->cBufferSize);
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsyncstatic int crSaInsAt(CR_SORTARRAY *pArray, uint32_t iPos, uint64_t element)
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsync uint32_t cNewBufferSize = pArray->cBufferSize + 16;
859d0408dbaebc06a6a82b0eeeb81e84f9af7c44vboxsync pNew = (uint64_t*)RTMemRealloc(pArray->pElements, cNewBufferSize * sizeof (pArray->pElements[0]));
58ca9f00941a16020aa7f72c3af005df1cb218d6vboxsync pNew = (uint64_t*)RTMemAlloc(cNewBufferSize * sizeof (pArray->pElements[0]));
3fb3de312d1ff675e0f7cc62a7d46cbb1d5d9353vboxsync for (int32_t i = (int32_t)pArray->cSize - 1; i >= (int32_t)iPos; --i)
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsyncstatic void crSaDelAt(CR_SORTARRAY *pArray, uint32_t iPos)
3fb3de312d1ff675e0f7cc62a7d46cbb1d5d9353vboxsync for (uint32_t i = iPos; i < pArray->cSize - 1; ++i)
22866e6b8e8304e8604724f7509c33253e7eedcfvboxsyncstatic int crSaAdd(CR_SORTARRAY *pArray, uint64_t element)
862ba4401c9fa66fbb0264053634d47d0718ed74vboxsyncstatic int crSaRemove(CR_SORTARRAY *pArray, uint64_t element)
862ba4401c9fa66fbb0264053634d47d0718ed74vboxsync if (i >= 0)
2beb20cf9bf27df36f1704b083f93dff72af736evboxsync * * @return true if element is found */
2beb20cf9bf27df36f1704b083f93dff72af736evboxsyncVBOXSADECL(bool) CrSaContains(const CR_SORTARRAY *pArray, uint64_t element)
8782e654b5a355600d165b6e0bb761b8f4e769fdvboxsyncVBOXSADECL(int) CrSaAdd(CR_SORTARRAY *pArray, uint64_t element)
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsyncVBOXSADECL(int) CrSaRemove(CR_SORTARRAY *pArray, uint64_t element)
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsyncstatic int crSaIntersected(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2, CR_SORTARRAY *pResult)
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsync for (uint32_t i = 0, j = 0; i < pArray1->cSize && j < pArray2->cSize; )
2284808ae4f8f30c11d68ef1c354e2b9c6405469vboxsync if (pArray1->pElements[i] == pArray2->pElements[j])
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync else if (pArray1->pElements[i] < pArray2->pElements[j])
04dc6a47e0d4c6fffb1192998c068d3e8f00a495vboxsyncstatic void crSaIntersect(CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync for (uint32_t i = 0, j = 0; i < pArray1->cSize && j < pArray2->cSize; )
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync if (pArray1->pElements[i] == pArray2->pElements[j])
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync else if (pArray1->pElements[i] < pArray2->pElements[j])
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync * @return >= 0 success
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync * < 0 - no memory
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsyncVBOXSADECL(void) CrSaIntersect(CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsyncVBOXSADECL(int) CrSaIntersected(CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2, CR_SORTARRAY *pResult)
4d8251400411b4dcf2c86b5b0376a326ff45938cvboxsyncstatic int crSaUnited(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2, CR_SORTARRAY *pResult)
4d8251400411b4dcf2c86b5b0376a326ff45938cvboxsync uint32_t i = 0, j = 0;
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync if (pArray1->pElements[i] == pArray2->pElements[j])
f9ce005e61f0fbb51a2cabc53d58c3485151faa9vboxsync else if (pArray1->pElements[i] < pArray2->pElements[j])
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync rc = crSaInsAt(pResult, cResult++, pTail->pElements[iTail]);
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsyncVBOXSADECL(int) CrSaUnited(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2, CR_SORTARRAY *pResult)
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsyncstatic int crSaClone(const CR_SORTARRAY *pArray1, CR_SORTARRAY *pResult)
760446f710619a9daa6cedc7f0601f49e4ea3442vboxsync uint64_t *pNew = (uint64_t*)RTMemAlloc(cNewBufferSize * sizeof (pResult->pElements[0]));
c55bf74b54ecdfb5ebc4e5d90b620d0fee31737evboxsync memcpy(pResult->pElements, pArray1->pElements, pArray1->cSize * sizeof (pArray1->pElements[0]));
d528a04fa09ef242ac61f49472a5f1027b6b33e5vboxsync * @return VINF_SUCCESS on success
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync * VERR_NO_MEMORY - no memory
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsyncVBOXSADECL(int) CrSaClone(const CR_SORTARRAY *pArray1, CR_SORTARRAY *pResult)
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsyncstatic int crSaCmp(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync int diff = CrSaGetSize(pArray1) - CrSaGetSize(pArray2);
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsync return memcmp(pArray1->pElements, pArray2->pElements, pArray1->cSize * sizeof (pArray1->pElements[0]));
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsyncVBOXSADECL(int) CrSaCmp(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
462e60a19d02a99b2b1a5c08dff74bb0808d707cvboxsyncstatic bool crSaCovers(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
a64437373eb5fa1b2d6c3bc2e486837a6b9ae1d6vboxsync return false;
817d003403ed9395143bd4ba88fbd9cb60e5eeebvboxsync uint32_t i = 0, j = 0;
f9ce005e61f0fbb51a2cabc53d58c3485151faa9vboxsync return false;
f9ce005e61f0fbb51a2cabc53d58c3485151faa9vboxsync if (pArray1->pElements[i] == pArray2->pElements[j])
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync else if (pArray1->pElements[i] < pArray2->pElements[j])
4171ffb38eb8720b2ae9a8d13e95103ab26cfd12vboxsync return false;
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsync return true;
3ff8aa7d3c74cfbe8da5f77b8ea6c748cc79213avboxsyncVBOXSADECL(bool) CrSaCovers(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)