libkern/libkern/c++/OSOrderedSet.h

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