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    int size;
64
65    if (!super::init())
66        return false;
67
68    size = sizeof(const OSMetaClassBase *) * inCapacity;
69    array = (const OSMetaClassBase **) kalloc(size);
70    if (!array)
71        return false;
72
73    count = 0;
74    capacity = inCapacity;
75    capacityIncrement = (inCapacity)? inCapacity : 16;
76
77    bzero(array, size);
78    ACCUMSIZE(size);
79
80    return true;
81}
82
83bool OSArray::initWithObjects(const OSObject *objects[],
84                              unsigned int theCount,
85                              unsigned int theCapacity)
86{
87    unsigned int initCapacity;
88
89    if (!theCapacity)
90        initCapacity = theCount;
91    else if (theCount > theCapacity)
92        return false;
93    else
94        initCapacity = theCapacity;
95
96    if (!objects || !initWithCapacity(initCapacity))
97        return false;
98
99    for ( unsigned int i = 0; i < theCount; i++ ) {
100        const OSMetaClassBase *newObject = *objects++;
101
102        if (!newObject)
103            return false;
104
105        array[count++] = newObject;
106        newObject->taggedRetain(OSTypeID(OSCollection));
107    }
108
109    return true;
110}
111
112bool OSArray::initWithArray(const OSArray *anArray,
113                            unsigned int theCapacity)
114{
115    if ( !anArray )
116        return false;
117
118    return initWithObjects((const OSObject **) anArray->array,
119                           anArray->count, theCapacity);
120}
121
122OSArray *OSArray::withCapacity(unsigned int capacity)
123{
124    OSArray *me = new OSArray;
125
126    if (me && !me->initWithCapacity(capacity)) {
127        me->release();
128        return 0;
129    }
130
131    return me;
132}
133
134OSArray *OSArray::withObjects(const OSObject *objects[],
135                              unsigned int count,
136                              unsigned int capacity)
137{
138    OSArray *me = new OSArray;
139
140    if (me && !me->initWithObjects(objects, count, capacity)) {
141        me->release();
142        return 0;
143    }
144
145    return me;
146}
147
148OSArray *OSArray::withArray(const OSArray *array,
149                            unsigned int capacity)
150{
151    OSArray *me = new OSArray;
152
153    if (me && !me->initWithArray(array, capacity)) {
154        me->release();
155        return 0;
156    }
157
158    return me;
159}
160
161void OSArray::free()
162{
163    // Clear immutability - assumes the container is doing the right thing
164    (void) super::setOptions(0, kImmutable);
165
166    flushCollection();
167
168    if (array) {
169        kfree(array, sizeof(const OSMetaClassBase *) * capacity);
170        ACCUMSIZE( -(sizeof(const OSMetaClassBase *) * capacity) );
171    }
172
173    super::free();
174}
175
176
177unsigned int OSArray::getCount() const { return count; }
178unsigned int OSArray::getCapacity() const { return capacity; }
179unsigned int OSArray::getCapacityIncrement() const { return capacityIncrement; }
180unsigned int OSArray::setCapacityIncrement(unsigned int increment)
181{
182    capacityIncrement = (increment)? increment : 16;
183
184    return capacityIncrement;
185}
186
187unsigned int OSArray::ensureCapacity(unsigned int newCapacity)
188{
189    const OSMetaClassBase **newArray;
190    int oldSize, newSize;
191
192    if (newCapacity <= capacity)
193        return capacity;
194
195    // round up
196    newCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
197                * capacityIncrement;
198    newSize = sizeof(const OSMetaClassBase *) * newCapacity;
199
200    newArray = (const OSMetaClassBase **) kalloc(newSize);
201    if (newArray) {
202        oldSize = sizeof(const OSMetaClassBase *) * capacity;
203
204        ACCUMSIZE(newSize - oldSize);
205
206        bcopy(array, newArray, oldSize);
207        bzero(&newArray[capacity], newSize - oldSize);
208        kfree(array, oldSize);
209        array = newArray;
210        capacity = newCapacity;
211    }
212
213    return capacity;
214}
215
216void OSArray::flushCollection()
217{
218    unsigned int i;
219
220    haveUpdated();
221    for (i = 0; i < count; i++) {
222        array[i]->taggedRelease(OSTypeID(OSCollection));
223    }
224    count = 0;
225}
226
227bool OSArray::setObject(const OSMetaClassBase *anObject)
228{
229    return setObject(count, anObject);
230}
231
232bool OSArray::setObject(unsigned int index, const OSMetaClassBase *anObject)
233{
234    unsigned int i;
235    unsigned int newCount = count + 1;
236
237    if ((index > count) || !anObject)
238        return false;
239
240    // do we need more space?
241    if (newCount > capacity && newCount > ensureCapacity(newCount))
242        return false;
243
244    haveUpdated();
245    if (index != count) {
246        for (i = count; i > index; i--)
247            array[i] = array[i-1];
248    }
249    array[index] = anObject;
250    anObject->taggedRetain(OSTypeID(OSCollection));
251    count++;
252
253    return true;
254}
255
256bool OSArray::merge(const OSArray * otherArray)
257{
258    unsigned int otherCount = otherArray->getCount();
259    unsigned int newCount = count + otherCount;
260
261    if (!otherCount)
262        return true;
263
264    // do we need more space?
265    if (newCount > capacity && newCount > ensureCapacity(newCount))
266        return false;
267
268    haveUpdated();
269    for (unsigned int i = 0; i < otherCount; i++) {
270        const OSMetaClassBase *newObject = otherArray->getObject(i);
271
272        array[count++] = newObject;
273        newObject->taggedRetain(OSTypeID(OSCollection));
274    }
275
276    return true;
277}
278
279void OSArray::
280replaceObject(unsigned int index, const OSMetaClassBase *anObject)
281{
282    const OSMetaClassBase *oldObject;
283
284    if ((index >= count) || !anObject)
285        return;
286
287    haveUpdated();
288    oldObject = array[index];
289    array[index] = anObject;
290    anObject->taggedRetain(OSTypeID(OSCollection));
291
292    oldObject->taggedRelease(OSTypeID(OSCollection));
293}
294
295void OSArray::removeObject(unsigned int index)
296{
297    unsigned int i;
298    const OSMetaClassBase *oldObject;
299
300    if (index >= count)
301        return;
302
303    haveUpdated();
304    oldObject = array[index];
305
306    count--;
307    for (i = index; i < count; i++)
308        array[i] = array[i+1];
309
310    oldObject->taggedRelease(OSTypeID(OSCollection));
311}
312
313bool OSArray::isEqualTo(const OSArray *anArray) const
314{
315    unsigned int i;
316
317    if ( this == anArray )
318        return true;
319
320    if ( count != anArray->getCount() )
321        return false;
322
323    for ( i = 0; i < count; i++ ) {
324        if ( !array[i]->isEqualTo(anArray->getObject(i)) )
325            return false;
326    }
327
328    return true;
329}
330
331bool OSArray::isEqualTo(const OSMetaClassBase *anObject) const
332{
333    OSArray *otherArray;
334
335    otherArray = OSDynamicCast(OSArray, anObject);
336    if ( otherArray )
337        return isEqualTo(otherArray);
338    else
339        return false;
340}
341
342OSObject *OSArray::getObject(unsigned int index) const
343{
344    if (index >= count)
345        return 0;
346    else
347        return (OSObject *) (const_cast<OSMetaClassBase *>(array[index]));
348}
349
350OSObject *OSArray::getLastObject() const
351{
352    if (count == 0)
353        return 0;
354    else
355        return ( OSObject *) (const_cast<OSMetaClassBase *>(array[count - 1]));
356}
357
358unsigned int OSArray::getNextIndexOfObject(const OSMetaClassBase * anObject,
359                                            unsigned int index) const
360{
361    while ((index < count) && (array[index] != anObject))
362        index++;
363    if (index >= count)
364        index = (unsigned int)-1;
365    return index;
366}
367
368unsigned int OSArray::iteratorSize() const
369{
370    return sizeof(unsigned int);
371}
372
373bool OSArray::initIterator(void *inIterator) const
374{
375    unsigned int *iteratorP = (unsigned int *) inIterator;
376
377    *iteratorP = 0;
378    return true;
379}
380
381bool OSArray::getNextObjectForIterator(void *inIterator, OSObject **ret) const
382{
383    unsigned int *iteratorP = (unsigned int *) inIterator;
384    unsigned int index = (*iteratorP)++;
385
386    if (index < count) {
387        *ret = (OSObject *)(const_cast<OSMetaClassBase *> (array[index]));
388        return true;
389    }
390    else {
391        *ret = 0;
392        return false;
393    }
394}
395
396bool OSArray::serialize(OSSerialize *s) const
397{
398    if (s->previouslySerialized(this)) return true;
399
400    if (!s->addXMLStartTag(this, "array")) return false;
401
402    for (unsigned i = 0; i < count; i++) {
403        if (!array[i]->serialize(s)) return false;
404    }
405
406    return s->addXMLEndTag("array");
407}
408
409unsigned OSArray::setOptions(unsigned options, unsigned mask, void *)
410{
411    unsigned old = super::setOptions(options, mask);
412    if ((old ^ options) & mask) {
413
414	// Value changed need to recurse over all of the child collections
415	for ( unsigned i = 0; i < count; i++ ) {
416	    OSCollection *coll = OSDynamicCast(OSCollection, array[i]);
417	    if (coll)
418		coll->setOptions(options, mask);
419	}
420    }
421
422    return old;
423}
424
425OSCollection * OSArray::copyCollection(OSDictionary *cycleDict)
426{
427    bool allocDict = !cycleDict;
428    OSCollection *ret = 0;
429    OSArray *newArray = 0;
430
431    if (allocDict) {
432	cycleDict = OSDictionary::withCapacity(16);
433	if (!cycleDict)
434	    return 0;
435    }
436
437    do {
438	// Check for a cycle
439	ret = super::copyCollection(cycleDict);
440	if (ret)
441	    continue;
442
443	newArray = OSArray::withArray(this);
444	if (!newArray)
445	    continue;
446
447	// Insert object into cycle Dictionary
448	cycleDict->setObject((const OSSymbol *) this, newArray);
449
450	for (unsigned int i = 0; i < count; i++) {
451	    OSCollection *coll =
452		OSDynamicCast(OSCollection, EXT_CAST(newArray->array[i]));
453
454	    if (coll) {
455		OSCollection *newColl = coll->copyCollection(cycleDict);
456		if (!newColl)
457		    goto abortCopy;
458
459		newArray->replaceObject(i, newColl);
460		newColl->release();
461	    };
462	};
463
464	ret = newArray;
465	newArray = 0;
466
467    } while (false);
468
469abortCopy:
470    if (newArray)
471	newArray->release();
472
473    if (allocDict)
474	cycleDict->release();
475
476    return ret;
477}
478
479