libkern/libkern/c++/OSOrderedSet.h

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