libtracker-data: Use binary search to insert instead of linear search

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