summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorPhilip Van Hoof <philip@codeminded.be>2010-08-31 17:11:26 +0200
committerPhilip Van Hoof <philip@codeminded.be>2010-09-01 17:06:32 +0200
commita240cfd6f7aa2972b3a721a51d0ce8483617186a (patch)
treebdbd2ec514d1a39db6ba4d49f6f39ba98ad0e110 /src
parentad07b6f419163da0739da60e9ac33fcbf9f96a5c (diff)
downloadtracker-a240cfd6f7aa2972b3a721a51d0ce8483617186a.tar.gz
libtracker-data: Use binary search to insert instead of linear search
Diffstat (limited to 'src')
-rw-r--r--src/libtracker-data/tracker-class.c37
1 files changed, 28 insertions, 9 deletions
diff --git a/src/libtracker-data/tracker-class.c b/src/libtracker-data/tracker-class.c
index 05b1f59c2..33cca25d2 100644
--- a/src/libtracker-data/tracker-class.c
+++ b/src/libtracker-data/tracker-class.c
@@ -613,7 +613,8 @@ insert_vals_into_arrays (GArray *sub_pred_ids,
gint pred_id,
gint object_id)
{
- guint i;
+ guint i, j, k;
+ gint64 tmp;
gint64 sub_pred_id;
gint64 obj_graph_id;
@@ -622,16 +623,34 @@ insert_vals_into_arrays (GArray *sub_pred_ids,
obj_graph_id = (gint64) object_id;
obj_graph_id = obj_graph_id << 32 | graph_id;
- for (i = 0; i < sub_pred_ids->len; i++) {
- if (sub_pred_id < g_array_index (sub_pred_ids, gint64, i)) {
- g_array_insert_val (sub_pred_ids, i, sub_pred_id);
- g_array_insert_val (obj_graph_ids, i, obj_graph_id);
- return;
- }
+ i = 0;
+ if (sub_pred_ids->len == 0 || g_array_index (sub_pred_ids, gint64, i) > sub_pred_id) {
+ g_array_prepend_val (sub_pred_ids, sub_pred_id);
+ g_array_prepend_val (obj_graph_ids, obj_graph_id);
+ return;
+ }
+
+ j = sub_pred_ids->len - 1;
+ if (g_array_index (sub_pred_ids, gint64, j) <= sub_pred_id) {
+ g_array_append_val (sub_pred_ids, sub_pred_id);
+ g_array_append_val (obj_graph_ids, obj_graph_id);
+ return;
+ }
+
+ while (j - i > 1) {
+ k = (i + j) / 2;
+ tmp = g_array_index (sub_pred_ids, gint64, k);
+ if (tmp == sub_pred_id) {
+ j = k + 1;
+ break;
+ } else if (tmp > sub_pred_id)
+ j = k;
+ else
+ i = k;
}
- g_array_append_val (sub_pred_ids, sub_pred_id);
- g_array_append_val (obj_graph_ids, obj_graph_id);
+ g_array_insert_val (sub_pred_ids, j, sub_pred_id);
+ g_array_insert_val (obj_graph_ids, j, obj_graph_id);
}
void