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) || ((m_nSize - m_nCount) < nIncrement) ) {      \
 114     if( m_nSize == 0 ) {                                                    \
 115       /* was empty, determine initial size */                               \
 116       size_t size = WX_ARRAY_DEFAULT_INITIAL_SIZE;                          \
 117       if (size < nIncrement) size = nIncrement;                             \
 118       /* allocate some memory */                                            \
 119       m_pItems = new T[size];                                               \
 120       /* only grow if allocation succeeded */                               \
 121       if ( m_pItems ) {                                                     \
 122           m_nSize = size;                                                   \
 123       }                                                                     \
 124     }                                                                       \
 125     else                                                                    \
 126     {                                                                       \
 127       /* add at least 50% but not too much */                               \
 128       size_t ndefIncrement = m_nSize < WX_ARRAY_DEFAULT_INITIAL_SIZE        \
 129                             ? WX_ARRAY_DEFAULT_INITIAL_SIZE : m_nSize >> 1; \
 130       if ( ndefIncrement > ARRAY_MAXSIZE_INCREMENT )                        \
 131         ndefIncrement = ARRAY_MAXSIZE_INCREMENT;                            \
 132       if ( nIncrement < ndefIncrement )                                     \
 133         nIncrement = ndefIncrement;                                         \
 134       T *pNew = new T[m_nSize + nIncrement];                                \
 135       /* only grow if allocation succeeded */                               \
 136       if ( pNew ) {                                                         \
 137           m_nSize += nIncrement;                                            \
 138           /* copy data to new location */                                   \
 139           memcpy(pNew, m_pItems, m_nCount*sizeof(T));                       \
 140           delete [] m_pItems;                                               \
 141           m_pItems = pNew;                                                  \
 142       }                                                                     \
 143     }                                                                       \
 144   }                                                                         \
 145 }                                                                           \
 146                                                                             \
 147 /* dtor */                                                                  \
 148 name::~name()                                                               \
 149 {                                                                           \
 150   wxDELETEA(m_pItems);                                                      \
 151 }                                                                           \
 152                                                                             \
 153 /* clears the list */                                                       \
 154 void name::Clear()                                                          \
 155 {                                                                           \
 156   m_nSize  =                                                                \
 157   m_nCount = 0;                                                             \
 158                                                                             \
 159   wxDELETEA(m_pItems);                                                      \
 160 }                                                                           \
 161                                                                             \
 162 /* pre-allocates memory (frees the previous data!) */                       \
 163 void name::Alloc(size_t nSize)                                              \
 164 {                                                                           \
 165   /* only if old buffer was not big enough */                               \
 166   if ( nSize > m_nSize ) {                                                  \
 167     wxDELETEA(m_pItems);                                                    \
 168     m_nSize  = 0;                                                           \
 169     m_pItems = new T[nSize];                                                \
 170     /* only alloc if allocation succeeded */                                \
 171     if ( m_pItems ) {                                                       \
 172         m_nSize  = nSize;                                                   \
 173     }                                                                       \
 174   }                                                                         \
 175                                                                             \
 176   m_nCount = 0;                                                             \
 177 }                                                                           \
 178                                                                             \
 179 /* minimizes the memory usage by freeing unused memory */                   \
 180 void name::Shrink()                                                         \
 181 {                                                                           \
 182   /* only do it if we have some memory to free */                           \
 183   if( m_nCount < m_nSize ) {                                                \
 184     /* allocates exactly as much memory as we need */                       \
 185     T *pNew = new T[m_nCount];                                              \
 186     /* only shrink if allocation succeeded */                               \
 187     if ( pNew ) {                                                           \
 188         /* copy data to new location */                                     \
 189         memcpy(pNew, m_pItems, m_nCount*sizeof(T));                         \
 190         delete [] m_pItems;                                                 \
 191         m_pItems = pNew;                                                    \
 192     }                                                                       \
 193   }                                                                         \
 194 }                                                                           \
 195                                                                             \
 196 /* searches the array for an item (forward or backwards) */                 \
 197 int name::Index(T lItem, bool bFromEnd) const                               \
 198 {                                                                           \
 199   if ( bFromEnd ) {                                                         \
 200     if ( m_nCount > 0 ) {                                                   \
 201       size_t n = m_nCount;                                                  \
 202       do {                                                                  \
 203         if ( m_pItems[--n] == lItem )                                       \
 204           return n;                                                         \
 205       }                                                                     \
 206       while ( n != 0 );                                                     \
 207     }                                                                       \
 208   }                                                                         \
 209   else {                                                                    \
 210     for( size_t n = 0; n < m_nCount; n++ ) {                                \
 211       if( m_pItems[n] == lItem )                                            \
 212         return n;                                                           \
 213     }                                                                       \
 214   }                                                                         \
 215                                                                             \
 216   return wxNOT_FOUND;                                                       \
 217 }                                                                           \
 218                                                                             \
 219 /* search for a place to insert item into sorted array (binary search) */   \
 220 size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const               \
 221 {                                                                           \
 222   size_t i,                                                                 \
 223        lo = 0,                                                              \
 224        hi = m_nCount;                                                       \
 225   int res;                                                                  \
 226                                                                             \
 227   while ( lo < hi ) {                                                       \
 228     i = (lo + hi)/2;                                                        \
 229                                                                             \
 230     res = (*fnCompare)((const void *)(long)lItem,                           \
 231                        (const void *)(long)(m_pItems[i]));                  \
 232     if ( res < 0 )                                                          \
 233       hi = i;                                                               \
 234     else if ( res > 0 )                                                     \
 235       lo = i + 1;                                                           \
 236     else {                                                                  \
 237       lo = i;                                                               \
 238       break;                                                                \
 239     }                                                                       \
 240   }                                                                         \
 241                                                                             \
 242   return lo;                                                                \
 243 }                                                                           \
 244                                                                             \
 245 /* search for an item in a sorted array (binary search) */                  \
 246 int name::Index(T lItem, CMPFUNC fnCompare) const                           \
 247 {                                                                           \
 248     size_t n = IndexForInsert(lItem, fnCompare);                            \
 249                                                                             \
 250     return n < m_nCount && m_pItems[n] == lItem ? (int)n : wxNOT_FOUND;     \
 251 }                                                                           \
 252                                                                             \
 253 /* add item at the end */                                                   \
 254 void name::Add(T lItem, size_t nInsert)                                     \
 255 {                                                                           \
 256   if (nInsert == 0)                                                         \
 257       return;                                                               \
 258   Grow(nInsert);                                                            \
 259   for (size_t i = 0; i < nInsert; i++)                                      \
 260       m_pItems[m_nCount++] = lItem;                                         \
 261 }                                                                           \
 262                                                                             \
 263 /* add item assuming the array is sorted with fnCompare function */         \
 264 void name::Add(T lItem, CMPFUNC fnCompare)                                  \
 265 {                                                                           \
 266   Insert(lItem, IndexForInsert(lItem, fnCompare));                          \
 267 }                                                                           \
 268                                                                             \
 269 /* add item at the given position */                                        \
 270 void name::Insert(T lItem, size_t nIndex, size_t nInsert)                   \
 271 {                                                                           \
 272   wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::Insert") );   \
 273   wxCHECK_RET( m_nCount <= m_nCount + nInsert,                              \
 274                wxT("array size overflow in wxArray::Insert") );             \
 275                                                                             \
 276   if (nInsert == 0)                                                         \
 277       return;                                                               \
 278   Grow(nInsert);                                                            \
 279                                                                             \
 280   memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex],                   \
 281           (m_nCount - nIndex)*sizeof(T));                                   \
 282   for (size_t i = 0; i < nInsert; i++)                                      \
 283       m_pItems[nIndex + i] = lItem;                                         \
 284   m_nCount += nInsert;                                                      \
 285 }                                                                           \
 286                                                                             \
 287 /* removes item from array (by index) */                                    \
 288 void name::RemoveAt(size_t nIndex, size_t nRemove)                          \
 289 {                                                                           \
 290   wxCHECK_RET( nIndex < m_nCount, wxT("bad index in wxArray::RemoveAt") );  \
 291   wxCHECK_RET( nIndex + nRemove <= m_nCount,                                \
 292                wxT("removing too many elements in wxArray::RemoveAt") );    \
 293                                                                             \
 294   memmove(&m_pItems[nIndex], &m_pItems[nIndex + nRemove],                   \
 295           (m_nCount - nIndex - nRemove)*sizeof(T));                         \
 296   m_nCount -= nRemove;                                                      \
 297 }                                                                           \
 298                                                                             \
 299 /* removes item from array (by value) */                                    \
 300 void name::Remove(T lItem)                                                  \
 301 {                                                                           \
 302   int iIndex = Index(lItem);                                                \
 303                                                                             \
 304   wxCHECK_RET( iIndex != wxNOT_FOUND,                                       \
 305                wxT("removing inexistent item in wxArray::Remove") );        \
 306                                                                             \
 307   RemoveAt((size_t)iIndex);                                                 \
 308 }                                                                           \
 309                                                                             \
 310 /* sort array elements using passed comparaison function */                 \
 311 void name::Sort(CMPFUNC fCmp)                                               \
 312 {                                                                           \
 313   qsort(m_pItems, m_nCount, sizeof(T), fCmp);                               \
 314 }
 315
 316 _WX_DEFINE_BASEARRAY(const void *, wxBaseArrayPtrVoid)
 317 _WX_DEFINE_BASEARRAY(short,        wxBaseArrayShort)
 318 _WX_DEFINE_BASEARRAY(int,          wxBaseArrayInt)
 319 _WX_DEFINE_BASEARRAY(long,         wxBaseArrayLong)
 320 //_WX_DEFINE_BASEARRAY(double,       wxBaseArrayDouble)
 321