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