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