Merge pull request #135 from yipdw/bsearch

bsearch(3) implementation

2 files changed, 74 insertions, 0 deletions

diff --git a/src/library.js b/src/library.js
index a665fc8f..1971ab66 100644
--- a/src/library.js
+++ b/src/library.js
@@ -3201,6 +3201,29 @@ LibraryManager.library = {
     throw 'ABORT: ' + code + ', at ' + (new Error().stack);
   },
 
+  bsearch: function(key, base, num, size, compar) {
+    var cmp = FUNCTION_TABLE[compar];
+    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: ['memcpy'],
   realloc: function(ptr, size) {
     // Very simple, inefficient implementation - if you use a real malloc, best to use
diff --git a/tests/runner.py b/tests/runner.py
index 75436530..49339f51 100644
--- a/tests/runner.py
+++ b/tests/runner.py
@@ -2178,6 +2178,57 @@ if 'benchmark' not in str(sys.argv) and 'sanity' not in str(sys.argv):
           '''
         self.do_run(src)
 
+    def test_bsearch(self):
+      src = '''
+          #include <stdlib.h>
+          #include <stdio.h>
+
+          int cmp(const void* key, const void* member) {
+            return *(int *)key - *(int *)member;
+          }
+
+          void printResult(int* needle, int* haystack, unsigned int len) {
+            void *result = bsearch(needle, haystack, len, sizeof(unsigned int), cmp);
+
+            if (result == NULL) {
+              printf("null\\n");
+            } else {
+              printf("%d\\n", *(unsigned int *)result);
+            }
+          }
+
+          int main() {
+            int a[] = { -2, -1, 0, 6, 7, 9 };
+            int b[] = { 0, 1 };
+
+            /* Find all keys that exist. */
+            for(int i = 0; i < 6; i++) {
+              int val = a[i];
+
+              printResult(&val, a, 6);
+            }
+
+            /* Keys that are covered by the range of the array but aren't in
+             * the array cannot be found.
+             */
+            int v1 = 3;
+            int v2 = 8;
+            printResult(&v1, a, 6);
+            printResult(&v2, a, 6);
+
+            /* Keys outside the range of the array cannot be found. */
+            int v3 = -1;
+            int v4 = 2;
+
+            printResult(&v3, b, 2);
+            printResult(&v4, b, 2);
+
+            return 0;
+          }
+          '''
+
+      self.do_run(src, '-2\n-1\n0\n6\n7\n9\nnull\nnull\nnull\nnull')
+
     def test_nestedstructs(self):
         src = '''
           #include <stdio.h>