From 3c8bed4ee061f96acb4d70a591a9849bddd2a659 Mon Sep 17 00:00:00 2001
From: =?utf8?q?Zbigniew=20J=C4=99drzejewski-Szmek?= <zbyszek@in.waw.pl>
Date: Sat, 30 Mar 2013 22:12:56 -0400
Subject: [PATCH] strbuf: replace quick sort with bubble sort
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

No need to call the heavy artillery, when the original array
is sorted. Reduces complexity from n² log n to n log n, where
n is the number of items in the array, not very large, but
still.
---
 src/shared/strbuf.c | 41 +++++++++++++++++++++++++++++++----------
 1 file changed, 31 insertions(+), 10 deletions(-)

diff --git a/src/shared/strbuf.c b/src/shared/strbuf.c
index abc5c0dd2..e64f1ca07 100644
--- a/src/shared/strbuf.c
+++ b/src/shared/strbuf.c
@@ -95,13 +95,36 @@ void strbuf_cleanup(struct strbuf *str) {
         free(str);
 }
 
-static int strbuf_children_cmp(const void *v1, const void *v2) {
-        const struct strbuf_child_entry *n1 = v1;
-        const struct strbuf_child_entry *n2 = v2;
-
+static int strbuf_children_cmp(const struct strbuf_child_entry *n1,
+                               const struct strbuf_child_entry *n2) {
         return n1->c - n2->c;
 }
 
+static void bubbleinsert(struct strbuf_node *node,
+                         uint8_t c,
+                         struct strbuf_node *node_child) {
+
+        struct strbuf_child_entry new = {
+                .c = c,
+                .child = node_child,
+        };
+        int left = 0, right = node->children_count;
+
+        while (right > left) {
+                int middle = (right + left) / 2 ;
+                if (strbuf_children_cmp(&node->children[middle], &new) <= 0)
+                        left = middle + 1;
+                else
+                        right = middle;
+        }
+
+        memmove(node->children + left + 1, node->children + left,
+                sizeof(struct strbuf_child_entry) * (node->children_count - left));
+        node->children[left] = new;
+
+        node->children_count ++;
+}
+
 /* add string, return the index/offset into the buffer */
 ssize_t strbuf_add_string(struct strbuf *str, const char *s, size_t len) {
         uint8_t c;
@@ -137,8 +160,9 @@ ssize_t strbuf_add_string(struct strbuf *str, const char *s, size_t len) {
                 /* lookup child node */
                 c = s[len - 1 - depth];
                 search.c = c;
-                child = bsearch(&search, node->children, node->children_count, sizeof(struct strbuf_child_entry),
-                                strbuf_children_cmp);
+                child = bsearch(&search, node->children, node->children_count,
+                                sizeof(struct strbuf_child_entry),
+                                (__compar_fn_t) strbuf_children_cmp);
                 if (!child)
                         break;
                 node = child->child;
@@ -171,10 +195,7 @@ ssize_t strbuf_add_string(struct strbuf *str, const char *s, size_t len) {
         str->nodes_count++;
 
         node->children = child;
-        node->children[node->children_count].c = c;
-        node->children[node->children_count].child = node_child;
-        node->children_count++;
-        qsort(node->children, node->children_count, sizeof(struct strbuf_child_entry), strbuf_children_cmp);
+        bubbleinsert(node, c, node_child);
 
         return off;
 }
-- 
2.30.2