DynArray.cpp

Go to the documentation of this file.

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Project: uLib - User mode library.
// Module: DynArray -- Dynamic arrays in C++
// Author: Copyright (c) Love Nystrom 1999
// License: NNOSL (BSD descendant, see NNOSL.txt in the base directory).
// Credits: Someone at Borland International (original Pascal class).
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

#include <uLib/DynArray.h>
#include <uLib/MemFunc.h>

BEGIN_NAMESPACE( uLib )

// Protected identifiers preceded with one underscore.
// Private identifiers preceded with two underscores.

void* DynArray::__alloc( size_t Bytes ) {
    return mem_Alloc( Bytes );
    }

void* DynArray::__realloc( void* pBlk, size_t Bytes ) {
    if (!pBlk) return mem_Alloc( Bytes );
    else return mem_Realloc( pBlk, Bytes );
    }

void* DynArray::__free( void* pBlk ) {
    return mem_Free( pBlk ); // I.e: pFoo = __free( pFoo );
    }

#ifdef _MSC_VER
#pragma warning( disable: 4355 ) // 'this' in base member initializer list
#endif

DynArray::DynArray( DWORD dwSize, WORD wDelta )
: Count(_count), Size(_size), Items(*this) // Self-ref to access operator[] via a pointer.
{
    _count = 0;
    _items = NULL;
    Init( dwSize, wDelta );
}

#ifdef _MSC_VER
#pragma warning( default: 4355 )
#endif

DynArray::~DynArray() // virtual
{
    Done();
}

void DynArray::Init( DWORD dwSize, WORD wDelta )
{
    Done(); // Dispose old items (if any).
    dwSize = dwSize ? ROUND_UP( dwSize, wDelta ) : wDelta;

    _count = 0;
    _delta = wDelta;
    #if USE_DYNARRAY_LIMIT
    _size = (dwSize <= MAX_DYNITEM) ? dwSize : MAX_DYNITEM;
    #else
    _size = dwSize;
    #endif
    _items = _size ? (PVOID*)__alloc( _size*sizeof(PVOID) ) : NULL;
}

void DynArray::Done()
{
    if (_count) DeleteAll();
    if (_items) _items = (PVOID*)__free( _items );
}

PVOID DynArray::Insert( PVOID Item )
{
    #if USE_DYNARRAY_LIMIT
    if( Item == NULL || _count == MAX_DYNITEM )
    #else
    if (Item == NULL)
    #endif
        return NULL; // failure, ret NULL

    PVOID tmp = _items;
    _count++;
    if (_count > _size) { // Only place that deals with reallocation
        _size += _delta;
      #if USE_DYNARRAY_LIMIT
        if (_size > MAX_DYNITEM) _size = MAX_DYNITEM;
      #endif
        size_t nbytes = _size*sizeof(PVOID);
        tmp = _items ? __realloc( _items,nbytes ) : __alloc( nbytes );
        if (tmp) {                  // SUCCESS
            _items = (PVOID*) tmp;  // set items PVOID, and..
        } else {                    // FAILURE
            tmp = NULL;             // signal failure by returning NULL
            _size -= _delta;        // reset previous
            _count--;               // reset previous
        }
    }
    if (tmp) {
        _items[_count-1] = Item;
        tmp = Item; // signal success by returning Item
    }
    return tmp;
}

PVOID DynArray::InsertAt( DWORD Index,PVOID Item )
{
    // Begin by inserting Item at end of collection (to adjust count etc)

    PVOID p = DynArray::Insert( Item ); // Force use of base class method
    if ((Index >= (_count-1)) || (!p))
        return p;

    // Index not at end, so make a hole at index and set p at index position

    size_t  nbytes = (_count-Index-1)*sizeof(PVOID);
    memmove( &_items[Index+1], &_items[Index], nbytes ); // shove upward
    _items[Index] = p;
    return p;
}

PVOID DynArray::Push( PVOID Item ) // Insert Item into stack/fifo
{
    return Insert( Item );
}

PVOID DynArray::Pull( void ) // Push/Pull = FIFO action
{
    return Remove( (DWORD) 0 );
}

PVOID DynArray::Pop( void ) // Push/Pop = stack action
{
    return Remove( _count-1 );
}

void DynArray::DeleteItem( PVOID& Item )
{
    mem_Free( Item );
    Item = NULL;
}

void DynArray::Delete( PVOID& Item )
{
    LONG index = IndexOf( Item );
    if (index >= 0) Delete( index );
}

void DynArray::Delete( DWORD Index )
{
    if (Index >= _count) return;
    DeleteItem( _items[Index] );
    Remove( Index );
}

void DynArray::DeleteAll( void )
{
    while( _count ) Delete( _count-1 );
}

PVOID DynArray::Remove( PVOID Item )
{
    LONG index = IndexOf( Item );
    return (index >= 0) ? Remove( index ) : NULL;
}

PVOID DynArray::Remove( DWORD Index )
{
    if (Index >= _count) return NULL;
    PVOID item = At( Index );
    _count--;
    DWORD bytes = (_count-Index)*sizeof(PVOID);
    if (bytes) memmove( &_items[Index], &_items[Index+1], bytes ); // Contract
    _items[_count] = NULL;
    return item;
}

LONG DynArray::IndexOf( PVOID Item ) const
{
    if( Item != NULL )
        for( DWORD i=0; i<_count; i++ ) // This can get inefficient on big counts
        if (_items[i] == Item) return LONG( i ); // but there is no alternative.
    return -1;
}

PVOID DynArray::At( DWORD Index ) const
{
    if (Index >= _count) return NULL;
    return _items[Index];
}

PVOID DynArray::FirstThat( DYN_ITEMFUNC Match, PVOID userData ) const
{
    for( DWORD i=0; i<_count; i++ )
        if (Match( _items[i],userData ))
        return _items[i];
    return NULL;
}

PVOID DynArray::LastThat( DYN_ITEMFUNC Match, PVOID userData ) const
{
    for( DWORD i=_count; i>0; i-- )
        if (Match( _items[i-1],userData ))
        return _items[i-1];
    return NULL;
}

bool DynArray::ForEach( DYN_ITEMFUNC Action, PVOID userData ) const
{
    for( DWORD i=0; i<_count; i++ )
        if( !Action( _items[i],userData ))
        return false;
    return true;
}

// ------------------------------------------------------------------------

SortDynArray::SortDynArray( DWORD dwSize, WORD wDelta )
: DynArray( dwSize, wDelta )
{
    Duplicates = false;
}

PVOID SortDynArray::KeyOf( PVOID Item )
{
    return Item;
}

short SortDynArray::Compare( PVOID Item1, PVOID Item2 )
{
    // Base method assumes items are strings, and collates per default C(++).
    if (!Item1) return 1; else if (!Item2) return -1;
    return _tcscmp( (TSTR)Item1, (TSTR)Item2 );
}

bool SortDynArray::Search( PVOID Key, DWORD& Index )
{
    // Linear search.. Inefficient as hell, but works if the array is not too big.
    // PONDER: Implement iterative binary search here..?
    for( Index=0; Index < _count; Index++ ) {
        PVOID itemKey = _items[ Index ];
        if (itemKey) itemKey = KeyOf( itemKey );
        if (!itemKey) break;
        int cmp = Compare( itemKey, Key );
        if (cmp == 0) return true;      // Item was found, return it's index
        else if (cmp > 0) return false; // Item would have been here if it existed
    }
    // No key equal or bigger than Key was found, Index equals Count
    return false;
}

PVOID SortDynArray::Insert( PVOID Item )
{
    if (!Item) return NULL;
    DWORD ix;
    if (!Search( KeyOf(Item),ix )) return InsertAt( ix, Item );
    else if (Duplicates) return InsertAt( ix+1, Item );
    else return NULL;
}

END_NAMESPACE( uLib )
// EOF