libkern/libkern/c++/OSOrderedSet.h

   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 #ifndef _OS_OSORDEREDSET_H
  30 #define _OS_OSORDEREDSET_H
  31
  32 #include <libkern/c++/OSCollection.h>
  33 #include <libkern/OSTypes.h>
  34
  35 class OSOffset;
  36
  37 /*!
  38     @class OSOrderedSet
  39     @abstract A collection class for maintaining and sorting a set of OSMetaClassBase derived objects.
  40     @discussion
  41     An instance of OSOrderedSet maintains and sorts a collection of OSMetaClassBase derived objects.  The sorting algorithm is supplied to the instance via the OSOrderFunction.
  42 */
  43 class OSOrderedSet : public OSCollection
  44 {
  45     OSDeclareDefaultStructors(OSOrderedSet)
  46
  47 public:
  48     /*!
  49         @typedef OSOrderFunction
  50         @abstract The sorting function used by the collection to order objects.
  51         @param obj1 An object from the collection.
  52         @param obj2 An object to be compared to obj1.
  53         @param ref The ordering context used by the sorting function as a hint for sorting.
  54         @result Returns a comparison result of the object, a negative value if obj1 > obj2, 0 if obj1 == obj2, and a positive value if obj1 < obj2.
  55      */
  56     typedef SInt32 (*OSOrderFunction)(const OSMetaClassBase * obj1,
  57                                       const OSMetaClassBase * obj2,
  58                                       void * ref );
  59
  60 protected:
  61     struct _Element *   array;
  62     OSOrderFunction     ordering;
  63     void *              orderingRef;
  64     unsigned int        count;
  65     unsigned int        capacity;
  66     unsigned int        capacityIncrement;
  67
  68     struct ExpansionData { };
  69
  70     /*! @var reserved
  71         Reserved for future use.  (Internal use only)  */
  72     ExpansionData *reserved;
  73
  74 protected:
  75     /*
  76      * OSCollectionIterator interfaces.
  77      */
  78     virtual unsigned int iteratorSize() const;
  79     virtual bool initIterator(void *iterator) const;
  80     virtual bool getNextObjectForIterator(void *iterator, OSObject **ret) const;
  81
  82 public:
  83
  84     /*!
  85         @function withCapacity
  86         @abstract A static constructor function for creating and initializing an instance of OSOrderedSet.
  87         @param capacity The initial storage size in number of objects of the set.
  88         @param orderFunc A c-style function which implements the sorting algorithm for the set.
  89         @param orderingRef A ordering context used as a hint for ordering objects within the set.
  90         @result Returns an instance of OSSet, or 0 if a failure occurred.
  91     */
  92     static OSOrderedSet *withCapacity(unsigned int capacity,
  93                                       OSOrderFunction orderFunc = 0,
  94                                       void * orderingRef = 0);
  95
  96     /*!
  97         @function initWithCapacity
  98         @abstract A member function for initializing an instance of OSOrderedSet.
  99         @param capacity The initial storage size in number of objects of the set.
 100         @param orderFunc A c-style function which implements the sorting algorithm for the set.
 101         @param orderingRef A ordering context used as a hint for ordering objects within the set.
 102         @result Returns true if initialization was successful, or false if a failure occurred.
 103     */
 104     virtual bool initWithCapacity(unsigned int capacity,
 105                                   OSOrderFunction orderFunc = 0,
 106                                   void * orderingRef = 0);
 107     /*!
 108         @function free
 109         @abstract A member function to release and deallocate any resources used by the instance of OSOrderedSet.
 110     */
 111     virtual void free();
 112
 113     /*!
 114         @function getCount
 115         @abstract A member function to return the number of objects within the collection.
 116         @result Returns the number of items in the set.
 117     */
 118     virtual unsigned int getCount() const;
 119     /*!
 120         @function getCapacity
 121         @abstract A member function to return the storage capacity of the collection.
 122         @result Returns the total storage capacity of the set.
 123     */
 124     virtual unsigned int getCapacity() const;
 125     /*!
 126         @function getCapacityIncrement
 127         @abstract A member function to get the size by which the collection will grow.
 128         @result Returns the current growth size.
 129     */
 130     virtual unsigned int getCapacityIncrement() const;
 131     /*!
 132         @function setCapacityIncrement
 133         @abstract A member function to set the size by which the collection will grow.
 134         @param increment The new growth factor for the set.
 135         @result Returns new growth size.
 136     */
 137     virtual unsigned int setCapacityIncrement(unsigned increment);
 138
 139     /*!
 140         @function ensureCapacity
 141         @abstract A member function to expand the size of the collection.
 142         @param newCapacity The new size capacity for the collection.
 143         @result Returns new capacity of the set when successful or the old capacity on failure.
 144     */
 145     virtual unsigned int ensureCapacity(unsigned int newCapacity);
 146
 147     /*!
 148         @function flushCollection
 149         @abstract A member function to remove and release all items in the set.
 150     */
 151     virtual void flushCollection();
 152
 153     /*!
 154         @function setObject
 155         @abstract A member function to place an OSMetaClassBase derived object into the set.  The object will be automatically sorted in the set.
 156         @param anObject The object to be placed into the collection.
 157         @result Returns true if object was successfully added to the collection, false otherwise.
 158     */
 159     virtual bool setObject(const OSMetaClassBase *anObject);
 160     /*!
 161         @function setFirstObject
 162         @abstract A member function to place an OSMetaClassBase derived object order it first in the set.
 163         @param anObject The object to be placed into the collection.
 164         @result Returns true if object was successfully added to the collection, false otherwise.
 165     */
 166     virtual bool setFirstObject(const OSMetaClassBase *anObject);
 167     /*!
 168         @function setLastObject
 169         @abstract A member function to place an OSMetaClassBase derived object order it last in the set.
 170         @param anObject The object to be placed into the collection.
 171         @result Returns true if object was successfully added to the collection, false otherwise.
 172     */
 173     virtual bool setLastObject(const OSMetaClassBase *anObject);
 174
 175     /*!
 176         @function removeObject
 177         @abstract A member function to remove and release an object in the set.
 178         @param anObject The object to remove from the set.
 179     */
 180     virtual void removeObject(const OSMetaClassBase *anObject);
 181
 182     /*!
 183         @function containsObject
 184         @abstract A member function to query the set for the presence of a particular object.
 185         @param anObject The object to be located.
 186         @result Returns true if the object is present in the set, false otherwise.
 187     */
 188     virtual bool containsObject(const OSMetaClassBase *anObject) const;
 189     /*!
 190         @function member
 191         @abstract A member function to query the set for the presence of a particular object.
 192         @param anObject The object to be located.
 193         @result Returns true if the object is present in the set, false otherwise.
 194     */
 195     virtual bool member(const OSMetaClassBase *anObject) const;
 196
 197     /*!
 198         @function getFirstObject
 199         @abstract A member function to return the first object in the set.
 200         @result Returns the object ordered first in the set or 0 if none exist.
 201     */
 202     virtual OSObject *getFirstObject() const;
 203     /*!
 204         @function getLastObject
 205         @abstract A member function to return the last object in the set.
 206         @result Returns the object ordered last in the set or 0 if none exist.
 207     */
 208     virtual OSObject *getLastObject() const;
 209
 210     /*!
 211         @function orderObject
 212         @abstract A member function to return the ordering value of an object.
 213         @param anObject The object to be queried.
 214         @result Returns the ordering value for an object.
 215     */
 216     virtual SInt32 orderObject( const OSMetaClassBase * anObject );
 217
 218     /*!
 219         @function setObject
 220         @abstract A member function to place an object into the set at a particular index.
 221         @param index The index in the set to place the object.
 222         @param anObject The object to be placed into the set.
 223         @result Returns true if the object was successfully placed into the collection, false otherwise.
 224     */
 225     virtual bool setObject(unsigned int index, const OSMetaClassBase *anObject);
 226     /*!
 227         @function getObject
 228         @abstract A member function to return a reference to an object at a particular index.
 229         @param index The index into the set.
 230         @result Returns a reference to the object at the given index, 0 if none exist at that location.
 231     */
 232     virtual OSObject *getObject( unsigned int index) const;
 233     /*!
 234         @function getOrderingRef
 235         @abstract A member function to return a the ordering context.
 236         @result Returns the ordering context, or NULL if none exist.
 237     */
 238     virtual void *getOrderingRef();
 239
 240     /*!
 241         @function isEqualTo
 242         @abstract A member function to test the equality between an OSOrderedSet object and the receiver.
 243         @param anOrderedSet The OSOrderedSet object to be compared against the receiver.
 244         @result Returns true if the two objects are equivalent, false otherwise.
 245     */
 246     virtual bool isEqualTo(const OSOrderedSet *anOrderedSet) const;
 247     /*!
 248         @function isEqualTo
 249         @abstract A member function to test the equality between an arbitrary OSMetaClassBase derived object and the receiver.
 250         @param anObject The OSMetaClassBase derived object to be compared against the receiver.
 251         @result Returns true if the two objects are equivalent, false otherwise.
 252     */
 253     virtual bool isEqualTo(const OSMetaClassBase *anObject) const;
 254
 255
 256     /*!
 257         @function setOptions
 258         @abstract This function is used to recursively set option bits in this set and all child collections.
 259         @param options Set the (options & mask) bits.
 260         @param mask The mask of bits which need to be set, 0 to get the current value.
 261         @result The options before the set operation, NB setOptions(?,0) returns the current value of this collection.
 262      */
 263     virtual unsigned setOptions(unsigned options, unsigned mask, void * = 0);
 264
 265     /*!
 266         @function copyCollection
 267         @abstract Do a deep copy of this ordered set and its collections.
 268         @discussion This function copies this set and all included collections recursively.  Objects that don't derive from OSContainter are NOT copied, that is objects like OSString and OSData.
 269         @param cycleDict Is a dictionary of all of the collections that have been, to start the copy at the top level just leave this field 0.
 270         @result The newly copied collecton or 0 if insufficient memory
 271     */
 272     OSCollection *copyCollection(OSDictionary *cycleDict = 0);
 273
 274     OSMetaClassDeclareReservedUnused(OSOrderedSet, 0);
 275     OSMetaClassDeclareReservedUnused(OSOrderedSet, 1);
 276     OSMetaClassDeclareReservedUnused(OSOrderedSet, 2);
 277     OSMetaClassDeclareReservedUnused(OSOrderedSet, 3);
 278     OSMetaClassDeclareReservedUnused(OSOrderedSet, 4);
 279     OSMetaClassDeclareReservedUnused(OSOrderedSet, 5);
 280     OSMetaClassDeclareReservedUnused(OSOrderedSet, 6);
 281     OSMetaClassDeclareReservedUnused(OSOrderedSet, 7);
 282 };
 283
 284 #endif /* ! _OS_OSORDEREDSET_H */