vector.c

Go to the documentation of this file.

#include "vector.h"
#include <stdlib.h>
#include <string.h>
#include <assert.h>

// first, the private functions:

#ifdef _MSC_VER
__inline
#else
inline
#endif
static Bool Resize(Vector *vec, unsigned int newSize) {
    void *newArray;
    // try to allocate a new array and check for failure
    if ((newArray = realloc(vec->array, vec->itemSize * newSize)) == NULL) {
        // no memory
        return FALSE;
    }
    // keep the new array
    vec->array = newArray;
    // store the new size
    vec->size = newSize;
    // indicate success
    return TRUE;
}

#define Enlarge(vec, inc) \
    Resize(vec, \
    ((inc) > (vec)->size << 1) ? (inc) + ((vec)->size << 1) : (vec)->size << 1)

#define Shrink(vec) \
    if (((vec)->size > (vec)->minSize) && \
        (((vec)->size >> 2) >= (vec)->items)) \
        Resize(vec, \
        ((vec)->size >> 1 > (vec)->minSize) ? (vec)->size >> 1 : (vec)->minSize)

static void HeapMoveDown(Vector *vec, unsigned int index, void *temp) {
    void *child;
    unsigned int childInd;
    
    // requries use of the less than operation, so it must already be set
    assert(vec->lessOp != NULL);
    // loop through heap
    for (; (childInd = HEAP_CHILD_INDEX(index)) <= vec->items; index = childInd) {
        child = &(((char*)vec->array)[childInd * vec->itemSize]);
        if ((childInd < (vec->items - 1)) &&
        (*(vec->lessOp))(vec->itemSize + (char*)child, child)) {
            childInd++;
            child = (char*)child + vec->itemSize;
        }
        if ((*(vec->lessOp))(child, temp)) {
            memcpy(&((char *)vec->array)[index * vec->itemSize], child,
            vec->itemSize);
        }
        else
            break;
    }
    // found the spot to put the item temp
    memcpy(&(((char *)vec->array)[index * vec->itemSize]), temp, vec->itemSize);
}


// the public functions. These are commented in the header file.

Bool VectorInit(Vector *vec, unsigned int initSize) {
    // the vector to initialize must exist
    assert(vec != NULL);
    // the initial size must be at least the minimum size
    assert(initSize >= vec->minSize);
    // allocate the array
    if ((vec->array = malloc(vec->itemSize * initSize)) == NULL) {
        // failed to create the array
        return FALSE;
    }
    #ifndef NDEBUG
    // make it easier to check that all data is initialized before being used
    // by putting crud in the array
    memset(vec->array, 0xCD, vec->itemSize * initSize);
    #endif
    // initialize the new vector's members
    vec->size  = initSize;
    vec->items = 0;
    // success!
    return TRUE;
}

void VectorDestroy(Vector *vec) {
    // check for items in the array and for a destructor function
    if (vec->destructOp && (vec->items > 0)) {
        void *item;
        unsigned int loop = vec->items;
        // loop through the items
        for (item = vec->array; loop > 0; loop--,
        item = (char*)item + vec->itemSize) {
            // call the destructor
            (*(vec->destructOp))(item);
        }
    }
    // deallocate the array
    if (vec->array != NULL) {
        free(vec->array);
    }
    #ifndef NDEBUG
    // put crud in vec to help catch improper use of vec after being destroyed
    memset(vec, 0xAB, sizeof(Vector));
    #endif
}

Bool VectorCopy(Vector *target, Vector *source){
    void *array;
    // attempt to allocate memory for the new copy
    if ((array = malloc(source->itemSize * source->size)) == NULL) {
        // couldn't get the memory
        return FALSE;
    }
    // copy the vector data
    *target = *source;
    // set the array
    target->array = array;
    // copy the items
    memcpy(target->array, source->array, source->itemSize * source->items);
    // success!
    return TRUE;
}

void VectorClear(Vector *vec) {
    // check for items in the array and for a destructor function
    if (vec->destructOp && (vec->items > 0)) {
        void *item;
        unsigned int loop = vec->items;
        // loop through the items
        for (item = vec->array; loop > 0; loop--,
        item = (char*)item + vec->itemSize) {
            // call the destructor
            (*(vec->destructOp))(item);
        }
    }
    // clear the item count
    vec->items = 0;
    // reduce the vector size if needed
    Shrink(vec);
}

void *VectorAdd(Vector *vec) {
    // check array size
    if (vec->items == vec->size) {
        // enlarge the array to take the new item
        if (!Resize(vec, vec->size << 1)) {
            // failure!
            return NULL;
        }
    }
    // make room for an item and send it back
    return &(((char *)vec->array)[vec->items++ * vec->itemSize]);
}

void *VectorPush(Vector *vec, void *item) {
    void *newItem;
    // check array size
    if (vec->items == vec->size) {
        // enlarge the array to take the new item
        if (!Resize(vec, vec->size << 1)) {
            // failure!
            return NULL;
        }
    }
    // add the item
    memcpy(newItem = &(((char *)vec->array)[vec->items++ * vec->itemSize]),
     item, vec->itemSize);
    // send it back
    return newItem;
}

void *VectorHeapPush(Vector *vec, void *item) {
    void *parent;
    unsigned int index = vec->items++, parentInd;
    // requries use of the less than operation, so it must already be set
    assert(vec->lessOp != NULL);
    // check array size
    if (vec->items == vec->size) {
        // enlarge the array to take the new item
        if (!Resize(vec, vec->size << 1)) {
            // failure!
            return NULL;
        }
    }
    for (; parentInd = HEAP_PARENT_INDEX(index),
    index && (*(vec->lessOp))(item,
    (parent = &((char *)vec->array)[parentInd * vec->itemSize]));
    index = parentInd) {
        // move item up
        memcpy(&(((char *)vec->array)[index * vec->itemSize]), parent,
        vec->itemSize);
    }
    // copy in the new item
    memcpy(parent = &(((char *)vec->array)[index * vec->itemSize]), item,
    vec->itemSize);
    return parent;
}

void VectorPop(Vector *vec) {
    // decrease size and check for removal from empty vector
    if (vec->items > 0) {
        vec->items--;
        // call the destructor
        if (vec->destructOp) {
            (*(vec->destructOp))
            (&(((char *)vec->array)[vec->items * vec->itemSize]));
        }
        // reduce the vector size if needed
        Shrink(vec);
    }
}

void VectorHeapPop(Vector *vec) {
    // decrease size and check for removal from empty vector
    if (vec->items > 0) {
        vec->items--;
        // call the destructor
        if (vec->destructOp) {
            (*(vec->destructOp))(vec->array);
        }
        // take the last item, now outside the heap, and move it through the
        //  heap to find it's new place
        HeapMoveDown(vec, 0,
        &(((char *)vec->array)[vec->items * vec->itemSize]));
        // reduce the vector size if needed
        Shrink(vec);
    }
}

void VectorHeapSort(Vector *vec) {
    void *lastItem;
    unsigned int items;
    #ifdef _MSC_VER
    // quick kludge fix for original code not working with MS VC++
    char tempVal[1024];
    assert(vec->itemSize <= 1024);
    #else
    char tempVal[vec->itemSize];
    #endif
    // check for items to sort
    if (vec->items == 0) return;
    // order the vector into a heap
    VectorMakeHeap(vec);
    // keep a local copy of the number of items
    items = vec->items--; // the first item is already sorted
    lastItem = &(((char *)vec->array)[vec->items * vec->itemSize]);
    // loop until sorted
    for (; vec->items < 0xFFFFFFFF;  vec->items--,
    lastItem = (char*)lastItem -  vec->itemSize) {
        // copy the last item into the temp spot
        memcpy(tempVal, lastItem, vec->itemSize);
        // copy the first item into the last
        memcpy(lastItem, vec->array, vec->itemSize);
        // put the temp item back into the heap
        HeapMoveDown(vec, 0, tempVal);
    }
    // restore the vector's item count
    vec->items = items;
}

void *VectorInsertMany(Vector *vec, unsigned int index, unsigned int count) {
    void *dest;
    unsigned int newSize = vec->items + count;
    // assure the given index is valid
    assert(index <= vec->items);
    // check array size
    if (newSize > vec->size) {
        // enlarge the array to take the new item
        if (!Enlarge(vec, newSize)) {
            // failure!
            return NULL;
        }
    }
    // get a pointer to the sport where the new items will go
    dest = &(((char *)vec->array)[index * vec->itemSize]);
    // copy everything
    memmove((char*)dest + count * vec->itemSize, dest,
     vec->itemSize * (vec->items - index));
    // set the new number of items
    vec->items = newSize;
    #ifndef NDEBUG
    // put crud in the new item
    memset(dest, 0xCD, vec->itemSize * count);
    #endif
    // send back the first item
    return dest;
}

void VectorRemoveMany(Vector *vec, unsigned int index, unsigned int count) {
    void *trg, *item;
    unsigned int loop;
    // assure the given index is valid
    assert(index < vec->items);
    // cannot remove more items than what are already in the vector
    assert(count <= (vec->items - index));
    // get a pointer to the item to be removed
    item = trg = &(((char *)vec->array)[index * vec->itemSize]);
    // check for a destructor
    if (vec->destructOp) {
        // loop through all the items to be removed
        for (loop = count; loop > 0; loop--, item = (char*)item + vec->itemSize) {
            // call the item's destructor
            (*vec->destructOp)(trg);
        }
    }
    else {
        // compute the address of the first item following what is removed
        item = (char*)trg + count * vec->itemSize;
    }
    // move the remaining items that follow the removed items forward in the
    // array
    memmove(trg, item, vec->itemSize * (vec->items - (index + count)));
    // update the number of items
    vec->items -= count;
    // reduce the vector size if needed
    Shrink(vec);
}

void VectorMakeHeap(Vector *vec) {
    unsigned int loop;
    void *item;
    #ifdef _MSC_VER
    // quick kludge fix for original code not working with MS VC++
    char tempVal[1024];
    assert(vec->itemSize <= 1024);
    #else
    char tempVal[vec->itemSize];
    #endif
    // check for items to heapify
    if (vec->items == 0) return;
    loop = vec->items >> 1;
    item = &(((char *)vec->array)[loop * vec->itemSize]);
    // loop through the array
    for (; loop < 0xFFFFFFFF; loop--, item = (char*)item - vec->itemSize) {
        // make a temp copy of the data at m_pArray[uLoop]
        memcpy(tempVal, item, vec->itemSize);
        // make this branch of the tree a heap
        HeapMoveDown(vec, loop, tempVal);
    }
}

Bool VectorReserve(Vector *vec, unsigned int size) {
    // see if the requested size is larger than the current size
    if (size > vec->size) {
        // Enlarge the array
        return Resize(vec, size);
    }
    // the array is already large enough
    return TRUE;
}

void GenericPointerFree(void *item) {
    if (*(char**)item != NULL) {
        free(*((void **)item));
    }
}

---