Developer CD Series 2000 April: Mac OS SDK/Dev.CD Apr 00 SDK1.toast/Development Kits/Mac OS/Text Encoding Converter 1.5/Sample Code/UnicodeHub/LDynamicArray.cp

Text File | 1998-06-15 | 14.3 KB | 525 lines | [TEXT/CWIE]

// ===========================================================================
//    LDynamicArray.cp           ©1994-1996 Metrowerks Inc. All rights reserved.
// ===========================================================================
//
//    Description:
//        An ordered collection of fixed-size items. Positions in the Array are
//        one-based--the first item is at index 1.
//
//    Note about index values:
//        Index values are signed, 32-bit integers. Index 0 is not an
//        item in the Array and is used to indicate an nonexistant item.
//
//    Note about items:
//        When specifying an item, you pass a pointer to the item data
//        as a parameter. The Array stores a copy of the item data.

#ifdef PowerPlant_PCH
#include PowerPlant_PCH
#endif

#include "LDynamicArray.h"
#include <UMemoryMgr.h>

#pragma mark === Constructors / Destructor ===

// ---------------------------------------------------------------------------
//        • LDynamicArray
// ---------------------------------------------------------------------------
//    Construct an empty Array of items of the specified size, pre-allocating
//    space for a certain number of items
//
//    Errors:
//        Construction can fail if there is not enough memory to create
//        the Handle for storing the items

LDynamicArray::LDynamicArray(
    Uint32    inItemSize,
    Uint32    inSpaces)
{
    mItemSize = inItemSize;
    mItemCount = 0;
    mAllocation = inSpaces;
    mLockCount = 0;

    mItemsH = nil;
    if (inSpaces > 0) {
        mItemsH = ::NewHandle(inSpaces * inItemSize);
        ThrowIfMemFail_(mItemsH);
    }
}


// ---------------------------------------------------------------------------
//        • LDynamicArray
// ---------------------------------------------------------------------------
//    Construct an Array of items using an existing Handle.
//
//    Caller is responsible for ensuring that inItemsHandle is a valid
//    Handle of Pointer values
//
//    The Array assumes ownership of inItemsHandle, meaning that the Array
//    is responsible for disposing of it.

LDynamicArray::LDynamicArray(
    Uint32    inItemSize,
    Handle    inItemsHandle)
{
    mItemSize = inItemSize;
    mItemsH = inItemsHandle;
    mLockCount = 0;
    mItemCount = ::GetHandleSize(inItemsHandle) / inItemSize;
    ::HUnlock(mItemsH);                    // Maintain proper lock count
    mAllocation = mItemCount;
}


// ---------------------------------------------------------------------------
//        • ~LDynamicArray
// ---------------------------------------------------------------------------
//    Destructor

LDynamicArray::~LDynamicArray()
{
    if (mItemsH != nil) {
        ::DisposeHandle(mItemsH);
    }
}


// ---------------------------------------------------------------------------
//        • ValidIndex
// ---------------------------------------------------------------------------
//    Return whether an index is valid (between 1 and the number of items)
//    for the VariableArray.
//
//    If inIndex is the special flag index_Last, the index's value
//    is changed to the actual index of the last item.

Boolean
LDynamicArray::ValidIndex(
    ArrayIndexT        &inIndex) const
{
    if (inIndex == index_Last) {
        inIndex = mItemCount;
    }
    return (inIndex > 0) && (inIndex <= mItemCount);
}


// ---------------------------------------------------------------------------
//        • InsertItemsAt
// ---------------------------------------------------------------------------
//    Insert items at the specified position in an Array
//
//    inCount items are inserted into the Array starting at inAtIndex.
//    All items are set to the same value, as specified by inItem.
//
//    If inAtIndex is greater than the number of items in the Array,
//    then the items are inserted after the last item.
//
//    Errors:
//        Insertion can fail if there is not enough memory to store
//        the new items

void
LDynamicArray::InsertItemsAt(
    Uint32            inCount,
    ArrayIndexT        inAtIndex,
    const void        *inItem)
{
    if (inCount < 1) {                // Exit if nothing to insert
        return;
    }

    if (mLockCount > 0) {
        SignalPStr_("\pCan't insert into a locked Array");
        return;
    }
                                    // Grow storage
    Uint32    newCount = mItemCount + inCount;
    if (newCount > mAllocation) {
        AllocateSpace(newCount - mAllocation + 1);
    }

    Uint32    saveCount = mItemCount;
    mItemCount = newCount;

    if (inAtIndex > saveCount) {    // Check upper bound
        inAtIndex = saveCount + 1;    // Insert at end of Array

    } else {                        // Insert at start or middle of Array
        if (inAtIndex < 1) {        // Check lower bound
            inAtIndex = 1;            // Insert at start of Array
        }

        if (saveCount > 0) {         // Move existing items to make
                                    //   room for new ones
            ShiftItems(inAtIndex, saveCount, inAtIndex + inCount);
        }
    }
                                    // Inserted items are all set
                                    //   to the same value, if specified
    if (inItem != nil) {
        ArrayIndexT    index = inAtIndex;
        do {
            PokeItem(index, inItem);
        } while (++index < inAtIndex + inCount);
    }
}


// ---------------------------------------------------------------------------
//        • RemoveItemsAt
// ---------------------------------------------------------------------------
//    Remove items from an Array starting at a specified position
//
//    Does nothing if inAtIndex is out of range. Checks if inCount would remove
//    items past the end of the Array, and adjusts it accordingly to remove
//    the items from inAtIndex to the end of the Array. That means you can pass
//    a large number to remove the items from inAtIndex to the end of the Array.

void
LDynamicArray::RemoveItemsAt(
    Uint32        inCount,
    ArrayIndexT    inAtIndex)
{
    if (inCount < 1) {                // Nothing to do
        return;
    }

    if (mLockCount > 0) {
        SignalPStr_("\pCan't remove from a locked Array");
        return;
    }

    if (ValidIndex(inAtIndex)) {

        if (inAtIndex + inCount <= mItemCount) {
                                    // Removing items from the middle
                                    // Shift down items that are above
                                    //   the ones being removed
            ShiftItems(inAtIndex + inCount, mItemCount, inAtIndex);

        } else {                    // Removing items at the end
                                    // Limit inCount to the number of items
                                    //   from inWhere to the end
            inCount = mItemCount - inAtIndex + 1;
        }

        mItemCount -= inCount;        // Reduce storage
        mAllocation = mItemCount;
        ::SetHandleSize(mItemsH, mItemCount * mItemSize);
    }
}


// ---------------------------------------------------------------------------
//        • FetchItemAt
// ---------------------------------------------------------------------------
//    Pass back the Item at the specified index
//
//    Returns true if an item exists at inIndex (and sets outItem)
//    Returns false if inIndex is out of range (and leaves outItem unchanged)

Boolean
LDynamicArray::FetchItemAt(
    ArrayIndexT    inAtIndex,
    void        *outItem) const        // Pointer to the item
{
    Boolean    itemExists = false;

    if (ValidIndex(inAtIndex)) {
        PeekItem(inAtIndex, outItem);
        itemExists = true;
    }

    return itemExists;
}


// ---------------------------------------------------------------------------
//        • AssignItemsAt
// ---------------------------------------------------------------------------
//    Assign the same value to Items starting at the specified index
//
//    inValue is a pointer to the item data. The Array makes and stores
//    a copy of the item data.
//
//    Does nothing if inIndex is out of range

void
LDynamicArray::AssignItemsAt(
    Uint32            inCount,
    ArrayIndexT        inAtIndex,
    const void        *inValue)
{
    if (ValidIndex(inAtIndex)) {

        ArrayIndexT        lastIndex = inAtIndex + inCount - 1;
        if (lastIndex > mItemCount) {
            lastIndex = mItemCount;    // Don't go past end of Array
        }

        for (ArrayIndexT i = inAtIndex; i <= lastIndex; i++) {
            PokeItem(i, inValue);
        }
    }
}


// ---------------------------------------------------------------------------
//        • SetItemAt
// ---------------------------------------------------------------------------
//    Sets the value of the Item at the specified index
//
//    inItem is a pointer to the item data. The Array makes and stores
//    a copy of the item data.
//
//    Does nothing if inIndex is out of range

void
LDynamicArray::SetItemAt(
    ArrayIndexT        inAtIndex,
    const void        *inItem)            // Pointer to the item
{
    if (ValidIndex(inAtIndex)) {
        PokeItem(inAtIndex, inItem);
    }
}


// ---------------------------------------------------------------------------
//        • SwapItems
// ---------------------------------------------------------------------------
//    Swap the values of the Items at the specified indices
//
//    Does nothing if either index is out of range

void
LDynamicArray::SwapItems(
    ArrayIndexT    inIndexA,
    ArrayIndexT    inIndexB)
{
                                    // Do nothing if either index is out
                                    //   of range
    if (ValidIndex(inIndexA) && ValidIndex(inIndexB)) {

                                     // Store copy of item A
        StPointerBlock    itemACopy(mItemSize);
        PeekItem(inIndexA, itemACopy.mPtr);

        PokeItem(inIndexA, GetItemPtr(inIndexB));    // A = B
        PokeItem(inIndexB, itemACopy.mPtr);            // B = Copy of A
    }
}


// ---------------------------------------------------------------------------
//        • MoveItem
// ---------------------------------------------------------------------------
//    Move an item from one position to another in an Array. The net result
//    is the same as removing the item and inserting at a new position.
//
//    Does nothing if either index is out of range
//
//    Example:
//                BEFORE                        AFTER MoveItem(2, 6)
//        index    1  2  3  4  5  6            1  2  3  4  5  6
//        item    a  b  c  d  e  f            a  c  d  e  b  f

void
LDynamicArray::MoveItem(
    ArrayIndexT    inFromIndex,
    ArrayIndexT    inToIndex)
{
                                    // Do nothing if either index is out
                                    //   of range or if "from" and "to"
                                    //   indices are the same
    if ( ValidIndex(inFromIndex) && ValidIndex(inToIndex) &&
         (inFromIndex != inToIndex) ) {

                                    // Store copy of item to move
        StPointerBlock    itemToMove(mItemSize);
        PeekItem(inFromIndex, itemToMove.mPtr);

        if (inFromIndex < inToIndex) {
                                    // Move item to a higher index
                                    // Shift items between "from" and "to"
                                    //   down one spot
            ShiftItems(inFromIndex + 1, inToIndex, inFromIndex);
        } else {
                                    // Move item to a lower index
                                    // Shift items between "to" and "from"
                                    //   up one spot
            ShiftItems(inToIndex, inFromIndex - 1, inToIndex + 1);
        }

                                    // Store item at new position
        PokeItem(inToIndex, itemToMove.mPtr);
    }
}


// ---------------------------------------------------------------------------
//        • FetchIndexOf
// ---------------------------------------------------------------------------
//    Returns the index of the specified item within the Array
//
//    Returns index_Bad if the item is not in the Array

ArrayIndexT
LDynamicArray::FetchIndexOf(
    const void    *inItem) const        // Pointer to the item to find
{
    if (mItemCount == 0) {            // Array is empty
        return index_Bad;
    }

    ArrayIndexT    findIndex = 0;        // Search from beginning of Array

    if (mItemSize == sizeof(void*)) {
                                    // Special case for Array of Pointers
        void*    findMe = *((void**) inItem);
        void*    *itemPtr = (void**) *mItemsH;
        while (++findIndex <= mItemCount) {
            if (findMe == *itemPtr++) {
                break;
            }
        }

    } else {                        // Items of any size
        StHandleLocker    lock(mItemsH);
        char    *itemPtr = *mItemsH;
        while (++findIndex <= mItemCount) {
            if (BlocksAreEqual(inItem, itemPtr, mItemSize)) {
                break;
            }
            itemPtr += mItemSize;
        }
    }

    if (findIndex > mItemCount) {    // Search stopped because we reached the
        findIndex = index_Bad;        //   end without finding the item
    }

    return findIndex;
}


// ---------------------------------------------------------------------------
//        • Remove
// ---------------------------------------------------------------------------
//    Remove an item from an Array

void
LDynamicArray::Remove(
    const void    *inItem)                // Pointer to the item to remove
{
    ArrayIndexT    index = FetchIndexOf(inItem);
    if (index != index_Bad) {
        RemoveItemsAt(1, index);
    }
}


// ---------------------------------------------------------------------------
//        • Lock
// ---------------------------------------------------------------------------
//    Lock the Handle that stores the data for the items in the Array
//
//    Class maintains a lock count, so each call to Lock() should be
//    balanced by a corresponding call to Unlock()

void
LDynamicArray::Lock()
{
    mLockCount++;
    if ((mLockCount == 1) && (mItemsH != nil)) {
                                        // First lock,
        ::HLock(mItemsH);                //   so really lock the Handle
    }
}


// ---------------------------------------------------------------------------
//        • Unlock
// ---------------------------------------------------------------------------
//    Unlock the Handle that stores the data for the items in the Array
//
//    Class maintains a lock count, so each call to Lock() should be
//    balanced by a corresponding call to Unlock()

void
LDynamicArray::Unlock()
{
    SignalIf_(mLockCount == 0);            // Too many Unlocks

    if ((--mLockCount == 0) && (mItemsH != nil)) {
                                        // Last unlock
        ::HUnlock(mItemsH);                //   so really unlock the Handle
    }
}


// ---------------------------------------------------------------------------
//        • GetItemPtr
// ---------------------------------------------------------------------------
//    Returns a pointer to the start of an Items data within the internal
//    storage Handle.
//
//    WARNING: The return pointer references information inside a
//    relocatable block. This pointer will become invalid if the
//    Handle block moves.

void*
LDynamicArray::GetItemPtr(
    Int32    inAtIndex) const
{
    return (*mItemsH + (inAtIndex - 1) * mItemSize);
}


// ---------------------------------------------------------------------------
//        • AllocateSpace
// ---------------------------------------------------------------------------
//    Allocate space for more items

void
LDynamicArray::AllocateSpace(
    Uint32    inSpaces)
{
    Uint32    newSize = (mAllocation + inSpaces) * mItemSize;

    if (mItemsH == nil) {
        mItemsH = ::NewHandle(newSize);
    } else {
        ::SetHandleSize(mItemsH, newSize);
    }
    ThrowIfMemError_();

    mAllocation += inSpaces;
}


// ---------------------------------------------------------------------------
//        • ShiftItems
// ---------------------------------------------------------------------------
//    Moves items within the Handle used for internal storage
//        Moves items in the range inStartPos to inEndPos (inclusive) so
//        that those items start at index inDestPos, overwriting any items
//        that were there.
//
//    For internal use. Performs no bounds checking.

void
LDynamicArray::ShiftItems(
    ArrayIndexT    inStartPos,
    ArrayIndexT    inEndPos,
    ArrayIndexT    inDestPos)
{
    ::BlockMoveData(*mItemsH + (inStartPos - 1) * mItemSize,
                    *mItemsH + (inDestPos - 1) * mItemSize,
                    (inEndPos - inStartPos + 1) * mItemSize);
}