xsarray.c

Go to the documentation of this file.

 
//  Copyright (c) 2003-2021 Xsens Technologies B.V. or subsidiaries worldwide.
//  All rights reserved.
//  
//  Redistribution and use in source and binary forms, with or without modification,
//  are permitted provided that the following conditions are met:
//  
//  1.  Redistributions of source code must retain the above copyright notice,
//      this list of conditions, and the following disclaimer.
//  
//  2.  Redistributions in binary form must reproduce the above copyright notice,
//      this list of conditions, and the following disclaimer in the documentation
//      and/or other materials provided with the distribution.
//  
//  3.  Neither the names of the copyright holders nor the names of their contributors
//      may be used to endorse or promote products derived from this software without
//      specific prior written permission.
//  
//  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
//  EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
//  MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
//  THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
//  SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT 
//  OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
//  HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY OR
//  TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
//  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.THE LAWS OF THE NETHERLANDS 
//  SHALL BE EXCLUSIVELY APPLICABLE AND ANY DISPUTES SHALL BE FINALLY SETTLED UNDER THE RULES 
//  OF ARBITRATION OF THE INTERNATIONAL CHAMBER OF COMMERCE IN THE HAGUE BY ONE OR MORE 
//  ARBITRATORS APPOINTED IN ACCORDANCE WITH SAID RULES.
//  
 
 
//  Copyright (c) 2003-2021 Xsens Technologies B.V. or subsidiaries worldwide.
//  All rights reserved.
//  
//  Redistribution and use in source and binary forms, with or without modification,
//  are permitted provided that the following conditions are met:
//  
//  1.  Redistributions of source code must retain the above copyright notice,
//      this list of conditions, and the following disclaimer.
//  
//  2.  Redistributions in binary form must reproduce the above copyright notice,
//      this list of conditions, and the following disclaimer in the documentation
//      and/or other materials provided with the distribution.
//  
//  3.  Neither the names of the copyright holders nor the names of their contributors
//      may be used to endorse or promote products derived from this software without
//      specific prior written permission.
//  
//  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
//  EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
//  MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
//  THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
//  SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT 
//  OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
//  HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY OR
//  TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
//  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.THE LAWS OF THE NETHERLANDS 
//  SHALL BE EXCLUSIVELY APPLICABLE AND ANY DISPUTES SHALL BE FINALLY SETTLED UNDER THE RULES 
//  OF ARBITRATION OF THE INTERNATIONAL CHAMBER OF COMMERCE IN THE HAGUE BY ONE OR MORE 
//  ARBITRATORS APPOINTED IN ACCORDANCE WITH SAID RULES.
//  
 
#include "xsarray.h"
#include <stdlib.h>
#include <string.h>
#include "xsdebugcounters.h"
 
#define elemSize(thisArray)                     (thisArray->m_descriptor->itemSize)
#define elemAtX(b, i, thisArray)        ((void*)(((char*) (b))+((i)*elemSize(thisArray))))
#define elemAt(b, i)                            elemAtX(b, i, thisArray)
 
#ifdef DOXYGEN
 
        void XsArray_constructDerived(void* thisPtr, XsSize count, void const* src);
#endif
 
void XsArray_construct(void* thisPtr, XsArrayDescriptor const* const descriptor, XsSize count, void const* src)
{
        XsArray* thisArray = (XsArray*) thisPtr;
        *((XsArrayDescriptor const**) &thisArray->m_descriptor) = descriptor;
        *((XsSize*) &thisArray->m_size) = count;
 
        if (thisArray->m_size)
        {
                // init to size
                *((void**) &thisArray->m_data) = malloc(thisArray->m_size * elemSize(thisArray));
                XsArray_incAllocCount();
 
                // init the configurations
                if (src)
                {
                        if (thisArray->m_descriptor->rawCopy)
                                thisArray->m_descriptor->rawCopy(thisArray->m_data, src, thisArray->m_size, thisArray->m_descriptor->itemSize);
                        else
                        {
                                XsSize i;
                                assert(thisArray->m_descriptor->itemCopyConstruct);
                                for (i = 0; i < thisArray->m_size; ++i)
                                        thisArray->m_descriptor->itemCopyConstruct(elemAt(thisArray->m_data, i), elemAt(src, i));
                        }
                }
                else if (thisArray->m_descriptor->itemConstruct)
                {
                        XsSize i;
                        for (i = 0; i < thisArray->m_size; ++i)
                                thisArray->m_descriptor->itemConstruct(elemAt(thisArray->m_data, i));
                }
        }
        else
                *((void**) &thisArray->m_data) = 0;
        *((XsSize*) &thisArray->m_reserved) = thisArray->m_size;
        *((XsSize*) &thisArray->m_flags) = XSDF_Managed;
}
 
void XsArray_copyConstruct(void* thisPtr, void const* src)
{
        XsArray* thisArray = (XsArray*) thisPtr;
        XsArray const* srcArray = (XsArray const*) src;
        assert(srcArray);
        XsArray_construct(thisArray, srcArray->m_descriptor, srcArray->m_size, srcArray->m_data);
}
 
void XsArray_destruct(void* thisPtr)
{
        XsArray* thisArray = (XsArray*) thisPtr;
        if (thisArray->m_data && (thisArray->m_flags & XSDF_Managed))
        {
                XsSize i;
                // clear contents
                if (thisArray->m_descriptor->itemDestruct)
                        for (i = 0; i < thisArray->m_reserved; ++i)
                                thisArray->m_descriptor->itemDestruct(elemAt(thisArray->m_data, i));
                free((void*) thisArray->m_data);
                XsArray_incFreeCount();
        }
        // init to 0
        *((void**) &thisArray->m_data) = 0;
        *((XsSize*) &thisArray->m_size) = 0;
        *((XsSize*) &thisArray->m_reserved) = 0;
        *((XsSize*) &thisArray->m_flags) = (thisArray->m_flags & (XSDF_Managed | XSDF_FixedSize));
}
 
void XsArray_assign(void* thisPtr, XsSize count, void const* src)
{
        XsSize i;
        XsArray* thisArray = (XsArray*) thisPtr;
 
        // check if we need to reallocate
        if (count > thisArray->m_reserved)
        {
                assert(thisArray->m_flags & XSDF_Managed);
 
                if (thisArray->m_data)
                        XsArray_destruct(thisArray);
                XsArray_construct(thisArray, thisArray->m_descriptor, count, src);
                return;
        }
 
        // no reallocation necessary, clear excess objects
        if (thisArray->m_descriptor->itemDestruct)
                for (i = count; i < thisArray->m_size; ++i)
                        thisArray->m_descriptor->itemDestruct(elemAt(thisArray->m_data, i));
 
        if (src)
        {
                if (thisArray->m_descriptor->rawCopy)
                        thisArray->m_descriptor->rawCopy(thisArray->m_data, src, count, thisArray->m_descriptor->itemSize);
                else
                {
                        for (i = 0; i < count; ++i)
                                thisArray->m_descriptor->itemCopy(elemAt(thisArray->m_data, i), elemAt(src, i));
                }
        }
 
        *((XsSize*) &thisArray->m_size) = count;
}
 
void XsArray_resize(void* thisPtr, XsSize count)
{
        XsArray* thisArray = (XsArray*) thisPtr;
        if (thisArray->m_size == count)
                return;
        if (thisArray->m_size == 0)
        {
                XsArray_assign(thisArray, count, 0);
                return;
        }
        if (count < thisArray->m_size)
        {
                XsArray_erase(thisArray, count, thisArray->m_size - count);
                return;
        }
        if (count > thisArray->m_reserved)
                XsArray_reserve(thisArray, count);
        *((XsSize*) &thisArray->m_size) = count;
}
 
void XsArray_reserve(void* thisPtr, XsSize count)
{
        XsArray* thisArray = (XsArray*) thisPtr;
        XsArray tmp = { 0, thisArray->m_size, 0, XSDF_Managed, thisArray->m_descriptor };
        XsSize i;
 
        if (count && count <= thisArray->m_reserved)
                return;
 
        if (count < thisArray->m_size)
                count = thisArray->m_size;
 
        if (count == thisArray->m_reserved)
                return;
 
        if (!(thisArray->m_flags & XSDF_Managed))
        {
                // attempting this on an unmanaged list is ignored silently
                return;
        }
 
        if (!count)
        {
                XsArray_destruct(thisArray);
                return;
        }
 
        *((XsSize*) &tmp.m_reserved) = count;
 
        // init to size
        *((void**) &tmp.m_data) = malloc(tmp.m_reserved * elemSize(thisArray));
        assert(tmp.m_data);
        if (!tmp.m_data)
                return;
        XsArray_incAllocCount();
 
        if (thisArray->m_descriptor->itemConstruct)
                for (i = 0; i < tmp.m_reserved; ++i)
                        thisArray->m_descriptor->itemConstruct(elemAt(tmp.m_data, i));
 
        for (i = 0; i < thisArray->m_size; ++i)
                thisArray->m_descriptor->itemSwap(elemAt(thisArray->m_data, i), elemAt(tmp.m_data, i));
 
        XsArray_destruct(thisArray);
        XsArray_swap(thisArray, &tmp);
}
 
void XsArray_copy(void* thisPtr, void const* src)
{
        XsArray* thisArray = (XsArray*) thisPtr;
        XsArray const* srcArray = (XsArray const*) src;
 
        if (srcArray == thisArray)
                return;
        XsArray_assign(thisArray, srcArray->m_size, srcArray->m_data);
}
 
void XsArray_append(void* thisPtr, void const* other)
{
        XsSize i;
        XsArray* thisArray = (XsArray*) thisPtr;
        XsArray const* otherArray = (XsArray const*) other;
 
        if (otherArray->m_size == 0)
                return;
 
        if (otherArray == thisArray)
        {
                if (thisArray->m_size + thisArray->m_size > thisArray->m_reserved)
                        XsArray_reserve(thisArray, thisArray->m_size + thisArray->m_size);      // maybe reserve more here?
 
                if (thisArray->m_descriptor->rawCopy)
                        thisArray->m_descriptor->rawCopy(elemAt(thisArray->m_data, thisArray->m_size), thisArray->m_data, thisArray->m_size, thisArray->m_descriptor->itemSize);
                else
                {
                        for (i = 0; i < thisArray->m_size; ++i)
                                thisArray->m_descriptor->itemCopy(elemAt(thisArray->m_data, i + thisArray->m_size), elemAt(thisArray->m_data, i));
                }
 
                *((XsSize*) &thisArray->m_size) = thisArray->m_size + thisArray->m_size;
                return;
        }
 
        if (thisArray->m_size == 0)
        {
                XsArray_copy(thisArray, otherArray);
                return;
        }
 
        if (thisArray->m_size + otherArray->m_size > thisArray->m_reserved)
                XsArray_reserve(thisArray, thisArray->m_size + otherArray->m_size);     // maybe reserve more here?
 
        if (thisArray->m_descriptor->rawCopy)
                thisArray->m_descriptor->rawCopy(elemAt(thisArray->m_data, thisArray->m_size), otherArray->m_data, otherArray->m_size, thisArray->m_descriptor->itemSize);
        else
        {
                for (i = 0; i < otherArray->m_size; ++i)
                        thisArray->m_descriptor->itemCopy(elemAt(thisArray->m_data, i + thisArray->m_size), elemAt(otherArray->m_data, i));
        }
 
        *((XsSize*) &thisArray->m_size) = thisArray->m_size + otherArray->m_size;
}
 
void XsArray_insert(void* thisPtr, XsSize index, XsSize count, void const* src)
{
        XsSize s;
        XsArray* thisArray = (XsArray*) thisPtr;
        XsSize i, d = count;
        if (thisArray->m_size + count > thisArray->m_reserved)
                XsArray_reserve(thisArray, ((thisArray->m_size + count) * 3) / 2);              // we reserve 50% more space here to handle multiple sequential insertions efficiently
 
        // fix index if beyond end of list
        if (index > thisArray->m_size)
                index = thisArray->m_size;
 
        // move items to the back by swapping
        for (i = thisArray->m_size - 1; i >= index && i < thisArray->m_size; --i)
                thisArray->m_descriptor->itemSwap(elemAt(thisArray->m_data, i), elemAt(thisArray->m_data, i + d));
 
        // copy items to the array
        if (thisArray->m_descriptor->rawCopy)
                thisArray->m_descriptor->rawCopy(elemAt(thisArray->m_data, index), src, count, thisArray->m_descriptor->itemSize);
        else
        {
                for (s = 0; s < count; ++s)
                        thisArray->m_descriptor->itemCopy(elemAt(thisArray->m_data, s + index), elemAt(src, s));
        }
 
        // update size
        *((XsSize*) &thisArray->m_size) = thisArray->m_size + count;
}
 
void XsArray_swap(void* a, void* b)
{
        XsArray* aArray = (XsArray*) a;
        XsArray* bArray = (XsArray*) b;
 
        if (!aArray->m_data && !bArray->m_data)
                return;
        if ((!aArray->m_data || (aArray->m_flags & XSDF_Managed)) && (!bArray->m_data || (bArray->m_flags & XSDF_Managed)))
        {
                // administrative swap
                XsArray tmp;
                *((void**) &tmp.m_data) = aArray->m_data;
                *((void**) &aArray->m_data) = bArray->m_data;
                *((void**) &bArray->m_data) = tmp.m_data;
 
                *((XsSize*) &tmp.m_size) = aArray->m_size;
                *((XsSize*) &aArray->m_size) = bArray->m_size;
                *((XsSize*) &bArray->m_size) = tmp.m_size;
 
                *((XsSize*) &tmp.m_reserved) = aArray->m_reserved;
                *((XsSize*) &aArray->m_reserved) = bArray->m_reserved;
                *((XsSize*) &bArray->m_reserved) = tmp.m_reserved;
 
                *((XsSize*) &tmp.m_flags) = aArray->m_flags;
                *((XsSize*) &aArray->m_flags) = bArray->m_flags;
                *((XsSize*) &bArray->m_flags) = tmp.m_flags;
        }
        else
        {
                // elementwise swap
                XsSize i;
                assert(aArray->m_size == bArray->m_size);
                for (i = 0; i < aArray->m_size; ++i)
                        aArray->m_descriptor->itemSwap(elemAtX(aArray->m_data, i, aArray), elemAtX(bArray->m_data, i, bArray));
        }
}
 
void XsArray_erase(void* thisPtr, XsSize index, XsSize count)
{
        XsSize i, newCount;
        XsArray* thisArray = (XsArray*) thisPtr;
 
        if (count == 0 || index >= thisArray->m_size)
                return;
 
        if (count + index > thisArray->m_size)
                count = thisArray->m_size - index;
 
        newCount = thisArray->m_size - count;
 
        // move items into the gap by swapping
        for (i = index; i < newCount; ++i)
                thisArray->m_descriptor->itemSwap(elemAt(thisArray->m_data, i), elemAt(thisArray->m_data, i + count));
 
        *((XsSize*) &thisArray->m_size) = newCount;
}
 
int XsArray_compare(void const* a, void const* b)
{
        XsSize i;
        XsArray const* aArray = (XsArray const*) a;
        XsArray const* bArray = (XsArray const*) b;
 
        if (aArray == bArray)
                return 0;
 
        if (aArray->m_size != bArray->m_size)
                return (aArray->m_size < bArray->m_size) ? -1 : 1;
 
        assert(aArray->m_descriptor->itemCompare);
        // we could theoretically only check the sizes and ignore the element-comparison in thisArray case
        for (i = 0; i < aArray->m_size; ++i) // loop over all elements of the lists
        {
                int r = aArray->m_descriptor->itemCompare(elemAtX(aArray->m_data, i, aArray), elemAtX(bArray->m_data, i, bArray));
                if (r)
                        return r;
        }
        return 0;
}
 
int XsArray_comparePredicate(void const* a, void const* b, XsArrayItemCompareFunc predicate)
{
        XsSize i;
        XsArray const* aArray = (XsArray const*) a;
        XsArray const* bArray = (XsArray const*) b;
 
        if (aArray == bArray)
                return 0;
 
        if (aArray->m_size != bArray->m_size)
                return (aArray->m_size < bArray->m_size) ? -1 : 1;
 
        assert(predicate);
        // we could theoretically only check the sizes and ignore the element-comparison in thisArray case
        for (i = 0; i < aArray->m_size; ++i) // loop over all elements of the lists
        {
                int r = predicate(elemAtX(aArray->m_data, i, aArray), elemAtX(bArray->m_data, i, bArray));
                if (r)
                        return r;
        }
        return 0;
}
 
int XsArray_compareSet(void const* a, void const* b)
{
        XsSize n, m;
        XsArray const* aArray = (XsArray const*) a;
        XsArray const* bArray = (XsArray const*) b;
 
        if (aArray == bArray)
                return 0;
 
        if (aArray->m_size != bArray->m_size)
                return (aArray->m_size < bArray->m_size) ? -1 : 1;
 
        for (n = 0; n < aArray->m_size; ++n) // loop over all elements of list aArray
        {
                int found = 0;
                for (m = 0; m < bArray->m_size; ++m)    // loop over all elements of list bArray
                {
                        if (aArray->m_descriptor->itemCompare(elemAtX(aArray->m_data, n, aArray), elemAtX(bArray->m_data, m, bArray)) == 0)
                        {
                                found = 1;
                                break;
                        }
                }
                if (!found)
                        return -1;
        }
        return 0;
}
 
ptrdiff_t XsArray_find(void const* thisPtr, void const* needle)
{
        XsSize i;
        XsArray const* thisArray = (XsArray const*) thisPtr;
 
        assert(thisArray->m_descriptor->itemCompare);
        // we could theoretically only check the sizes and ignore the element-comparison in thisArray case
        for (i = 0; i < thisArray->m_size; ++i) // loop over all elements of the lists
                if (!thisArray->m_descriptor->itemCompare(elemAt(thisArray->m_data, i), needle))
                        return (ptrdiff_t) i;
        return -1;
}
 
ptrdiff_t XsArray_findPredicate(void const* thisPtr, void const* needle, XsArrayItemCompareFunc predicate)
{
        XsSize i;
        XsArray const* thisArray = (XsArray const*) thisPtr;
 
        assert(predicate);
        // we could theoretically only check the sizes and ignore the element-comparison in thisArray case
        for (i = 0; i < thisArray->m_size; ++i) // loop over all elements of the lists
                if (!predicate(elemAt(thisArray->m_data, i), needle))
                        return (ptrdiff_t) i;
        return -1;
}
 
void const* XsArray_at(void const* thisPtr, XsSize index)
{
        XsArray const* thisArray = (XsArray const*) thisPtr;
        if (index >= thisArray->m_size)
                return 0;
        return elemAt(thisArray->m_data, index);
}
 
void* XsArray_atIndex(void* thisPtr, XsSize index)
{
        XsArray* thisArray = (XsArray*) thisPtr;
        if (index >= thisArray->m_size)
                return 0;
        return elemAt(thisArray->m_data, index);
}
 
void XsArray_removeDuplicates(void* thisPtr)
{
        XsSize i, j;
        XsArray* thisArray = (XsArray*) thisPtr;
        if (thisArray->m_size > 1)
        {
                for (i = 0; i < thisArray->m_size - 1; ++i)
                {
                        for (j = thisArray->m_size - 1; j > i; --j)
                        {
                                if (!thisArray->m_descriptor->itemCompare(elemAt(thisArray->m_data, i), elemAt(thisArray->m_data, j)))
                                        XsArray_erase(thisPtr, j, 1);
                        }
                }
        }
}
 
void XsArray_removeDuplicatesPredicate(void* thisPtr, XsArrayItemCompareFunc predicate)
{
        XsSize i, j;
        XsArray* thisArray = (XsArray*) thisPtr;
        if (thisArray->m_size > 1)
        {
                for (i = 0; i < thisArray->m_size - 1; ++i)
                {
                        for (j = thisArray->m_size - 1; j > i; --j)
                        {
                                if (!predicate(elemAt(thisArray->m_data, i), elemAt(thisArray->m_data, j)))
                                        XsArray_erase(thisPtr, j, 1);
                        }
                }
        }
}
 
int XsArray_empty(void const* thisPtr)
{
        XsArray const* thisArray = (XsArray const*) thisPtr;
        return (thisArray->m_size == 0) || (thisArray->m_data == 0) || (thisArray->m_flags & XSDF_Empty);
}
 
void XsArray_rawCopy(void* to, void const* from, XsSize count, XsSize iSize)
{
        memcpy(to, from, count * iSize);
}
 
void XsArray_sort(void* thisPtr)
{
        XsArray* thisArray = (XsArray*) thisPtr;
        qsort(thisArray->m_data, thisArray->m_size, thisArray->m_descriptor->itemSize, thisArray->m_descriptor->itemCompare);
}
 
void XsArray_reverse(void* thisPtr)
{
        XsSize i, half;
        XsArray* thisArray = (XsArray*) thisPtr;
        half = thisArray->m_size >> 1;
        for (i = 0; i < half; ++i)
                thisArray->m_descriptor->itemSwap(elemAt(thisArray->m_data, i), elemAt(thisArray->m_data, (thisArray->m_size - 1) - i));
}