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 |
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 |
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(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 | |
112 | bool |
113 | OSArray::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 | |
124 | OSSharedPtr<OSArray> |
125 | OSArray::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 | |
136 | OSSharedPtr<OSArray> |
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, theCount: count, theCapacity: capacity)) { |
144 | return nullptr; |
145 | } |
146 | |
147 | return me; |
148 | } |
149 | |
150 | OSSharedPtr<OSArray> |
151 | OSArray::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 | |
163 | void |
164 | OSArray::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 | |
181 | unsigned int |
182 | OSArray::getCount() const |
183 | { |
184 | return count; |
185 | } |
186 | unsigned int |
187 | OSArray::getCapacity() const |
188 | { |
189 | return capacity; |
190 | } |
191 | unsigned int |
192 | OSArray::getCapacityIncrement() const |
193 | { |
194 | return capacityIncrement; |
195 | } |
196 | unsigned int |
197 | OSArray::setCapacityIncrement(unsigned int increment) |
198 | { |
199 | capacityIncrement = (increment)? increment : 16; |
200 | |
201 | return capacityIncrement; |
202 | } |
203 | |
204 | unsigned int |
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 |
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 |
247 | OSArray::setObject(const OSMetaClassBase *anObject) |
248 | { |
249 | return setObject(index: count, anObject); |
250 | } |
251 | |
252 | bool |
253 | OSArray::setObject(OSSharedPtr<const OSMetaClassBase> const& anObject) |
254 | { |
255 | return setObject(index: count, anObject); |
256 | } |
257 | |
258 | bool |
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(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 | |
285 | bool |
286 | OSArray::setObject(unsigned int index, OSSharedPtr<const OSMetaClassBase> const& anObject) |
287 | { |
288 | return setObject(index, anObject: anObject.get()); |
289 | } |
290 | |
291 | bool |
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(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 | |
320 | void |
321 | OSArray:: |
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(p: anObject, OSRetain); |
331 | } |
332 | |
333 | void |
334 | OSArray::replaceObject(unsigned int index, OSSharedPtr<const OSMetaClassBase> const& anObject) |
335 | { |
336 | return replaceObject(index, anObject: anObject.get()); |
337 | } |
338 | |
339 | void |
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(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 | |
358 | bool |
359 | 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(anObject: anArray->getObject(index: i))) { |
373 | return false; |
374 | } |
375 | } |
376 | |
377 | return true; |
378 | } |
379 | |
380 | bool |
381 | OSArray::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 | |
393 | OSObject * |
394 | 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 * |
404 | 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 |
414 | 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 |
427 | OSArray::iteratorSize() const |
428 | { |
429 | return sizeof(unsigned int); |
430 | } |
431 | |
432 | bool |
433 | OSArray::initIterator(void *inIterator) const |
434 | { |
435 | unsigned int *iteratorP = (unsigned int *) inIterator; |
436 | |
437 | *iteratorP = 0; |
438 | return true; |
439 | } |
440 | |
441 | bool |
442 | 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 |
457 | OSArray::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 | |
476 | unsigned |
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> |
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(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 | |