[apple/xnu.git] / libkern / c++ / OSOrderedSet.cpp

/*
 * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * The contents of this file constitute Original Code as defined in and
 * are subject to the Apple Public Source License Version 1.1 (the
 * "License").  You may not use this file except in compliance with the
 * License.  Please obtain a copy of the License at
 * http://www.apple.com/publicsource and read it before using this file.
 * 
 * This Original Code and all software distributed under the License are
 * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
 * License for the specific language governing rights and limitations
 * under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */

#include <libkern/c++/OSDictionary.h>
#include <libkern/c++/OSOrderedSet.h>
#include <libkern/c++/OSLib.h>

#define super OSCollection

OSDefineMetaClassAndStructors(OSOrderedSet, OSCollection)
OSMetaClassDefineReservedUnused(OSOrderedSet, 0);
OSMetaClassDefineReservedUnused(OSOrderedSet, 1);
OSMetaClassDefineReservedUnused(OSOrderedSet, 2);
OSMetaClassDefineReservedUnused(OSOrderedSet, 3);
OSMetaClassDefineReservedUnused(OSOrderedSet, 4);
OSMetaClassDefineReservedUnused(OSOrderedSet, 5);
OSMetaClassDefineReservedUnused(OSOrderedSet, 6);
OSMetaClassDefineReservedUnused(OSOrderedSet, 7);

#if OSALLOCDEBUG
extern "C" {
    extern int debug_container_malloc_size;
};
#define ACCUMSIZE(s) do { debug_container_malloc_size += (s); } while(0)
#else
#define ACCUMSIZE(s)
#endif

struct _Element {
    const OSMetaClassBase *		obj;
//    unsigned int	pri;
};

#define EXT_CAST(obj) \
    reinterpret_cast<OSObject *>(const_cast<OSMetaClassBase *>(obj))

bool OSOrderedSet::
initWithCapacity(unsigned int inCapacity,
                 OSOrderFunction inOrdering, void *inOrderingRef)
{
    int size;

    if (!super::init())
        return false;

    size = sizeof(_Element) * inCapacity;
    array = (_Element *) kalloc(size);
    if (!array)
        return false;

    count = 0;
    capacity = inCapacity;
    capacityIncrement = (inCapacity)? inCapacity : 16;
    ordering = inOrdering;
    orderingRef = inOrderingRef;

    bzero(array, size);
    ACCUMSIZE(size);

    return this;	
}

OSOrderedSet * OSOrderedSet::
withCapacity(unsigned int capacity,
             OSOrderFunction ordering, void * orderingRef)
{
    OSOrderedSet *me = new OSOrderedSet;

    if (me && !me->initWithCapacity(capacity, ordering, orderingRef)) {
        me->release();
	me = 0;
    }

    return me;
}

void OSOrderedSet::free()
{
    (void) super::setOptions(0, kImmutable);
    flushCollection();

    if (array) {
        kfree((vm_offset_t)array, sizeof(_Element) * capacity);
        ACCUMSIZE( -(sizeof(_Element) * capacity) );
    }

    super::free();
}

unsigned int OSOrderedSet::getCount() const { return count; }
unsigned int OSOrderedSet::getCapacity() const { return capacity; }
unsigned int OSOrderedSet::getCapacityIncrement() const
	{ return capacityIncrement; }
unsigned int OSOrderedSet::setCapacityIncrement(unsigned int increment)
{
    capacityIncrement = (increment)? increment : 16;
    return capacityIncrement;
}

unsigned int OSOrderedSet::ensureCapacity(unsigned int newCapacity)
{
    _Element *newArray;
    int oldSize, newSize;

    if (newCapacity <= capacity)
        return capacity;

    // round up
    newCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
                * capacityIncrement;
    newSize = sizeof(_Element) * newCapacity;

    newArray = (_Element *) kalloc(newSize);
    if (newArray) {
        oldSize = sizeof(_Element) * capacity;

        ACCUMSIZE(newSize - oldSize);

        bcopy(array, newArray, oldSize);
        bzero(&newArray[capacity], newSize - oldSize);
        kfree((vm_offset_t)array, oldSize);
        array = newArray;
        capacity = newCapacity;
    }

    return capacity;
}

void OSOrderedSet::flushCollection()
{
    unsigned int i;

    haveUpdated();

    for (i = 0; i < count; i++)
        array[i].obj->taggedRelease(OSTypeID(OSCollection));

    count = 0;
}

/* internal */
bool OSOrderedSet::setObject(unsigned int index, const OSMetaClassBase *anObject)
{
    unsigned int i;
    unsigned int newCount = count + 1;

    if ((index > count) || !anObject)
        return false;

    if (containsObject(anObject))
        return false;

    // do we need more space?
    if (newCount > capacity && newCount > ensureCapacity(newCount))
        return false;

    haveUpdated();
    if (index != count) {
        for (i = count; i > index; i--)
            array[i] = array[i-1];
    }
    array[index].obj = anObject;
//    array[index].pri = pri;
    anObject->taggedRetain(OSTypeID(OSCollection));
    count++;

    return true;
}


bool OSOrderedSet::setFirstObject(const OSMetaClassBase *anObject)
{
    return( setObject(0, anObject));
}

bool OSOrderedSet::setLastObject(const OSMetaClassBase *anObject)
{
    return( setObject( count, anObject));
}


#define ORDER(obj1,obj2) \
    (ordering ? ((*ordering)( (OSObject *) obj1, (OSObject *) obj2, orderingRef)) : 0)

bool OSOrderedSet::setObject(const OSMetaClassBase *anObject )
{
    unsigned int i;

    // queue it behind those with same priority
    for( i = 0;
	(i < count) && (ORDER(array[i].obj, anObject) >= 0);
	i++ ) {}

    return( setObject(i, anObject));
}

void OSOrderedSet::removeObject(const OSMetaClassBase *anObject)
{
    bool		deleted = false;
    unsigned int 	i;

    for (i = 0; i < count; i++) {

        if( deleted)
            array[i-1] = array[i];
        else if( (array[i].obj == anObject)) {
            deleted = true;
	    haveUpdated();	// Pity we can't flush the log
            array[i].obj->taggedRelease(OSTypeID(OSCollection));
        }
    }

    if (deleted)
	count--;
}

bool OSOrderedSet::containsObject(const OSMetaClassBase *anObject) const
{
    return anObject && member(anObject);
}

bool OSOrderedSet::member(const OSMetaClassBase *anObject) const
{
    unsigned int i;

    for( i = 0;
	(i < count) && (array[i].obj != anObject);
	i++ ) {}

    return( i < count);
}

/* internal */
OSObject *OSOrderedSet::getObject( unsigned int index ) const
{
    if (index >= count)
        return 0;

//    if( pri)
//	*pri = array[index].pri;

    return( (OSObject *) array[index].obj );
}

OSObject *OSOrderedSet::getFirstObject() const
{
    if( count)
        return( (OSObject *) array[0].obj );
    else
	return( 0 );
}

OSObject *OSOrderedSet::getLastObject() const
{
    if( count)
        return( (OSObject *) array[count-1].obj );
    else
	return( 0 );
}

SInt32 OSOrderedSet::orderObject( const OSMetaClassBase * anObject )
{
    return( ORDER( anObject, 0 ));
}

void *OSOrderedSet::getOrderingRef()
{
    return orderingRef;
}

bool OSOrderedSet::isEqualTo(const OSOrderedSet *anOrderedSet) const
{
    unsigned int i;
    
    if ( this == anOrderedSet )
        return true;

    if ( count != anOrderedSet->getCount() )
        return false;

    for ( i = 0; i < count; i++ ) {
        if ( !array[i].obj->isEqualTo(anOrderedSet->getObject(i)) )
            return false;
    }

    return true;
}

bool OSOrderedSet::isEqualTo(const OSMetaClassBase *anObject) const
{
    OSOrderedSet *oSet;

    oSet = OSDynamicCast(OSOrderedSet, anObject);
    if ( oSet )
        return isEqualTo(oSet);
    else
        return false;
}

unsigned int OSOrderedSet::iteratorSize() const
{
    return( sizeof(unsigned int));
}

bool OSOrderedSet::initIterator(void *inIterator) const
{
    unsigned int *iteratorP = (unsigned int *) inIterator;

    *iteratorP = 0;
    return true;
}

bool OSOrderedSet::
getNextObjectForIterator(void *inIterator, OSObject **ret) const
{
    unsigned int *iteratorP = (unsigned int *) inIterator;
    unsigned int index = (*iteratorP)++;

    if (index < count)
        *ret = (OSObject *) array[index].obj;
    else
        *ret = 0;

    return (*ret != 0);
}


unsigned OSOrderedSet::setOptions(unsigned options, unsigned mask, void *)
{
    unsigned old = super::setOptions(options, mask);
    if ((old ^ options) & mask) {

	// Value changed need to recurse over all of the child collections
	for ( unsigned i = 0; i < count; i++ ) {
	    OSCollection *coll = OSDynamicCast(OSCollection, array[i].obj);
	    if (coll)
		coll->setOptions(options, mask);
	}
    }

    return old;
}

OSCollection * OSOrderedSet::copyCollection(OSDictionary *cycleDict)
{
    bool allocDict = !cycleDict;
    OSCollection *ret = 0;
    OSOrderedSet *newSet = 0;

    if (allocDict) {
	cycleDict = OSDictionary::withCapacity(16);
	if (!cycleDict)
	    return 0;
    }

    do {
	// Check for a cycle
	ret = super::copyCollection(cycleDict);
	if (ret)
	    continue;
	
	// Duplicate the set with no contents
	newSet = OSOrderedSet::withCapacity(capacity, ordering, orderingRef);
	if (!newSet)
	    continue;

	// Insert object into cycle Dictionary
	cycleDict->setObject((const OSSymbol *) this, newSet);

	newSet->capacityIncrement = capacityIncrement;

	// Now copy over the contents to the new duplicate
	for (unsigned int i = 0; i < count; i++) {
	    OSObject *obj = EXT_CAST(array[i].obj);
	    OSCollection *coll = OSDynamicCast(OSCollection, obj);
	    if (coll) {
		OSCollection *newColl = coll->copyCollection(cycleDict);
		if (newColl) {
		    obj = newColl;	// Rely on cycleDict ref for a bit
		    newColl->release();
		}
		else
		    goto abortCopy;
	    };
	    newSet->setLastObject(obj);
	};

	ret = newSet;
	newSet = 0;

    } while (false);

abortCopy:
    if (newSet)
	newSet->release();

    if (allocDict)
	cycleDict->release();

    return ret;
}
Commit	Line	Data
1c79356b A	1	/*
	2	* Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
	3	*
	4	* @APPLE_LICENSE_HEADER_START@
	5	*
37839358 A	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.
1c79356b	11	*
37839358 A	12	* This Original Code and all software distributed under the License are
37839358 A	13	* distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
1c79356b A	14	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
1c79356b A	15	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
37839358 A	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.
1c79356b A	19	*
	20	* @APPLE_LICENSE_HEADER_END@
	21	*/
	22
91447636	23	#include <libkern/c++/OSDictionary.h>
1c79356b A	24	#include <libkern/c++/OSOrderedSet.h>
	25	#include <libkern/c++/OSLib.h>
	26
	27	#define super OSCollection
	28
	29	OSDefineMetaClassAndStructors(OSOrderedSet, OSCollection)
	30	OSMetaClassDefineReservedUnused(OSOrderedSet, 0);
	31	OSMetaClassDefineReservedUnused(OSOrderedSet, 1);
	32	OSMetaClassDefineReservedUnused(OSOrderedSet, 2);
	33	OSMetaClassDefineReservedUnused(OSOrderedSet, 3);
	34	OSMetaClassDefineReservedUnused(OSOrderedSet, 4);
	35	OSMetaClassDefineReservedUnused(OSOrderedSet, 5);
	36	OSMetaClassDefineReservedUnused(OSOrderedSet, 6);
	37	OSMetaClassDefineReservedUnused(OSOrderedSet, 7);
	38
	39	#if OSALLOCDEBUG
	40	extern "C" {
	41	extern int debug_container_malloc_size;
	42	};
	43	#define ACCUMSIZE(s) do { debug_container_malloc_size += (s); } while(0)
	44	#else
	45	#define ACCUMSIZE(s)
	46	#endif
	47
	48	struct _Element {
	49	const OSMetaClassBase * obj;
	50	// unsigned int pri;
	51	};
	52
91447636 A	53	#define EXT_CAST(obj) \
91447636 A	54	reinterpret_cast<OSObject >(const_cast<OSMetaClassBase >(obj))
1c79356b A	55
	56	bool OSOrderedSet::
	57	initWithCapacity(unsigned int inCapacity,
	58	OSOrderFunction inOrdering, void *inOrderingRef)
	59	{
	60	int size;
	61
	62	if (!super::init())
	63	return false;
	64
	65	size = sizeof(_Element) * inCapacity;
	66	array = (_Element *) kalloc(size);
	67	if (!array)
	68	return false;
	69
	70	count = 0;
	71	capacity = inCapacity;
	72	capacityIncrement = (inCapacity)? inCapacity : 16;
	73	ordering = inOrdering;
	74	orderingRef = inOrderingRef;
	75
	76	bzero(array, size);
	77	ACCUMSIZE(size);
	78
	79	return this;
	80	}
	81
	82	OSOrderedSet * OSOrderedSet::
	83	withCapacity(unsigned int capacity,
	84	OSOrderFunction ordering, void * orderingRef)
	85	{
	86	OSOrderedSet *me = new OSOrderedSet;
	87
	88	if (me && !me->initWithCapacity(capacity, ordering, orderingRef)) {
55e303ae	89	me->release();
1c79356b A	90	me = 0;
	91	}
	92
	93	return me;
	94	}
	95
	96	void OSOrderedSet::free()
	97	{
91447636	98	(void) super::setOptions(0, kImmutable);
1c79356b A	99	flushCollection();
	100
	101	if (array) {
	102	kfree((vm_offset_t)array, sizeof(_Element) * capacity);
	103	ACCUMSIZE( -(sizeof(_Element) * capacity) );
	104	}
	105
	106	super::free();
	107	}
	108
	109	unsigned int OSOrderedSet::getCount() const { return count; }
	110	unsigned int OSOrderedSet::getCapacity() const { return capacity; }
	111	unsigned int OSOrderedSet::getCapacityIncrement() const
	112	{ return capacityIncrement; }
	113	unsigned int OSOrderedSet::setCapacityIncrement(unsigned int increment)
	114	{
	115	capacityIncrement = (increment)? increment : 16;
	116	return capacityIncrement;
	117	}
	118
	119	unsigned int OSOrderedSet::ensureCapacity(unsigned int newCapacity)
	120	{
	121	_Element *newArray;
	122	int oldSize, newSize;
	123
	124	if (newCapacity <= capacity)
	125	return capacity;
	126
	127	// round up
	128	newCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
	129	* capacityIncrement;
	130	newSize = sizeof(_Element) * newCapacity;
	131
	132	newArray = (_Element *) kalloc(newSize);
	133	if (newArray) {
	134	oldSize = sizeof(_Element) * capacity;
	135
	136	ACCUMSIZE(newSize - oldSize);
	137
	138	bcopy(array, newArray, oldSize);
	139	bzero(&newArray[capacity], newSize - oldSize);
	140	kfree((vm_offset_t)array, oldSize);
	141	array = newArray;
	142	capacity = newCapacity;
	143	}
	144
	145	return capacity;
	146	}
	147
	148	void OSOrderedSet::flushCollection()
	149	{
	150	unsigned int i;
	151
	152	haveUpdated();
	153
	154	for (i = 0; i < count; i++)
9bccf70c	155	array[i].obj->taggedRelease(OSTypeID(OSCollection));
1c79356b A	156
	157	count = 0;
	158	}
	159
	160	/* internal */
	161	bool OSOrderedSet::setObject(unsigned int index, const OSMetaClassBase *anObject)
	162	{
	163	unsigned int i;
	164	unsigned int newCount = count + 1;
	165
	166	if ((index > count) \|\| !anObject)
	167	return false;
	168
	169	if (containsObject(anObject))
	170	return false;
	171
	172	// do we need more space?
	173	if (newCount > capacity && newCount > ensureCapacity(newCount))
	174	return false;
	175
	176	haveUpdated();
	177	if (index != count) {
	178	for (i = count; i > index; i--)
	179	array[i] = array[i-1];
	180	}
	181	array[index].obj = anObject;
	182	// array[index].pri = pri;
9bccf70c	183	anObject->taggedRetain(OSTypeID(OSCollection));
1c79356b A	184	count++;
	185
	186	return true;
	187	}
	188
	189
	190	bool OSOrderedSet::setFirstObject(const OSMetaClassBase *anObject)
	191	{
	192	return( setObject(0, anObject));
	193	}
	194
	195	bool OSOrderedSet::setLastObject(const OSMetaClassBase *anObject)
	196	{
	197	return( setObject( count, anObject));
	198	}
	199
	200
	201	#define ORDER(obj1,obj2) \
	202	(ordering ? ((ordering)( (OSObject ) obj1, (OSObject *) obj2, orderingRef)) : 0)
	203
	204	bool OSOrderedSet::setObject(const OSMetaClassBase *anObject )
	205	{
	206	unsigned int i;
	207
	208	// queue it behind those with same priority
	209	for( i = 0;
	210	(i < count) && (ORDER(array[i].obj, anObject) >= 0);
	211	i++ ) {}
	212
	213	return( setObject(i, anObject));
	214	}
	215
	216	void OSOrderedSet::removeObject(const OSMetaClassBase *anObject)
	217	{
	218	bool deleted = false;
	219	unsigned int i;
	220
	221	for (i = 0; i < count; i++) {
	222
	223	if( deleted)
	224	array[i-1] = array[i];
	225	else if( (array[i].obj == anObject)) {
1c79356b	226	deleted = true;
91447636 A	227	haveUpdated(); // Pity we can't flush the log
91447636 A	228	array[i].obj->taggedRelease(OSTypeID(OSCollection));
1c79356b A	229	}
	230	}
	231
91447636 A	232	if (deleted)
91447636 A	233	count--;
1c79356b A	234	}
	235
	236	bool OSOrderedSet::containsObject(const OSMetaClassBase *anObject) const
	237	{
	238	return anObject && member(anObject);
	239	}
	240
	241	bool OSOrderedSet::member(const OSMetaClassBase *anObject) const
	242	{
	243	unsigned int i;
	244
	245	for( i = 0;
	246	(i < count) && (array[i].obj != anObject);
	247	i++ ) {}
	248
	249	return( i < count);
	250	}
	251
	252	/* internal */
	253	OSObject *OSOrderedSet::getObject( unsigned int index ) const
	254	{
	255	if (index >= count)
	256	return 0;
	257
	258	// if( pri)
	259	// *pri = array[index].pri;
	260
	261	return( (OSObject *) array[index].obj );
	262	}
	263
	264	OSObject *OSOrderedSet::getFirstObject() const
	265	{
	266	if( count)
	267	return( (OSObject *) array[0].obj );
	268	else
	269	return( 0 );
	270	}
	271
	272	OSObject *OSOrderedSet::getLastObject() const
	273	{
	274	if( count)
	275	return( (OSObject *) array[count-1].obj );
	276	else
	277	return( 0 );
	278	}
	279
	280	SInt32 OSOrderedSet::orderObject( const OSMetaClassBase * anObject )
	281	{
	282	return( ORDER( anObject, 0 ));
	283	}
	284
	285	void *OSOrderedSet::getOrderingRef()
	286	{
	287	return orderingRef;
	288	}
	289
	290	bool OSOrderedSet::isEqualTo(const OSOrderedSet *anOrderedSet) const
	291	{
	292	unsigned int i;
	293
	294	if ( this == anOrderedSet )
	295	return true;
	296
	297	if ( count != anOrderedSet->getCount() )
298	return false;
299
300	for ( i = 0; i < count; i++ ) {
301	if ( !array[i].obj->isEqualTo(anOrderedSet->getObject(i)) )
302	return false;
303	}
304
305	return true;
306	}
307
308	bool OSOrderedSet::isEqualTo(const OSMetaClassBase *anObject) const
309	{
310	OSOrderedSet *oSet;
311
312	oSet = OSDynamicCast(OSOrderedSet, anObject);
313	if ( oSet )
314	return isEqualTo(oSet);
315	else
316	return false;
317	}
318
319	unsigned int OSOrderedSet::iteratorSize() const
320	{
321	return( sizeof(unsigned int));
322	}
323
324	bool OSOrderedSet::initIterator(void *inIterator) const
325	{
326	unsigned int iteratorP = (unsigned int ) inIterator;
327
328	*iteratorP = 0;
329	return true;
330	}
331
332	bool OSOrderedSet::
333	getNextObjectForIterator(void inIterator, OSObject *ret) const
334	{
335	unsigned int iteratorP = (unsigned int ) inIterator;
336	unsigned int index = (*iteratorP)++;
337
338	if (index < count)
339	ret = (OSObject ) array[index].obj;
340	else
341	*ret = 0;
342
343	return (*ret != 0);
344	}
345
91447636 A	346
	347	unsigned OSOrderedSet::setOptions(unsigned options, unsigned mask, void *)
	348	{
	349	unsigned old = super::setOptions(options, mask);
	350	if ((old ^ options) & mask) {
	351
	352	// Value changed need to recurse over all of the child collections
	353	for ( unsigned i = 0; i < count; i++ ) {
	354	OSCollection *coll = OSDynamicCast(OSCollection, array[i].obj);
	355	if (coll)
	356	coll->setOptions(options, mask);
	357	}
	358	}
	359
	360	return old;
	361	}
	362
	363	OSCollection * OSOrderedSet::copyCollection(OSDictionary *cycleDict)
	364	{
	365	bool allocDict = !cycleDict;
	366	OSCollection *ret = 0;
	367	OSOrderedSet *newSet = 0;
	368
	369	if (allocDict) {
	370	cycleDict = OSDictionary::withCapacity(16);
	371	if (!cycleDict)
	372	return 0;
	373	}
	374
	375	do {
	376	// Check for a cycle
	377	ret = super::copyCollection(cycleDict);
	378	if (ret)
	379	continue;
	380
	381	// Duplicate the set with no contents
	382	newSet = OSOrderedSet::withCapacity(capacity, ordering, orderingRef);
	383	if (!newSet)
	384	continue;
	385
	386	// Insert object into cycle Dictionary
	387	cycleDict->setObject((const OSSymbol *) this, newSet);
	388
	389	newSet->capacityIncrement = capacityIncrement;
	390
	391	// Now copy over the contents to the new duplicate
	392	for (unsigned int i = 0; i < count; i++) {
	393	OSObject *obj = EXT_CAST(array[i].obj);
	394	OSCollection *coll = OSDynamicCast(OSCollection, obj);
	395	if (coll) {
	396	OSCollection *newColl = coll->copyCollection(cycleDict);
	397	if (newColl) {
	398	obj = newColl; // Rely on cycleDict ref for a bit
	399	newColl->release();
	400	}
	401	else
	402	goto abortCopy;
	403	};
	404	newSet->setLastObject(obj);
	405	};
	406
	407	ret = newSet;
	408	newSet = 0;
	409
410	} while (false);
411
412	abortCopy:
413	if (newSet)
414	newSet->release();
415
416	if (allocDict)
417	cycleDict->release();
418
419	return ret;
420	}