Vastly improve performance of distribute_buffer

1 files changed, 11 insertions, 10 deletions

diff --git a/common.h b/common.h
index 984d890..5580dbe 100644
--- a/common.h
+++ b/common.h
@@ -53,20 +53,21 @@ static size_t binary_search(const char *needle, char *haystack, size_t nmel, siz
 
 static void distribute_buffer(char *base, size_t bufnmel, size_t sortnmel, size_t width, cmpfun cmp)
 {
-	char *sorted = base + bufnmel * width;
 	while (bufnmel) {
-		char *last = sorted - width;
-		size_t equals;
-		for (equals = 1; equals < bufnmel; equals++) {
-			if (cmp(last, last - equals * width)) break;
+		char *sorted = base + bufnmel * width;
+
+		size_t insertpos = binary_search(base, sorted, sortnmel, width, cmp);
+		while (insertpos < sortnmel && !cmp(base, sorted + insertpos * width)) {
+			insertpos++;
 		}
 
-		size_t insertpos = binary_search(last, sorted, sortnmel, width, cmp);
-		rotate(sorted - equals * width, insertpos + equals, width, equals);
+		if (insertpos > 0) {
+			rotate(base, bufnmel + insertpos, width, bufnmel);
+		}
 
-		bufnmel  -= equals;
-		sortnmel += equals;
-		sorted   -= equals * width;
+		base     += (insertpos + 1) * width;
+		bufnmel  -= 1;
+		sortnmel -= insertpos;
 	}
 }