ldb_tdb: Sort inputs to list_union()

This allows us to merge the lists finding common values.

Signed-off-by: Andrew Bartlett <abartlet@samba.org>
Reviewed-by: Garming Sam <garming@catalyst.net.nz>

diff --git a/lib/ldb/ldb_tdb/ldb_index.c b/lib/ldb/ldb_tdb/ldb_index.c
index cb14462ad29ded8260c26eaeb2bf39f6eaec206b..45dfbebceb273a9a473ff791ffdfdc0dde0ffac0 100644 (file)
--- a/lib/ldb/ldb_tdb/ldb_index.c
+++ b/lib/ldb/ldb_tdb/ldb_index.c
@@ -53,6 +53,9 @@ static int ltdb_index_dn_base_dn(struct ldb_module *module,
                                 struct ldb_dn *base_dn,
                                 struct dn_list *dn_list);
 
+static void ltdb_dn_list_sort(struct ltdb_private *ltdb,
+                             struct dn_list *list);
+
 /* we put a @IDXVERSION attribute on index entries. This
    allows us to tell if it was written by an older version
 */
@@ -740,7 +743,9 @@ static int ltdb_index_dn_simple(struct ldb_module *module,
 }
 
 
-static bool list_union(struct ldb_context *, struct dn_list *, const struct dn_list *);
+static bool list_union(struct ldb_context *ldb,
+                      struct ltdb_private *ltdb,
+                      struct dn_list *list, struct dn_list *list2);
 
 /*
   return a list of dn's that might match a leaf indexed search
@@ -881,7 +886,8 @@ static bool list_intersect(struct ldb_context *ldb,
   list = list | list2
 */
 static bool list_union(struct ldb_context *ldb,
-                      struct dn_list *list, const struct dn_list *list2)
+                      struct ltdb_private *ltdb,
+                      struct dn_list *list, struct dn_list *list2)
 {
        struct ldb_val *dn3;
 
@@ -902,6 +908,13 @@ static bool list_union(struct ldb_context *ldb,
                return true;
        }
 
+       /*
+        * Sort the lists (if not in GUID DN mode) so we can do
+        * the de-duplication during the merge
+        */
+       ltdb_dn_list_sort(ltdb, list);
+       ltdb_dn_list_sort(ltdb, list2);
+
        dn3 = talloc_array(list, struct ldb_val, list->count + list2->count);
        if (!dn3) {
                ldb_oom(ldb);
@@ -964,7 +977,7 @@ static int ltdb_index_dn_or(struct ldb_module *module,
                        return ret;
                }
 
-               if (!list_union(ldb, list, list2)) {
+               if (!list_union(ldb, ltdb, list, list2)) {
                        talloc_free(list2);
                        return LDB_ERR_OPERATIONS_ERROR;
                }
@@ -1343,6 +1356,25 @@ static int ltdb_index_filter(struct ltdb_private *ltdb,
        return LDB_SUCCESS;
 }
 
+/*
+  sort a DN list
+ */
+static void ltdb_dn_list_sort(struct ltdb_private *ltdb,
+                             struct dn_list *list)
+{
+       if (list->count < 2) {
+               return;
+       }
+
+       /* We know the list is sorted when using the GUID index */
+       if (ltdb->cache->GUID_index_attribute != NULL) {
+               return;
+       }
+
+       TYPESAFE_QSORT(list->dn, list->count,
+                      ldb_val_equal_exact_for_qsort);
+}
+
 /*
   remove any duplicated entries in a indexed result
  */