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

/*
 * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 * 
 * The 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, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */
/* IOSymbol.cpp created by gvdl on Fri 1998-11-17 */

#include <string.h>
#include <sys/cdefs.h>

__BEGIN_DECLS
#include <kern/lock.h>
__END_DECLS

#include <libkern/c++/OSSymbol.h>
#include <libkern/c++/OSLib.h>
#include <string.h>

#define super OSString

typedef struct { int i, j; } OSSymbolPoolState;

#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

class OSSymbolPool
{
private:
    static const unsigned int kInitBucketCount = 16;

    typedef struct { unsigned int count; OSSymbol **symbolP; } Bucket;

    Bucket *buckets;
    unsigned int nBuckets;
    unsigned int count;
    mutex_t *poolGate;

    static inline void hashSymbol(const char *s,
                                  unsigned int *hashP,
                                  unsigned int *lenP)
    {
        unsigned int hash = 0;
        unsigned int len = 0;

        /* Unroll the loop. */
        for (;;) {
            if (!*s) break; len++; hash ^= *s++;
            if (!*s) break; len++; hash ^= *s++ <<  8;
            if (!*s) break; len++; hash ^= *s++ << 16;
            if (!*s) break; len++; hash ^= *s++ << 24;
        }
        *lenP = len;
        *hashP = hash;
    }

    static unsigned long log2(unsigned int x);
    static unsigned long exp2ml(unsigned int x);

    void reconstructSymbols();

public:
    static void *operator new(size_t size);
    static void operator delete(void *mem, size_t size);

    OSSymbolPool() { };
    OSSymbolPool(const OSSymbolPool *old);
    virtual ~OSSymbolPool();

    bool init();

    inline void closeGate() { mutex_lock(poolGate); };
    inline void openGate()  { mutex_unlock(poolGate); };

    OSSymbol *findSymbol(const char *cString, OSSymbol ***replace) const;
    OSSymbol *insertSymbol(OSSymbol *sym);
    void removeSymbol(OSSymbol *sym);

    OSSymbolPoolState initHashState();
    OSSymbol *nextHashState(OSSymbolPoolState *stateP);
};

void * OSSymbolPool::operator new(size_t size)
{
    void *mem = (void *)kalloc(size);
    ACCUMSIZE(size);
    assert(mem);
    bzero(mem, size);

    return mem;
}

void OSSymbolPool::operator delete(void *mem, size_t size)
{
    kfree((vm_offset_t)mem, size);
    ACCUMSIZE(-size);
}

bool OSSymbolPool::init()
{
    count = 0;
    nBuckets = exp2ml(1 + log2(kInitBucketCount));
    buckets = (Bucket *) kalloc(nBuckets * sizeof(Bucket));
    ACCUMSIZE(nBuckets * sizeof(Bucket));
    if (!buckets)
        return false;

    bzero(buckets, nBuckets * sizeof(Bucket));

    poolGate = mutex_alloc(0);

    return poolGate != 0;
}

OSSymbolPool::OSSymbolPool(const OSSymbolPool *old)
{
    count = old->count;
    nBuckets = old->nBuckets;
    buckets = old->buckets;

    poolGate = 0;	// Do not duplicate the poolGate
}

OSSymbolPool::~OSSymbolPool()
{
    if (buckets) {
        kfree((vm_offset_t)buckets, nBuckets * sizeof(Bucket));
        ACCUMSIZE(-(nBuckets * sizeof(Bucket)));
    }

    if (poolGate)
        kfree((vm_offset_t) poolGate, 36 * 4);
}

unsigned long OSSymbolPool::log2(unsigned int x)
{
    unsigned long i;

    for (i = 0; x > 1 ; i++)
        x >>= 1;
    return i;
}

unsigned long OSSymbolPool::exp2ml(unsigned int x)
{
    return (1 << x) - 1;
}

OSSymbolPoolState OSSymbolPool::initHashState()
{
    OSSymbolPoolState newState = { nBuckets, 0 };
    return newState;
}

OSSymbol *OSSymbolPool::nextHashState(OSSymbolPoolState *stateP)
{
    Bucket *thisBucket = &buckets[stateP->i];

    while (!stateP->j) {
        if (!stateP->i)
            return 0;
        stateP->i--;
        thisBucket--;
        stateP->j = thisBucket->count;
    }

    stateP->j--;
    if (thisBucket->count == 1)
        return (OSSymbol *) thisBucket->symbolP;
    else
        return thisBucket->symbolP[stateP->j];
}

void OSSymbolPool::reconstructSymbols()
{
    OSSymbolPool old(this);
    OSSymbol *insert;
    OSSymbolPoolState state;

    nBuckets += nBuckets + 1;
    count = 0;
    buckets = (Bucket *) kalloc(nBuckets * sizeof(Bucket));
    ACCUMSIZE(nBuckets * sizeof(Bucket));
    /* @@@ gvdl: Zero test and panic if can't set up pool */
    bzero(buckets, nBuckets * sizeof(Bucket));

    state = old.initHashState();
    while ( (insert = old.nextHashState(&state)) )
        insertSymbol(insert);
}

OSSymbol *OSSymbolPool::findSymbol(const char *cString, OSSymbol ***replace) const
{
    Bucket *thisBucket;
    unsigned int j, inLen, hash;
    OSSymbol *probeSymbol, **list;

    hashSymbol(cString, &hash, &inLen); inLen++;
    thisBucket = &buckets[hash % nBuckets];
    j = thisBucket->count;

    *replace = NULL;

    if (!j)
        return 0;

    if (j == 1) {
        probeSymbol = (OSSymbol *) thisBucket->symbolP;

        if (inLen == probeSymbol->length
        &&  (strcmp(probeSymbol->string, cString) == 0)) {
	    probeSymbol->retain();
	    if (probeSymbol->getRetainCount() != 0xffff)
		return probeSymbol;
	    else
		// replace this one
		*replace = (OSSymbol **) &thisBucket->symbolP;
        }
	return 0;
    }

    for (list = thisBucket->symbolP; j--; list++) {
        probeSymbol = *list;
        if (inLen == probeSymbol->length
        &&  (strcmp(probeSymbol->string, cString) == 0)) {
	    probeSymbol->retain();
	    if (probeSymbol->getRetainCount() != 0xffff)
		return probeSymbol;
	    else
		// replace this one
		*replace = list;
	}
    }

    return 0;
}

OSSymbol *OSSymbolPool::insertSymbol(OSSymbol *sym)
{
    const char *cString = sym->string;
    Bucket *thisBucket;
    unsigned int j, inLen, hash;
    OSSymbol *probeSymbol, **list;

    hashSymbol(cString, &hash, &inLen); inLen++;
    thisBucket = &buckets[hash % nBuckets];
    j = thisBucket->count;

    if (!j) {
        thisBucket->symbolP = (OSSymbol **) sym;
        thisBucket->count++;
        count++;
        return 0;
    }

    if (j == 1) {
        probeSymbol = (OSSymbol *) thisBucket->symbolP;

        if (inLen == probeSymbol->length
        &&  strcmp(probeSymbol->string, cString) == 0)
            return probeSymbol;

        list = (OSSymbol **) kalloc(2 * sizeof(OSSymbol *));
        ACCUMSIZE(2 * sizeof(OSSymbol *));
        /* @@@ gvdl: Zero test and panic if can't set up pool */
        list[0] = sym;
        list[1] = probeSymbol;
        thisBucket->symbolP = list;
        thisBucket->count++;
        count++;
        if (count > nBuckets)
            reconstructSymbols();

        return 0;
    }

    for (list = thisBucket->symbolP; j--; list++) {
        probeSymbol = *list;
        if (inLen == probeSymbol->length
        &&  strcmp(probeSymbol->string, cString) == 0)
            return probeSymbol;
    }

    j = thisBucket->count++;
    count++;
    list = (OSSymbol **) kalloc(thisBucket->count * sizeof(OSSymbol *));
    ACCUMSIZE(thisBucket->count * sizeof(OSSymbol *));
    /* @@@ gvdl: Zero test and panic if can't set up pool */
    list[0] = sym;
    bcopy(thisBucket->symbolP, list + 1, j * sizeof(OSSymbol *));
    kfree((vm_offset_t)thisBucket->symbolP, j * sizeof(OSSymbol *));
    ACCUMSIZE(-(j * sizeof(OSSymbol *)));
    thisBucket->symbolP = list;
    if (count > nBuckets)
        reconstructSymbols();

    return 0;
}

void OSSymbolPool::removeSymbol(OSSymbol *sym)
{
    Bucket *thisBucket;
    unsigned int j, inLen, hash;
    OSSymbol *probeSymbol, **list;

    hashSymbol(sym->string, &hash, &inLen); inLen++;
    thisBucket = &buckets[hash % nBuckets];
    j = thisBucket->count;
    list = thisBucket->symbolP;

    if (!j)
        return;

    if (j == 1) {
        probeSymbol = (OSSymbol *) list;

        if (probeSymbol == sym) {
            thisBucket->symbolP = 0;
            count--;
            thisBucket->count--;
            return;
        }
        return;
    }

    if (j == 2) {
        probeSymbol = list[0];
        if (probeSymbol == sym) {
            thisBucket->symbolP = (OSSymbol **) list[1];
            kfree((vm_offset_t)list, 2 * sizeof(OSSymbol *));
	    ACCUMSIZE(-(2 * sizeof(OSSymbol *)));
            count--;
            thisBucket->count--;
            return;
        }

        probeSymbol = list[1];
        if (probeSymbol == sym) {
            thisBucket->symbolP = (OSSymbol **) list[0];
            kfree((vm_offset_t)list, 2 * sizeof(OSSymbol *));
	    ACCUMSIZE(-(2 * sizeof(OSSymbol *)));
            count--;
            thisBucket->count--;
            return;
        }
        return;
    }

    for (; j--; list++) {
        probeSymbol = *list;
        if (probeSymbol == sym) {

            list = (OSSymbol **)
                kalloc((thisBucket->count-1) * sizeof(OSSymbol *));
	    ACCUMSIZE((thisBucket->count-1) * sizeof(OSSymbol *));
            if (thisBucket->count-1 != j)
                bcopy(thisBucket->symbolP, list,
                      (thisBucket->count-1-j) * sizeof(OSSymbol *));
            if (j)
                bcopy(thisBucket->symbolP + thisBucket->count-j,
                      list + thisBucket->count-1-j,
                      j * sizeof(OSSymbol *));
            kfree((vm_offset_t)thisBucket->symbolP, thisBucket->count * sizeof(OSSymbol *));
	    ACCUMSIZE(-(thisBucket->count * sizeof(OSSymbol *)));
            thisBucket->symbolP = list;
            count--;
            thisBucket->count--;
            return;
        }
    }
}

/*
 *********************************************************************
 * From here on we are actually implementing the OSSymbol class
 *********************************************************************
 */
OSDefineMetaClassAndStructorsWithInit(OSSymbol, OSString,
                                      OSSymbol::initialize())
OSMetaClassDefineReservedUnused(OSSymbol, 0);
OSMetaClassDefineReservedUnused(OSSymbol, 1);
OSMetaClassDefineReservedUnused(OSSymbol, 2);
OSMetaClassDefineReservedUnused(OSSymbol, 3);
OSMetaClassDefineReservedUnused(OSSymbol, 4);
OSMetaClassDefineReservedUnused(OSSymbol, 5);
OSMetaClassDefineReservedUnused(OSSymbol, 6);
OSMetaClassDefineReservedUnused(OSSymbol, 7);

static OSSymbolPool *pool;

void OSSymbol::initialize()
{
    pool = new OSSymbolPool;
    assert(pool);

    if (!pool->init()) {
        delete pool;
        assert(false);
    };
}

bool OSSymbol::initWithCStringNoCopy(const char *) { return false; }
bool OSSymbol::initWithCString(const char *) { return false; }
bool OSSymbol::initWithString(const OSString *) { return false; }

const OSSymbol *OSSymbol::withString(const OSString *aString)
{
    // This string may be a OSSymbol already, cheap check.
    if (OSDynamicCast(OSSymbol, aString)) {
	aString->retain();
	return (const OSSymbol *) aString;
    }
    else if (((const OSSymbol *) aString)->flags & kOSStringNoCopy)
        return OSSymbol::withCStringNoCopy(aString->getCStringNoCopy());
    else
        return OSSymbol::withCString(aString->getCStringNoCopy());
}

const OSSymbol *OSSymbol::withCString(const char *cString)
{
    OSSymbol **replace;

    pool->closeGate();

    OSSymbol *newSymb = pool->findSymbol(cString, &replace);
    if (!newSymb && (newSymb = new OSSymbol) ) {
	if (newSymb->OSString::initWithCString(cString)) {
	    if (replace)
		*replace = newSymb;
	    else
		pool->insertSymbol(newSymb);
	} else {
	    newSymb->OSString::free();
	    newSymb = 0;
	}
    }
    pool->openGate();

    return newSymb;
}

const OSSymbol *OSSymbol::withCStringNoCopy(const char *cString)
{
    OSSymbol **replace;

    pool->closeGate();

    OSSymbol *newSymb = pool->findSymbol(cString, &replace);
    if (!newSymb && (newSymb = new OSSymbol) ) {
	if (newSymb->OSString::initWithCStringNoCopy(cString)) {
	    if (replace)
		*replace = newSymb;
	    else
		pool->insertSymbol(newSymb);
	} else {
	    newSymb->OSString::free();
	    newSymb = 0;
	}
    }
    pool->openGate();

    return newSymb;
}

void OSSymbol::checkForPageUnload(void *startAddr, void *endAddr)
{
    OSSymbol *probeSymbol;
    OSSymbolPoolState state;

    pool->closeGate();
    state = pool->initHashState();
    while ( (probeSymbol = pool->nextHashState(&state)) ) {
        if (probeSymbol->string >= startAddr && probeSymbol->string < endAddr) {
            const char *oldString = probeSymbol->string;

            probeSymbol->string = (char *) kalloc(probeSymbol->length);
	    ACCUMSIZE(probeSymbol->length);
            bcopy(oldString, probeSymbol->string, probeSymbol->length);
            probeSymbol->flags &= ~kOSStringNoCopy;
        }
    }
    pool->openGate();
}

void OSSymbol::free()
{
    pool->closeGate();
    pool->removeSymbol(this);
    pool->openGate();
    
    super::free();
}

bool OSSymbol::isEqualTo(const char *aCString) const
{
    return super::isEqualTo(aCString);
}

bool OSSymbol::isEqualTo(const OSSymbol *aSymbol) const
{
    return aSymbol == this;
}

bool OSSymbol::isEqualTo(const OSMetaClassBase *obj) const
{
    OSSymbol *	sym;
    OSString *	str;

    if ((sym = OSDynamicCast(OSSymbol, obj)))
	return isEqualTo(sym);
    else if ((str = OSDynamicCast(OSString, obj)))
	return super::isEqualTo(str);
    else
	return false;
}
Commit	Line	Data
1c79356b A	1	/*
	2	* Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
	3	*
	4	* @APPLE_LICENSE_HEADER_START@
	5	*
d7e50217	6	* Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved.
1c79356b	7	*
d7e50217 A	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
1c79356b A	17	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
1c79356b A	18	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
d7e50217 A	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.
1c79356b A	22	*
	23	* @APPLE_LICENSE_HEADER_END@
	24	*/
	25	/* IOSymbol.cpp created by gvdl on Fri 1998-11-17 */
	26
9bccf70c	27	#include <string.h>
1c79356b A	28	#include <sys/cdefs.h>
	29
	30	__BEGIN_DECLS
	31	#include <kern/lock.h>
	32	__END_DECLS
	33
	34	#include <libkern/c++/OSSymbol.h>
	35	#include <libkern/c++/OSLib.h>
9bccf70c	36	#include <string.h>
1c79356b A	37
	38	#define super OSString
	39
	40	typedef struct { int i, j; } OSSymbolPoolState;
	41
	42	#if OSALLOCDEBUG
	43	extern "C" {
	44	extern int debug_container_malloc_size;
	45	};
	46	#define ACCUMSIZE(s) do { debug_container_malloc_size += (s); } while(0)
	47	#else
	48	#define ACCUMSIZE(s)
	49	#endif
	50
	51	class OSSymbolPool
	52	{
	53	private:
	54	static const unsigned int kInitBucketCount = 16;
	55
	56	typedef struct { unsigned int count; OSSymbol **symbolP; } Bucket;
	57
	58	Bucket *buckets;
	59	unsigned int nBuckets;
	60	unsigned int count;
	61	mutex_t *poolGate;
	62
	63	static inline void hashSymbol(const char *s,
	64	unsigned int *hashP,
	65	unsigned int *lenP)
	66	{
	67	unsigned int hash = 0;
	68	unsigned int len = 0;
	69
	70	/* Unroll the loop. */
	71	for (;;) {
	72	if (!s) break; len++; hash ^= s++;
	73	if (!s) break; len++; hash ^= s++ << 8;
	74	if (!s) break; len++; hash ^= s++ << 16;
	75	if (!s) break; len++; hash ^= s++ << 24;
	76	}
	77	*lenP = len;
	78	*hashP = hash;
	79	}
	80
	81	static unsigned long log2(unsigned int x);
	82	static unsigned long exp2ml(unsigned int x);
	83
	84	void reconstructSymbols();
	85
	86	public:
	87	static void *operator new(size_t size);
	88	static void operator delete(void *mem, size_t size);
	89
	90	OSSymbolPool() { };
	91	OSSymbolPool(const OSSymbolPool *old);
	92	virtual ~OSSymbolPool();
	93
	94	bool init();
	95
	96	inline void closeGate() { mutex_lock(poolGate); };
	97	inline void openGate() { mutex_unlock(poolGate); };
	98
9bccf70c	99	OSSymbol findSymbol(const char cString, OSSymbol ***replace) const;
1c79356b	100	OSSymbol insertSymbol(OSSymbol sym);
9bccf70c	101	void removeSymbol(OSSymbol *sym);
1c79356b A	102
	103	OSSymbolPoolState initHashState();
	104	OSSymbol nextHashState(OSSymbolPoolState stateP);
	105	};
	106
	107	void * OSSymbolPool::operator new(size_t size)
	108	{
	109	void mem = (void )kalloc(size);
	110	ACCUMSIZE(size);
	111	assert(mem);
	112	bzero(mem, size);
	113
	114	return mem;
	115	}
	116
	117	void OSSymbolPool::operator delete(void *mem, size_t size)
	118	{
	119	kfree((vm_offset_t)mem, size);
	120	ACCUMSIZE(-size);
	121	}
	122
	123	bool OSSymbolPool::init()
	124	{
	125	count = 0;
	126	nBuckets = exp2ml(1 + log2(kInitBucketCount));
	127	buckets = (Bucket ) kalloc(nBuckets sizeof(Bucket));
	128	ACCUMSIZE(nBuckets * sizeof(Bucket));
	129	if (!buckets)
	130	return false;
	131
	132	bzero(buckets, nBuckets * sizeof(Bucket));
	133
	134	poolGate = mutex_alloc(0);
	135
	136	return poolGate != 0;
	137	}
	138
	139	OSSymbolPool::OSSymbolPool(const OSSymbolPool *old)
	140	{
	141	count = old->count;
	142	nBuckets = old->nBuckets;
	143	buckets = old->buckets;
	144
	145	poolGate = 0; // Do not duplicate the poolGate
	146	}
	147
	148	OSSymbolPool::~OSSymbolPool()
	149	{
	150	if (buckets) {
	151	kfree((vm_offset_t)buckets, nBuckets * sizeof(Bucket));
	152	ACCUMSIZE(-(nBuckets * sizeof(Bucket)));
	153	}
	154
	155	if (poolGate)
	156	kfree((vm_offset_t) poolGate, 36 * 4);
	157	}
	158
	159	unsigned long OSSymbolPool::log2(unsigned int x)
	160	{
	161	unsigned long i;
	162
	163	for (i = 0; x > 1 ; i++)
	164	x >>= 1;
	165	return i;
166	}
167
168	unsigned long OSSymbolPool::exp2ml(unsigned int x)
169	{
170	return (1 << x) - 1;
171	}
172
173	OSSymbolPoolState OSSymbolPool::initHashState()
174	{
175	OSSymbolPoolState newState = { nBuckets, 0 };
176	return newState;
177	}
178
179	OSSymbol OSSymbolPool::nextHashState(OSSymbolPoolState stateP)
180	{
181	Bucket *thisBucket = &buckets[stateP->i];
182
183	while (!stateP->j) {
184	if (!stateP->i)
185	return 0;
186	stateP->i--;
187	thisBucket--;
188	stateP->j = thisBucket->count;
189	}
190
191	stateP->j--;
192	if (thisBucket->count == 1)
193	return (OSSymbol *) thisBucket->symbolP;
194	else
195	return thisBucket->symbolP[stateP->j];
196	}
197
198	void OSSymbolPool::reconstructSymbols()
199	{
200	OSSymbolPool old(this);
201	OSSymbol *insert;
202	OSSymbolPoolState state;
203
204	nBuckets += nBuckets + 1;
205	count = 0;
206	buckets = (Bucket ) kalloc(nBuckets sizeof(Bucket));
207	ACCUMSIZE(nBuckets * sizeof(Bucket));
208	/* @@@ gvdl: Zero test and panic if can't set up pool */
209	bzero(buckets, nBuckets * sizeof(Bucket));
210
211	state = old.initHashState();
212	while ( (insert = old.nextHashState(&state)) )
213	insertSymbol(insert);
214	}
215
9bccf70c	216	OSSymbol OSSymbolPool::findSymbol(const char cString, OSSymbol ***replace) const
1c79356b A	217	{
	218	Bucket *thisBucket;
	219	unsigned int j, inLen, hash;
	220	OSSymbol probeSymbol, *list;
	221
	222	hashSymbol(cString, &hash, &inLen); inLen++;
	223	thisBucket = &buckets[hash % nBuckets];
	224	j = thisBucket->count;
	225
9bccf70c A	226	*replace = NULL;
9bccf70c A	227
1c79356b A	228	if (!j)
	229	return 0;
	230
	231	if (j == 1) {
	232	probeSymbol = (OSSymbol *) thisBucket->symbolP;
	233
	234	if (inLen == probeSymbol->length
9bccf70c A	235	&& (strcmp(probeSymbol->string, cString) == 0)) {
	236	probeSymbol->retain();
	237	if (probeSymbol->getRetainCount() != 0xffff)
	238	return probeSymbol;
	239	else
	240	// replace this one
	241	replace = (OSSymbol *) &thisBucket->symbolP;
	242	}
	243	return 0;
1c79356b A	244	}
	245
	246	for (list = thisBucket->symbolP; j--; list++) {
	247	probeSymbol = *list;
	248	if (inLen == probeSymbol->length
9bccf70c A	249	&& (strcmp(probeSymbol->string, cString) == 0)) {
	250	probeSymbol->retain();
	251	if (probeSymbol->getRetainCount() != 0xffff)
	252	return probeSymbol;
	253	else
	254	// replace this one
	255	*replace = list;
	256	}
1c79356b A	257	}
	258
	259	return 0;
	260	}
	261
	262	OSSymbol OSSymbolPool::insertSymbol(OSSymbol sym)
	263	{
	264	const char *cString = sym->string;
	265	Bucket *thisBucket;
	266	unsigned int j, inLen, hash;
	267	OSSymbol probeSymbol, *list;
	268
	269	hashSymbol(cString, &hash, &inLen); inLen++;
	270	thisBucket = &buckets[hash % nBuckets];
	271	j = thisBucket->count;
	272
	273	if (!j) {
	274	thisBucket->symbolP = (OSSymbol **) sym;
	275	thisBucket->count++;
	276	count++;
	277	return 0;
	278	}
	279
	280	if (j == 1) {
	281	probeSymbol = (OSSymbol *) thisBucket->symbolP;
	282
	283	if (inLen == probeSymbol->length
	284	&& strcmp(probeSymbol->string, cString) == 0)
	285	return probeSymbol;
	286
	287	list = (OSSymbol *) kalloc(2 sizeof(OSSymbol *));
	288	ACCUMSIZE(2 * sizeof(OSSymbol *));
	289	/* @@@ gvdl: Zero test and panic if can't set up pool */
	290	list[0] = sym;
	291	list[1] = probeSymbol;
	292	thisBucket->symbolP = list;
	293	thisBucket->count++;
	294	count++;
	295	if (count > nBuckets)
	296	reconstructSymbols();
	297
	298	return 0;
	299	}
	300
	301	for (list = thisBucket->symbolP; j--; list++) {
	302	probeSymbol = *list;
	303	if (inLen == probeSymbol->length
	304	&& strcmp(probeSymbol->string, cString) == 0)
	305	return probeSymbol;
	306	}
	307
	308	j = thisBucket->count++;
	309	count++;
	310	list = (OSSymbol *) kalloc(thisBucket->count sizeof(OSSymbol *));
	311	ACCUMSIZE(thisBucket->count * sizeof(OSSymbol *));
	312	/* @@@ gvdl: Zero test and panic if can't set up pool */
	313	list[0] = sym;
	314	bcopy(thisBucket->symbolP, list + 1, j * sizeof(OSSymbol *));
	315	kfree((vm_offset_t)thisBucket->symbolP, j * sizeof(OSSymbol *));
	316	ACCUMSIZE(-(j * sizeof(OSSymbol *)));
	317	thisBucket->symbolP = list;
	318	if (count > nBuckets)
	319	reconstructSymbols();
	320
321	return 0;
322	}
323
9bccf70c	324	void OSSymbolPool::removeSymbol(OSSymbol *sym)
1c79356b A	325	{
	326	Bucket *thisBucket;
	327	unsigned int j, inLen, hash;
	328	OSSymbol probeSymbol, *list;
	329
9bccf70c	330	hashSymbol(sym->string, &hash, &inLen); inLen++;
1c79356b A	331	thisBucket = &buckets[hash % nBuckets];
	332	j = thisBucket->count;
	333	list = thisBucket->symbolP;
	334
	335	if (!j)
	336	return;
	337
	338	if (j == 1) {
	339	probeSymbol = (OSSymbol *) list;
	340
9bccf70c	341	if (probeSymbol == sym) {
1c79356b A	342	thisBucket->symbolP = 0;
	343	count--;
	344	thisBucket->count--;
	345	return;
	346	}
	347	return;
	348	}
	349
	350	if (j == 2) {
	351	probeSymbol = list[0];
9bccf70c	352	if (probeSymbol == sym) {
1c79356b A	353	thisBucket->symbolP = (OSSymbol **) list[1];
	354	kfree((vm_offset_t)list, 2 * sizeof(OSSymbol *));
	355	ACCUMSIZE(-(2 * sizeof(OSSymbol *)));
	356	count--;
	357	thisBucket->count--;
	358	return;
	359	}
	360
	361	probeSymbol = list[1];
9bccf70c	362	if (probeSymbol == sym) {
1c79356b A	363	thisBucket->symbolP = (OSSymbol **) list[0];
	364	kfree((vm_offset_t)list, 2 * sizeof(OSSymbol *));
	365	ACCUMSIZE(-(2 * sizeof(OSSymbol *)));
	366	count--;
	367	thisBucket->count--;
	368	return;
	369	}
	370	return;
	371	}
	372
	373	for (; j--; list++) {
	374	probeSymbol = *list;
9bccf70c	375	if (probeSymbol == sym) {
1c79356b A	376
	377	list = (OSSymbol **)
	378	kalloc((thisBucket->count-1) * sizeof(OSSymbol *));
	379	ACCUMSIZE((thisBucket->count-1) * sizeof(OSSymbol *));
	380	if (thisBucket->count-1 != j)
	381	bcopy(thisBucket->symbolP, list,
	382	(thisBucket->count-1-j) * sizeof(OSSymbol *));
	383	if (j)
	384	bcopy(thisBucket->symbolP + thisBucket->count-j,
	385	list + thisBucket->count-1-j,
	386	j * sizeof(OSSymbol *));
	387	kfree((vm_offset_t)thisBucket->symbolP, thisBucket->count * sizeof(OSSymbol *));
	388	ACCUMSIZE(-(thisBucket->count * sizeof(OSSymbol *)));
	389	thisBucket->symbolP = list;
	390	count--;
	391	thisBucket->count--;
	392	return;
	393	}
	394	}
	395	}
	396
	397	/*
	398	*********************************************************************
	399	* From here on we are actually implementing the OSSymbol class
	400	*********************************************************************
	401	*/
	402	OSDefineMetaClassAndStructorsWithInit(OSSymbol, OSString,
	403	OSSymbol::initialize())
	404	OSMetaClassDefineReservedUnused(OSSymbol, 0);
	405	OSMetaClassDefineReservedUnused(OSSymbol, 1);
	406	OSMetaClassDefineReservedUnused(OSSymbol, 2);
	407	OSMetaClassDefineReservedUnused(OSSymbol, 3);
	408	OSMetaClassDefineReservedUnused(OSSymbol, 4);
	409	OSMetaClassDefineReservedUnused(OSSymbol, 5);
	410	OSMetaClassDefineReservedUnused(OSSymbol, 6);
	411	OSMetaClassDefineReservedUnused(OSSymbol, 7);
	412
	413	static OSSymbolPool *pool;
	414
	415	void OSSymbol::initialize()
	416	{
	417	pool = new OSSymbolPool;
	418	assert(pool);
	419
	420	if (!pool->init()) {
	421	delete pool;
	422	assert(false);
	423	};
	424	}
	425
	426	bool OSSymbol::initWithCStringNoCopy(const char *) { return false; }
	427	bool OSSymbol::initWithCString(const char *) { return false; }
	428	bool OSSymbol::initWithString(const OSString *) { return false; }
	429
	430	const OSSymbol OSSymbol::withString(const OSString aString)
	431	{
	432	// This string may be a OSSymbol already, cheap check.
	433	if (OSDynamicCast(OSSymbol, aString)) {
	434	aString->retain();
	435	return (const OSSymbol *) aString;
	436	}
	437	else if (((const OSSymbol *) aString)->flags & kOSStringNoCopy)
	438	return OSSymbol::withCStringNoCopy(aString->getCStringNoCopy());
	439	else
440	return OSSymbol::withCString(aString->getCStringNoCopy());
441	}
442
443	const OSSymbol OSSymbol::withCString(const char cString)
444	{
9bccf70c A	445	OSSymbol **replace;
9bccf70c A	446
1c79356b A	447	pool->closeGate();
1c79356b A	448
9bccf70c A	449	OSSymbol *newSymb = pool->findSymbol(cString, &replace);
	450	if (!newSymb && (newSymb = new OSSymbol) ) {
	451	if (newSymb->OSString::initWithCString(cString)) {
	452	if (replace)
	453	*replace = newSymb;
	454	else
	455	pool->insertSymbol(newSymb);
	456	} else {
	457	newSymb->OSString::free();
1c79356b A	458	newSymb = 0;
	459	}
	460	}
	461	pool->openGate();
	462
	463	return newSymb;
	464	}
	465
	466	const OSSymbol OSSymbol::withCStringNoCopy(const char cString)
	467	{
9bccf70c A	468	OSSymbol **replace;
9bccf70c A	469
1c79356b A	470	pool->closeGate();
1c79356b A	471
9bccf70c A	472	OSSymbol *newSymb = pool->findSymbol(cString, &replace);
	473	if (!newSymb && (newSymb = new OSSymbol) ) {
	474	if (newSymb->OSString::initWithCStringNoCopy(cString)) {
	475	if (replace)
	476	*replace = newSymb;
	477	else
	478	pool->insertSymbol(newSymb);
	479	} else {
	480	newSymb->OSString::free();
1c79356b A	481	newSymb = 0;
	482	}
	483	}
	484	pool->openGate();
	485
	486	return newSymb;
	487	}
	488
	489	void OSSymbol::checkForPageUnload(void startAddr, void endAddr)
	490	{
	491	OSSymbol *probeSymbol;
	492	OSSymbolPoolState state;
	493
	494	pool->closeGate();
	495	state = pool->initHashState();
	496	while ( (probeSymbol = pool->nextHashState(&state)) ) {
	497	if (probeSymbol->string >= startAddr && probeSymbol->string < endAddr) {
	498	const char *oldString = probeSymbol->string;
	499
	500	probeSymbol->string = (char *) kalloc(probeSymbol->length);
	501	ACCUMSIZE(probeSymbol->length);
	502	bcopy(oldString, probeSymbol->string, probeSymbol->length);
	503	probeSymbol->flags &= ~kOSStringNoCopy;
	504	}
	505	}
	506	pool->openGate();
	507	}
	508
	509	void OSSymbol::free()
	510	{
	511	pool->closeGate();
9bccf70c	512	pool->removeSymbol(this);
1c79356b A	513	pool->openGate();
	514
	515	super::free();
	516	}
	517
	518	bool OSSymbol::isEqualTo(const char *aCString) const
	519	{
	520	return super::isEqualTo(aCString);
	521	}
	522
	523	bool OSSymbol::isEqualTo(const OSSymbol *aSymbol) const
	524	{
	525	return aSymbol == this;
	526	}
	527
	528	bool OSSymbol::isEqualTo(const OSMetaClassBase *obj) const
	529	{
	530	OSSymbol * sym;
	531	OSString * str;
	532
	533	if ((sym = OSDynamicCast(OSSymbol, obj)))
	534	return isEqualTo(sym);
	535	else if ((str = OSDynamicCast(OSString, obj)))
	536	return super::isEqualTo(str);
	537	else
	538	return false;
	539	}