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