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