![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to OSOrderedSet.cpp CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / XNU / libkern / c++|
Return to OSOrderedSet.cpp CVS log | Up to [Apple XNU] / XNU / libkern / c++ |
1.1 root 1: /*
2: * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * The contents of this file constitute Original Code as defined in and
7: * are subject to the Apple Public Source License Version 1.1 (the
8: * "License"). You may not use this file except in compliance with the
9: * License. Please obtain a copy of the License at
10: * http://www.apple.com/publicsource and read it before using this file.
11: *
12: * This Original Code and all software distributed under the License are
13: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
14: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
15: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
16: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
17: * License for the specific language governing rights and limitations
18: * under the License.
19: *
20: * @APPLE_LICENSE_HEADER_END@
21: */
22:
23: #include <libkern/c++/OSOrderedSet.h>
24: #include <libkern/c++/OSLib.h>
25:
26: #define super OSCollection
27:
28: OSDefineMetaClassAndStructors(OSOrderedSet, OSCollection)
29:
30: #ifdef DEBUG
31: extern "C" {
32: extern int debug_container_malloc_size;
33: };
34: #define ACCUMSIZE(s) do { debug_container_malloc_size += (s); } while(0)
35: #else
36: #define ACCUMSIZE(s)
37: #endif
38:
39: struct _Element {
40: OSObject * obj;
41: // unsigned int pri;
42: };
43:
44:
45: bool OSOrderedSet::initWithCapacity(unsigned int inCapacity,
46: OSOrderFunction ordering, void * orderingRef)
47: {
48: int size;
49:
50: if (!super::init())
51: return false;
52:
53: size = sizeof(_Element) * inCapacity;
54: array = (_Element *) kalloc(size);
55: if (!array)
56: return false;
57:
58: count = 0;
59: capacity = inCapacity;
60: capacityIncrement = capacity;
61: this->ordering = ordering;
62: this->orderingRef = orderingRef;
63:
64: bzero(array, size);
65: ACCUMSIZE(size);
66:
67: return this;
68: }
69:
70: OSOrderedSet * OSOrderedSet::withCapacity(unsigned int capacity,
71: OSOrderFunction ordering, void * orderingRef)
72: {
73: OSOrderedSet *me = new OSOrderedSet;
74:
75: if (me && !me->initWithCapacity(capacity, ordering, orderingRef)) {
76: me->free();
77: me = 0;
78: }
79:
80: return me;
81: }
82:
83: void OSOrderedSet::free()
84: {
85: flushCollection();
86:
87: if (array) {
88: kfree((vm_offset_t)array, sizeof(_Element) * capacity);
89: ACCUMSIZE( -(sizeof(_Element) * capacity) );
90: }
91:
92: super::free();
93: }
94:
95: unsigned int OSOrderedSet::getCount() const { return count; }
96: unsigned int OSOrderedSet::getCapacity() const { return capacity; }
97: unsigned int OSOrderedSet::getCapacityIncrement() const
98: { return capacityIncrement; }
99: unsigned int OSOrderedSet::setCapacityIncrement(unsigned int increment)
100: {
101: return capacityIncrement = increment;
102: }
103:
104: unsigned int OSOrderedSet::ensureCapacity(unsigned int newCapacity)
105: {
106: _Element *newArray;
107: int oldSize, newSize;
108:
109: if (!capacityIncrement || newCapacity <= capacity)
110: return capacity;
111:
112: // round up
113: newCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
114: * capacityIncrement;
115: newSize = sizeof(_Element) * newCapacity;
116:
117: newArray = (_Element *) kalloc(newSize);
118: if (newArray) {
119: oldSize = sizeof(_Element) * capacity;
120:
121: ACCUMSIZE(newSize - oldSize);
122:
123: bcopy(array, newArray, oldSize);
124: bzero(&newArray[capacity], newSize - oldSize);
125: kfree((vm_offset_t)array, oldSize);
126: array = newArray;
127: capacity = newCapacity;
128: }
129:
130: return capacity;
131: }
132:
133: void OSOrderedSet::flushCollection()
134: {
135: unsigned int i;
136:
137: haveUpdated();
138:
139: for (i = 0; i < count; i++)
140: array[i].obj->release();
141:
142: count = 0;
143: }
144:
145: /* internal */
146: bool OSOrderedSet::setObject(unsigned int index, OSObject *anObject)
147: {
148: unsigned int i;
149: unsigned int newCount = count + 1;
150:
151: if ((index > count) || !anObject)
152: return false;
153:
154: if (containsObject(anObject))
155: return false;
156:
157: // do we need more space?
158: if (newCount > capacity && newCount > ensureCapacity(newCount))
159: return false;
160:
161: haveUpdated();
162: if (index != count) {
163: for (i = count; i > index; i--)
164: array[i] = array[i-1];
165: }
166: array[index].obj = anObject;
167: // array[index].pri = pri;
168: anObject->retain();
169: count++;
170:
171: return true;
172: }
173:
174:
175: bool OSOrderedSet::setFirstObject(OSObject *anObject)
176: {
177: return( setObject(0, anObject));
178: }
179:
180: bool OSOrderedSet::setLastObject(OSObject *anObject)
181: {
182: return( setObject( count, anObject));
183: }
184:
185:
186: #define ORDER(obj1,obj2) \
187: (ordering ? ((*ordering)( obj1, obj2, orderingRef)) : 0)
188:
189: bool OSOrderedSet::setObject(OSObject *anObject )
190: {
191: unsigned int i;
192:
193: // queue it behind those with same priority
194: for( i = 0;
195: (i < count) && (ORDER(array[i].obj, anObject) >= 0);
196: i++ ) {}
197:
198: return( setObject(i, anObject));
199: }
200:
201: void OSOrderedSet::removeObject(OSObject *anObject)
202: {
203: bool deleted = false;
204: unsigned int i;
205:
206: for (i = 0; i < count; i++) {
207:
208: if( deleted)
209: array[i-1] = array[i];
210: else if( (array[i].obj == anObject)) {
211: array[i].obj->release();
212: deleted = true;
213: }
214: }
215:
216: if( deleted) {
217: count--;
218: haveUpdated();
219: }
220: }
221:
222: bool OSOrderedSet::containsObject(const OSObject *anObject) const
223: {
224: return anObject && member(anObject);
225: }
226:
227: bool OSOrderedSet::member(const OSObject *anObject) const
228: {
229: unsigned int i;
230:
231: for( i = 0;
232: (i < count) && (array[i].obj != anObject);
233: i++ ) {}
234:
235: return( i < count);
236: }
237:
238: /* internal */
239: OSObject *OSOrderedSet::getObject( unsigned int index ) const
240: {
241: if (index >= count)
242: return 0;
243:
244: // if( pri)
245: // *pri = array[index].pri;
246:
247: return( array[index].obj );
248: }
249:
250: OSObject *OSOrderedSet::getFirstObject() const
251: {
252: if( count)
253: return( array[0].obj );
254: else
255: return( 0 );
256: }
257:
258: OSObject *OSOrderedSet::getLastObject() const
259: {
260: if( count)
261: return( array[count-1].obj );
262: else
263: return( 0 );
264: }
265:
266: SInt32 OSOrderedSet::orderObject( OSObject * anObject )
267: {
268: return( ORDER( anObject, 0 ));
269: }
270:
271: void *OSOrderedSet::getOrderingRef()
272: {
273: return orderingRef;
274: }
275:
276: bool OSOrderedSet::isEqualTo(OSOrderedSet *anOrderedSet) const
277: {
278: unsigned int i;
279:
280: if ( this == anOrderedSet )
281: return true;
282:
283: if ( count != anOrderedSet->getCount() )
284: return false;
285:
286: for ( i = 0; i < count; i++ ) {
287: if ( !array[i].obj->isEqualTo(anOrderedSet->getObject(i)) )
288: return false;
289: }
290:
291: return true;
292: }
293:
294: bool OSOrderedSet::isEqualTo(const OSObject *anObject) const
295: {
296: OSOrderedSet *oSet;
297:
298: oSet = OSDynamicCast(OSOrderedSet, (OSObject *)anObject);
299: if ( oSet )
300: return isEqualTo(oSet);
301: else
302: return false;
303: }
304:
305: unsigned int OSOrderedSet::iteratorSize() const
306: {
307: return( sizeof(unsigned int));
308: }
309:
310: bool OSOrderedSet::initIterator(void *inIterator) const
311: {
312: unsigned int *iteratorP = (unsigned int *) inIterator;
313:
314: *iteratorP = 0;
315: return true;
316: }
317:
318: bool OSOrderedSet::getNextObjectForIterator(void *inIterator, OSObject **ret) const
319: {
320: unsigned int *iteratorP = (unsigned int *) inIterator;
321: unsigned int index = (*iteratorP)++;
322:
323: if (index < count)
324: *ret = array[index].obj;
325: else
326: *ret = 0;
327:
328: return (*ret != 0);
329: }
330:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.