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