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 | |
29 | #define IOKIT_ENABLE_SHARED_PTR |
30 | |
31 | #include <libkern/c++/OSDictionary.h> |
32 | #include <libkern/c++/OSLib.h> |
33 | #include <libkern/c++/OSOrderedSet.h> |
34 | #include <libkern/c++/OSSharedPtr.h> |
35 | #include <os/cpp_util.h> |
36 | |
37 | #define super OSCollection |
38 | |
39 | OSDefineMetaClassAndStructors(OSOrderedSet, OSCollection) |
40 | OSMetaClassDefineReservedUnused(OSOrderedSet, 0); |
41 | OSMetaClassDefineReservedUnused(OSOrderedSet, 1); |
42 | OSMetaClassDefineReservedUnused(OSOrderedSet, 2); |
43 | OSMetaClassDefineReservedUnused(OSOrderedSet, 3); |
44 | OSMetaClassDefineReservedUnused(OSOrderedSet, 4); |
45 | OSMetaClassDefineReservedUnused(OSOrderedSet, 5); |
46 | OSMetaClassDefineReservedUnused(OSOrderedSet, 6); |
47 | OSMetaClassDefineReservedUnused(OSOrderedSet, 7); |
48 | |
49 | |
50 | struct _Element { |
51 | OSTaggedPtr<const OSMetaClassBase> obj; |
52 | }; |
53 | |
54 | #define EXT_CAST(obj) \ |
55 | reinterpret_cast<OSObject *>(const_cast<OSMetaClassBase *>(obj)) |
56 | |
57 | bool |
58 | OSOrderedSet:: |
59 | initWithCapacity(unsigned int inCapacity, |
60 | OSOrderFunction inOrdering, void *inOrderingRef) |
61 | { |
62 | if (!super::init()) { |
63 | return false; |
64 | } |
65 | |
66 | if (inCapacity > (UINT_MAX / sizeof(_Element))) { |
67 | return false; |
68 | } |
69 | |
70 | array = kallocp_type_container(_Element, &inCapacity, Z_WAITOK_ZERO); |
71 | if (!array) { |
72 | return false; |
73 | } |
74 | |
75 | count = 0; |
76 | capacity = inCapacity; |
77 | capacityIncrement = (inCapacity)? inCapacity : 16; |
78 | ordering = inOrdering; |
79 | orderingRef = inOrderingRef; |
80 | |
81 | OSCONTAINER_ACCUMSIZE(sizeof(_Element) * inCapacity); |
82 | |
83 | return true; |
84 | } |
85 | |
86 | OSSharedPtr<OSOrderedSet> |
87 | OSOrderedSet:: |
88 | withCapacity(unsigned int capacity, |
89 | OSOrderFunction ordering, void * orderingRef) |
90 | { |
91 | auto me = OSMakeShared<OSOrderedSet>(); |
92 | |
93 | if (me && !me->initWithCapacity(inCapacity: capacity, inOrdering: ordering, inOrderingRef: orderingRef)) { |
94 | return nullptr; |
95 | } |
96 | |
97 | return me; |
98 | } |
99 | |
100 | static SInt32 |
101 | OSOrderedSetBlockToFunc(const OSMetaClassBase * obj1, |
102 | const OSMetaClassBase * obj2, |
103 | void * context) |
104 | { |
105 | OSOrderedSet::OSOrderBlock ordering = (typeof(ordering))context; |
106 | |
107 | return ordering(obj1, obj2); |
108 | } |
109 | |
110 | |
111 | OSSharedPtr<OSOrderedSet> |
112 | OSOrderedSet::withCapacity(unsigned int capacity, OSOrderBlock ordering) |
113 | { |
114 | auto me = OSMakeShared<OSOrderedSet>(); |
115 | |
116 | if (me && !me->initWithCapacity(inCapacity: capacity, inOrdering: &OSOrderedSetBlockToFunc, inOrderingRef: ordering)) { |
117 | return nullptr; |
118 | } |
119 | |
120 | return me; |
121 | } |
122 | |
123 | void |
124 | OSOrderedSet::free() |
125 | { |
126 | (void) super::setOptions(options: 0, mask: kImmutable); |
127 | flushCollection(); |
128 | |
129 | if (array) { |
130 | kfree_type(_Element, capacity, array); |
131 | OSCONTAINER_ACCUMSIZE( -(sizeof(_Element) * capacity)); |
132 | } |
133 | |
134 | super::free(); |
135 | } |
136 | |
137 | unsigned int |
138 | OSOrderedSet::getCount() const |
139 | { |
140 | return count; |
141 | } |
142 | unsigned int |
143 | OSOrderedSet::getCapacity() const |
144 | { |
145 | return capacity; |
146 | } |
147 | unsigned int |
148 | OSOrderedSet::getCapacityIncrement() const |
149 | { |
150 | return capacityIncrement; |
151 | } |
152 | unsigned int |
153 | OSOrderedSet::setCapacityIncrement(unsigned int increment) |
154 | { |
155 | capacityIncrement = (increment)? increment : 16; |
156 | return capacityIncrement; |
157 | } |
158 | |
159 | unsigned int |
160 | OSOrderedSet::ensureCapacity(unsigned int newCapacity) |
161 | { |
162 | _Element *newArray; |
163 | unsigned int finalCapacity; |
164 | |
165 | if (newCapacity <= capacity) { |
166 | return capacity; |
167 | } |
168 | |
169 | // round up |
170 | finalCapacity = (((newCapacity - 1) / capacityIncrement) + 1) |
171 | * capacityIncrement; |
172 | if (finalCapacity < newCapacity) { |
173 | return capacity; |
174 | } |
175 | |
176 | newArray = kreallocp_type_container(_Element, array, |
177 | capacity, &finalCapacity, Z_WAITOK_ZERO); |
178 | if (newArray) { |
179 | OSCONTAINER_ACCUMSIZE(sizeof(_Element) * (finalCapacity - capacity)); |
180 | array = newArray; |
181 | capacity = finalCapacity; |
182 | } |
183 | |
184 | return capacity; |
185 | } |
186 | |
187 | void |
188 | OSOrderedSet::flushCollection() |
189 | { |
190 | unsigned int i; |
191 | |
192 | haveUpdated(); |
193 | |
194 | for (i = 0; i < count; i++) { |
195 | array[i].obj.reset(); |
196 | } |
197 | |
198 | count = 0; |
199 | } |
200 | |
201 | /* internal */ |
202 | bool |
203 | OSOrderedSet::setObject(unsigned int index, const OSMetaClassBase *anObject) |
204 | { |
205 | unsigned int i; |
206 | unsigned int newCount = count + 1; |
207 | |
208 | if ((index > count) || !anObject) { |
209 | return false; |
210 | } |
211 | |
212 | if (containsObject(anObject)) { |
213 | return false; |
214 | } |
215 | |
216 | // do we need more space? |
217 | if (newCount > capacity && newCount > ensureCapacity(newCapacity: newCount)) { |
218 | return false; |
219 | } |
220 | |
221 | haveUpdated(); |
222 | if (index != count) { |
223 | for (i = count; i > index; i--) { |
224 | array[i] = os::move(t&: array[i - 1]); |
225 | } |
226 | } |
227 | array[index].obj.reset(p: anObject, OSRetain); |
228 | count++; |
229 | |
230 | return true; |
231 | } |
232 | |
233 | bool |
234 | OSOrderedSet::setObject(unsigned int index, OSSharedPtr<const OSMetaClassBase> const& anObject) |
235 | { |
236 | return setObject(index, anObject: anObject.get()); |
237 | } |
238 | |
239 | bool |
240 | OSOrderedSet::setFirstObject(const OSMetaClassBase *anObject) |
241 | { |
242 | return setObject(index: 0, anObject); |
243 | } |
244 | |
245 | bool |
246 | OSOrderedSet::setFirstObject(OSSharedPtr<const OSMetaClassBase> const& anObject) |
247 | { |
248 | return setFirstObject(anObject.get()); |
249 | } |
250 | |
251 | bool |
252 | OSOrderedSet::setLastObject(const OSMetaClassBase *anObject) |
253 | { |
254 | return setObject( index: count, anObject); |
255 | } |
256 | |
257 | bool |
258 | OSOrderedSet::setLastObject(OSSharedPtr<const OSMetaClassBase> const& anObject) |
259 | { |
260 | return setLastObject(anObject.get()); |
261 | } |
262 | |
263 | |
264 | #define ORDER(obj1, obj2) \ |
265 | (ordering ? ((*ordering)( (const OSObject *) obj1, (const OSObject *) obj2, orderingRef)) : 0) |
266 | |
267 | bool |
268 | OSOrderedSet::setObject(const OSMetaClassBase *anObject ) |
269 | { |
270 | unsigned int i; |
271 | |
272 | // queue it behind those with same priority |
273 | for (i = 0; |
274 | (i < count) && (ORDER(array[i].obj.get(), anObject) >= 0); |
275 | i++) { |
276 | } |
277 | |
278 | return setObject(index: i, anObject); |
279 | } |
280 | |
281 | bool |
282 | OSOrderedSet::setObject(OSSharedPtr<const OSMetaClassBase> const& anObject) |
283 | { |
284 | return setObject(anObject.get()); |
285 | } |
286 | |
287 | void |
288 | OSOrderedSet::removeObject(const OSMetaClassBase *anObject) |
289 | { |
290 | bool deleted = false; |
291 | unsigned int i; |
292 | |
293 | for (i = 0; i < count; i++) { |
294 | if (deleted) { |
295 | array[i - 1] = os::move(t&: array[i]); |
296 | } else if (array[i].obj == anObject) { |
297 | deleted = true; |
298 | haveUpdated(); // Pity we can't flush the log |
299 | array[i].obj.reset(); |
300 | } |
301 | } |
302 | |
303 | if (deleted) { |
304 | count--; |
305 | } |
306 | } |
307 | |
308 | void |
309 | OSOrderedSet::removeObject(OSSharedPtr<const OSMetaClassBase> const& anObject) |
310 | { |
311 | return removeObject(anObject: anObject.get()); |
312 | } |
313 | |
314 | bool |
315 | OSOrderedSet::containsObject(const OSMetaClassBase *anObject) const |
316 | { |
317 | return anObject && member(anObject); |
318 | } |
319 | |
320 | bool |
321 | OSOrderedSet::member(const OSMetaClassBase *anObject) const |
322 | { |
323 | unsigned int i; |
324 | |
325 | for (i = 0; |
326 | (i < count) && (array[i].obj != anObject); |
327 | i++) { |
328 | } |
329 | |
330 | return i < count; |
331 | } |
332 | |
333 | /* internal */ |
334 | OSObject * |
335 | OSOrderedSet::getObject( unsigned int index ) const |
336 | { |
337 | if (index >= count) { |
338 | return NULL; |
339 | } |
340 | |
341 | return const_cast<OSObject *>((const OSObject *) array[index].obj.get()); |
342 | } |
343 | |
344 | OSObject * |
345 | OSOrderedSet::getFirstObject() const |
346 | { |
347 | if (count) { |
348 | return const_cast<OSObject *>((const OSObject *) array[0].obj.get()); |
349 | } else { |
350 | return NULL; |
351 | } |
352 | } |
353 | |
354 | OSObject * |
355 | OSOrderedSet::getLastObject() const |
356 | { |
357 | if (count) { |
358 | return const_cast<OSObject *>((const OSObject *) array[count - 1].obj.get()); |
359 | } else { |
360 | return NULL; |
361 | } |
362 | } |
363 | |
364 | SInt32 |
365 | OSOrderedSet::orderObject( const OSMetaClassBase * anObject ) |
366 | { |
367 | return ORDER( anObject, NULL ); |
368 | } |
369 | |
370 | void * |
371 | OSOrderedSet::getOrderingRef() |
372 | { |
373 | return orderingRef; |
374 | } |
375 | |
376 | bool |
377 | OSOrderedSet::isEqualTo(const OSOrderedSet *anOrderedSet) const |
378 | { |
379 | unsigned int i; |
380 | |
381 | if (this == anOrderedSet) { |
382 | return true; |
383 | } |
384 | |
385 | if (count != anOrderedSet->getCount()) { |
386 | return false; |
387 | } |
388 | |
389 | for (i = 0; i < count; i++) { |
390 | if (!array[i].obj->isEqualTo(anObject: anOrderedSet->getObject(index: i))) { |
391 | return false; |
392 | } |
393 | } |
394 | |
395 | return true; |
396 | } |
397 | |
398 | bool |
399 | OSOrderedSet::isEqualTo(const OSMetaClassBase *anObject) const |
400 | { |
401 | OSOrderedSet *oSet; |
402 | |
403 | oSet = OSDynamicCast(OSOrderedSet, anObject); |
404 | if (oSet) { |
405 | return isEqualTo(anOrderedSet: oSet); |
406 | } else { |
407 | return false; |
408 | } |
409 | } |
410 | |
411 | unsigned int |
412 | OSOrderedSet::iteratorSize() const |
413 | { |
414 | return sizeof(unsigned int); |
415 | } |
416 | |
417 | bool |
418 | OSOrderedSet::initIterator(void *inIterator) const |
419 | { |
420 | unsigned int *iteratorP = (unsigned int *) inIterator; |
421 | |
422 | *iteratorP = 0; |
423 | return true; |
424 | } |
425 | |
426 | bool |
427 | OSOrderedSet:: |
428 | getNextObjectForIterator(void *inIterator, OSObject **ret) const |
429 | { |
430 | unsigned int *iteratorP = (unsigned int *) inIterator; |
431 | unsigned int index = (*iteratorP)++; |
432 | |
433 | if (index < count) { |
434 | *ret = const_cast<OSObject *>((const OSObject *) array[index].obj.get()); |
435 | } else { |
436 | *ret = NULL; |
437 | } |
438 | |
439 | return *ret != NULL; |
440 | } |
441 | |
442 | |
443 | unsigned |
444 | OSOrderedSet::setOptions(unsigned options, unsigned mask, void *) |
445 | { |
446 | unsigned old = super::setOptions(options, mask); |
447 | if ((old ^ options) & mask) { |
448 | // Value changed need to recurse over all of the child collections |
449 | for (unsigned i = 0; i < count; i++) { |
450 | OSCollection *coll = OSDynamicCast(OSCollection, array[i].obj.get()); |
451 | if (coll) { |
452 | coll->setOptions(options, mask); |
453 | } |
454 | } |
455 | } |
456 | |
457 | return old; |
458 | } |
459 | |
460 | OSSharedPtr<OSCollection> |
461 | OSOrderedSet::copyCollection(OSDictionary *cycleDict) |
462 | { |
463 | OSSharedPtr<OSDictionary> ourCycleDict; |
464 | OSSharedPtr<OSCollection> ret; |
465 | OSSharedPtr<OSOrderedSet> newSet; |
466 | |
467 | if (!cycleDict) { |
468 | ourCycleDict = OSDictionary::withCapacity(capacity: 16); |
469 | if (!ourCycleDict) { |
470 | return nullptr; |
471 | } |
472 | cycleDict = ourCycleDict.get(); |
473 | } |
474 | |
475 | do { |
476 | // Check for a cycle |
477 | ret = super::copyCollection(cycleDict); |
478 | if (ret) { |
479 | continue; |
480 | } |
481 | |
482 | // Duplicate the set with no contents |
483 | newSet = OSOrderedSet::withCapacity(capacity, ordering, orderingRef); |
484 | if (!newSet) { |
485 | continue; |
486 | } |
487 | |
488 | // Insert object into cycle Dictionary |
489 | cycleDict->setObject(aKey: (const OSSymbol *) this, anObject: newSet.get()); |
490 | |
491 | newSet->capacityIncrement = capacityIncrement; |
492 | |
493 | // Now copy over the contents to the new duplicate |
494 | for (unsigned int i = 0; i < count; i++) { |
495 | OSObject *obj = EXT_CAST(array[i].obj.get()); |
496 | OSCollection *coll = OSDynamicCast(OSCollection, obj); |
497 | if (coll) { |
498 | OSSharedPtr<OSCollection> newColl = coll->copyCollection(cycleDict); |
499 | if (newColl) { |
500 | obj = newColl.get(); // Rely on cycleDict ref for a bit |
501 | } else { |
502 | return ret; |
503 | } |
504 | } |
505 | |
506 | newSet->setLastObject(obj); |
507 | } |
508 | |
509 | ret = os::move(t&: newSet); |
510 | } while (false); |
511 | |
512 | return ret; |
513 | } |
514 | |