prj/tech/libsrc/cpptools/dynarray.cpp

   1 ///////////////////////////////////////////////////////////////////////////////
   2 // $Source: x:/prj/tech/libsrc/cpptools/RCS/dynarray.cpp $
   3 // $Author: TOML $
   4 // $Date: 1998/05/23 07:08:04 $
   5 // $Revision: 1.11 $
   6 //
   7
   8 #include <lg.h>
   9 #include <dynarray.h>
  10
  11 #include <stdlib.h>
  12
  13 #ifndef NO_DB_MEM
  14 // Must be last header
  15 #include <memall.h>
  16 #include <dbmem.h>
  17 #endif
  18
  19 //include "storintr.h"
  20
  21 ///////////////////////////////////////////////////////////////////////////////
  22 //
  23 // CLASS: cDynArrayBase
  24 //
  25
  26 #ifndef SHIP
  27 char BASED_CODE cDynArrayBase::gm_pszOutOfRange[] = "Index out of range";
  28 #endif
  29
  30 ///////////////////////////////////////
  31 //
  32 // Assignment operator
  33 //
  34
  35 cDynArrayBase& cDynArrayBase::operator=(const cDynArrayBase &Array)
  36 {
  37     // Blow the current array away
  38     SetSize(0);
  39
  40     // Copy the values
  41     m_nBlockSizeLessOne = Array.m_nBlockSizeLessOne;
  42     m_nItemSize = Array.m_nItemSize;
  43     m_nItems = Array.m_nItems;
  44     VerifyMsg(Resize(m_nItems), "Array allocation failed");
  45
  46     AssertMsg(!m_nItems || m_pItems, "Expected items in dynarray");
  47
  48     // Call set item for all the items
  49     for (index_t i = 0; i<m_nItems; i++)
  50         SetItem(Array.ItemPtr(i), i);
  51
  52     return *this;
  53 }
  54
  55 ///////////////////////////////////////
  56 //
  57 // Resize the array buffer to the desired number of slots.
  58 //
  59 // NOTE: The logical size does not change.
  60 //
  61
  62 BOOL cDynArrayBase::DoResize(index_t evenSlots)
  63 {
  64     if (evenSlots)
  65     {
  66         tDynArrayItem *newP;
  67
  68         // Note: Allow for scratch block at the end
  69         if (m_pItems)
  70             newP = realloc(m_pItems, (evenSlots+1) * m_nItemSize);
  71         else
  72             newP = malloc((evenSlots+1) * m_nItemSize);
  73
  74         AssertMsg(newP, "Dynamic array resize failed");
  75
  76         if (!newP)
  77             return FALSE;
  78
  79         m_pItems = (BYTE *) newP;
  80     }
  81
  82     else if (m_pItems)
  83     {
  84         free(m_pItems);
  85         m_pItems = 0;
  86     }
  87
  88     m_nSlots = evenSlots;
  89
  90     return TRUE;
  91 }
  92
  93
  94 ///////////////////////////////////////
  95 //
  96 // MoveItemToIndex
  97 //
  98 // Move an element to a specified position in the array, shifting
  99 // other element in the list appropriately.
 100 //
 101
 102 void cDynArrayBase::MoveItemToIndex(index_t currentIndex, index_t newIndex)
 103 {
 104     AssertMsg(currentIndex < m_nItems && newIndex < m_nItems, gm_pszOutOfRange);
 105
 106     if (currentIndex == newIndex)
 107         return;
 108
 109     // In order to move the item, we must first make a copy of it.
 110     // We always keep extra space at the end of the item data block
 111     // for this purpose.
 112     CopyToTemporary(currentIndex);
 113
 114     // If the element is before target location...
 115     if (currentIndex < newIndex)
 116     {
 117         // Shift items between current and target locations down one
 118         memmove(UnsafeItemPtr( currentIndex), UnsafeItemPtr( currentIndex+1),
 119                         (newIndex - currentIndex) * m_nItemSize);
 120
 121     }
 122
 123     // ...else the element is after target location...
 124     {
 125         // Shift items between target and current locations up one.
 126         memmove(UnsafeItemPtr( newIndex+1), UnsafeItemPtr( newIndex),
 127                         (currentIndex - newIndex) * m_nItemSize);
 128
 129     }
 130
 131     // Copy element into new position
 132     CopyFromTemporary(newIndex);
 133 }
 134
 135
 136
 137 ///////////////////////////////////////
 138 //
 139 // Write the array to the stream
 140 //
 141
 142 BOOL cDynArrayBase::ToStream(cOStore &) const
 143 {
 144 #if 0
 145     int iElement = 0;
 146
 147     index_t numElems = Size();
 148
 149     if (!OStore.WriteHeader("DYNARRAY"))
 150         return FALSE;
 151
 152     OStore.To(numElems);
 153
 154     for (index_t i = 0; i < numElems; i++)
 155     {
 156         if (!OStore.To(i))
 157             return FALSE;
 158
 159         if (!ItemToStream(OStore, UnsafeItemPtr(i)))
 160             return FALSE;
 161     }
 162
 163     return OStore.WriteTrailer();
 164 #else
 165     return FALSE;
 166 #endif
 167 }
 168
 169 ///////////////////////////////////////
 170 //
 171 // Read the array from a stream
 172 //
 173
 174 BOOL cDynArrayBase::FromStream(cIStore &)
 175 {
 176 #if 0
 177     if (!IStore.ReadHeader("DYNARRAY"))
 178         return FALSE;
 179
 180     // Get the number of elements
 181     index_t numElems;
 182     if (!IStore.From(numElems))
 183         return FALSE;
 184
 185     SetSize(numElems);
 186
 187     for (index_t i = 0; i<numElems; i++)
 188     {
 189         index_t j;
 190         if (!IStore.From(j))
 191             return FALSE;
 192
 193         if (j != i)
 194             return IStore.Fail();
 195
 196         // Stream in the node over the item
 197         if (!ItemFromStream(IStore, UnsafeItemPtr(i)))
 198             return FALSE;
 199     }
 200
 201     return IStore.ReadTrailer();
 202 #else
 203     return FALSE;
 204 #endif
 205 }
 206
 207
 208 ///////////////////////////////////////
 209 //
 210 // Read an item from the stream (default binary mode)
 211 //
 212
 213 BOOL cDynArrayBase::ItemFromStream(cIStore &, tDynArrayItem *)
 214 {
 215 #if 0
 216     // Copy item from stream, overwriting whatever was in the item before
 217     return IStore.From((unsigned char *)pItem, GetElementSize());
 218 #else
 219     return FALSE;
 220 #endif
 221 }
 222
 223
 224 ///////////////////////////////////////
 225 //
 226 // Write an item to the stream (default binary mode)
 227 //
 228
 229 BOOL cDynArrayBase::ItemToStream(cOStore &, const tDynArrayItem *) const
 230 {
 231 #if 0
 232     return OStore.To((const unsigned char *)pItem, GetElementSize());
 233 #else
 234     return FALSE;
 235 #endif
 236 }
 237
 238
 239 ///////////////////////////////////////
 240 //
 241 // Swap the content of two arrays (all state and ownership
 242 // of allocated memory). If information should only go one-way,
 243 // empty one first.
 244 //
 245
 246 void cDynArrayBase::SwapContents(cDynArrayBase &x)
 247 {
 248
 249     BYTE * p;
 250     p = x.m_pItems;
 251     x.m_pItems = m_pItems;
 252     m_pItems = p;
 253
 254     size_t sz;
 255     sz = x.m_nItemSize;
 256     x.m_nItemSize = m_nItemSize;
 257     m_nItemSize = sz;
 258
 259     index_t  ix;
 260     ix = x.m_nItems;
 261     x.m_nItems = m_nItems;
 262     m_nItems = ix;
 263
 264     ix = x.m_nSlots;
 265     x.m_nSlots = m_nSlots;
 266     m_nSlots = ix;
 267 }
 268
 269
 270 ///////////////////////////////////////
 271 //
 272 // Find an element using a supplied comparison function.  This routine uses
 273 // a binary search algorithm so the array must be sorted.
 274 //
 275
 276 index_t cDynArrayBase::BSearch(tDynArrayKey *pKey, tSearchFunc SearchFunc) const
 277 {
 278     if (!m_pItems)
 279         return BAD_INDEX;
 280
 281     tDynArrayItem *pNewItem = bsearch(pKey, m_pItems, m_nItems, m_nItemSize, SearchFunc);
 282
 283     if (!pNewItem)
 284         return BAD_INDEX;
 285
 286     return ((BYTE *)pNewItem - m_pItems) / m_nItemSize;
 287 }
 288
 289
 290 ///////////////////////////////////////
 291 //
 292 // Find an element using a supplied comparison function.  This routine uses
 293 // a straight linear search algorithm.
 294 //
 295
 296 index_t cDynArrayBase::LSearch(tDynArrayKey *pKey, tSearchFunc SearchFunc) const
 297 {
 298     if (!m_pItems)
 299         return BAD_INDEX;
 300
 301     BYTE * pNewItem;
 302     #ifdef LSEARCH_IN_RTL
 303     // @TBD: Is this part of our RTL yet?
 304     pNewItem = (BYTE *) lsearch(pItem, m_pItems, m_nItems, m_nItemSize, SearchFunc);
 305     #else
 306     pNewItem = m_pItems;
 307
 308     for (index_t Remaining = m_nItems; Remaining; Remaining--)
 309     {
 310         if (SearchFunc(pKey, (tDynArrayItem *)pNewItem)==0)
 311             break;
 312         pNewItem += m_nItemSize;
 313     }
 314
 315     if (!Remaining)
 316         pNewItem = 0;
 317     #endif
 318
 319     if (!pNewItem)
 320         return BAD_INDEX;
 321
 322     return (pNewItem - m_pItems) / m_nItemSize;
 323 }
 324
 325
 326 ///////////////////////////////////////
 327 //
 328 // Sort the array of elements based on the supplied comparison function.
 329 //
 330
 331 void cDynArrayBase::Sort(tSortFunc SortFunc)
 332 {
 333     if (!m_pItems)
 334         return;
 335
 336     qsort(m_pItems, m_nItems, m_nItemSize, SortFunc);
 337 }
 338
 339 ///////////////////////////////////////////////////////////////////////////////
 340