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