summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorZbigniew Jędrzejewski-Szmek <zbyszek@in.waw.pl>2013-03-30 22:12:56 -0400
committerZbigniew Jędrzejewski-Szmek <zbyszek@in.waw.pl>2013-03-31 14:35:17 -0400
commit3c8bed4ee061f96acb4d70a591a9849bddd2a659 (patch)
tree9be6b06310d2e8837dfe928487e5a47aee4fde03
parenta9c307e5d2157c561eae7fc76303cadf7a77b99e (diff)
strbuf: replace quick sort with bubble sort
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.
-rw-r--r--src/shared/strbuf.c41
1 files changed, 31 insertions, 10 deletions
diff --git a/src/shared/strbuf.c b/src/shared/strbuf.c
index abc5c0dd29..e64f1ca07a 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;
}