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