Return to OSSymbol.cpp CVS log

Up to [Apple XNU] / XNU / libkern / c++

Annotation of XNU/libkern/c++/OSSymbol.cpp, revision 1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.