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
39OSDefineMetaClassAndStructors(OSOrderedSet, OSCollection)
40OSMetaClassDefineReservedUnused(OSOrderedSet, 0);
41OSMetaClassDefineReservedUnused(OSOrderedSet, 1);
42OSMetaClassDefineReservedUnused(OSOrderedSet, 2);
43OSMetaClassDefineReservedUnused(OSOrderedSet, 3);
44OSMetaClassDefineReservedUnused(OSOrderedSet, 4);
45OSMetaClassDefineReservedUnused(OSOrderedSet, 5);
46OSMetaClassDefineReservedUnused(OSOrderedSet, 6);
47OSMetaClassDefineReservedUnused(OSOrderedSet, 7);
48
49
50struct _Element {
51 OSTaggedPtr<const OSMetaClassBase> obj;
52};
53
54#define EXT_CAST(obj) \
55 reinterpret_cast<OSObject *>(const_cast<OSMetaClassBase *>(obj))
56
57bool
58OSOrderedSet::
59initWithCapacity(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
86OSSharedPtr<OSOrderedSet>
87OSOrderedSet::
88withCapacity(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
100static SInt32
101OSOrderedSetBlockToFunc(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
111OSSharedPtr<OSOrderedSet>
112OSOrderedSet::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
123void
124OSOrderedSet::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
137unsigned int
138OSOrderedSet::getCount() const
139{
140 return count;
141}
142unsigned int
143OSOrderedSet::getCapacity() const
144{
145 return capacity;
146}
147unsigned int
148OSOrderedSet::getCapacityIncrement() const
149{
150 return capacityIncrement;
151}
152unsigned int
153OSOrderedSet::setCapacityIncrement(unsigned int increment)
154{
155 capacityIncrement = (increment)? increment : 16;
156 return capacityIncrement;
157}
158
159unsigned int
160OSOrderedSet::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
187void
188OSOrderedSet::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 */
202bool
203OSOrderedSet::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
233bool
234OSOrderedSet::setObject(unsigned int index, OSSharedPtr<const OSMetaClassBase> const& anObject)
235{
236 return setObject(index, anObject: anObject.get());
237}
238
239bool
240OSOrderedSet::setFirstObject(const OSMetaClassBase *anObject)
241{
242 return setObject(index: 0, anObject);
243}
244
245bool
246OSOrderedSet::setFirstObject(OSSharedPtr<const OSMetaClassBase> const& anObject)
247{
248 return setFirstObject(anObject.get());
249}
250
251bool
252OSOrderedSet::setLastObject(const OSMetaClassBase *anObject)
253{
254 return setObject( index: count, anObject);
255}
256
257bool
258OSOrderedSet::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
267bool
268OSOrderedSet::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
281bool
282OSOrderedSet::setObject(OSSharedPtr<const OSMetaClassBase> const& anObject)
283{
284 return setObject(anObject.get());
285}
286
287void
288OSOrderedSet::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
308void
309OSOrderedSet::removeObject(OSSharedPtr<const OSMetaClassBase> const& anObject)
310{
311 return removeObject(anObject: anObject.get());
312}
313
314bool
315OSOrderedSet::containsObject(const OSMetaClassBase *anObject) const
316{
317 return anObject && member(anObject);
318}
319
320bool
321OSOrderedSet::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 */
334OSObject *
335OSOrderedSet::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
344OSObject *
345OSOrderedSet::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
354OSObject *
355OSOrderedSet::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
364SInt32
365OSOrderedSet::orderObject( const OSMetaClassBase * anObject )
366{
367 return ORDER( anObject, NULL );
368}
369
370void *
371OSOrderedSet::getOrderingRef()
372{
373 return orderingRef;
374}
375
376bool
377OSOrderedSet::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
398bool
399OSOrderedSet::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
411unsigned int
412OSOrderedSet::iteratorSize() const
413{
414 return sizeof(unsigned int);
415}
416
417bool
418OSOrderedSet::initIterator(void *inIterator) const
419{
420 unsigned int *iteratorP = (unsigned int *) inIterator;
421
422 *iteratorP = 0;
423 return true;
424}
425
426bool
427OSOrderedSet::
428getNextObjectForIterator(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
443unsigned
444OSOrderedSet::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
460OSSharedPtr<OSCollection>
461OSOrderedSet::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