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