1/*
2 * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28/* IOArray.m created by rsulack on Fri 12-Sep-1997 */
29/* IOArray.cpp converted to C++ by gvdl on Fri 1998-10-30 */
30
31
32#include <libkern/c++/OSArray.h>
33#include <libkern/c++/OSDictionary.h>
34#include <libkern/c++/OSSerialize.h>
35#include <libkern/c++/OSLib.h>
36
37#define super OSCollection
38
39OSDefineMetaClassAndStructors(OSArray, OSCollection)
40OSMetaClassDefineReservedUnused(OSArray, 0);
41OSMetaClassDefineReservedUnused(OSArray, 1);
42OSMetaClassDefineReservedUnused(OSArray, 2);
43OSMetaClassDefineReservedUnused(OSArray, 3);
44OSMetaClassDefineReservedUnused(OSArray, 4);
45OSMetaClassDefineReservedUnused(OSArray, 5);
46OSMetaClassDefineReservedUnused(OSArray, 6);
47OSMetaClassDefineReservedUnused(OSArray, 7);
48
49#if OSALLOCDEBUG
50extern "C" {
51    extern int debug_container_malloc_size;
52};
53#define ACCUMSIZE(s) do { debug_container_malloc_size += (s); } while(0)
54#else
55#define ACCUMSIZE(s)
56#endif
57
58#define EXT_CAST(obj) \
59    reinterpret_cast<OSObject *>(const_cast<OSMetaClassBase *>(obj))
60
61bool OSArray::initWithCapacity(unsigned int inCapacity)
62{
63    unsigned int size;
64
65    if (!super::init())
66        return false;
67
68    // integer overflow check
69    if (inCapacity > (UINT_MAX / sizeof(const OSMetaClassBase*)))
70        return false;
71
72    size = sizeof(const OSMetaClassBase *) * inCapacity;
73    array = (const OSMetaClassBase **) kalloc(size);
74    if (!array)
75        return false;
76
77    count = 0;
78    capacity = inCapacity;
79    capacityIncrement = (inCapacity)? inCapacity : 16;
80
81    bzero(array, size);
82    ACCUMSIZE(size);
83
84    return true;
85}
86
87bool OSArray::initWithObjects(const OSObject *objects[],
88                              unsigned int theCount,
89                              unsigned int theCapacity)
90{
91    unsigned int initCapacity;
92
93    if (!theCapacity)
94        initCapacity = theCount;
95    else if (theCount > theCapacity)
96        return false;
97    else
98        initCapacity = theCapacity;
99
100    if (!objects || !initWithCapacity(initCapacity))
101        return false;
102
103    for ( unsigned int i = 0; i < theCount; i++ ) {
104        const OSMetaClassBase *newObject = *objects++;
105
106        if (!newObject)
107            return false;
108
109        array[count++] = newObject;
110        newObject->taggedRetain(OSTypeID(OSCollection));
111    }
112
113    return true;
114}
115
116bool OSArray::initWithArray(const OSArray *anArray,
117                            unsigned int theCapacity)
118{
119    if ( !anArray )
120        return false;
121
122    return initWithObjects((const OSObject **) anArray->array,
123                           anArray->count, theCapacity);
124}
125
126OSArray *OSArray::withCapacity(unsigned int capacity)
127{
128    OSArray *me = new OSArray;
129
130    if (me && !me->initWithCapacity(capacity)) {
131        me->release();
132        return 0;
133    }
134
135    return me;
136}
137
138OSArray *OSArray::withObjects(const OSObject *objects[],
139                              unsigned int count,
140                              unsigned int capacity)
141{
142    OSArray *me = new OSArray;
143
144    if (me && !me->initWithObjects(objects, count, capacity)) {
145        me->release();
146        return 0;
147    }
148
149    return me;
150}
151
152OSArray *OSArray::withArray(const OSArray *array,
153                            unsigned int capacity)
154{
155    OSArray *me = new OSArray;
156
157    if (me && !me->initWithArray(array, capacity)) {
158        me->release();
159        return 0;
160    }
161
162    return me;
163}
164
165void OSArray::free()
166{
167    // Clear immutability - assumes the container is doing the right thing
168    (void) super::setOptions(0, kImmutable);
169
170    flushCollection();
171
172    if (array) {
173        kfree(array, sizeof(const OSMetaClassBase *) * capacity);
174        ACCUMSIZE( -(sizeof(const OSMetaClassBase *) * capacity) );
175    }
176
177    super::free();
178}
179
180
181unsigned int OSArray::getCount() const { return count; }
182unsigned int OSArray::getCapacity() const { return capacity; }
183unsigned int OSArray::getCapacityIncrement() const { return capacityIncrement; }
184unsigned int OSArray::setCapacityIncrement(unsigned int increment)
185{
186    capacityIncrement = (increment)? increment : 16;
187
188    return capacityIncrement;
189}
190
191unsigned int OSArray::ensureCapacity(unsigned int newCapacity)
192{
193    const OSMetaClassBase **newArray;
194    unsigned int finalCapacity;
195    unsigned int oldSize, newSize;
196
197    if (newCapacity <= capacity)
198        return capacity;
199
200    // round up
201    finalCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
202                * capacityIncrement;
203
204    // integer overflow check
205    if ((finalCapacity < newCapacity) || (finalCapacity > (UINT_MAX / sizeof(const OSMetaClassBase*))))
206        return capacity;
207
208    newSize = sizeof(const OSMetaClassBase *) * finalCapacity;
209
210    newArray = (const OSMetaClassBase **) kalloc(newSize);
211    if (newArray) {
212        oldSize = sizeof(const OSMetaClassBase *) * capacity;
213
214        ACCUMSIZE(newSize - oldSize);
215
216        bcopy(array, newArray, oldSize);
217        bzero(&newArray[capacity], newSize - oldSize);
218        kfree(array, oldSize);
219        array = newArray;
220        capacity = finalCapacity;
221    }
222
223    return capacity;
224}
225
226void OSArray::flushCollection()
227{
228    unsigned int i;
229
230    haveUpdated();
231    for (i = 0; i < count; i++) {
232        array[i]->taggedRelease(OSTypeID(OSCollection));
233    }
234    count = 0;
235}
236
237bool OSArray::setObject(const OSMetaClassBase *anObject)
238{
239    return setObject(count, anObject);
240}
241
242bool OSArray::setObject(unsigned int index, const OSMetaClassBase *anObject)
243{
244    unsigned int i;
245    unsigned int newCount = count + 1;
246
247    if ((index > count) || !anObject)
248        return false;
249
250    // do we need more space?
251    if (newCount > capacity && newCount > ensureCapacity(newCount))
252        return false;
253
254    haveUpdated();
255    if (index != count) {
256        for (i = count; i > index; i--)
257            array[i] = array[i-1];
258    }
259    array[index] = anObject;
260    anObject->taggedRetain(OSTypeID(OSCollection));
261    count++;
262
263    return true;
264}
265
266bool OSArray::merge(const OSArray * otherArray)
267{
268    unsigned int otherCount = otherArray->getCount();
269    unsigned int newCount = count + otherCount;
270
271    if (!otherCount)
272        return true;
273
274    // do we need more space?
275    if (newCount > capacity && newCount > ensureCapacity(newCount))
276        return false;
277
278    haveUpdated();
279    for (unsigned int i = 0; i < otherCount; i++) {
280        const OSMetaClassBase *newObject = otherArray->getObject(i);
281
282        array[count++] = newObject;
283        newObject->taggedRetain(OSTypeID(OSCollection));
284    }
285
286    return true;
287}
288
289void OSArray::
290replaceObject(unsigned int index, const OSMetaClassBase *anObject)
291{
292    const OSMetaClassBase *oldObject;
293
294    if ((index >= count) || !anObject)
295        return;
296
297    haveUpdated();
298    oldObject = array[index];
299    array[index] = anObject;
300    anObject->taggedRetain(OSTypeID(OSCollection));
301
302    oldObject->taggedRelease(OSTypeID(OSCollection));
303}
304
305void OSArray::removeObject(unsigned int index)
306{
307    unsigned int i;
308    const OSMetaClassBase *oldObject;
309
310    if (index >= count)
311        return;
312
313    haveUpdated();
314    oldObject = array[index];
315
316    count--;
317    for (i = index; i < count; i++)
318        array[i] = array[i+1];
319
320    oldObject->taggedRelease(OSTypeID(OSCollection));
321}
322
323bool OSArray::isEqualTo(const OSArray *anArray) const
324{
325    unsigned int i;
326
327    if ( this == anArray )
328        return true;
329
330    if ( count != anArray->getCount() )
331        return false;
332
333    for ( i = 0; i < count; i++ ) {
334        if ( !array[i]->isEqualTo(anArray->getObject(i)) )
335            return false;
336    }
337
338    return true;
339}
340
341bool OSArray::isEqualTo(const OSMetaClassBase *anObject) const
342{
343    OSArray *otherArray;
344
345    otherArray = OSDynamicCast(OSArray, anObject);
346    if ( otherArray )
347        return isEqualTo(otherArray);
348    else
349        return false;
350}
351
352OSObject *OSArray::getObject(unsigned int index) const
353{
354    if (index >= count)
355        return 0;
356    else
357        return (OSObject *) (const_cast<OSMetaClassBase *>(array[index]));
358}
359
360OSObject *OSArray::getLastObject() const
361{
362    if (count == 0)
363        return 0;
364    else
365        return ( OSObject *) (const_cast<OSMetaClassBase *>(array[count - 1]));
366}
367
368unsigned int OSArray::getNextIndexOfObject(const OSMetaClassBase * anObject,
369                                            unsigned int index) const
370{
371    while ((index < count) && (array[index] != anObject))
372        index++;
373    if (index >= count)
374        index = (unsigned int)-1;
375    return index;
376}
377
378unsigned int OSArray::iteratorSize() const
379{
380    return sizeof(unsigned int);
381}
382
383bool OSArray::initIterator(void *inIterator) const
384{
385    unsigned int *iteratorP = (unsigned int *) inIterator;
386
387    *iteratorP = 0;
388    return true;
389}
390
391bool OSArray::getNextObjectForIterator(void *inIterator, OSObject **ret) const
392{
393    unsigned int *iteratorP = (unsigned int *) inIterator;
394    unsigned int index = (*iteratorP)++;
395
396    if (index < count) {
397        *ret = (OSObject *)(const_cast<OSMetaClassBase *> (array[index]));
398        return true;
399    }
400    else {
401        *ret = 0;
402        return false;
403    }
404}
405
406bool OSArray::serialize(OSSerialize *s) const
407{
408    if (s->previouslySerialized(this)) return true;
409
410    if (!s->addXMLStartTag(this, "array")) return false;
411
412    for (unsigned i = 0; i < count; i++) {
413        if (array[i] == NULL || !array[i]->serialize(s)) return false;
414    }
415
416    return s->addXMLEndTag("array");
417}
418
419unsigned OSArray::setOptions(unsigned options, unsigned mask, void *)
420{
421    unsigned old = super::setOptions(options, mask);
422    if ((old ^ options) & mask) {
423
424	// Value changed need to recurse over all of the child collections
425	for ( unsigned i = 0; i < count; i++ ) {
426	    OSCollection *coll = OSDynamicCast(OSCollection, array[i]);
427	    if (coll)
428		coll->setOptions(options, mask);
429	}
430    }
431
432    return old;
433}
434
435OSCollection * OSArray::copyCollection(OSDictionary *cycleDict)
436{
437    bool allocDict = !cycleDict;
438    OSCollection *ret = 0;
439    OSArray *newArray = 0;
440
441    if (allocDict) {
442	cycleDict = OSDictionary::withCapacity(16);
443	if (!cycleDict)
444	    return 0;
445    }
446
447    do {
448	// Check for a cycle
449	ret = super::copyCollection(cycleDict);
450	if (ret)
451	    continue;
452
453	newArray = OSArray::withArray(this);
454	if (!newArray)
455	    continue;
456
457	// Insert object into cycle Dictionary
458	cycleDict->setObject((const OSSymbol *) this, newArray);
459
460	for (unsigned int i = 0; i < count; i++) {
461	    OSCollection *coll =
462		OSDynamicCast(OSCollection, EXT_CAST(newArray->array[i]));
463
464	    if (coll) {
465		OSCollection *newColl = coll->copyCollection(cycleDict);
466		if (!newColl)
467		    goto abortCopy;
468
469		newArray->replaceObject(i, newColl);
470		newColl->release();
471	    };
472	};
473
474	ret = newArray;
475	newArray = 0;
476
477    } while (false);
478
479abortCopy:
480    if (newArray)
481	newArray->release();
482
483    if (allocDict)
484	cycleDict->release();
485
486    return ret;
487}
488
489