OpenGL/util/sortarray.cpp

	sortarray.cpp revision 635c83753ed04cf3637e019af0e15ba40e07f2fe
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync/* $Id$ */
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync/** @file
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync * Sorted array impl
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync */
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync/*
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync * Copyright (C) 2014 Oracle Corporation
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync *
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync * This file is part of VirtualBox Open Source Edition (OSE), as
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync * available from http://www.virtualbox.org. This file is free software;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync * you can redistribute it and/or modify it under the terms of the GNU
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync * General Public License (GPL) as published by the Free Software
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync * Foundation, in version 2 as it comes in the "COPYING" file of the
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync */
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
930b5f872e89407f445d4000d4e4aaecaa6a0998vboxsync#include <cr_sortarray.h>
930b5f872e89407f445d4000d4e4aaecaa6a0998vboxsync#include <cr_error.h>
930b5f872e89407f445d4000d4e4aaecaa6a0998vboxsync#include <iprt/err.h>
930b5f872e89407f445d4000d4e4aaecaa6a0998vboxsync#include <iprt/mem.h>
930b5f872e89407f445d4000d4e4aaecaa6a0998vboxsync
930b5f872e89407f445d4000d4e4aaecaa6a0998vboxsync#include <memory.h>
930b5f872e89407f445d4000d4e4aaecaa6a0998vboxsync
930b5f872e89407f445d4000d4e4aaecaa6a0998vboxsyncVBOXSADECL(int) CrSaInit(CR_SORTARRAY *pArray, uint32_t cInitBuffer)
930b5f872e89407f445d4000d4e4aaecaa6a0998vboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    pArray->cBufferSize = cInitBuffer;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    pArray->cSize = 0;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    if (cInitBuffer)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        pArray->pElements = (uint64_t*)RTMemAlloc(cInitBuffer * sizeof (pArray->pElements[0]));
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        if (!pArray->pElements)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            WARN(("no memory"));
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            /* sanity */
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            pArray->cBufferSize = 0;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            return VERR_NO_MEMORY;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    else
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        pArray->pElements = NULL;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    return VINF_SUCCESS;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsyncVBOXSADECL(void) CrSaCleanup(CR_SORTARRAY *pArray)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    if (pArray->pElements)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        RTMemFree(pArray->pElements);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    CrSaInit(pArray, 0);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsyncstatic int crSaSearch(const CR_SORTARRAY *pArray, uint64_t element)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    int iMin = 0;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    int iMax = pArray->cSize;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    int i = 0;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    while (iMin < iMax)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        i = (iMax + iMin) / 2;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        uint64_t el = pArray->pElements[i];
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        if (el == element)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            return i;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        else if (el < element)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            iMin = i + 1;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        else
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            iMax = i;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    return -1;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsyncstatic void crSaDbgValidate(const CR_SORTARRAY *pArray)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    Assert(pArray->cSize <= pArray->cBufferSize);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    Assert(!pArray->pElements == !pArray->cBufferSize);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    if (!pArray->cSize)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        return;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    uint64_t cur = pArray->pElements[0];
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    for (uint32_t i = 1; i < pArray->cSize; ++i)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        Assert(pArray->pElements[i] > cur);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        cur = pArray->pElements[i];
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync#ifdef DEBUG
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync# define crSaValidate crSaDbgValidate
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync#else
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync# define crSaValidate(_a) do {} while (0)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync#endif
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsyncstatic int crSaInsAt(CR_SORTARRAY *pArray, uint32_t iPos, uint64_t element)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    if (pArray->cSize == pArray->cBufferSize)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        uint32_t cNewBufferSize = pArray->cBufferSize + 16;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        uint64_t *pNew;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        if (pArray->pElements)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            pNew = (uint64_t*)RTMemRealloc(pArray->pElements, cNewBufferSize * sizeof (pArray->pElements[0]));
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        else
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            pNew = (uint64_t*)RTMemAlloc(cNewBufferSize * sizeof (pArray->pElements[0]));
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        if (!pNew)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            WARN(("no memory"));
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            return VERR_NO_MEMORY;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        pArray->pElements = pNew;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        pArray->cBufferSize = cNewBufferSize;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        crSaValidate(pArray);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    for (int32_t i = (int32_t)pArray->cSize - 1; i >= (int32_t)iPos; --i)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        pArray->pElements[i+1] = pArray->pElements[i];
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    pArray->pElements[iPos] = element;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    ++pArray->cSize;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    crSaValidate(pArray);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    return VINF_SUCCESS;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsyncstatic void crSaDelAt(CR_SORTARRAY *pArray, uint32_t iPos)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    Assert(pArray->cSize > iPos);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    for (uint32_t i = iPos; i < pArray->cSize - 1; ++i)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        pArray->pElements[i] = pArray->pElements[i+1];
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    --pArray->cSize;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsyncstatic int crSaAdd(CR_SORTARRAY *pArray, uint64_t element)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    int iMin = 0;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    int iMax = pArray->cSize;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    int i = 0;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    uint64_t el;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    if (!iMax)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        return crSaInsAt(pArray, 0, element);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    while (iMin < iMax)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        i = (iMax + iMin) / 2;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        el = pArray->pElements[i];
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        if (el == element)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            return VINF_ALREADY_INITIALIZED;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        else if (el < element)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            iMin = i + 1;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        else
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            iMax = i;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    if (el < element)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        return crSaInsAt(pArray, i+1, element);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    return crSaInsAt(pArray, i, element);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsyncstatic int crSaRemove(CR_SORTARRAY *pArray, uint64_t element)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    int i = crSaSearch(pArray, element);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    if (i >= 0)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        crSaDelAt(pArray, i);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        return VINF_SUCCESS;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    return VINF_ALREADY_INITIALIZED;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync/*
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync *  * @return true if element is found */
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsyncVBOXSADECL(bool) CrSaContains(const CR_SORTARRAY *pArray, uint64_t element)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    return crSaSearch(pArray, element) >= 0;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsyncVBOXSADECL(int) CrSaAdd(CR_SORTARRAY *pArray, uint64_t element)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    return crSaAdd(pArray, element);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsyncVBOXSADECL(int) CrSaRemove(CR_SORTARRAY *pArray, uint64_t element)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    return crSaRemove(pArray, element);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsyncstatic int crSaIntersected(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2, CR_SORTARRAY *pResult)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    int rc = VINF_SUCCESS;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    CrSaClear(pResult);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    for (uint32_t i = 0, j = 0; i < pArray1->cSize && j < pArray2->cSize; )
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        if (pArray1->pElements[i] == pArray2->pElements[j])
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            rc = CrSaAdd(pResult, pArray1->pElements[i]);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            if (rc < 0)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync                WARN(("CrSaAdd failed"));
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync                return rc;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            ++i;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            ++j;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        else if (pArray1->pElements[i] < pArray2->pElements[j])
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            ++i;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        else
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            ++j;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    return VINF_SUCCESS;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsyncstatic void crSaIntersect(CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    for (uint32_t i = 0, j = 0; i < pArray1->cSize && j < pArray2->cSize; )
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        if (pArray1->pElements[i] == pArray2->pElements[j])
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            ++i;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            ++j;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        else if (pArray1->pElements[i] < pArray2->pElements[j])
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            crSaDelAt(pArray1, i);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        else
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            ++j;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync/*
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync * @return >= 0 success
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync * < 0 - no memory
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync *  */
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsyncVBOXSADECL(void) CrSaIntersect(CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    crSaIntersect(pArray1, pArray2);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsyncVBOXSADECL(int) CrSaIntersected(CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2, CR_SORTARRAY *pResult)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    return crSaIntersected(pArray1, pArray2, pResult);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsyncstatic int crSaUnited(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2, CR_SORTARRAY *pResult)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    int rc = VINF_SUCCESS;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    CrSaClear(pResult);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    uint32_t i = 0, j = 0;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    uint32_t cResult = 0;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    while (i < pArray1->cSize && j < pArray2->cSize)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        uint64_t element;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        if (pArray1->pElements[i] == pArray2->pElements[j])
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            element = pArray1->pElements[i];
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            ++i;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            ++j;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        else if (pArray1->pElements[i] < pArray2->pElements[j])
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            element = pArray1->pElements[i];
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            ++i;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        else
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            element = pArray1->pElements[j];
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            ++j;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        rc = crSaInsAt(pResult, cResult++, element);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        if (rc < 0)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            WARN(("crSaInsAt failed"));
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            return rc;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    uint32_t iTail;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    const CR_SORTARRAY *pTail;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    if (i < pArray1->cSize)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        iTail = i;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        pTail = pArray1;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    else if (j < pArray2->cSize)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        iTail = j;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        pTail = pArray2;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    else
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        iTail = 0;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        pTail = 0;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    if (pTail)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        for (;iTail < pTail->cSize; ++iTail)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            rc = crSaInsAt(pResult, cResult++, pTail->pElements[iTail]);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            if (rc < 0)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync                WARN(("crSaInsAt failed"));
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync                return rc;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    return VINF_SUCCESS;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsyncVBOXSADECL(int) CrSaUnited(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2, CR_SORTARRAY *pResult)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    return crSaUnited(pArray1, pArray2, pResult);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsyncstatic int crSaClone(const CR_SORTARRAY *pArray1, CR_SORTARRAY *pResult)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    int rc = 0;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    CrSaClear(pResult);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    if (pArray1->cSize > pResult->cBufferSize)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        CrSaCleanup(pResult);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        uint32_t cNewBufferSize = pArray1->cSize;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        uint64_t *pNew = (uint64_t*)RTMemAlloc(cNewBufferSize * sizeof (pResult->pElements[0]));
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        if (!pNew)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            WARN(("no memory"));
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            return VERR_NO_MEMORY;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        pResult->pElements = pNew;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        pResult->cBufferSize = cNewBufferSize;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        crSaValidate(pResult);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    pResult->cSize = pArray1->cSize;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    memcpy(pResult->pElements, pArray1->pElements, pArray1->cSize * sizeof (pArray1->pElements[0]));
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    return VINF_SUCCESS;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync/*
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync * @return VINF_SUCCESS on success
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync * VERR_NO_MEMORY - no memory
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync *  */
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsyncVBOXSADECL(int) CrSaClone(const CR_SORTARRAY *pArray1, CR_SORTARRAY *pResult)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    return crSaClone(pArray1, pResult);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsyncstatic int crSaCmp(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    int diff = CrSaGetSize(pArray1) - CrSaGetSize(pArray2);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    if (diff)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        return diff;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    return memcmp(pArray1->pElements, pArray2->pElements, pArray1->cSize * sizeof (pArray1->pElements[0]));
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsyncVBOXSADECL(int) CrSaCmp(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    return crSaCmp(pArray1, pArray2);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsyncstatic bool crSaCovers(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    if (CrSaGetSize(pArray1) < CrSaGetSize(pArray2))
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        return false;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    uint32_t i = 0, j = 0;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    while (j < pArray2->cSize)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        if (i == pArray1->cSize)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            return false;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        if (pArray1->pElements[i] == pArray2->pElements[j])
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        {
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            ++i;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            ++j;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        else if (pArray1->pElements[i] < pArray2->pElements[j])
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            ++i;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync        else
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync            return false;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    }
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    return true;
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsyncVBOXSADECL(bool) CrSaCovers(const CR_SORTARRAY *pArray1, const CR_SORTARRAY *pArray2)
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync{
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync    return crSaCovers(pArray1, pArray2);
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync}
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync
3194da424708abdd288b28d96892b3a5f3f7df0bvboxsync