Drivers, Kernel, & Hardware: Kernel Device Drivers Right arrow

OSOrderedSet

Inherits from:	OSCollection
Declared In:	OSOrderedSet.h

Overview

OSOrderedSet provides an ordered set store of objects.

Discussion

OSOrderedSet is a container for Libkern C++ objects (those derived from OSMetaClassBase, in particular OSObject). Storage and access follow ordered set logic. A given object is stored in the set only once, but you can:

Define a sorting function for automated ordering (upon addition only)
Manually insert new objects in the set (overriding sorting)
Add and remove objects in the set
Test whether the set contains a particular object
Get the object stored at a particular index.

Note that automated ordering is performed only upon addition of objects and depends on the existing objects being properly sorted. There is no function to re-sort the contents of an OSOrderedSet or to change the ordering function. In general, you should either use the one ordered-insertion function, or the indexed-insertion functions, and not mix the two.

As with all Libkern collection classes, OSOrderedSet retains objects added to it, and releases objects removed from it. An OSOrderedSet also grows as necessary to accommodate new objects, unlike Core Foundation collections (it does not, however, shrink).

Use Restrictions

With very few exceptions in the I/O Kit, all Libkern-based C++ classes, functions, and macros are unsafe to use in a primary interrupt context. Consult the I/O Kit documentation related to primary interrupts for more information.

OSOrderedSet provides no concurrency protection; it's up to the usage context to provide any protection necessary. Some portions of the I/O Kit, such as IORegistryEntry, handle synchronization via defined member functions for setting properties.

Functions

containsObject: Checks the ordered set for the presence of an object.
copyCollection: Creates a deep copy of this ordered set and its child collections.
ensureCapacity: Ensures the set has enough space to store the requested number of distinct objects.
flushCollection: Removes and releases all objects within the ordered set.
free: Deallocatesand releases any resources used by the OSOrderedSet instance.
getCapacity: Returns the number of objects the ordered set can store without reallocating.
getCapacityIncrement: Returns the storage increment of the ordered set.
getCount: Returns the current number of objects within the ordered set.
getFirstObject: The object at index 0 in the ordered set if there is one, otherwise NULL.
getLastObject: The last object in the ordered set if there is one, otherwise NULL.
getObject: Gets the object at a particular index.
getOrderingRef: Returns the ordering context the ordered set was created with.
initWithCapacity: Initializes a new instance of OSOrderedSet.
isEqualTo(const OSMetaClassBase *): Tests the equality of an OSOrderedSet against an arbitrary object.
isEqualTo(const OSOrderedSet *): Tests the equality of two OSOrderedSet objects.
member: Checks the ordered set for the presence of an object.
orderObject: Calls the ordered set's order function against a NULL object.
removeObject: Removes an object from the ordered set.
setCapacityIncrement: Sets the storage increment of the ordered set.
setFirstObject: Adds an object to the OSOrderedSet at index 0 if it is not already present.
setLastObject: Adds an object at the end of the OSOrderedSet if it is not already present.
setObject(const OSMetaClassBase *): Adds an object to the OSOrderedSet if it is not already present, storing it in sorted order if there is an order function.
setObject(unsigned int, const OSMetaClassBase *): Adds an object to an OSOrderedSet at a specified index if it is not already present.
setOptions
withCapacity: Creates and initializes an empty OSOrderedSet.

containsObject

Checks the ordered set for the presence of an object.

public

virtual bool containsObject(
    const OSMetaClassBase * anObject) const;

Parameters

anObject: The OSMetaClassBase-derived object to check for in the ordered set.

Return Value

true if anObject is present within the ordered set, false otherwise.

Discussion

Pointer equality is used. This function returns false if passed NULL.

copyCollection

Creates a deep copy of this ordered set and its child collections.

public

OSCollection *copyCollection(
    OSDictionary *cycleDict = 0);

Parameters

cycleDict: A dictionary of all of the collections that have been copied so far, which is used to track circular references. To start the copy at the top level, pass NULL.

Return Value

The newly copied ordered set, with a retain count of 1, or NULL if there is insufficient memory to do the copy.

Discussion

The receiving ordered set, and any collections it contains, recursively, are copied. Objects that are not derived from OSCollection are retained rather than copied.

ensureCapacity

Ensures the set has enough space to store the requested number of distinct objects.

public

virtual unsigned int ensureCapacity(
    unsigned int newCapacity);

Parameters

newCapacity: The total number of distinct objects the ordered set should be able to store.

Return Value

The new capacity of the ordered set, which may be different from the number requested (if smaller, reallocation of storage failed).

Discussion

This function immediately resizes the ordered set, if necessary, to accommodate at least newCapacity distinct objects. If newCapacity is not greater than the current capacity, or if an allocation error occurs, the original capacity is returned.

There is no way to reduce the capacity of an OSOrderedSet.

flushCollection

Removes and releases all objects within the ordered set.

public

virtual void flushCollection();

Discussion

The ordered set's capacity (and therefore direct memory consumption) is not reduced by this function.

free

Deallocatesand releases any resources used by the OSOrderedSet instance.

public

virtual void free();

Discussion

This function should not be called directly; use release instead.

getCapacity

Returns the number of objects the ordered set can store without reallocating.

public

virtual unsigned int getCapacity() const;

Return Value

The number objects the ordered set can store without reallocating.

Discussion

OSOrderedSet objects grow when full to accommodate additional objects. See getCapacityIncrement and ensureCapacity.

getCapacityIncrement

Returns the storage increment of the ordered set.

public

virtual unsigned int getCapacityIncrement() const;

Return Value

The storage increment of the ordered set.

Discussion

An OSOrderedSet allocates storage for objects in multiples of the capacity increment.

getCount

Returns the current number of objects within the ordered set.

public

virtual unsigned int getCount() const;

Return Value

The current number of objects within the ordered set.

getFirstObject

The object at index 0 in the ordered set if there is one, otherwise NULL.

public

virtual OSObject * getFirstObject() const;

Discussion

The returned object will be released if removed from the ordered set; if you plan to store the reference, you should call retain on that object.

getLastObject

The last object in the ordered set if there is one, otherwise NULL.

public

virtual OSObject * getLastObject() const;

Discussion

The returned object will be released if removed from the ordered set; if you plan to store the reference, you should call retain on that object.

getObject

Gets the object at a particular index.

public

virtual OSObject * getObject(
    unsigned int index) const;

Parameters

index: The index into the set.

Return Value

The object at the given index, or NULL if none exists at that location.

Discussion

The returned object will be released if removed from the set; if you plan to store the reference, you should call retain on that object.

getOrderingRef

Returns the ordering context the ordered set was created with.

public

virtual void * getOrderingRef();

Return Value

The ordered set's ordering context, or NULL if it doesn't have one.

initWithCapacity

Initializes a new instance of OSOrderedSet.

public

virtual bool initWithCapacity( 
    unsigned int capacity, 
    OSOrderFunction orderFunc = 0, 
    void *orderingContext = 0);

Parameters

capacity: The initial storage capacity of the new ordered set object.
orderFunc: A C function that implements the sorting algorithm for the set.
orderingContext: An ordering context, which is passed to orderFunc.

Return Value

true on success, false on failure.

Discussion

Not for general use. Use the static instance creation method withCapacity instead.

capacity must be nonzero. The new set will grow as needed to accommodate more key/object pairs (unlike Core Foundation collections, for which the initial capacity is a hard limit).

If orderFunc is provided, it is used by setObject(const OSMetaClassBase *) to determine where to insert a new object. Other object-setting functions ignore ordering.

orderingContext is not retained or otherwise memory-managed by the ordered set. If it needs to be deallocated, you must track references to it and the ordered set in order to deallocate it appropriately. See getOrderingRef.

isEqualTo(const OSMetaClassBase *)

Tests the equality of an OSOrderedSet against an arbitrary object.

public

virtual bool isEqualTo(
    const OSMetaClassBase * anObject) const;

Parameters

anObject: The object being compared against the receiver.

Return Value

true if the two objects are equivalent, false otherwise.

Discussion

An OSOrderedSet object is considered equal to another object if the other object is derived from OSOrderedSet and compares equal as an OSOrderedSet.

isEqualTo(const OSOrderedSet *)

Tests the equality of two OSOrderedSet objects.

public

virtual bool isEqualTo(
    const OSOrderedSet * anOrderedSet) const;

Parameters

anOrderedSet: The ordered set object being compared against the receiver.

Return Value

true if the two sets are equivalent, false otherwise.

Discussion

Two OSOrderedSet objects are considered equal if they have same count and the same object pointer values in the same order.

member

Checks the ordered set for the presence of an object.

public

virtual bool member(
    const OSMetaClassBase * anObject) const;

Parameters

anObject: The OSMetaClassBase-derived object to check for in the ordered set.

Return Value

true if anObject is present within the ordered set, false otherwise.

Discussion

Pointer equality is used. Returns false if passed NULL.

containsObject(const OSMetaClassBase *) checks for NULL before scanning the contents, and is therefore more efficient than this function.

orderObject

Calls the ordered set's order function against a NULL object.

public

virtual SInt32 orderObject(
    const OSMetaClassBase * anObject);

Parameters

anObject: The object to be ordered.

Return Value

The ordering value for the object.

Discussion

This function calls the ordered set's order function with anObject, NULL, and the ordering context (or NULL if none was set), and returns the result of that function.

removeObject

Removes an object from the ordered set.

public

virtual void removeObject(
    const OSMetaClassBase * anObject);

Parameters

anObject: The OSMetaClassBase-derived object to be removed from the ordered set.

Discussion

The object removed from the ordered set is released.

setCapacityIncrement

Sets the storage increment of the ordered set.

public

virtual unsigned int setCapacityIncrement(
    unsigned increment);

Return Value

The new storage increment of the ordered set, which may be different from the number requested.

Discussion

An OSOrderedSet allocates storage for objects in multiples of the capacity increment. Calling this function does not immediately reallocate storage.

setFirstObject

Adds an object to the OSOrderedSet at index 0 if it is not already present.

public

virtual bool setFirstObject(
    const OSMetaClassBase * anObject);

Parameters

anObject: The OSMetaClassBase-derived object to be added to the ordered set.

Return Value

true if anObject was successfully added to the ordered set, false otherwise (including if it was already in the ordered set at any index).

Discussion

The set adds storage to accomodate the new object, if necessary. If successfully added, the object is retained.

This function ignores any ordering function of the ordered set, and can disrupt the automatic sorting mechanism. Only call this function if you are managing the ordered set directly.

A false return value can mean either that anObject is already present in the set, or that a memory allocation failure occurred. If you need to know whether the object is already present, use containsObject(const OSMetaClassBase *).

setLastObject

Adds an object at the end of the OSOrderedSet if it is not already present.

public

virtual bool setLastObject(
    const OSMetaClassBase * anObject);

Parameters

anObject: The OSMetaClassBase-derived object to be added to the ordered set.

Return Value

true if anObject was successfully added to the ordered set, false otherwise (including if it was already in the ordered set at any index).

Discussion

The set adds storage to accomodate the new object, if necessary. If successfully added, the object is retained.

This function ignores any ordering function of the ordered set, and can disrupt the automatic sorting mechanism. Only call this function if you are managing the ordered set directly.

setObject(const OSMetaClassBase *)

Adds an object to the OSOrderedSet if it is not already present, storing it in sorted order if there is an order function.

public

virtual bool setObject(
    const OSMetaClassBase * anObject);

Parameters

anObject: The OSMetaClassBase-derived object to be added to the ordered set.

Return Value

true if anObject was successfully added to the ordered set, false otherwise (including if it was already in the ordered set).

Discussion

The set adds storage to accomodate the new object, if necessary. If successfully added, the object is retained.

If anObject is not already in the ordered set and there is an order function, this function loops through the existing objects, calling the order function with arguments each existingObject, anObject, and the ordering context (or NULL if none was set), until the order function returns a value greater than or equal to 0. It then inserts anObject at the index of the existing object.

If there is no order function, the object is inserted at index 0.

setObject(unsigned int, const OSMetaClassBase *)

Adds an object to an OSOrderedSet at a specified index if it is not already present.

public

virtual bool setObject( 
    unsigned int index, 
    const OSMetaClassBase * anObject);

Parameters

index: The index at which to insert the new object.
anObject: The OSMetaClassBase-derived object to be added to the ordered set.

Return Value

true if the object was successfully added to the ordered set, false otherwise (including if it was already in the set).

Discussion

The set adds storage to accomodate the new object, if necessary. If successfully added, the object is retained.

This function ignores any ordering function of the ordered set, and can disrupt the automatic sorting mechanism. Only call this function if you are managing the ordered set directly.

A false return value can mean either that the object is already present in the set, or that a memory allocation failure occurred. If you need to know whether the object is already present, use containsObject containsObject.

setOptions

public

virtual unsigned setOptions( 
    unsigned options, 
    unsigned mask, 
    void *context = 0);

Parameters

options: A bitfield whose values turn the options on (1) or off (0).
mask: A mask indicating which bits in options to change. Pass 0 to get the whole current options bitfield without changing any settings.
context: Unused.

Return Value

The options bitfield as it was before the set operation.

Discussion

Kernel extensions should not call this function.

Child collections' options are changed only if the receiving ordered set's options actually change.

withCapacity

Creates and initializes an empty OSOrderedSet.

public

static OSOrderedSet * withCapacity( 
    unsigned int capacity, 
    OSOrderFunction orderFunc = 0, 
    void *orderingContext = 0);

Parameters

capacity: The initial storage capacity of the new ordered set object.
orderFunc: A C function that implements the sorting algorithm for the set.
orderingContext: An ordering context, which is passed to orderFunc.

Return Value

An empty instance of OSOrderedSet with a retain count of 1; NULL on failure.

Discussion

capacity must be nonzero. The new OSOrderedSet will grow as needed to accommodate more key/object pairs (unlike Core Foundation collections, for which the initial capacity is a hard limit).

If orderFunc is provided, it is used by setObject(const OSMetaClassBase *) to determine where to insert a new object. Other object-setting functions ignore ordering.

Typedefs

OSOrderFunction: The sorting function used by an OSOrderedSet to order objects.

OSOrderFunction

The sorting function used by an OSOrderedSet to order objects.

public

typedef SInt32 ( *OSOrderFunction)(
    const OSMetaClassBase * obj1, 
    const OSMetaClassBase * obj2, 
    void * context);

Parameters

obj1: An object from the ordered set. May be NULL.
obj2: The object being ordered within the ordered set. May be NULL.
context: A pointer to a user-provided context. May be NULL.

Return Value

A comparison result of the object:

a positive value if obj2 should precede obj1,
a negative value if obj1 should precede obj2,
and 0 if obj1 and obj2 have an equivalent ordering.

Last Updated: 2009-10-14