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