diff options
| author | Jukka Jylänki <jujjyl@gmail.com> | 2014-03-15 18:41:36 +0200 |
|---|---|---|
| committer | Jukka Jylänki <jujjyl@gmail.com> | 2014-03-28 23:06:16 -0400 |
| commit | 58f9620df20ab6a9bf35c7c91075ecd81597b411 (patch) | |
| tree | c3a97f61a720386d90fab1fe90e3ba2320684b5c | |
| parent | cde38c81c2330c139fa5d7d12a9e3688c5059f9c (diff) | |
Migrate to using musl 0.9.13 libc bsearch to take advantage of compiled asm.js performance in the algorithm.
| -rw-r--r-- | src/library.js | 28 | ||||
| -rw-r--r-- | system/lib/libc/musl/src/stdlib/bsearch.c | 20 | ||||
| -rw-r--r-- | system/lib/libcextra.symbols | 1 | ||||
| -rw-r--r-- | tools/system_libs.py | 1 |
4 files changed, 22 insertions, 28 deletions
diff --git a/src/library.js b/src/library.js index 881fa54b..2ff395c4 100644 --- a/src/library.js +++ b/src/library.js @@ -3035,34 +3035,6 @@ LibraryManager.library = { Module['abort'](); }, - bsearch: function(key, base, num, size, compar) { - function cmp(x, y) { -#if ASM_JS - return Module['dynCall_iii'](compar, x, y); -#else - return FUNCTION_TABLE[compar](x, y); -#endif - }; - var left = 0; - var right = num; - var mid, test, addr; - - while (left < right) { - mid = (left + right) >>> 1; - addr = base + (mid * size); - test = cmp(key, addr); - if (test < 0) { - right = mid; - } else if (test > 0) { - left = mid + 1; - } else { - return addr; - } - } - - return 0; - }, - realloc__deps: ['malloc', 'memcpy', 'free'], realloc: function(ptr, size) { // Very simple, inefficient implementation - if you use a real malloc, best to use diff --git a/system/lib/libc/musl/src/stdlib/bsearch.c b/system/lib/libc/musl/src/stdlib/bsearch.c new file mode 100644 index 00000000..61d89367 --- /dev/null +++ b/system/lib/libc/musl/src/stdlib/bsearch.c @@ -0,0 +1,20 @@ +#include <stdlib.h> + +void *bsearch(const void *key, const void *base, size_t nel, size_t width, int (*cmp)(const void *, const void *)) +{ + void *try; + int sign; + while (nel > 0) { + try = (char *)base + width*(nel/2); + sign = cmp(key, try); + if (!sign) return try; + else if (nel == 1) break; + else if (sign < 0) + nel /= 2; + else { + base = try; + nel -= nel/2; + } + } + return NULL; +} diff --git a/system/lib/libcextra.symbols b/system/lib/libcextra.symbols index 54176b1d..096b261d 100644 --- a/system/lib/libcextra.symbols +++ b/system/lib/libcextra.symbols @@ -22,6 +22,7 @@ T __wcscoll_l T __wcsxfrm_l W __wctype_l + T bsearch T btowc T ecvt T err diff --git a/tools/system_libs.py b/tools/system_libs.py index ee185a51..d37872a4 100644 --- a/tools/system_libs.py +++ b/tools/system_libs.py @@ -221,6 +221,7 @@ def calculate(temp_files, in_temp, stdout, stderr): 'fputws.c', ]], ['stdlib', [ + 'bsearch.c', 'ecvt.c', 'fcvt.c', 'gcvt.c', |