libkern/libkern/c++/OSOrderedSet.h

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