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    count = 0;
224}
225
226bool OSArray::setObject(const OSMetaClassBase *anObject)
227{
228    return setObject(count, anObject);
229}
230
231bool OSArray::setObject(unsigned int index, const OSMetaClassBase *anObject)
232{
233    unsigned int i;
234    unsigned int newCount = count + 1;
235
236    if ((index > count) || !anObject)
237        return false;
238
239    // do we need more space?
240    if (newCount > capacity && newCount > ensureCapacity(newCount))
241        return false;
242
243    haveUpdated();
244    if (index != count) {
245        for (i = count; i > index; i--)
246            array[i] = array[i-1];
247    }
248    array[index] = anObject;
249    anObject->taggedRetain(OSTypeID(OSCollection));
250    count++;
251
252    return true;
253}
254
255bool OSArray::merge(const OSArray * otherArray)
256{
257    unsigned int otherCount = otherArray->getCount();
258    unsigned int newCount = count + otherCount;
259
260    if (!otherCount)
261        return true;
262
263    // do we need more space?
264    if (newCount > capacity && newCount > ensureCapacity(newCount))
265        return false;
266
267    haveUpdated();
268    for (unsigned int i = 0; i < otherCount; i++) {
269        const OSMetaClassBase *newObject = otherArray->getObject(i);
270
271        array[count++] = newObject;
272        newObject->taggedRetain(OSTypeID(OSCollection));
273    }
274
275    return true;
276}
277
278void OSArray::
279replaceObject(unsigned int index, const OSMetaClassBase *anObject)
280{
281    const OSMetaClassBase *oldObject;
282
283    if ((index >= count) || !anObject)
284        return;
285
286    haveUpdated();
287    oldObject = array[index];
288    array[index] = anObject;
289    anObject->taggedRetain(OSTypeID(OSCollection));
290
291    oldObject->taggedRelease(OSTypeID(OSCollection));
292}
293
294void OSArray::removeObject(unsigned int index)
295{
296    unsigned int i;
297    const OSMetaClassBase *oldObject;
298
299    if (index >= count)
300        return;
301
302    haveUpdated();
303    oldObject = array[index];
304
305    count--;
306    for (i = index; i < count; i++)
307        array[i] = array[i+1];
308
309    oldObject->taggedRelease(OSTypeID(OSCollection));
310}
311
312bool OSArray::isEqualTo(const OSArray *anArray) const
313{
314    unsigned int i;
315
316    if ( this == anArray )
317        return true;
318
319    if ( count != anArray->getCount() )
320        return false;
321
322    for ( i = 0; i < count; i++ ) {
323        if ( !array[i]->isEqualTo(anArray->getObject(i)) )
324            return false;
325    }
326
327    return true;
328}
329
330bool OSArray::isEqualTo(const OSMetaClassBase *anObject) const
331{
332    OSArray *otherArray;
333
334    otherArray = OSDynamicCast(OSArray, anObject);
335    if ( otherArray )
336        return isEqualTo(otherArray);
337    else
338        return false;
339}
340
341OSObject *OSArray::getObject(unsigned int index) const
342{
343    if (index >= count)
344        return 0;
345    else
346        return (OSObject *) (const_cast<OSMetaClassBase *>(array[index]));
347}
348
349OSObject *OSArray::getLastObject() const
350{
351    if (count == 0)
352        return 0;
353    else
354        return ( OSObject *) (const_cast<OSMetaClassBase *>(array[count - 1]));
355}
356
357unsigned int OSArray::getNextIndexOfObject(const OSMetaClassBase * anObject,
358                                            unsigned int index) const
359{
360    while ((index < count) && (array[index] != anObject))
361        index++;
362    if (index >= count)
363        index = (unsigned int)-1;
364    return index;
365}
366
367unsigned int OSArray::iteratorSize() const
368{
369    return sizeof(unsigned int);
370}
371
372bool OSArray::initIterator(void *inIterator) const
373{
374    unsigned int *iteratorP = (unsigned int *) inIterator;
375
376    *iteratorP = 0;
377    return true;
378}
379
380bool OSArray::getNextObjectForIterator(void *inIterator, OSObject **ret) const
381{
382    unsigned int *iteratorP = (unsigned int *) inIterator;
383    unsigned int index = (*iteratorP)++;
384
385    if (index < count) {
386        *ret = (OSObject *)(const_cast<OSMetaClassBase *> (array[index]));
387        return true;
388    }
389    else {
390        *ret = 0;
391        return false;
392    }
393}
394
395bool OSArray::serialize(OSSerialize *s) const
396{
397    if (s->previouslySerialized(this)) return true;
398
399    if (!s->addXMLStartTag(this, "array")) return false;
400
401    for (unsigned i = 0; i < count; i++) {
402        if (!array[i]->serialize(s)) return false;
403    }
404
405    return s->addXMLEndTag("array");
406}
407
408unsigned OSArray::setOptions(unsigned options, unsigned mask, void *)
409{
410    unsigned old = super::setOptions(options, mask);
411    if ((old ^ options) & mask) {
412
413	// Value changed need to recurse over all of the child collections
414	for ( unsigned i = 0; i < count; i++ ) {
415	    OSCollection *coll = OSDynamicCast(OSCollection, array[i]);
416	    if (coll)
417		coll->setOptions(options, mask);
418	}
419    }
420
421    return old;
422}
423
424OSCollection * OSArray::copyCollection(OSDictionary *cycleDict)
425{
426    bool allocDict = !cycleDict;
427    OSCollection *ret = 0;
428    OSArray *newArray = 0;
429
430    if (allocDict) {
431	cycleDict = OSDictionary::withCapacity(16);
432	if (!cycleDict)
433	    return 0;
434    }
435
436    do {
437	// Check for a cycle
438	ret = super::copyCollection(cycleDict);
439	if (ret)
440	    continue;
441
442	newArray = OSArray::withArray(this);
443	if (!newArray)
444	    continue;
445
446	// Insert object into cycle Dictionary
447	cycleDict->setObject((const OSSymbol *) this, newArray);
448
449	for (unsigned int i = 0; i < count; i++) {
450	    OSCollection *coll =
451		OSDynamicCast(OSCollection, EXT_CAST(newArray->array[i]));
452
453	    if (coll) {
454		OSCollection *newColl = coll->copyCollection(cycleDict);
455		if (!newColl)
456		    goto abortCopy;
457
458		newArray->replaceObject(i, newColl);
459		newColl->release();
460	    };
461	};
462
463	ret = newArray;
464	newArray = 0;
465
466    } while (false);
467
468abortCopy:
469    if (newArray)
470	newArray->release();
471
472    if (allocDict)
473	cycleDict->release();
474
475    return ret;
476}
477
478