dynarray.h

浙江大学的悟空嵌入式系统模拟器

///////////////////////////////////////////////////////////////////////////////
// Name:        dynarray.h
// Purpose:     auto-resizable (i.e. dynamic) array support
// Author:      Vadim Zeitlin
// Modified by:
// Created:     12.09.97
// RCS-ID:      $Id: dynarray.h,v 1.1 2005/03/16 06:48:57 kehc Exp $
// Copyright:   (c) 1998 Vadim Zeitlin <[e-mail]>
// Licence:     wxWindows license
///////////////////////////////////////////////////////////////////////////////

#ifndef   _DYNARRAY_H
#define   _DYNARRAY_H

#if defined(__GNUG__) && !defined(__APPLE__)
#pragma interface "dynarray.h"
#endif

#include "wx/defs.h"

/*
  This header defines the dynamic arrays and object arrays (i.e. arrays which
  own their elements). Dynamic means that the arrays grow automatically as
  needed.

  These macros are ugly (especially if you look in the sources ;-), but they
  allow us to define "template" classes without actually using templates and so
  this works with all compilers (and may be also much faster to compile even
  with a compiler which does support templates). The arrays defined with these
  macros are type-safe.

  Range checking is performed in debug build for both arrays and objarrays but
  not in release build - so using an invalid index will just lead to a crash
  then.

  Note about memory usage: arrays never shrink automatically (although you may
  use Shrink() function explicitly), they only grow, so loading 10 millions in
  an array only to delete them 2 lines below might be a bad idea if the array
  object is not going to be destroyed soon. However, as it does free memory
  when destroyed, it is ok if the array is a local variable.
 */

// ----------------------------------------------------------------------------
// constants
// ----------------------------------------------------------------------------

/*
   The initial size by which an array grows when an element is added default
   value avoids allocate one or two bytes when the array is created which is
   rather inefficient
*/
#define WX_ARRAY_DEFAULT_INITIAL_SIZE    (16)

// ----------------------------------------------------------------------------
// types
// ----------------------------------------------------------------------------

/*
    Callback compare function for quick sort.

    It must return negative value, 0 or positive value if the first item is
    less than, equal to or greater than the second one.
 */
extern "C"
{
typedef int (wxCMPFUNC_CONV *CMPFUNC)(const void* pItem1, const void* pItem2);
}

// ----------------------------------------------------------------------------
// Base class managing data having size of type 'long' (not used directly)
//
// NB: for efficiency this often used class has no virtual functions (hence no
//     virtual table), even dtor is *not* virtual. If used as expected it
//     won't create any problems because ARRAYs from DEFINE_ARRAY have no dtor
//     at all, so it's not too important if it's not called (this happens when
//     you cast "SomeArray *" as "BaseArray *" and then delete it)
// ----------------------------------------------------------------------------

#define  _WX_DECLARE_BASEARRAY(T, name, classexp)                   \
classexp name                                                       \
{                                                                   \
public:                                                             \
  name();                                                           \
  name(const name& array);                                          \
  name& operator=(const name& src);                                 \
  ~name();                                                          \
                                                                    \
  void Empty() { m_nCount = 0; }                                    \
  void Clear();                                                     \
  void Alloc(size_t uiSize);                                        \
  void Shrink();                                                    \
                                                                    \
  size_t  GetCount() const { return m_nCount; }                     \
  bool  IsEmpty() const { return m_nCount == 0; }                   \
  size_t  Count() const { return m_nCount; }                        \
                                                                    \
  typedef T base_type;                                              \
protected:                                                          \
  T& Item(size_t uiIndex) const                                     \
    { wxASSERT( uiIndex < m_nCount ); return m_pItems[uiIndex]; }   \
  T& operator[](size_t uiIndex) const { return Item(uiIndex); }     \
                                                                    \
  int Index(T lItem, bool bFromEnd = FALSE) const;                  \
  int Index(T lItem, CMPFUNC fnCompare) const;                      \
  size_t IndexForInsert(T lItem, CMPFUNC fnCompare) const;          \
  void Add(T lItem, size_t nInsert = 1);                            \
  void Add(T lItem, CMPFUNC fnCompare);                             \
  void Insert(T lItem, size_t uiIndex, size_t nInsert = 1);         \
  void Remove(T lItem);                                             \
  void RemoveAt(size_t uiIndex, size_t nRemove = 1);                \
                                                                    \
  void Sort(CMPFUNC fnCompare);                                     \
                                                                    \
private:                                                            \
                                                                    \
  void    Grow(size_t nIncrement = 0);                              \
                                                                    \
  size_t  m_nSize,                                                  \
          m_nCount;                                                 \
                                                                    \
  T      *m_pItems;                                                 \
}

// ============================================================================
// The private helper macros containing the core of the array classes
// ============================================================================

// Implementation notes:
//
// JACS: Salford C++ doesn't like 'var->operator=' syntax, as in:
//          { ((wxBaseArray *)this)->operator=((const wxBaseArray&)src);
//       so using a temporary variable instead.
//
// The classes need a (even trivial) ~name() to link under Mac X
//
// _WX_ERROR_REMOVE is needed to resolve the name conflict between the wxT()
// macro and T typedef: we can't use wxT() inside WX_DEFINE_ARRAY!

#define _WX_ERROR_REMOVE wxT("removing inexisting element in wxArray::Remove")

// ----------------------------------------------------------------------------
// _WX_DEFINE_TYPEARRAY: array for simple types
// ----------------------------------------------------------------------------

#define  _WX_DEFINE_TYPEARRAY(T, name, base, classexp)                \
wxCOMPILE_TIME_ASSERT2(sizeof(T) <= sizeof(base::base_type),          \
                       TypeTooBigToBeStoredIn##base,                  \
                       name);                                         \
typedef int (CMPFUNC_CONV *CMPFUNC##T)(T *pItem1, T *pItem2);         \
classexp name : public base                                           \
{                                                                     \
public:                                                               \
  name() { }                                                          \
  ~name() { }                                                         \
                                                                      \
  name& operator=(const name& src)                                    \
    { base* temp = (base*) this;                                      \
      (*temp) = ((const base&)src);                                   \
      return *this; }                                                 \
                                                                      \
  T& operator[](size_t uiIndex) const                                 \
    { return (T&)(base::Item(uiIndex)); }                             \
  T& Item(size_t uiIndex) const                                       \
    { return (T&)(base::Item(uiIndex)); }                             \
  T& Last() const                                                     \
    { return (T&)(base::Item(Count() - 1)); }                         \
                                                                      \
  int Index(T Item, bool bFromEnd = FALSE) const                      \
    { return base::Index(Item, bFromEnd); }                           \
                                                                      \
  void Add(T Item, size_t nInsert = 1)                                \
    { base::Add(Item, nInsert); }                                     \
  void Insert(T Item, size_t uiIndex, size_t nInsert = 1)             \
    { base::Insert(Item, uiIndex, nInsert) ; }                        \
                                                                      \
  void RemoveAt(size_t uiIndex, size_t nRemove = 1)                   \
    { base::RemoveAt(uiIndex, nRemove); }                             \
  void Remove(T Item)                                                 \
    { int iIndex = Index(Item);                                       \
      wxCHECK2_MSG( iIndex != wxNOT_FOUND, return,                    \
         _WX_ERROR_REMOVE);                                           \
      base::RemoveAt((size_t)iIndex); }                               \
                                                                      \
  void Sort(CMPFUNC##T fCmp) { base::Sort((CMPFUNC)fCmp); }           \
}

// ----------------------------------------------------------------------------
// _WX_DEFINE_SORTED_TYPEARRAY: sorted array for simple data types
//    cannot handle types with size greater than pointer because of sorting
// ----------------------------------------------------------------------------

#define _WX_DEFINE_SORTED_TYPEARRAY(T, name, base, defcomp, classexp) \
wxCOMPILE_TIME_ASSERT2(sizeof(T) <= sizeof(void *),                   \
                       TypeTooBigToBeStoredInSorted##base,            \
                       name);                                         \
typedef int (CMPFUNC_CONV *SCMPFUNC##T)(T pItem1, T pItem2);          \
classexp name : public base                                           \
{                                                                     \
public:                                                               \
  name(SCMPFUNC##T fn defcomp) { m_fnCompare = fn; }                  \
                                                                      \
  name& operator=(const name& src)                                    \
    { base* temp = (base*) this;                                      \
      (*temp) = ((const base&)src);                                   \
      m_fnCompare = src.m_fnCompare;                                  \
      return *this; }                                                 \
                                                                      \
  T& operator[](size_t uiIndex) const                                 \
    { return (T&)(base::Item(uiIndex)); }                             \