src/common/dynarray.cpp

   1 ///////////////////////////////////////////////////////////////////////////////
   2 // Name:        dynarray.cpp
   3 // Purpose:     implementation of wxBaseArray class
   4 // Author:      Vadim Zeitlin
   5 // Modified by:
   6 // Created:     12.09.97
   7 // RCS-ID:      $Id$
   8 // Copyright:   (c) 1998 Vadim Zeitlin <zeitlin@dptmaths.ens-cachan.fr>
   9 // Licence:     wxWindows license
  10 ///////////////////////////////////////////////////////////////////////////////
  11
  12 // ============================================================================
  13 // headers
  14 // ============================================================================
  15
  16 #ifdef __GNUG__
  17 #pragma implementation "dynarray.h"
  18 #endif
  19
  20 #include  "wx/wxprec.h"
  21
  22 #ifdef __BORLANDC__
  23   #pragma hdrstop
  24 #endif
  25
  26 #include "wx/dynarray.h"
  27 #include "wx/intl.h"
  28
  29 #include <stdlib.h>
  30 #include <string.h> // for memmove
  31
  32 #ifndef max
  33   #define max(a, b)   (((a) > (b)) ? (a) : (b))
  34 #endif
  35
  36 // we cast the value to long from which we cast it to void * in IndexForInsert:
  37 // this can't work if the pointers are not big enough
  38 wxCOMPILE_TIME_ASSERT( sizeof(long) <= sizeof(void *),
  39                        wxArraySizeOfPtrLessSizeOfLong ); // < 32 symbols
  40
  41 // ============================================================================
  42 // constants
  43 // ============================================================================
  44
  45 // size increment = max(50% of current size, ARRAY_MAXSIZE_INCREMENT)
  46 #define   ARRAY_MAXSIZE_INCREMENT    4096
  47
  48 // ============================================================================
  49 // implementation
  50 // ============================================================================
  51
  52 // ----------------------------------------------------------------------------
  53 // wxBaseArray - dynamic array of 'T's
  54 // ----------------------------------------------------------------------------
  55
  56 #define _WX_DEFINE_BASEARRAY(T, name)                                       \
  57 /* ctor */                                                                  \
  58 name::name()                                                                \
  59 {                                                                           \
  60   m_nSize  =                                                                \
  61   m_nCount = 0;                                                             \
  62   m_pItems = (T *)NULL;                                                     \
  63 }                                                                           \
  64                                                                             \
  65 /* copy ctor */                                                             \
  66 name::name(const name& src)                                                 \
  67 {                                                                           \
  68   m_nSize  = /* not src.m_nSize to save memory */                           \
  69   m_nCount = src.m_nCount;                                                  \
  70                                                                             \
  71   if ( m_nSize != 0 ) {                                                     \
  72       m_pItems = new T[m_nSize];                                            \
  73       /* only copy if allocation succeeded */                               \
  74       if ( m_pItems ) {                                                     \
  75           memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T));               \
  76       }                                                                     \
  77       else {                                                                \
  78           m_nSize = 0;                                                      \
  79       }                                                                     \
  80   }                                                                         \
  81   else                                                                      \
  82     m_pItems = (T *) NULL;                                                  \
  83 }                                                                           \
  84                                                                             \
  85 /* assignment operator */                                                   \
  86 name& name::operator=(const name& src)                                      \
  87 {                                                                           \
  88   wxDELETEA(m_pItems);                                                      \
  89                                                                             \
  90   m_nSize  = /* not src.m_nSize to save memory */                           \
  91   m_nCount = src.m_nCount;                                                  \
  92                                                                             \
  93   if ( m_nSize != 0 ){                                                      \
  94       m_pItems = new T[m_nSize];                                            \
  95       /* only copy if allocation succeeded */                               \
  96       if ( m_pItems ) {                                                     \
  97           memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T));               \
  98       }                                                                     \
  99       else {                                                                \
 100           m_nSize = 0;                                                      \
 101       }                                                                     \
 102   }                                                                         \
 103   else                                                                      \
 104     m_pItems = (T *) NULL;                                                  \
 105                                                                             \
 106   return *this;                                                             \
 107 }                                                                           \
 108                                                                             \
 109 /* grow the array */                                                        \
 110 void name::Grow(size_t nIncrement)                                          \
 111 {                                                                           \
 112   /* only do it if no more place */                                         \
 113   if( m_nCount == m_nSize ) {                                               \
 114     if( m_nSize == 0 ) {                                                    \
 115         /* was empty, alloc some memory */                                  \
 116       m_pItems = new T[WX_ARRAY_DEFAULT_INITIAL_SIZE];                      \
 117       /* only grow if allocation succeeded */                               \
 118       if ( m_pItems ) {                                                     \
 119           m_nSize = WX_ARRAY_DEFAULT_INITIAL_SIZE;                          \
 120       }                                                                     \
 121     }                                                                       \
 122     else                                                                    \
 123     {                                                                       \
 124       /* add at least 50% but not too much */                               \
 125       size_t ndefIncrement = m_nSize < WX_ARRAY_DEFAULT_INITIAL_SIZE        \
 126                             ? WX_ARRAY_DEFAULT_INITIAL_SIZE : m_nSize >> 1; \
 127       if ( ndefIncrement > ARRAY_MAXSIZE_INCREMENT )                        \
 128         ndefIncrement = ARRAY_MAXSIZE_INCREMENT;                            \
 129       if ( nIncrement < ndefIncrement )                                     \
 130         nIncrement = ndefIncrement;                                         \
 131       T *pNew = new T[m_nSize + nIncrement];                                \
 132       /* only grow if allocation succeeded */                               \
 133       if ( pNew ) {                                                         \
 134           m_nSize += nIncrement;                                            \
 135           /* copy data to new location */                                   \
 136           memcpy(pNew, m_pItems, m_nCount*sizeof(T));                       \
 137           delete [] m_pItems;                                               \
 138           m_pItems = pNew;                                                  \
 139       }                                                                     \
 140     }                                                                       \
 141   }                                                                         \
 142 }                                                                           \
 143                                                                             \
 144 /* dtor */                                                                  \
 145 name::~name()                                                               \
 146 {                                                                           \
 147   wxDELETEA(m_pItems);                                                      \
 148 }                                                                           \
 149                                                                             \
 150 /* clears the list */                                                       \
 151 void name::Clear()                                                          \
 152 {                                                                           \
 153   m_nSize  =                                                                \
 154   m_nCount = 0;                                                             \
 155                                                                             \
 156   wxDELETEA(m_pItems);                                                      \
 157 }                                                                           \
 158                                                                             \
 159 /* pre-allocates memory (frees the previous data!) */                       \
 160 void name::Alloc(size_t nSize)                                              \
 161 {                                                                           \
 162   /* only if old buffer was not big enough */                               \
 163   if ( nSize > m_nSize ) {                                                  \
 164     wxDELETEA(m_pItems);                                                    \
 165     m_nSize  = 0;                                                           \
 166     m_pItems = new T[nSize];                                                \
 167     /* only alloc if allocation succeeded */                                \
 168     if ( m_pItems ) {                                                       \
 169         m_nSize  = nSize;                                                   \
 170     }                                                                       \
 171   }                                                                         \
 172                                                                             \
 173   m_nCount = 0;                                                             \
 174 }                                                                           \
 175                                                                             \
 176 /* minimizes the memory usage by freeing unused memory */                   \
 177 void name::Shrink()                                                         \
 178 {                                                                           \
 179   /* only do it if we have some memory to free */                           \
 180   if( m_nCount < m_nSize ) {                                                \
 181     /* allocates exactly as much memory as we need */                       \
 182     T *pNew = new T[m_nCount];                                              \
 183     /* only shrink if allocation succeeded */                               \
 184     if ( pNew ) {                                                           \
 185         /* copy data to new location */                                     \
 186         memcpy(pNew, m_pItems, m_nCount*sizeof(T));                         \
 187         delete [] m_pItems;                                                 \
 188         m_pItems = pNew;                                                    \
 189     }                                                                       \
 190   }                                                                         \
 191 }                                                                           \
 192                                                                             \
 193 /* searches the array for an item (forward or backwards) */                 \
 194 int name::Index(T lItem, bool bFromEnd) const                               \
 195 {                                                                           \
 196   if ( bFromEnd ) {                                                         \
 197     if ( m_nCount > 0 ) {                                                   \
 198       size_t n = m_nCount;                                                  \
 199       do {                                                                  \
 200         if ( m_pItems[--n] == lItem )                                       \
 201           return n;                                                         \
 202       }                                                                     \
 203       while ( n != 0 );                                                     \
 204     }                                                                       \
 205   }                                                                         \
 206   else {                                                                    \
 207     for( size_t n = 0; n < m_nCount; n++ ) {                                \
 208       if( m_pItems[n] == lItem )                                            \
 209         return n;                                                           \
 210     }                                                                       \
 211   }                                                                         \
 212                                                                             \
 213   return wxNOT_FOUND;                                                       \
 214 }                                                                           \
 215                                                                             \
 216 /* search for a place to insert item into sorted array (binary search) */   \
 217 size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const               \
 218 {                                                                           \
 219   size_t i,                                                                 \
 220        lo = 0,                                                              \
 221        hi = m_nCount;                                                       \
 222   int res;                                                                  \
 223                                                                             \
 224   while ( lo < hi ) {                                                       \
 225     i = (lo + hi)/2;                                                        \
 226                                                                             \
 227     res = (*fnCompare)((const void *)(long)lItem,                           \
 228                        (const void *)(long)(m_pItems[i]));                  \
 229     if ( res < 0 )                                                          \
 230       hi = i;                                                               \
 231     else if ( res > 0 )                                                     \
 232       lo = i + 1;                                                           \
 233     else {                                                                  \
 234       lo = i;                                                               \
 235       break;                                                                \
 236     }                                                                       \
 237   }                                                                         \
 238                                                                             \
 239   return lo;                                                                \
 240 }                                                                           \
 241                                                                             \
 242 /* search for an item in a sorted array (binary search) */                  \
 243 int name::Index(T lItem, CMPFUNC fnCompare) const                           \
 244 {                                                                           \
 245     size_t n = IndexForInsert(lItem, fnCompare);                            \
 246                                                                             \
 247     return n < m_nCount && m_pItems[n] == lItem ? (int)n : wxNOT_FOUND;     \
 248 }                                                                           \
 249                                                                             \
 250 /* add item at the end */                                                   \
 251 void name::Add(T lItem, size_t nInsert)                                     \
 252 {                                                                           \
 253   Grow(nInsert);                                                            \
 254   for (size_t i = 0; i < nInsert; i++)                                      \
 255       m_pItems[m_nCount++] = lItem;                                         \
 256 }                                                                           \
 257                                                                             \
 258 /* add item assuming the array is sorted with fnCompare function */         \
 259 void name::Add(T lItem, CMPFUNC fnCompare)                                  \
 260 {                                                                           \
 261   Insert(lItem, IndexForInsert(lItem, fnCompare));                          \
 262 }                                                                           \
 263                                                                             \
 264 /* add item at the given position */                                        \
 265 void name::Insert(T lItem, size_t nIndex, size_t nInsert)                   \
 266 {                                                                           \
 267   wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::Insert") );   \
 268   wxCHECK_RET( m_nCount <= m_nCount + nInsert,                              \
 269                wxT("array size overflow in wxArray::Insert") );             \
 270                                                                             \
 271   Grow(nInsert);                                                            \
 272                                                                             \
 273   memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex],                   \
 274           (m_nCount - nIndex)*sizeof(T));                                   \
 275   for (size_t i = 0; i < nInsert; i++)                                      \
 276       m_pItems[nIndex + i] = lItem;                                         \
 277   m_nCount += nInsert;                                                      \
 278 }                                                                           \
 279                                                                             \
 280 /* removes item from array (by index) */                                    \
 281 void name::RemoveAt(size_t nIndex, size_t nRemove)                          \
 282 {                                                                           \
 283   wxCHECK_RET( nIndex < m_nCount, wxT("bad index in wxArray::RemoveAt") );  \
 284   wxCHECK_RET( nIndex + nRemove <= m_nCount,                                \
 285                wxT("removing too many elements in wxArray::RemoveAt") );    \
 286                                                                             \
 287   memmove(&m_pItems[nIndex], &m_pItems[nIndex + nRemove],                   \
 288           (m_nCount - nIndex - nRemove)*sizeof(T));                         \
 289   m_nCount -= nRemove;                                                      \
 290 }                                                                           \
 291                                                                             \
 292 /* removes item from array (by value) */                                    \
 293 void name::Remove(T lItem)                                                  \
 294 {                                                                           \
 295   int iIndex = Index(lItem);                                                \
 296                                                                             \
 297   wxCHECK_RET( iIndex != wxNOT_FOUND,                                       \
 298                wxT("removing inexistent item in wxArray::Remove") );        \
 299                                                                             \
 300   RemoveAt((size_t)iIndex);                                                 \
 301 }                                                                           \
 302                                                                             \
 303 /* sort array elements using passed comparaison function */                 \
 304 void name::Sort(CMPFUNC fCmp)                                               \
 305 {                                                                           \
 306   qsort(m_pItems, m_nCount, sizeof(T), fCmp);                               \
 307 }
 308
 309 _WX_DEFINE_BASEARRAY(const void *, wxBaseArrayPtrVoid)
 310 _WX_DEFINE_BASEARRAY(short,        wxBaseArrayShort)
 311 _WX_DEFINE_BASEARRAY(int,          wxBaseArrayInt)
 312 _WX_DEFINE_BASEARRAY(long,         wxBaseArrayLong)
 313 //_WX_DEFINE_BASEARRAY(double,       wxBaseArrayDouble)
 314