1 /*
2 * Copyright (c) 2000-2016 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28 /* IOSymbol.cpp created by gvdl on Fri 1998-11-17 */
29
30 #define IOKIT_ENABLE_SHARED_PTR
31
32 #include <string.h>
33 #include <sys/cdefs.h>
34
35 #include <kern/locks.h>
36
37 #include <libkern/c++/OSSymbol.h>
38 #include <libkern/c++/OSSharedPtr.h>
39 #include <libkern/c++/OSLib.h>
40 #include <os/cpp_util.h>
41 #include <string.h>
42
43 #define super OSString
44
45 typedef struct { unsigned int i, j; } OSSymbolPoolState;
46
47 #define INITIAL_POOL_SIZE ((unsigned int)((exp2ml(1 + log2(kInitBucketCount)))))
48
49 #define GROW_FACTOR (1)
50 #define SHRINK_FACTOR (3)
51
52 #define GROW_POOL() do \
53 if (count * GROW_FACTOR > nBuckets) { \
54 reconstructSymbols(true); \
55 } \
56 while (0)
57
58 #define SHRINK_POOL() do \
59 if (count * SHRINK_FACTOR < nBuckets && \
60 nBuckets > INITIAL_POOL_SIZE) { \
61 reconstructSymbols(false); \
62 } \
63 while (0)
64
65 class OSSymbolPool
66 {
67 private:
68 static const unsigned int kInitBucketCount = 16;
69
70 typedef struct { unsigned int count; OSSymbol **symbolP; } Bucket;
71
72 Bucket *buckets;
73 unsigned int nBuckets;
74 unsigned int count;
75 lck_rw_t *poolGate;
76
77 static inline void
hashSymbol(const char * s,unsigned int * hashP,unsigned int * lenP)78 hashSymbol(const char *s,
79 unsigned int *hashP,
80 unsigned int *lenP)
81 {
82 unsigned int hash = 0;
83 unsigned int len = 0;
84
85 /* Unroll the loop. */
86 for (;;) {
87 if (!*s) {
88 break;
89 }
90 len++; hash ^= (unsigned int)(unsigned char) *s++;
91 if (!*s) {
92 break;
93 }
94 len++; hash ^= ((unsigned int)(unsigned char) *s++) << 8;
95 if (!*s) {
96 break;
97 }
98 len++; hash ^= ((unsigned int)(unsigned char) *s++) << 16;
99 if (!*s) {
100 break;
101 }
102 len++; hash ^= ((unsigned int)(unsigned char) *s++) << 24;
103 }
104 *lenP = len;
105 *hashP = hash;
106 }
107
108 static unsigned long log2(unsigned int x);
109 static unsigned long exp2ml(unsigned long x);
110
111 void reconstructSymbols(void);
112 void reconstructSymbols(bool grow);
113
114 public:
115 static void *operator new(size_t size);
116 static void operator delete(void *mem, size_t size);
117
OSSymbolPool()118 OSSymbolPool()
119 {
120 }
121 OSSymbolPool(const OSSymbolPool *old);
122 virtual
123 ~OSSymbolPool();
124
125 bool init();
126
127 inline void
closeReadGate()128 closeReadGate()
129 {
130 lck_rw_lock(poolGate, LCK_RW_TYPE_SHARED);
131 }
132
133 inline void
openReadGate()134 openReadGate()
135 {
136 lck_rw_unlock(poolGate, LCK_RW_TYPE_SHARED);
137 }
138
139
140 inline void
closeWriteGate()141 closeWriteGate()
142 {
143 lck_rw_lock(poolGate, LCK_RW_TYPE_EXCLUSIVE);
144 }
145
146 inline void
openWriteGate()147 openWriteGate()
148 {
149 lck_rw_unlock(poolGate, LCK_RW_TYPE_EXCLUSIVE);
150 }
151
152 OSSharedPtr<OSSymbol> findSymbol(const char *cString) const;
153 OSSharedPtr<OSSymbol> insertSymbol(OSSymbol *sym);
154 void removeSymbol(OSSymbol *sym);
155
156 OSSymbolPoolState initHashState();
157 LIBKERN_RETURNS_NOT_RETAINED OSSymbol * nextHashState(OSSymbolPoolState *stateP);
158 };
159
160 void *
operator new(__assert_only size_t size)161 OSSymbolPool::operator new(__assert_only size_t size)
162 {
163 OSMETA_ACCUMSIZE(size);
164 assert(size == sizeof(OSSymbolPool));
165
166 return (void *)kalloc_type_tag(OSSymbolPool, Z_WAITOK_ZERO_NOFAIL,
167 VM_KERN_MEMORY_LIBKERN);
168 }
169
170 void
operator delete(void * mem,__assert_only size_t size)171 OSSymbolPool::operator delete(void *mem, __assert_only size_t size)
172 {
173 assert(size == sizeof(OSSymbolPool));
174 kfree_type(OSSymbolPool, mem);
175 }
176
177 extern lck_grp_t *IOLockGroup;
178
179 bool
init()180 OSSymbolPool::init()
181 {
182 count = 0;
183 nBuckets = INITIAL_POOL_SIZE;
184 buckets = kalloc_type_tag(Bucket, nBuckets, Z_WAITOK_ZERO,
185 VM_KERN_MEMORY_LIBKERN);
186 if (!buckets) {
187 return false;
188 }
189 OSMETA_ACCUMSIZE(nBuckets * sizeof(Bucket));
190
191 poolGate = lck_rw_alloc_init(IOLockGroup, LCK_ATTR_NULL);
192
193 return poolGate != NULL;
194 }
195
OSSymbolPool(const OSSymbolPool * old)196 OSSymbolPool::OSSymbolPool(const OSSymbolPool *old)
197 {
198 count = old->count;
199 nBuckets = old->nBuckets;
200 buckets = old->buckets;
201
202 poolGate = NULL; // Do not duplicate the poolGate
203 }
204
~OSSymbolPool()205 OSSymbolPool::~OSSymbolPool()
206 {
207 if (buckets) {
208 Bucket *thisBucket;
209 for (thisBucket = &buckets[0]; thisBucket < &buckets[nBuckets]; thisBucket++) {
210 if (thisBucket->count > 1) {
211 kfree_type(OSSymbol *, thisBucket->count, thisBucket->symbolP);
212 OSMETA_ACCUMSIZE(-(thisBucket->count * sizeof(OSSymbol *)));
213 }
214 }
215 kfree_type(Bucket, nBuckets, buckets);
216 OSMETA_ACCUMSIZE(-(nBuckets * sizeof(Bucket)));
217 }
218
219 if (poolGate) {
220 lck_rw_free(poolGate, IOLockGroup);
221 }
222 }
223
224 unsigned long
log2(unsigned int x)225 OSSymbolPool::log2(unsigned int x)
226 {
227 unsigned long i;
228
229 for (i = 0; x > 1; i++) {
230 x >>= 1;
231 }
232 return i;
233 }
234
235 unsigned long
exp2ml(unsigned long x)236 OSSymbolPool::exp2ml(unsigned long x)
237 {
238 return (1 << x) - 1;
239 }
240
241 OSSymbolPoolState
initHashState()242 OSSymbolPool::initHashState()
243 {
244 OSSymbolPoolState newState = { nBuckets, 0 };
245 return newState;
246 }
247
248 OSSymbol *
nextHashState(OSSymbolPoolState * stateP)249 OSSymbolPool::nextHashState(OSSymbolPoolState *stateP)
250 {
251 Bucket *thisBucket = &buckets[stateP->i];
252
253 while (!stateP->j) {
254 if (!stateP->i) {
255 return NULL;
256 }
257 stateP->i--;
258 thisBucket--;
259 stateP->j = thisBucket->count;
260 }
261
262 stateP->j--;
263 if (thisBucket->count == 1) {
264 return (OSSymbol *) thisBucket->symbolP;
265 } else {
266 return thisBucket->symbolP[stateP->j];
267 }
268 }
269
270 void
reconstructSymbols(void)271 OSSymbolPool::reconstructSymbols(void)
272 {
273 this->reconstructSymbols(true);
274 }
275
276 void
reconstructSymbols(bool grow)277 OSSymbolPool::reconstructSymbols(bool grow)
278 {
279 unsigned int new_nBuckets = nBuckets;
280 OSSymbol *insert;
281 OSSymbolPoolState state;
282
283 if (grow) {
284 new_nBuckets += new_nBuckets + 1;
285 } else {
286 /* Don't shrink the pool below the default initial size.
287 */
288 if (nBuckets <= INITIAL_POOL_SIZE) {
289 return;
290 }
291 new_nBuckets = (new_nBuckets - 1) / 2;
292 }
293
294 /* Create old pool to iterate after doing above check, cause it
295 * gets finalized at return.
296 */
297 OSSymbolPool old(this);
298
299 count = 0;
300 nBuckets = new_nBuckets;
301 buckets = kalloc_type_tag(Bucket, nBuckets, Z_WAITOK_ZERO,
302 VM_KERN_MEMORY_LIBKERN);
303 OSMETA_ACCUMSIZE(nBuckets * sizeof(Bucket));
304 /* @@@ gvdl: Zero test and panic if can't set up pool */
305
306 state = old.initHashState();
307 while ((insert = old.nextHashState(&state))) {
308 insertSymbol(insert);
309 }
310 }
311
312 OSSharedPtr<OSSymbol>
findSymbol(const char * cString) const313 OSSymbolPool::findSymbol(const char *cString) const
314 {
315 Bucket *thisBucket;
316 unsigned int j, inLen, hash;
317 OSSymbol *probeSymbol, **list;
318 OSSharedPtr<OSSymbol> ret;
319
320 hashSymbol(cString, &hash, &inLen); inLen++;
321 thisBucket = &buckets[hash % nBuckets];
322 j = thisBucket->count;
323
324 if (!j) {
325 return NULL;
326 }
327
328 if (j == 1) {
329 probeSymbol = (OSSymbol *) thisBucket->symbolP;
330
331 if (inLen == probeSymbol->length
332 && strncmp(probeSymbol->string, cString, probeSymbol->length) == 0
333 && probeSymbol->taggedTryRetain(nullptr)) {
334 ret.reset(probeSymbol, OSNoRetain);
335 return ret;
336 }
337 return NULL;
338 }
339
340 for (list = thisBucket->symbolP; j--; list++) {
341 probeSymbol = *list;
342 if (inLen == probeSymbol->length
343 && strncmp(probeSymbol->string, cString, probeSymbol->length) == 0
344 && probeSymbol->taggedTryRetain(nullptr)) {
345 ret.reset(probeSymbol, OSNoRetain);
346 return ret;
347 }
348 }
349
350 return NULL;
351 }
352
353 OSSharedPtr<OSSymbol>
insertSymbol(OSSymbol * sym)354 OSSymbolPool::insertSymbol(OSSymbol *sym)
355 {
356 const char *cString = sym->string;
357 Bucket *thisBucket;
358 unsigned int j, inLen, hash;
359 OSSymbol *probeSymbol, **list;
360 OSSharedPtr<OSSymbol> ret;
361
362 hashSymbol(cString, &hash, &inLen); inLen++;
363 thisBucket = &buckets[hash % nBuckets];
364 j = thisBucket->count;
365
366 if (!j) {
367 thisBucket->symbolP = (OSSymbol **) sym;
368 thisBucket->count++;
369 count++;
370 return nullptr;
371 }
372
373 if (j == 1) {
374 probeSymbol = (OSSymbol *) thisBucket->symbolP;
375
376 if (inLen == probeSymbol->length
377 && strncmp(probeSymbol->string, cString, probeSymbol->length) == 0
378 && probeSymbol->taggedTryRetain(nullptr)) {
379 ret.reset(probeSymbol, OSNoRetain);
380 return ret;
381 }
382
383 list = kalloc_type_tag(OSSymbol *, 2, Z_WAITOK_ZERO_NOFAIL,
384 VM_KERN_MEMORY_LIBKERN);
385 OSMETA_ACCUMSIZE(2 * sizeof(OSSymbol *));
386 /* @@@ gvdl: Zero test and panic if can't set up pool */
387 list[0] = sym;
388 list[1] = probeSymbol;
389 thisBucket->symbolP = list;
390 thisBucket->count++;
391 count++;
392 GROW_POOL();
393
394 return nullptr;
395 }
396
397 for (list = thisBucket->symbolP; j--; list++) {
398 probeSymbol = *list;
399 if (inLen == probeSymbol->length
400 && strncmp(probeSymbol->string, cString, probeSymbol->length) == 0
401 && probeSymbol->taggedTryRetain(nullptr)) {
402 ret.reset(probeSymbol, OSNoRetain);
403 return ret;
404 }
405 }
406
407 j = thisBucket->count++;
408 count++;
409 list = kalloc_type_tag(OSSymbol *, thisBucket->count, Z_WAITOK_ZERO,
410 VM_KERN_MEMORY_LIBKERN);
411 /* @@@ gvdl: Zero test and panic if can't set up pool */
412 list[0] = sym;
413 bcopy(thisBucket->symbolP, list + 1, j * sizeof(OSSymbol *));
414 kfree_type(OSSymbol *, j, thisBucket->symbolP);
415
416 OSMETA_ACCUMSIZE((thisBucket->count - j) * sizeof(OSSymbol *));
417 thisBucket->symbolP = list;
418 GROW_POOL();
419
420 return nullptr;
421 }
422
423 void
removeSymbol(OSSymbol * sym)424 OSSymbolPool::removeSymbol(OSSymbol *sym)
425 {
426 Bucket *thisBucket;
427 unsigned int j, inLen, hash;
428 OSSymbol *probeSymbol, **list;
429
430 hashSymbol(sym->string, &hash, &inLen); inLen++;
431 thisBucket = &buckets[hash % nBuckets];
432 j = thisBucket->count;
433 list = thisBucket->symbolP;
434
435 if (!j) {
436 // couldn't find the symbol; probably means string hash changed
437 panic("removeSymbol %s count %d ", sym->string ? sym->string : "no string", count);
438 return;
439 }
440
441 if (j == 1) {
442 probeSymbol = (OSSymbol *) list;
443
444 if (probeSymbol == sym) {
445 thisBucket->symbolP = NULL;
446 count--;
447 thisBucket->count--;
448 SHRINK_POOL();
449 return;
450 }
451 // couldn't find the symbol; probably means string hash changed
452 panic("removeSymbol %s count %d ", sym->string ? sym->string : "no string", count);
453 return;
454 }
455
456 if (j == 2) {
457 probeSymbol = list[0];
458 if (probeSymbol == sym) {
459 thisBucket->symbolP = (OSSymbol **) list[1];
460 kfree_type(OSSymbol *, 2, list);
461 OSMETA_ACCUMSIZE(-(2 * sizeof(OSSymbol *)));
462 count--;
463 thisBucket->count--;
464 SHRINK_POOL();
465 return;
466 }
467
468 probeSymbol = list[1];
469 if (probeSymbol == sym) {
470 thisBucket->symbolP = (OSSymbol **) list[0];
471 kfree_type(OSSymbol *, 2, list);
472 OSMETA_ACCUMSIZE(-(2 * sizeof(OSSymbol *)));
473 count--;
474 thisBucket->count--;
475 SHRINK_POOL();
476 return;
477 }
478 // couldn't find the symbol; probably means string hash changed
479 panic("removeSymbol %s count %d ", sym->string ? sym->string : "no string", count);
480 return;
481 }
482
483 for (; j--; list++) {
484 probeSymbol = *list;
485 if (probeSymbol == sym) {
486 list = kalloc_type_tag(OSSymbol *, thisBucket->count - 1,
487 Z_WAITOK, VM_KERN_MEMORY_LIBKERN);
488 if (thisBucket->count - 1 != j) {
489 bcopy(thisBucket->symbolP, list,
490 (thisBucket->count - 1 - j) * sizeof(OSSymbol *));
491 }
492 if (j) {
493 bcopy(thisBucket->symbolP + thisBucket->count - j,
494 list + thisBucket->count - 1 - j,
495 j * sizeof(OSSymbol *));
496 }
497 kfree_type(OSSymbol *, thisBucket->count, thisBucket->symbolP);
498 OSMETA_ACCUMSIZE(-sizeof(OSSymbol *));
499 thisBucket->symbolP = list;
500 count--;
501 thisBucket->count--;
502 return;
503 }
504 }
505 // couldn't find the symbol; probably means string hash changed
506 panic("removeSymbol %s count %d ", sym->string ? sym->string : "no string", count);
507 }
508
509 /*
510 *********************************************************************
511 * From here on we are actually implementing the OSSymbol class
512 *********************************************************************
513 */
514 OSDefineMetaClassAndStructorsWithInitAndZone(OSSymbol, OSString,
515 OSSymbol::initialize(), ZC_ZFREE_CLEARMEM)
516 OSMetaClassDefineReservedUnused(OSSymbol, 0);
517 OSMetaClassDefineReservedUnused(OSSymbol, 1);
518 OSMetaClassDefineReservedUnused(OSSymbol, 2);
519 OSMetaClassDefineReservedUnused(OSSymbol, 3);
520 OSMetaClassDefineReservedUnused(OSSymbol, 4);
521 OSMetaClassDefineReservedUnused(OSSymbol, 5);
522 OSMetaClassDefineReservedUnused(OSSymbol, 6);
523 OSMetaClassDefineReservedUnused(OSSymbol, 7);
524
525 static OSSymbolPool *pool;
526
527 void
initialize()528 OSSymbol::initialize()
529 {
530 pool = new OSSymbolPool;
531 assert(pool);
532
533 if (pool && !pool->init()) {
534 delete pool;
535 assert(false);
536 }
537 ;
538 }
539
540 bool
initWithCStringNoCopy(const char *)541 OSSymbol::initWithCStringNoCopy(const char *)
542 {
543 return false;
544 }
545 bool
initWithCString(const char *)546 OSSymbol::initWithCString(const char *)
547 {
548 return false;
549 }
550 bool
initWithString(const OSString *)551 OSSymbol::initWithString(const OSString *)
552 {
553 return false;
554 }
555
556 OSSharedPtr<const OSSymbol>
withString(const OSString * aString)557 OSSymbol::withString(const OSString *aString)
558 {
559 // This string may be a OSSymbol already, cheap check.
560 if (OSDynamicCast(OSSymbol, aString)) {
561 OSSharedPtr<const OSSymbol> aStringNew((const OSSymbol *)aString, OSRetain);
562 return aStringNew;
563 } else if (((const OSSymbol *) aString)->flags & kOSStringNoCopy) {
564 return OSSymbol::withCStringNoCopy(aString->getCStringNoCopy());
565 } else {
566 return OSSymbol::withCString(aString->getCStringNoCopy());
567 }
568 }
569
570 OSSharedPtr<const OSSymbol>
withCString(const char * cString)571 OSSymbol::withCString(const char *cString)
572 {
573 OSSharedPtr<const OSSymbol> symbol;
574
575 // Check if the symbol exists already, we don't need to take a lock here,
576 // since existingSymbolForCString will take the shared lock.
577 symbol = OSSymbol::existingSymbolForCString(cString);
578 if (symbol) {
579 return symbol;
580 }
581
582 OSSharedPtr<OSSymbol> newSymb = OSMakeShared<OSSymbol>();
583 if (!newSymb) {
584 return os::move(newSymb);
585 }
586
587 if (newSymb->OSString::initWithCString(cString)) {
588 pool->closeWriteGate();
589 symbol = pool->insertSymbol(newSymb.get());
590 pool->openWriteGate();
591
592 if (symbol) {
593 // Somebody must have inserted the new symbol so free our copy
594 newSymb.detach()->OSString::free();
595 return symbol;
596 }
597 }
598
599 return os::move(newSymb); // return the newly created & inserted symbol.
600 }
601
602 OSSharedPtr<const OSSymbol>
withCStringNoCopy(const char * cString)603 OSSymbol::withCStringNoCopy(const char *cString)
604 {
605 OSSharedPtr<const OSSymbol> symbol;
606 OSSharedPtr<OSSymbol> newSymb;
607
608 // Check if the symbol exists already, we don't need to take a lock here,
609 // since existingSymbolForCString will take the shared lock.
610 symbol = OSSymbol::existingSymbolForCString(cString);
611 if (symbol) {
612 return symbol;
613 }
614
615 newSymb = OSMakeShared<OSSymbol>();
616 if (!newSymb) {
617 return os::move(newSymb);
618 }
619
620 if (newSymb->OSString::initWithCStringNoCopy(cString)) {
621 pool->closeWriteGate();
622 symbol = pool->insertSymbol(newSymb.get());
623 pool->openWriteGate();
624
625 if (symbol) {
626 newSymb.detach()->OSString::free();
627 // Somebody must have inserted the new symbol so free our copy
628 return symbol;
629 }
630 }
631
632 return os::move(newSymb); // return the newly created & inserted symbol.
633 }
634
635 OSSharedPtr<const OSSymbol>
existingSymbolForString(const OSString * aString)636 OSSymbol::existingSymbolForString(const OSString *aString)
637 {
638 if (OSDynamicCast(OSSymbol, aString)) {
639 OSSharedPtr<const OSSymbol> aStringNew((const OSSymbol *)aString, OSRetain);
640 return aStringNew;
641 }
642
643 return OSSymbol::existingSymbolForCString(aString->getCStringNoCopy());
644 }
645
646 OSSharedPtr<const OSSymbol>
existingSymbolForCString(const char * cString)647 OSSymbol::existingSymbolForCString(const char *cString)
648 {
649 OSSharedPtr<OSSymbol> symbol;
650
651 pool->closeReadGate();
652 symbol = pool->findSymbol(cString);
653 pool->openReadGate();
654
655 return os::move(symbol);
656 }
657
658 void
checkForPageUnload(void * startAddr,void * endAddr)659 OSSymbol::checkForPageUnload(void *startAddr, void *endAddr)
660 {
661 OSSymbol *probeSymbol;
662 OSSymbolPoolState state;
663
664 pool->closeWriteGate();
665 state = pool->initHashState();
666 while ((probeSymbol = pool->nextHashState(&state))) {
667 if (probeSymbol->string >= startAddr && probeSymbol->string < endAddr) {
668 probeSymbol->OSString::initWithCString(probeSymbol->string);
669 }
670 }
671 pool->openWriteGate();
672 }
673
674 void
taggedRelease(const void * tag) const675 OSSymbol::taggedRelease(const void *tag) const
676 {
677 super::taggedRelease(tag);
678 }
679
680 void
taggedRelease(const void * tag,const int when) const681 OSSymbol::taggedRelease(const void *tag, const int when) const
682 {
683 super::taggedRelease(tag, when);
684 }
685
686 void
free()687 OSSymbol::free()
688 {
689 pool->closeWriteGate();
690 pool->removeSymbol(this);
691 pool->openWriteGate();
692 super::free();
693 }
694
695 bool
isEqualTo(const char * aCString) const696 OSSymbol::isEqualTo(const char *aCString) const
697 {
698 return super::isEqualTo(aCString);
699 }
700
701 bool
isEqualTo(const OSSymbol * aSymbol) const702 OSSymbol::isEqualTo(const OSSymbol *aSymbol) const
703 {
704 return aSymbol == this;
705 }
706
707 bool
isEqualTo(const OSMetaClassBase * obj) const708 OSSymbol::isEqualTo(const OSMetaClassBase *obj) const
709 {
710 OSSymbol * sym;
711 OSString * str;
712
713 if ((sym = OSDynamicCast(OSSymbol, obj))) {
714 return isEqualTo(sym);
715 } else if ((str = OSDynamicCast(OSString, obj))) {
716 return super::isEqualTo(str);
717 } else {
718 return false;
719 }
720 }
721
722 unsigned int
bsearch(const void * key,const void * array,unsigned int arrayCount,size_t memberSize)723 OSSymbol::bsearch(
724 const void * key,
725 const void * array,
726 unsigned int arrayCount,
727 size_t memberSize)
728 {
729 const void **p;
730 unsigned int baseIdx = 0;
731 unsigned int lim;
732
733 for (lim = arrayCount; lim; lim >>= 1) {
734 p = (typeof(p))(((uintptr_t) array) + (baseIdx + (lim >> 1)) * memberSize);
735 if (key == *p) {
736 return baseIdx + (lim >> 1);
737 }
738 if (key > *p) {
739 // move right
740 baseIdx += (lim >> 1) + 1;
741 lim--;
742 }
743 // else move left
744 }
745 // not found, insertion point here
746 return baseIdx + (lim >> 1);
747 }
748