From e8da3ce84ae3ed4d9b6dacf24866e599a5df7d41 Mon Sep 17 00:00:00 2001 From: Bobby Bingham Date: Sun, 6 Jul 2014 17:00:35 -0500 Subject: Vastly improve performance of distribute_buffer --- common.h | 21 +++++++++++---------- 1 file 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; } } -- cgit v1.2.3