1/* 2 File: CDynamicArray.cpp 3 4 Contains: Implementation of the CDynamicArray class 5 6 7*/ 8 9#include "CDynamicArray.h" 10#include "CArrayIterator.h" 11#include "IrDALog.h" 12 13#if (hasTracing > 0 && hasCDynamicArrayTracing > 0) 14 15enum 16{ 17 kLogNew = 1, 18 kLogFree, 19 kLogInit, 20 21 kLogSetSize1, 22 kLogSetSize2, 23 kLogSetSizeCurrent, 24 kLogSetSizeNew, 25 26 kLogIOAllocBuffer, 27 kLogIOAllocSize, 28 kLogIOFreeBuffer, 29 kLogIOFreeSize, 30 31 kLogRemoveAt, 32 kLogRemoveAtObj 33}; 34 35static 36EventTraceCauseDesc gTraceEvents[] = { 37 {kLogNew, "CDynamicArray: New, obj="}, 38 {kLogFree, "CDynamicArray: Free, obj="}, 39 {kLogInit, "CDynamicArray: Init, elemsize=, chunksize="}, 40 41 {kLogSetSize1, "CDynamicArray: set size, obj="}, 42 {kLogSetSize2, "CDynamicArray: set size, new count="}, 43 {kLogSetSizeCurrent, "CDynamicArray: set size, current alloc="}, 44 {kLogSetSizeNew, "CDynamicArray: set size, new alloc="}, 45 46 {kLogIOAllocBuffer, "CDynamicArray: ioalloc, buf="}, 47 {kLogIOAllocSize, "CDynamicArray: ioalloc, size="}, 48 {kLogIOFreeBuffer, "CDynamicArray: iofree, buf="}, 49 {kLogIOFreeSize, "CDynamicArray: iofree, size="}, 50 51 {kLogRemoveAt, "CDynamicArray: remove at, index=, count="}, 52 {kLogRemoveAtObj, "CDynamicArray: remove at, obj="} 53}; 54#define XTRACE(x, y, z) IrDALogAdd( x, y, z, gTraceEvents, true ) 55#else 56#define XTRACE(x, y, z) ((void) 0) 57#endif 58 59 60//-------------------------------------------------------------------------------- 61#define super OSObject 62 OSDefineMetaClassAndStructors(CDynamicArray, OSObject); 63//-------------------------------------------------------------------------------- 64 65 66//-------------------------------------------------------------------------------- 67// CDynamicArray::cDynamicArray 68//-------------------------------------------------------------------------------- 69CDynamicArray * 70CDynamicArray::cDynamicArray(Size elementSize, ArrayIndex chunkSize) 71{ 72 CDynamicArray *obj = new CDynamicArray; 73 74 XTRACE(kLogNew, (int)obj >> 16, (short)obj); 75 76 if (obj && !obj->init(elementSize, chunkSize)) { 77 obj->release(); 78 obj = nil; 79 } 80 return obj; 81} 82 83//-------------------------------------------------------------------------------- 84// CDynamicArray::init 85//-------------------------------------------------------------------------------- 86Boolean 87CDynamicArray::init(Size elementSize, ArrayIndex chunkSize) 88{ 89 90 XTRACE(kLogInit, elementSize, chunkSize); 91/* 92 put things in a known state. 93 note that fArrayBlock is not allocated here, but in ::SetArraySize() below. 94*/ 95 96 fSize = 0; 97 fElementSize = elementSize; 98 fChunkSize = chunkSize; 99 fAllocatedSize = 0; 100 fArrayBlock = nil; 101 fIterator = nil; 102 103 return super::init(); 104 105} // CDynamicArray::CDynamicArray 106 107 108//-------------------------------------------------------------------------------- 109// CDynamicArray::free 110//-------------------------------------------------------------------------------- 111void 112CDynamicArray::free() 113{ 114 XTRACE(kLogFree, 0, (short)this); 115 116 if (fIterator) { 117 fIterator->DeleteArray(); 118 fIterator = nil; 119 } 120 121 if (fArrayBlock) { 122 int len = ComputeByteCount(fAllocatedSize); 123 XTRACE(kLogIOFreeBuffer, 0, (short)fArrayBlock); 124 XTRACE(kLogIOFreeSize, len >> 16, (short)len); 125 IOFree( fArrayBlock, len); 126 fArrayBlock = nil; 127 } 128 129 super::free(); 130} // CDynamicArray::free 131 132 133//-------------------------------------------------------------------------------- 134// CDynamicArray::SafeElementPtrAt(ArrayIndex index) 135//-------------------------------------------------------------------------------- 136void* CDynamicArray::SafeElementPtrAt(ArrayIndex index) 137{ 138 139 return ((fSize > 0) && (index > kEmptyIndex) && (index < fSize)) 140 ? ElementPtrAt(index) 141 : nil; 142 143} // CDynamicArray::SafeElementPtrAt 144 145 146//-------------------------------------------------------------------------------- 147// CDynamicArray::RemoveElementsAt 148//-------------------------------------------------------------------------------- 149IrDAErr CDynamicArray::RemoveElementsAt(ArrayIndex index, ArrayIndex count) 150/* 151 remove count elements starting with index. 152 actually, all we do is compress the array by overlaying elements 153 from below the target block on top the target block, then 154 resetting the array block size. 155 156 Ergo, deletions from the end of the array are more efficient than from 157 the middle or front. 158 159 note that the elements themselves are *NOT* delete'd 160*/ 161{ 162 IrDAErr result = noErr; 163 164 XTRACE(kLogRemoveAt, index, count); 165 XTRACE(kLogRemoveAtObj, (int)this >> 16, (short)this); 166 167 // can't remove: before the start (index < 0) 168 // zero or negative count (count <= 0) 169 // after the end (index >= fSize) 170 // past the end (index + count > fSize) 171 172 // quick return if there is nothing to do 173 if (fSize == 0) 174 return 0; 175 176 XASSERT(index >= 0); 177 XASSERT(count >= 0); 178 XASSERT(index < fSize); 179 XASSERT((index + count) <= fSize); 180 181 if (count > 0) 182 { 183 void *indexPtr, *nextElementPtr, *lastElementPtr; 184 185 XASSERT(fArrayBlock); 186 187 indexPtr = ElementPtrAt(index); 188 nextElementPtr = ElementPtrAt(index + count); 189 lastElementPtr = ElementPtrAt(fSize); 190 191 // removed from middle? Compress the array 192 if (nextElementPtr < lastElementPtr) 193 BlockMove(nextElementPtr, indexPtr, (long)lastElementPtr - (long)nextElementPtr); 194 195 // take up slack if necessary. 196 result = SetArraySize(fSize - count); 197 XREQUIRENOT(result, Fail_SetArraySize); 198 199 fSize -= count; 200 201 // Keep all iterators apprised 202 if (fIterator) 203 fIterator->RemoveElementsAt(index, count); 204 } 205 206Fail_SetArraySize: 207 208 return result; 209 210} // CDynamicArray::RemoveElementsAt 211 212 213//-------------------------------------------------------------------------------- 214// CDynamicArray::GetElementsAt 215//-------------------------------------------------------------------------------- 216IrDAErr CDynamicArray::GetElementsAt(ArrayIndex index, void* elemPtr, ArrayIndex count) 217{ 218 // can't get: before the start (index < 0) 219 // after the end (index >= fSize) 220 // negative count (count < 0) 221 // past the end (index + count > fSize) 222 223 XASSERT(index >= 0); 224 XASSERT(index < fSize); 225 XASSERT(count >= 0); 226 XASSERT((index + count) <= fSize); 227 228 XASSERT(fArrayBlock); 229 230 if (count > 0) 231 BlockMove(ElementPtrAt(index), elemPtr, ComputeByteCount(count)); 232 233 return 0; 234 235} // CDynamicArray::GetElementsAt 236 237 238//-------------------------------------------------------------------------------- 239// CDynamicArray::InsertElementsBefore 240//-------------------------------------------------------------------------------- 241IrDAErr CDynamicArray::InsertElementsBefore(ArrayIndex index, void* elemPtr, ArrayIndex count) 242{ 243 IrDAErr result = noErr; 244 245 // can't insert: before the start (index < 0) 246 // negative count (count < 0) 247 248 require(index >= 0, Bogus); 249 require(count >= 0, Bogus); 250 251 // put a cap on the index 252 // anything past the end of the array gets inserted at the end 253 254 if (index > fSize) 255 index = fSize; 256 257 if (count > 0) 258 { 259 void *indexPtr, *nextIndexPtr, *lastElementPtr; 260 261 result = SetArraySize(fSize + count); 262 nrequire(result, Fail_SetArraySize); 263 264 check(fArrayBlock); 265 266 indexPtr = ElementPtrAt(index); 267 nextIndexPtr = ElementPtrAt(index + count); 268 lastElementPtr = ElementPtrAt(fSize); 269 270 // clear out a hole? 271 if (index < fSize) 272 BlockMove(indexPtr, nextIndexPtr, (long)lastElementPtr - (long)indexPtr); 273 274 BlockMove(elemPtr, indexPtr, ComputeByteCount(count)); 275 276 fSize += count; 277 278 // Keep all iterators apprised 279 if (fIterator) 280 fIterator->InsertElementsBefore(index, count); 281 } 282 283Fail_SetArraySize: 284 285 return result; 286 287Bogus: 288 return kIrDAErrBadParameter; 289 290} // CDynamicArray::InsertElementsBefore 291 292 293//-------------------------------------------------------------------------------- 294// CDynamicArray::ReplaceElementsAt 295//-------------------------------------------------------------------------------- 296IrDAErr CDynamicArray::ReplaceElementsAt(ArrayIndex index, void* elemPtr, ArrayIndex count) 297{ 298 // can't replace: before the start (index < 0) 299 // after the end (index >= fSize) 300 // negative count (count < 0) 301 // past the end (index + count > fSize) 302 303 XASSERT(index >= 0); 304 XASSERT(index < fSize); 305 XASSERT(count >= 0); 306 XASSERT((index + count) <= fSize); 307 308 XASSERT(fArrayBlock); 309 310 if (count > 0) 311 BlockMove(elemPtr, ElementPtrAt(index), ComputeByteCount(count)); 312 313 return 0; 314 315} // CDynamicArray::ReplaceElementsAt 316 317 318//-------------------------------------------------------------------------------- 319// CDynamicArray::Merge 320//-------------------------------------------------------------------------------- 321IrDAErr CDynamicArray::Merge(CDynamicArray* aDynamicArray) 322{ 323 IrDAErr result = errElementSizeMismatch; // assume the worst 324 325 XREQUIRE(fElementSize == aDynamicArray->fElementSize, Fail_ElementSize); 326 327 if (aDynamicArray->fSize > 0) 328 result = InsertElementsBefore(fSize, aDynamicArray->ElementPtrAt(0), aDynamicArray->fSize); 329 else 330 result = noErr; 331 332Fail_ElementSize: 333 334 return result; 335 336} // CDynamicArray::Merge 337 338//-------------------------------------------------------------------------------- 339// CDynamicArray::SetArraySize 340//-------------------------------------------------------------------------------- 341IrDAErr CDynamicArray::SetArraySize(ArrayIndex theSize) 342{ 343 ArrayIndex newAllocatedSize; 344 345 if (theSize == 0) 346 { 347 return noErr; // always leave the inital chunk allocated 348 } 349 350 else if ((theSize > fAllocatedSize) || (fAllocatedSize - theSize >= fChunkSize)) 351 { 352 XASSERT(fChunkSize > 0); 353 354 // Set the # of allocated elements to the nearest multiple of fChunkSize 355 // Wait until after the NewPtr/ReallocPtr to set fAllocatedSize 356 // in case (re)allocation fails 357 358 if (fChunkSize) 359 newAllocatedSize = (theSize + fChunkSize) - (theSize + fChunkSize) % fChunkSize; 360 else 361 newAllocatedSize = theSize; 362 363 364 if (newAllocatedSize != fAllocatedSize) { 365 UInt8 * newArrayBlock; 366 int new_bytecount, old_bytecount; 367 368 new_bytecount = ComputeByteCount(newAllocatedSize); 369 old_bytecount = ComputeByteCount(fAllocatedSize); 370 371 XTRACE(kLogSetSize1, (int)this >> 16, (short)this); 372 XTRACE(kLogSetSize2, theSize >> 16, (short)theSize); 373 XTRACE(kLogSetSizeCurrent, fAllocatedSize >> 16, (short)fAllocatedSize); 374 XTRACE(kLogSetSizeNew, newAllocatedSize >> 16, (short)newAllocatedSize); 375 376 newArrayBlock = (UInt8 *)IOMalloc(new_bytecount); 377 require(newArrayBlock, Fail); 378 379 XTRACE(kLogIOAllocBuffer, (int)newArrayBlock >> 16, (short)newArrayBlock); 380 XTRACE(kLogIOAllocSize, new_bytecount >> 16, (short)new_bytecount); 381 382 // if old buffer existed, copy it over to new buffer and free it 383 if (fArrayBlock) { 384 int bytecount; // copy min of old size and new size 385 386 bytecount = Min(old_bytecount, new_bytecount); 387 BlockMove(fArrayBlock, newArrayBlock, bytecount); 388 389 XTRACE(kLogIOFreeBuffer, (int)fArrayBlock >> 16, (short)fArrayBlock); 390 XTRACE(kLogIOFreeSize, old_bytecount >> 16, (short)old_bytecount); 391 IOFree(fArrayBlock, old_bytecount); 392 } 393 394 fArrayBlock = newArrayBlock; 395 fAllocatedSize = newAllocatedSize; 396 } 397 } 398 399 return noErr; 400 401Fail: 402 return errNoMemory; 403 404} // CDynamicArray::SetArraySize 405 406 407//-------------------------------------------------------------------------------- 408// CDynamicArray::SetElementCount 409// 410// like SetArraySize, but sets logical size, too 411//-------------------------------------------------------------------------------- 412IrDAErr CDynamicArray::SetElementCount(ArrayIndex theSize) 413{ 414 415 IrDAErr result = SetArraySize(theSize); 416 if ( result == noErr ) 417 { 418 fSize = theSize; 419 } 420 421 return result; 422 423} // CDynamicArray::SetElementCount 424