/**********************************************************************/
/** Microsoft LAN Manager **/
/** Copyright(c) Microsoft Corp., 1987-1990 **/
/**********************************************************************/
/*
ARRAY.HXX
LM 3.0 Generic array class module
This module contains type generic implementations of static
and dynamic arrays that provide bounds checking.
FILE HISTORY:
Johnl 02-Aug-90 Created
Johnl 05-Dec-90 Changed Size to QuerySize, changed Cassert to
UIASSERT
RustanL 05-Dec-90 Added ARRAY_LIST
RustanL 06-Dec-90 Split DECLARE_ARRAY_OF into itself and
DEFINE_ARRAY_OF
RustanL 07-Dec-90 Added several enhancements to ARRAY class
RustanL 31-Dec-90 Removed 'inline' from ARRAY_LIST::Remove
*/
#ifndef _ARRAY_HXX_
#define _ARRAY_HXX_
/*************************************************************************
NAME: ARRAY
SYNOPSIS: Generic array implementation that provides bounds checking
INTERFACE:
DECLARE_ARRAY_OF( ) - Declares array package (interface) for type
DEFINE_ARRAY_OF() - Defines array package (implementation) for type
ARRAY_OF() - Declares an array object of type "type"
ARRAY_type( ) - Constructor, takes a suggested size of array,
and attempts to allocate the array of that
size. If the allocation fails, the size is
set to 0, but the array is still in a valid
state. In fact, the array will always be in
a valid state.
Initial allocations of size 0 are always
guaranteed to succeed. Hence, the client
can always check if QueryCount returns a
different value than was passed to the
constructor in order to determine the
space actually allocated. (Please note that
checking QueryCount for being is, in general,
not enough to determine if the allocation
was successful.)
An alternate version of the constructor accepts
an existing vector of objects. This version can
either use that vector as its own storage,
resizing as needed - in which case the creator
must surrender all rights to the presumably
dynamically allocated vector - or else treats
it as nonresizable. The default is never to
resize such, since the vector might not come
from freestore, or else may be shared with
another object.
~ARRAY_type() - Deletes the array
operator[] - Gives random access to array with bounds checking
(asserts out if you go out of bounds)
operator= - Copies one array to another (note, they must be of
the same size).
QueryCount() - Returns the count of elements of this array.
Resize() - Resizes the array to the number of elements
specified by size. (NOTE: the array only
reallocates memory if the size changes by more
than ARRAY_RESIZE_MEM bytes or when the new
size exceeds the current.) Returns TRUE if
successful. If FALSE is returned, then a memory
error occurred, and the array remains untouched.
Resize is guaranteed to work whenever the new
size does not exceed the previous.
CAVEATS:
NOTES:
CODEWORK. The Resize method could be made much more efficient if it
used a proper buffer object that could be realloced, rather than
having to allocate a brand new chunk of memory, call the
constructor on each item in this array, copy items into the new
array, call the destructor on every previously allocated item,
and finally deallocate the previous chunk of memory. This should
become a new class (BUFFER_ARRAY_OF or the like).
HISTORY:
Johnl 15-Jul-1990 Created
RustanL 06-Dec-1990 Created DEFINE_ARRAY_OF from DECLARE_ARRAY_OF
RustanL 07-Dec-1990 Added several enhancements
beng 14-Aug-1991 Added vector-adopt mode; renamed QCount;
op= relaxed; enhanced further
Yi-HsinS 28-Oct-1992 Add a flag to Resize indicating not to
downsize
**************************************************************************/
#define ARRAY_OF(type) ARRAY_##type
#define ARRAY_RESIZE_MEM 4096 // If the array loses more than 4096 bytes
// on a resize, then go ahead and reallocate
// memory etc., else just change _carray
/************************************************************/
#define DECL_ARRAY_OF(type,dec) \
\
class dec ARRAY_OF(type) \
{ \
private: \
type *_parray; \
UINT _carray; \
UINT _carrayAlloc; \
BOOL _fMayResize; \
\
BOOL WithinRange( INT iIndex ) const; \
\
public: \
ARRAY_OF(type)( UINT cElem ); \
ARRAY_OF(type)( type* ptype, UINT ctype, \
BOOL fMayResize = FALSE); \
\
~ARRAY_OF(type)(); \
\
type& operator[]( INT iIndex ) const \
{ \
ASSERT( WithinRange(iIndex) ); \
return _parray[ iIndex ]; \
} \
\
INT QueryCount() const \
{ \
return _carray; \
} \
\
ARRAY_OF(type) & operator=( ARRAY_OF(type)& a ); \
\
BOOL Resize( INT cElemNew, BOOL fDownSize = TRUE ); \
};
/************************************************************************/
#define DEFINE_ARRAY_OF( type ) \
\
ARRAY_OF(type)::ARRAY_OF(type)( UINT cElem ) \
: _parray(NULL), \
_carray(0), \
_carrayAlloc(0), \
_fMayResize(TRUE) \
{ \
if ( cElem > 0 ) \
{ \
_parray = new type[ cElem ]; \
} \
\
if ( _parray != NULL ) \
{ \
_carray = _carrayAlloc = cElem; \
} \
} \
\
\
ARRAY_OF(type)::ARRAY_OF(type)(type *px, UINT cx, BOOL fMayResize) \
: _parray(px), \
_carray(cx), \
_carrayAlloc(cx), \
_fMayResize(fMayResize) \
{ \
/* nothing doing. */ \
} \
\
\
ARRAY_OF(type)::~ARRAY_OF(type)() \
{ \
if ( _fMayResize && _carrayAlloc > 0 ) \
delete [ _carrayAlloc ] _parray; \
} \
\
\
ARRAY_OF(type) & ARRAY_OF(type)::operator=( ARRAY_OF(type)& a ) \
{ \
ASSERT(_carrayAlloc <= (UINT) a.QueryCount()); \
\
INT iLim = ( a.QueryCount() <= (INT) _carrayAlloc) \
? a.QueryCount() \
: (INT) _carrayAlloc; \
\
for ( INT i = 0; i < iLim; i++ ) \
_parray[i] = a._parray[i]; \
\
_carray = iLim; \
return *this; \
} \
\
\
BOOL ARRAY_OF(type)::WithinRange( INT iIndex ) const \
{ \
return ((iIndex >= 0) && (iIndex < (INT) _carray) && (_carray >= 0)); \
} \
\
\
BOOL ARRAY_OF(type)::Resize( INT cElemNew, BOOL fDownSize ) \
{ \
ASSERT( cElemNew >= 0 ); \
\
/* Prevent resizing owner-alloc arrays */ \
if (!_fMayResize) \
return FALSE; \
\
if ( ( cElemNew > (INT) _carrayAlloc ) \
|| ( fDownSize && \
(( _carrayAlloc - cElemNew )*sizeof(type) > ARRAY_RESIZE_MEM))\
) \
{ \
type * parrayNew; \
if ( cElemNew > 0 ) \
{ \
parrayNew = new type[ cElemNew ]; \
if ( parrayNew == NULL ) \
{ \
/* Memory failure */ \
if ( cElemNew > (INT) _carrayAlloc ) \
{ \
/* The array has been not been modified */ \
return FALSE; \
} \
else \
{ \
/* Guarantee: resizing the array for */ \
/* new sizes not exceeding the current */ \
/* will always succeed. */ \
_carray = cElemNew; \
return TRUE; \
} \
} \
\
/* Copy each existing item */ \
/* that will fit into the new array */ \
for ( INT i = 0 ; \
i < ( (INT)_carray < cElemNew ? (INT)_carray : cElemNew); \
i++ ) \
{ \
parrayNew[i] = _parray[i]; \
} \
\
} \
else \
{ \
parrayNew = NULL; \
} \
\
if ( _carrayAlloc > 0 ) \
{ \
delete[ _carrayAlloc ] _parray; \
} \
else \
{ \
ASSERT( _parray == NULL ); \
} \
_parray = parrayNew; \
_carray = _carrayAlloc = cElemNew; \
} \
else \
{ \
/* (Array does not report errors.) New size is less */ \
/* than current size, but not so much less that we want */ \
/* to realloc to save memory. */ \
_carray = cElemNew; \
} \
\
return TRUE; \
}
/*************************************************************************
NAME: ARRAY_LIST
SYNOPSIS: Generic unordered array collection implementation
which provides bounds checking, easy ways to add/remove
items, etc. In some respects, this collection can be
thought of as an efficient singly linked list, for singly
linked lists which don't change a lot dynamically. Hence
the name "array list".
INTERFACE:
DECLARE_ARRAY_LIST_OF( )
Declares array list package for type 'type'
DEFINE_ARRAY_LIST_OF()
Defines array list package for type 'type', excluding
the Sort and BinarySearch methods (see Notes below)
DEFINE_EXT_ARRAY_LIST_OF()
Defines the entire array list package for type 'type'
WARNING: If you use EXT_ARRAY_LIST, the Compare()
method for the parameter class must be _CRTAPI1.
Otherwise the underlying qsort() or BinarySearch() will fail.
ARRAY_LIST_OF()
Declares an array list object of type 'type'
ARRAY_LIST_type()
Constructor. Takes an optional parameter, nInitialSize,
which specifies the initial allocation size of the array
list in number of array list items. Note, any call to
Add or AddIdemp may cause the allocated size to be
enlarged, and any call to Remove may reduce the allocated
size. These allocations, however, are all kept away
from the user, except for the nInitialSize parameter to
the constructor.
Add()
Adds an item to the array list. Note, this will
not sort the list.
AddIdemp()
Idempotently adds an item to the array list. Note,
this will not sort the list.
Remove()
Removes an item from the array list. This may
result in shrinking the allocated size of the array,
and will not sort the list.
Find()
Finds the first occurrence of a given item in the array
list. Since the list is not assumed to be sorted, a
linear search is performed.
Clear()
Clears the array list of all of items items
operator[]()
Same as for the ARRAY class
operator=()
Same as for the ARRAY class
QueryCount()
Same as for the ARRAY class
Sort()
Sorts the array (see Notes below for Sort definition)
BinarySearch()
Works like Find, but performs a binary search rather
than a linear. This method assumes that the list is
sorted. (See Notes below for BinarySearch definition.)
CAVEATS:
Add and Remove will alter the ordering of the list in ways
unexpected. See the implementation of Remove for details.
The Sort routine calls qsort, which may swap the items.
Although qsort is given a pointer to the Compare function,
it does not have access to, or knowledge of, the assignment
operator; rather, it performs a straight binary copy of each
item. Hence, all types which require a custom assignment
operation should not use the Sort method.
CODEWORK. The debug version of BinarySearch could assert that
the array list is sorted. This, however, would require adding
an operator=( ARRAY ) and an operator=( ARRAY_LIST ) to this
class, since these would function differently with an additional
member keeping track of whether the array list is sorted.
CODEWORK. We have a C++ heapsort, which we could emend to
recognize type::Compare.
NOTES:
The array list declaration and definitions automatically
take care of declaring and defining, respectively, the
superclass ARRAY or the same type, since ARRAY_LIST inherits
from ARRAY.
The Find, Sort, and BinarySearch functions require the 'type'
class to define a Compare method.
The retail version of this class does not claim nor attempt to
keep track of if the list is sorted. Thus, it is always up to
the client to keep track of this. For the same reason, Remove
and AddIdemp always call Find, rather than BinarySearch. The
debug version could assert out if BinarySearch is called when
the list is not sorted (see Caveats above).
Since the Sort and BinarySearch definitions methods depend on
definitions in stdlib.h and search.h, the definitions for these
methods are only provided in the extended definition macro.
This way, clients who do not wish to make use of Sort and
BinarySearch, need not include stdlib.h and search.h.
HISTORY:
RustanL 5-Dec-1990 Created
beng 14-Aug-1991 Remove inlines; changes in ARRAY
Yi-HsinS 28-Oct-1992 Add a flag to Resize indicating not to
downsize
**************************************************************************/
#define ARRAY_LIST_OF(type) ARRAY_LIST_##type
/************************************************************/
#define DECL_ARRAY_LIST_OF(type,dec) \
\
DECL_ARRAY_OF(type,dec); \
\
class dec ARRAY_LIST_OF( type ) : public ARRAY_OF( type ) \
{ \
public: \
ARRAY_LIST_OF( type )( INT cAlloc = 0 ); \
\
BOOL Add( const type & t ); \
BOOL AddIdemp( const type & t ); \
BOOL Remove( const type & t ); \
INT Find( const type & t ) const; \
VOID Clear(); \
\
VOID Sort(); \
INT BinarySearch( const type & t ) const; \
static int _CRTAPI1 SortFunc ( \
const void * p1, const void * p2 ) ; \
};
/********************************************************************/
#define DEFINE_ARRAY_LIST_OF( type ) \
\
DEFINE_ARRAY_OF( type ); \
\
ARRAY_LIST_OF( type )::ARRAY_LIST_OF( type )( INT cAlloc ) \
: ARRAY_OF(type) ( cAlloc ) \
{ \
Resize(0, FALSE); /* do not downsize */ \
} \
\
BOOL ARRAY_LIST_OF( type )::Add( const type & t ) \
{ \
INT n = QueryCount(); \
\
if ( ! Resize( n + 1 )) \
return FALSE; /* Out of memory */ \
\
(*this)[n] = t; \
return TRUE; \
} \
\
\
BOOL ARRAY_LIST_OF( type )::AddIdemp( const type & t ) \
{ \
return (( Find( t ) >= 0 ) || Add( t )); \
} \
\
\
BOOL ARRAY_LIST_OF( type )::Remove( const type & t ) \
{ \
INT i = Find( t ); \
if ( i < 0 ) \
return FALSE; /* item not found */ \
\
/* Since Find was able to find the item, the array list */ \
/* cannot be empty. */ \
ASSERT(QueryCount() > 0); \
INT n = QueryCount() - 1; \
if ( i < n ) \
(*this)[i] = (*this)[n]; \
\
/* Reducing the size of an array always succeeds */ \
REQUIRE( Resize( n )); \
\
return TRUE; \
} \
\
\
INT ARRAY_LIST_OF( type )::Find( const type & t ) const \
{ \
for ( INT i = 0; i < QueryCount(); i++ ) \
{ \
if ( t.Compare( &(operator[]( i ))) == 0 ) \
return i; \
} \
\
return -1; /* not found */ \
} \
\
\
VOID ARRAY_LIST_OF( type )::Clear() \
{ \
/* Resizing to size 0 is guaranteed always to work. */ \
REQUIRE( Resize( 0 )); \
}
/********************************************************************/
#define DEFINE_EXT_ARRAY_LIST_OF( type ) \
\
DEFINE_ARRAY_LIST_OF( type ); \
\
int _CRTAPI1 ARRAY_LIST_OF( type )::SortFunc ( \
const void * p1, const void * p2 ) \
{ \
const type * pt1 = (const type *) p1 ; \
const type * pt2 = (const type *) p2 ; \
return pt1->Compare( pt2 ) ; \
} \
\
VOID ARRAY_LIST_OF( type )::Sort() \
{ \
qsort( &((*this)[0]), QueryCount(), sizeof( type ), \
ARRAY_LIST_OF( type )::SortFunc ); \
} \
\
\
INT ARRAY_LIST_OF( type )::BinarySearch( const type & t ) const \
{ \
type * ptBase = &((*this)[0]); \
type * pt = (type *)bsearch( (VOID *)&t, \
(VOID *)ptBase, \
QueryCount(), \
sizeof( type ), \
ARRAY_LIST_OF( type)::SortFunc ); \
\
return (( pt == NULL ) ? -1 : pt - ptBase ); \
}
// Helper macros for code preservation
#define DECLARE_ARRAY_OF(type) \
DECL_ARRAY_OF(type,DLL_TEMPLATE)
#define DECLARE_ARRAY_LIST_OF(type) \
DECL_ARRAY_LIST_OF(type,DLL_TEMPLATE)
#endif //_ARRAY_HXX_