shithub: util

Info  •  Files  •  Log  •  Branches

better bsearch, matches bad manual page ☺

--- a/llama2.c

+++ b/llama2.c

@@ -805,26 +805,31 @@

     print("%s", piece);

 }

-TokenIndex *bsearch_call(TokenIndex *tok, TokenIndex *list, int n, int s, int (*comp)(const void *a, const void *b), int A, int B) {

+void *bsearch(void *key, void *base, int num, int size, int (*comp)(void *a, void *b)) {

+	int A = 0;

+	int B = num;

 	int middle = A + ((B - A) / 2);

-	int result = comp(tok, &list[middle]);

+	int result;

-	if (result == 0)

-		return &list[middle];

-

 	if (A == B || A == middle)

 		return nil;

-	if (result > 0)

-		return bsearch_call(tok, list, n, s, comp, middle, B);

+	do {

+		result = comp(key, (void*)((uchar*)base + (middle * size)));

-	return bsearch_call(tok, list, n, s, comp, A, middle);

-}

+		if (result > 0)

+			A = middle;

+		else if (result < 0)

+			B = middle;

+		else

+			return (void*)((uchar*)base + (middle * size));

-void *bsearch(TokenIndex *tok, TokenIndex *list, int n, int s, int (*comp)(const void *a, const void *b)) {

-	return bsearch_call(tok, list, n, s, comp, 0, n);

-}

+		middle = A + ((B - A) / 2);

+	} while(A != B && A != middle);

+

+	return nil;

+}

 int str_lookup(char *str, TokenIndex *sorted_vocab, int vocab_size) {

     // efficiently find the perfect match for str in vocab, return its index or -1 if not found

-- 

⑨