libkern/libkern/c++/OSOrderedSet.h

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