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