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 OSMetaClassDefineReservedUnused(OSOrderedSet, 0); 30 OSMetaClassDefineReservedUnused(OSOrderedSet, 1); 31 OSMetaClassDefineReservedUnused(OSOrderedSet, 2); 32 OSMetaClassDefineReservedUnused(OSOrderedSet, 3); 33 OSMetaClassDefineReservedUnused(OSOrderedSet, 4); 34 OSMetaClassDefineReservedUnused(OSOrderedSet, 5); 35 OSMetaClassDefineReservedUnused(OSOrderedSet, 6); 36 OSMetaClassDefineReservedUnused(OSOrderedSet, 7); 37 38 #if OSALLOCDEBUG 39 extern "C" { 40 extern int debug_container_malloc_size; 41 }; 42 #define ACCUMSIZE(s) do { debug_container_malloc_size += (s); } while(0) 43 #else 44 #define ACCUMSIZE(s) 45 #endif 46 47 struct _Element { 48 const OSMetaClassBase * obj; 49 // unsigned int pri; 50 }; 51 52 53 bool OSOrderedSet:: 54 initWithCapacity(unsigned int inCapacity, 55 OSOrderFunction inOrdering, void *inOrderingRef) 56 { 57 int size; 58 59 if (!super::init()) 60 return false; 61 62 size = sizeof(_Element) * inCapacity; 63 array = (_Element *) kalloc(size); 64 if (!array) 65 return false; 66 67 count = 0; 68 capacity = inCapacity; 69 capacityIncrement = (inCapacity)? inCapacity : 16; 70 ordering = inOrdering; 71 orderingRef = inOrderingRef; 72 73 bzero(array, size); 74 ACCUMSIZE(size); 75 76 return this; 77 } 78 79 OSOrderedSet * OSOrderedSet:: 80 withCapacity(unsigned int capacity, 81 OSOrderFunction ordering, void * orderingRef) 82 { 83 OSOrderedSet *me = new OSOrderedSet; 84 85 if (me && !me->initWithCapacity(capacity, ordering, orderingRef)) { 86 me->free(); 87 me = 0; 88 } 89 90 return me; 91 } 92 93 void OSOrderedSet::free() 94 { 95 flushCollection(); 96 97 if (array) { 98 kfree((vm_offset_t)array, sizeof(_Element) * capacity); 99 ACCUMSIZE( -(sizeof(_Element) * capacity) ); 100 } 101 102 super::free(); 103 } 104 105 unsigned int OSOrderedSet::getCount() const { return count; } 106 unsigned int OSOrderedSet::getCapacity() const { return capacity; } 107 unsigned int OSOrderedSet::getCapacityIncrement() const 108 { return capacityIncrement; } 109 unsigned int OSOrderedSet::setCapacityIncrement(unsigned int increment) 110 { 111 capacityIncrement = (increment)? increment : 16; 112 return capacityIncrement; 113 } 114 115 unsigned int OSOrderedSet::ensureCapacity(unsigned int newCapacity) 116 { 117 _Element *newArray; 118 int oldSize, newSize; 119 120 if (newCapacity <= capacity) 121 return capacity; 122 123 // round up 124 newCapacity = (((newCapacity - 1) / capacityIncrement) + 1) 125 * capacityIncrement; 126 newSize = sizeof(_Element) * newCapacity; 127 128 newArray = (_Element *) kalloc(newSize); 129 if (newArray) { 130 oldSize = sizeof(_Element) * capacity; 131 132 ACCUMSIZE(newSize - oldSize); 133 134 bcopy(array, newArray, oldSize); 135 bzero(&newArray[capacity], newSize - oldSize); 136 kfree((vm_offset_t)array, oldSize); 137 array = newArray; 138 capacity = newCapacity; 139 } 140 141 return capacity; 142 } 143 144 void OSOrderedSet::flushCollection() 145 { 146 unsigned int i; 147 148 haveUpdated(); 149 150 for (i = 0; i < count; i++) 151 array[i].obj->taggedRelease(OSTypeID(OSCollection)); 152 153 count = 0; 154 } 155 156 /* internal */ 157 bool OSOrderedSet::setObject(unsigned int index, const OSMetaClassBase *anObject) 158 { 159 unsigned int i; 160 unsigned int newCount = count + 1; 161 162 if ((index > count) || !anObject) 163 return false; 164 165 if (containsObject(anObject)) 166 return false; 167 168 // do we need more space? 169 if (newCount > capacity && newCount > ensureCapacity(newCount)) 170 return false; 171 172 haveUpdated(); 173 if (index != count) { 174 for (i = count; i > index; i--) 175 array[i] = array[i-1]; 176 } 177 array[index].obj = anObject; 178 // array[index].pri = pri; 179 anObject->taggedRetain(OSTypeID(OSCollection)); 180 count++; 181 182 return true; 183 } 184 185 186 bool OSOrderedSet::setFirstObject(const OSMetaClassBase *anObject) 187 { 188 return( setObject(0, anObject)); 189 } 190 191 bool OSOrderedSet::setLastObject(const OSMetaClassBase *anObject) 192 { 193 return( setObject( count, anObject)); 194 } 195 196 197 #define ORDER(obj1,obj2) \ 198 (ordering ? ((*ordering)( (OSObject *) obj1, (OSObject *) obj2, orderingRef)) : 0) 199 200 bool OSOrderedSet::setObject(const OSMetaClassBase *anObject ) 201 { 202 unsigned int i; 203 204 // queue it behind those with same priority 205 for( i = 0; 206 (i < count) && (ORDER(array[i].obj, anObject) >= 0); 207 i++ ) {} 208 209 return( setObject(i, anObject)); 210 } 211 212 void OSOrderedSet::removeObject(const OSMetaClassBase *anObject) 213 { 214 bool deleted = false; 215 unsigned int i; 216 217 for (i = 0; i < count; i++) { 218 219 if( deleted) 220 array[i-1] = array[i]; 221 else if( (array[i].obj == anObject)) { 222 array[i].obj->taggedRelease(OSTypeID(OSCollection)); 223 deleted = true; 224 } 225 } 226 227 if( deleted) { 228 count--; 229 haveUpdated(); 230 } 231 } 232 233 bool OSOrderedSet::containsObject(const OSMetaClassBase *anObject) const 234 { 235 return anObject && member(anObject); 236 } 237 238 bool OSOrderedSet::member(const OSMetaClassBase *anObject) const 239 { 240 unsigned int i; 241 242 for( i = 0; 243 (i < count) && (array[i].obj != anObject); 244 i++ ) {} 245 246 return( i < count); 247 } 248 249 /* internal */ 250 OSObject *OSOrderedSet::getObject( unsigned int index ) const 251 { 252 if (index >= count) 253 return 0; 254 255 // if( pri) 256 // *pri = array[index].pri; 257 258 return( (OSObject *) array[index].obj ); 259 } 260 261 OSObject *OSOrderedSet::getFirstObject() const 262 { 263 if( count) 264 return( (OSObject *) array[0].obj ); 265 else 266 return( 0 ); 267 } 268 269 OSObject *OSOrderedSet::getLastObject() const 270 { 271 if( count) 272 return( (OSObject *) array[count-1].obj ); 273 else 274 return( 0 ); 275 } 276 277 SInt32 OSOrderedSet::orderObject( const OSMetaClassBase * anObject ) 278 { 279 return( ORDER( anObject, 0 )); 280 } 281 282 void *OSOrderedSet::getOrderingRef() 283 { 284 return orderingRef; 285 } 286 287 bool OSOrderedSet::isEqualTo(const OSOrderedSet *anOrderedSet) const 288 { 289 unsigned int i; 290 291 if ( this == anOrderedSet ) 292 return true; 293 294 if ( count != anOrderedSet->getCount() ) 295 return false; 296 297 for ( i = 0; i < count; i++ ) { 298 if ( !array[i].obj->isEqualTo(anOrderedSet->getObject(i)) ) 299 return false; 300 } 301 302 return true; 303 } 304 305 bool OSOrderedSet::isEqualTo(const OSMetaClassBase *anObject) const 306 { 307 OSOrderedSet *oSet; 308 309 oSet = OSDynamicCast(OSOrderedSet, anObject); 310 if ( oSet ) 311 return isEqualTo(oSet); 312 else 313 return false; 314 } 315 316 unsigned int OSOrderedSet::iteratorSize() const 317 { 318 return( sizeof(unsigned int)); 319 } 320 321 bool OSOrderedSet::initIterator(void *inIterator) const 322 { 323 unsigned int *iteratorP = (unsigned int *) inIterator; 324 325 *iteratorP = 0; 326 return true; 327 } 328 329 bool OSOrderedSet:: 330 getNextObjectForIterator(void *inIterator, OSObject **ret) const 331 { 332 unsigned int *iteratorP = (unsigned int *) inIterator; 333 unsigned int index = (*iteratorP)++; 334 335 if (index < count) 336 *ret = (OSObject *) array[index].obj; 337 else 338 *ret = 0; 339 340 return (*ret != 0); 341 } 342 343