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 OSCONTAINER_ACCUMSIZE(sizeof(*array) * inCapacity);
76
77 return true;
78 }
79
80 bool
initWithObjects(const OSObject * objects[],unsigned int theCount,unsigned int theCapacity)81 OSArray::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(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(newObject, OSRetain);
107 }
108
109 return true;
110 }
111
112 bool
initWithArray(const OSArray * anArray,unsigned int theCapacity)113 OSArray::initWithArray(const OSArray *anArray,
114 unsigned int theCapacity)
115 {
116 if (!anArray) {
117 return false;
118 }
119
120 return initWithObjects((const OSObject **) anArray->array,
121 anArray->count, theCapacity);
122 }
123
124 OSSharedPtr<OSArray>
withCapacity(unsigned int capacity)125 OSArray::withCapacity(unsigned int capacity)
126 {
127 OSSharedPtr<OSArray> me = OSMakeShared<OSArray>();
128
129 if (me && !me->initWithCapacity(capacity)) {
130 return nullptr;
131 }
132
133 return me;
134 }
135
136 OSSharedPtr<OSArray>
withObjects(const OSObject * objects[],unsigned int count,unsigned int capacity)137 OSArray::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, count, capacity)) {
144 return nullptr;
145 }
146
147 return me;
148 }
149
150 OSSharedPtr<OSArray>
withArray(const OSArray * array,unsigned int capacity)151 OSArray::withArray(const OSArray *array,
152 unsigned int capacity)
153 {
154 OSSharedPtr<OSArray> me = OSMakeShared<OSArray>();
155
156 if (me && !me->initWithArray(array, capacity)) {
157 return nullptr;
158 }
159
160 return me;
161 }
162
163 void
free()164 OSArray::free()
165 {
166 // Clear immutability - assumes the container is doing the right thing
167 (void) super::setOptions(0, kImmutable);
168
169 flushCollection();
170
171 if (array) {
172 os::destroy(array, array + capacity);
173 kfree_type(ArrayPtrType, capacity, array);
174 OSCONTAINER_ACCUMSIZE( -(sizeof(*array) * capacity));
175 }
176
177 super::free();
178 }
179
180
181 unsigned int
getCount() const182 OSArray::getCount() const
183 {
184 return count;
185 }
186 unsigned int
getCapacity() const187 OSArray::getCapacity() const
188 {
189 return capacity;
190 }
191 unsigned int
getCapacityIncrement() const192 OSArray::getCapacityIncrement() const
193 {
194 return capacityIncrement;
195 }
196 unsigned int
setCapacityIncrement(unsigned int increment)197 OSArray::setCapacityIncrement(unsigned int increment)
198 {
199 capacityIncrement = (increment)? increment : 16;
200
201 return capacityIncrement;
202 }
203
204 unsigned int
ensureCapacity(unsigned int newCapacity)205 OSArray::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
234 void
flushCollection()235 OSArray::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
246 bool
setObject(const OSMetaClassBase * anObject)247 OSArray::setObject(const OSMetaClassBase *anObject)
248 {
249 return setObject(count, anObject);
250 }
251
252 bool
setObject(OSSharedPtr<const OSMetaClassBase> const & anObject)253 OSArray::setObject(OSSharedPtr<const OSMetaClassBase> const& anObject)
254 {
255 return setObject(count, anObject);
256 }
257
258 bool
setObject(unsigned int index,const OSMetaClassBase * anObject)259 OSArray::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(newCount)) {
270 return false;
271 }
272
273 haveUpdated();
274 if (index != count) {
275 for (i = count; i > index; i--) {
276 array[i] = os::move(array[i - 1]);
277 }
278 }
279 array[index].reset(anObject, OSRetain);
280 count++;
281
282 return true;
283 }
284
285 bool
setObject(unsigned int index,OSSharedPtr<const OSMetaClassBase> const & anObject)286 OSArray::setObject(unsigned int index, OSSharedPtr<const OSMetaClassBase> const& anObject)
287 {
288 return setObject(index, anObject.get());
289 }
290
291 bool
merge(const OSArray * otherArray)292 OSArray::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(newCount)) {
307 return false;
308 }
309
310 haveUpdated();
311 for (unsigned int i = 0; i < otherCount; i++) {
312 const OSMetaClassBase *newObject = otherArray->getObject(i);
313
314 array[count++].reset(newObject, OSRetain);
315 }
316
317 return true;
318 }
319
320 void
321 OSArray::
replaceObject(unsigned int index,const OSMetaClassBase * anObject)322 replaceObject(unsigned int index, const OSMetaClassBase *anObject)
323 {
324 if ((index >= count) || !anObject) {
325 return;
326 }
327
328 haveUpdated();
329
330 array[index].reset(anObject, OSRetain);
331 }
332
333 void
replaceObject(unsigned int index,OSSharedPtr<const OSMetaClassBase> const & anObject)334 OSArray::replaceObject(unsigned int index, OSSharedPtr<const OSMetaClassBase> const& anObject)
335 {
336 return replaceObject(index, anObject.get());
337 }
338
339 void
removeObject(unsigned int index)340 OSArray::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(array[index]);
351
352 count--;
353 for (i = index; i < count; i++) {
354 array[i] = os::move(array[i + 1]);
355 }
356 }
357
358 bool
isEqualTo(const OSArray * anArray) const359 OSArray::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(anArray->getObject(i))) {
373 return false;
374 }
375 }
376
377 return true;
378 }
379
380 bool
isEqualTo(const OSMetaClassBase * anObject) const381 OSArray::isEqualTo(const OSMetaClassBase *anObject) const
382 {
383 OSArray *otherArray;
384
385 otherArray = OSDynamicCast(OSArray, anObject);
386 if (otherArray) {
387 return isEqualTo(otherArray);
388 } else {
389 return false;
390 }
391 }
392
393 OSObject *
getObject(unsigned int index) const394 OSArray::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
403 OSObject *
getLastObject() const404 OSArray::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
413 unsigned int
getNextIndexOfObject(const OSMetaClassBase * anObject,unsigned int index) const414 OSArray::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
426 unsigned int
iteratorSize() const427 OSArray::iteratorSize() const
428 {
429 return sizeof(unsigned int);
430 }
431
432 bool
initIterator(void * inIterator) const433 OSArray::initIterator(void *inIterator) const
434 {
435 unsigned int *iteratorP = (unsigned int *) inIterator;
436
437 *iteratorP = 0;
438 return true;
439 }
440
441 bool
getNextObjectForIterator(void * inIterator,OSObject ** ret) const442 OSArray::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
456 bool
serialize(OSSerialize * s) const457 OSArray::serialize(OSSerialize *s) const
458 {
459 if (s->previouslySerialized(this)) {
460 return true;
461 }
462
463 if (!s->addXMLStartTag(this, "array")) {
464 return false;
465 }
466
467 for (unsigned i = 0; i < count; i++) {
468 if (array[i] == NULL || !array[i]->serialize(s)) {
469 return false;
470 }
471 }
472
473 return s->addXMLEndTag("array");
474 }
475
476 unsigned
setOptions(unsigned options,unsigned mask,void *)477 OSArray::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
493 OSSharedPtr<OSCollection>
copyCollection(OSDictionary * cycleDict)494 OSArray::copyCollection(OSDictionary *cycleDict)
495 {
496 OSSharedPtr<OSDictionary> ourCycleDict;
497 OSSharedPtr<OSCollection> ret;
498 OSSharedPtr<OSArray> newArray;
499
500 if (!cycleDict) {
501 ourCycleDict = OSDictionary::withCapacity(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(this);
516 if (!newArray) {
517 continue;
518 }
519
520 // Insert object into cycle Dictionary
521 cycleDict->setObject((const OSSymbol *) this, 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(i, newColl.get());
536 }
537 }
538
539 ret = os::move(newArray);
540 } while (false);
541
542 return ret;
543 }
544