![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to OSSymbol.cpp CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / XNU / libkern / c++|
Return to OSSymbol.cpp CVS log | Up to [Apple XNU] / XNU / libkern / c++ |
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.