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