vector.c

Go to the documentation of this file.

/*  *************************************************************************************
    Copyright (c) 2021, Lowell D. Thomas
    All rights reserved.
    
    This file is part of APG Version 7.0.
    APG Version 7.0 may be used under the terms of the BSD 2-Clause License.
    
    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.
    
    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 HOLDER 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.
    
*   *************************************************************************************/
#include "./lib.h"
 
static const void* s_vpMagicNumber = (void*)"vector";
 
#if defined APG_VEC_STATS
 
typedef struct {
    const void* vpValidate; 
    exception* spException;
    void* vpMem;         
    char* cpData;           
    aint uiElementSize;     
    aint uiReserved;        
    aint uiUsed;            
    aint uiGrownCount;      
    aint uiGrownElements;   
    aint uiPushed;          
    aint uiPopped;          
    aint uiMaxUsed;         
} vector;
static void vStatsPush(vector* spCtx, aint uiPushed);
static void vStatsPop(vector* spCtx, aint uiPopped);
static void vStatsGrow(vector* spCtx, aint uiAddedElements);
 
#define STATS_PUSH(s, p) vStatsPush((s), (p))
 
#define STATS_POP(s, p) vStatsPop((s), (p))
 
#define STATS_GROW(s, n) vStatsGrow((s), (n))
#else
typedef struct {
    const void* vpValidate;       // must be equal to s_vpMagicNumber
    exception* spException;
    void* vpMem;         // context to the underlying memory component
    char* cpData;           // pointer to the vector's data buffer
    aint uiElementSize;     // number of bytes in one element
    aint uiReserved;        // number of elements that have been reserved on the buffer
    aint uiUsed;            // number of the reserved elements that have been used
} vector;
#define STATS_PUSH(s, p)
#define STATS_POP(s, p)
#define STATS_GROW(s, n)
#endif
 
static void vGrow(vector* spCtx, aint uiElements);
 
void* vpVecCtor(void* vpMem, aint uiElementSize, aint uiInitialAlloc) {
    vector* spCtx;
    exception* spEx = NULL;
    while(APG_TRUE){
        if (!bMemValidate(vpMem)) {
            vExContext();
            break;
        }
        spEx = spMemException(vpMem);
        if (uiElementSize == 0) {
            XTHROW(spEx, "element size cannot be zero");
            break;
        }
        if (uiInitialAlloc == 0) {
            XTHROW(spEx, "initial allocation cannot be zero");
            break;
        }
        spCtx = (vector*) vpMemAlloc(vpMem, sizeof(vector));
        memset((void*) spCtx, 0, sizeof(*spCtx));
        spCtx->cpData = (char*) vpMemAlloc(vpMem, (uiElementSize * uiInitialAlloc));
        spCtx->uiElementSize = uiElementSize;
        spCtx->uiReserved = uiInitialAlloc;
        spCtx->uiUsed = 0;
 
        // success
        spCtx->vpMem = vpMem;
        spCtx->spException = spEx;
        spCtx->vpValidate = s_vpMagicNumber;
        return (void*) spCtx;
    }
    return NULL;
}
 
void vVecDtor(void* vpCtx) {
    vector* spCtx = (vector*) vpCtx;
    if (vpCtx) {
        if (spCtx->vpValidate == s_vpMagicNumber) {
            void* vpMem = spCtx->vpMem;
            vMemFree(vpMem, (void*) spCtx->cpData);
            memset(vpCtx, 0, sizeof(vector));
            vMemFree(vpMem, vpCtx);
        }else{
            vExContext();
        }
    }
}
 
abool bVecValidate(void* vpCtx){
    vector* spCtx = (vector*) vpCtx;
    if (vpCtx && (spCtx->vpValidate == s_vpMagicNumber)) {
        return APG_TRUE;
    }
    return APG_FALSE;
}
 
void* vpVecPush(void* vpCtx, void* vpElement) {
    vector* spCtx = (vector*) vpCtx;
    if(vpCtx && (spCtx->vpValidate == s_vpMagicNumber)){
        void* vpReturn = NULL;
        if (spCtx->uiUsed >= spCtx->uiReserved) {
            vGrow(spCtx, 1);
        }
        vpReturn = (void*) (spCtx->cpData + (spCtx->uiUsed * spCtx->uiElementSize));
        if (vpElement) {
            // copy new element to vector
            memcpy(vpReturn, vpElement, spCtx->uiElementSize);
        }
        spCtx->uiUsed += 1;
        STATS_PUSH(spCtx, 1);
        return vpReturn;
    }
    vExContext();
    return NULL;
}
 
void* vpVecPushn(void* vpCtx, void* vpElement, aint uiCount) {
    vector* spCtx = (vector*) vpCtx;
    if(vpCtx && (spCtx->vpValidate == s_vpMagicNumber)){
        if (uiCount) {
            void* vpReturn = NULL;
            if ((spCtx->uiUsed + uiCount) > spCtx->uiReserved) {
                vGrow(spCtx, uiCount);
            }
            vpReturn = (void*) (spCtx->cpData + (spCtx->uiUsed * spCtx->uiElementSize));
            if (vpElement) {
                memcpy(vpReturn, vpElement, uiCount * spCtx->uiElementSize);
            }
            spCtx->uiUsed += uiCount;
            STATS_PUSH(spCtx, uiCount);
            return vpReturn;
        }
        XTHROW(spCtx->spException, "attempt to push 0 elements on the vector");
        return NULL;
    }
    vExContext();
    return NULL;
}
 
void* vpVecPop(void* vpCtx) {
    vector* spCtx = (vector*) vpCtx;
    if(vpCtx && (spCtx->vpValidate == s_vpMagicNumber)){
        if (spCtx->uiUsed) {
            spCtx->uiUsed -= 1;
            STATS_POP(spCtx, 1);
            return ((void*) (spCtx->cpData + (spCtx->uiUsed * spCtx->uiElementSize)));
        }
        return NULL;
    }
    vExContext();
    return NULL;
}
 
void* vpVecPopn(void* vpCtx, aint uiCount) {
    vector* spCtx = (vector*) vpCtx;
    if(vpCtx && (spCtx->vpValidate == s_vpMagicNumber)){
        if ((uiCount > 0) && (spCtx->uiUsed > 0)) {
            if (spCtx->uiUsed > uiCount) {
                // pop uiCount elements
                spCtx->uiUsed -= uiCount;
                STATS_POP(spCtx, uiCount);
                return (void*) (spCtx->cpData + (spCtx->uiUsed * spCtx->uiElementSize));
            }
            // pop all remaining elements
            STATS_POP(spCtx, spCtx->uiUsed);
            spCtx->uiUsed = 0;
            return spCtx->cpData;
        }
        return NULL;
    }
    vExContext();
    return NULL;
}
 
void* vpVecPopi(void* vpCtx, aint uiIndex) {
    vector* spCtx = (vector*) vpCtx;
    if(vpCtx && (spCtx->vpValidate == s_vpMagicNumber)){
        if(uiIndex >= spCtx->uiUsed){
            return NULL;
        }
        aint uiCount = spCtx->uiUsed - uiIndex; // will always be positive
        spCtx->uiUsed -= uiCount;
        STATS_POP(spCtx, uiCount);
        return ((void*) (spCtx->cpData + (uiIndex * spCtx->uiElementSize)));
    }
    vExContext();
    return NULL;
}
 
void* vpVecFirst(void* vpCtx) {
    vector* spCtx = (vector*) vpCtx;
    if(vpCtx && (spCtx->vpValidate == s_vpMagicNumber)){
        if (spCtx->uiUsed) {
            return ((void*) spCtx->cpData);
        }
        return NULL;
    }
    vExContext();
    return NULL;
}
 
void* vpVecLast(void* vpCtx) {
    vector* spCtx = (vector*) vpCtx;
    if(vpCtx && (spCtx->vpValidate == s_vpMagicNumber)){
        if (spCtx->uiUsed) {
            return ((void*) (spCtx->cpData + (spCtx->uiUsed - 1) * spCtx->uiElementSize));
        }
        return NULL;
    }
    vExContext();
    return NULL;
}
 
void* vpVecAt(void* vpCtx, aint uiIndex) {
    vector* spCtx = (vector*) vpCtx;
    if(vpCtx && (spCtx->vpValidate == s_vpMagicNumber)){
        if(spCtx->uiUsed == 0){
            return NULL;
        }
        if(uiIndex == 0){
            return ((void*) spCtx->cpData);
        }
        if(uiIndex < spCtx->uiUsed){
            return ((void*) (spCtx->cpData + (uiIndex * spCtx->uiElementSize)));
        }
        return NULL;
    }
    vExContext();
    return NULL;
}
 
aint uiVecLen(void* vpCtx){
    vector* spCtx = (vector*) vpCtx;
    if(vpCtx && (spCtx->vpValidate == s_vpMagicNumber)){
        return spCtx->uiUsed;
    }
    vExContext();
    return 0;
}
 
void* vpVecBuffer(void* vpCtx){
    vector* spCtx = (vector*) vpCtx;
    if(vpCtx && (spCtx->vpValidate == s_vpMagicNumber)){
        return (void*)spCtx->cpData;
    }
    vExContext();
    return NULL;
}
 
void vVecClear(void* vpCtx) {
    vector* spCtx = (vector*) vpCtx;
    if(vpCtx){
        if(spCtx->vpValidate == s_vpMagicNumber){
            STATS_POP(spCtx, spCtx->uiUsed);
            spCtx->uiUsed = 0;
        }else{
            vExContext();
        }
    }
}
 
static void vGrow(vector* spCtx, aint uiElements) {
    aint uiNewReserved;
    uiNewReserved = 2 * (spCtx->uiReserved + uiElements);
    spCtx->cpData = (char*)vpMemRealloc(spCtx->vpMem, (void*) spCtx->cpData, (spCtx->uiElementSize * uiNewReserved));
 
//    XTHROW(spCtx->spException, "pretending that the memory reallocation failed while growing the vector");
 
    STATS_GROW(spCtx, (uiNewReserved - spCtx->uiReserved));
    spCtx->uiReserved = uiNewReserved;
}
 
#if defined APG_VEC_STATS
 
void vVecStats(void* vpCtx, vec_stats* spStats){
    vector* spCtx = (vector*) vpCtx;
    if(spStats){
        spStats->uiElementSize = spCtx->uiElementSize;
        spStats->uiReserved = spCtx->uiReserved;
        spStats->uiUsed = spCtx->uiUsed;
        spStats->uiMaxUsed = spCtx->uiMaxUsed;
        spStats->uiPopped = spCtx->uiPopped;
        spStats->uiPushed = spCtx->uiPushed;
        spStats->uiGrownCount = spCtx->uiGrownCount;
        spStats->uiGrownElements = spCtx->uiGrownElements;
        spStats->uiGrownBytes = spCtx->uiElementSize * spCtx->uiGrownElements;
        spStats->uiReservedBytes = spCtx->uiElementSize * spCtx->uiReserved;
        spStats->uiOriginalBytes = spStats->uiReservedBytes - spStats->uiGrownBytes;
        spStats->uiOriginalElements = spStats->uiOriginalBytes / spCtx->uiElementSize;
        spStats->uiUsedBytes = spCtx->uiElementSize * spCtx->uiUsed;
        spStats->uiMaxUsedBytes = spCtx->uiElementSize * spCtx->uiMaxUsed;
    }
}
void vStatsPush(vector* spCtx, aint uiCount){
    spCtx->uiPushed += uiCount;
    if(spCtx->uiUsed > spCtx->uiMaxUsed){
        spCtx->uiMaxUsed = spCtx->uiUsed;
    }
}
void vStatsPop(vector* spCtx, aint uiCount){
    spCtx->uiPopped += uiCount;
}
void vStatsGrow(vector* spCtx, aint uiAddedElements){
    spCtx->uiGrownCount += 1;
    spCtx->uiGrownElements += uiAddedElements;
}
#else
 
void vVecStats(void* vpCtx, vec_stats* spStats){
    if(spStats){
        memset((void*) spStats, 0, sizeof(vec_stats));
    }
}
#endif