From 3be3043ed99a847b7295c1fa91826bad6a60eeb2 Mon Sep 17 00:00:00 2001
From: Nalin Dahyabhai <nalin@dahyabhai.net>
Date: Thu, 21 Apr 2011 16:38:08 -0400
Subject: - when we can keep the list sorted we can search it faster

---
 src/format.c | 105 ++++++++++++++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 94 insertions(+), 11 deletions(-)

(limited to 'src/format.c')

diff --git a/src/format.c b/src/format.c
index 40f0130..7c7eacb 100644
--- a/src/format.c
+++ b/src/format.c
@@ -24,6 +24,7 @@
 #endif
 
 #include <sys/types.h>
+#include <assert.h>
 #include <ctype.h>
 #include <errno.h>
 #include <fnmatch.h>
@@ -151,32 +152,114 @@ format_make_sdn_list(char **list)
 	return ret;
 }
 
-struct slapi_dn **
-format_add_sdn_list(struct slapi_dn ***list, const char *dn)
+/* Find the DN in a sorted list.  Return either where it is, or where it
+ * should be inserted. */
+static bool_t
+format_bsearch_sdn_list(struct slapi_dn **list, struct slapi_dn *sdn,
+			int len, unsigned int *point)
+{
+	int lo, mid, hi, result;
+	bool_t found;
+
+	if (len == -1) {
+		for (len = 0; (list != NULL) && (list[len] != NULL); len++) {
+			continue;
+		}
+	}
+	if (len > 0) {
+		lo = 0;
+		hi = len - 1;
+		for (;;) {
+			mid = (lo + hi) / 2;
+			result = slapi_sdn_compare(list[mid], &sdn);
+			if (result == 0) {
+				found = TRUE;
+				*point = mid;
+				break;
+			}
+			if (lo == hi) {
+				found = FALSE;
+				if (result < 0) {
+					*point = mid + 1;
+				} else {
+					*point = mid;
+				}
+				break;
+			}
+			if (result < 0) {
+				lo = MIN(hi, mid + 1);
+			} else {
+				hi = MAX(lo, mid - 1);
+			}
+		}
+	} else {
+		found = FALSE;
+		*point = 0;
+	}
+	return found;
+}
+
+static struct slapi_dn **
+format_add_sdn_list_maybe_sorted(struct slapi_dn ***list, const char *dn,
+				 bool_t sorted)
 {
 	struct slapi_dn **ret, *sdn;
-	unsigned int i;
+	unsigned int len, point;
+
 	sdn = slapi_sdn_new_dn_byval(dn);
-	for (i = 0;
-	     (list != NULL) && (*list != NULL) && ((*list)[i] != NULL);
-	     i++) {
-		if (slapi_sdn_compare(sdn, (*list)[i]) == 0) {
+	/* Figure out how long the current list is. */
+	for (len = 0;
+	     (list != NULL) && (*list != NULL) && ((*list)[len] != NULL);
+	     len++) {
+		/* If it's not sorted, we have to check every entry anyway, so
+		 * we might as well do it now. */
+		if (!sorted && (slapi_sdn_compare((*list)[len], sdn) == 0)) {
 			slapi_sdn_free(&sdn);
 			return *list;
 		}
 		continue;
 	}
-	ret = malloc((i + 2) * sizeof(struct slapi_dn*));
+	if (sorted) {
+		/* If it's sorted, we can search for the entry or figure out
+		 * where to insert the new one. */
+		if (format_bsearch_sdn_list(*list, sdn, len, &point)) {
+			slapi_sdn_free(&sdn);
+			return *list;
+		}
+	} else {
+		/* We're appending. */
+		point = len;
+	}
+	ret = malloc((len + 2) * sizeof(struct slapi_dn*));
 	if (ret != NULL) {
-		memcpy(ret, *list, i * sizeof(struct slapi_dn*));
-		ret[i++] = sdn;
-		ret[i] = NULL;
+		/* Copy pointers to entries before the insertion point. */
+		memcpy(ret, *list, point * sizeof(ret[0]));
+		/* The new entry. */
+		ret[point] = sdn;
+		/* If there are any after the insertion point, add them. */
+		if (len > point) {
+			memcpy(ret + point + 1, (*list) + point,
+			       (len - point) * sizeof(ret[0]));
+		}
+		ret[len + 1] = NULL;
 		free(*list);
 		*list = ret;
 	}
 	return *list;
 }
 
+struct slapi_dn **
+format_add_sdn_list(struct slapi_dn ***list, const char *dn)
+{
+	return format_add_sdn_list_maybe_sorted(list, dn, FALSE);
+}
+
+struct slapi_dn **
+format_add_sdn_list_sorted(struct slapi_dn ***list, const char *dn)
+{
+	return format_add_sdn_list_maybe_sorted(list, dn, TRUE);
+}
+
 static int
 format_check_entry(const char *dn, char *filter, void *identity)
 {
-- 
cgit