diff options
| author | Andrew Bartlett <abartlet@samba.org> | 2017-08-22 11:16:56 +1200 |
|---|---|---|
| committer | Andrew Bartlett <abartlet@samba.org> | 2017-09-22 21:20:23 +0200 |
| commit | 97b026a73fafa0d8b54d3b69fcce604d8c44ebcc (patch) | |
| tree | c99319335079907fe5a81434aaf02dbfdb7563d6 /lib/ldb | |
| parent | b6bf7e7b0b8bd11d2c804125140b2a8077c11d85 (diff) | |
| download | samba-97b026a73fafa0d8b54d3b69fcce604d8c44ebcc.tar.gz | |
ldb_tdb: Use the binary search more efficiently in list_intersect()
This change ensures we walk the short list and look up into the longer of the two lists.
ltdb_dn_list_find_val() will do a binary search for the GUID case.
Before GUID indexes this was O(n*m), now it is O(n*log(m)).
Signed-off-by: Andrew Bartlett <abartlet@samba.org>
Reviewed-by: Garming Sam <garming@catalyst.net.nz>
Diffstat (limited to 'lib/ldb')
| -rw-r--r-- | lib/ldb/ldb_tdb/ldb_index.c | 18 |
1 files changed, 14 insertions, 4 deletions
diff --git a/lib/ldb/ldb_tdb/ldb_index.c b/lib/ldb/ldb_tdb/ldb_index.c index d8a6958e3ce..16897209b03 100644 --- a/lib/ldb/ldb_tdb/ldb_index.c +++ b/lib/ldb/ldb_tdb/ldb_index.c @@ -839,6 +839,7 @@ static bool list_intersect(struct ldb_context *ldb, struct ltdb_private *ltdb, struct dn_list *list, const struct dn_list *list2) { + const struct dn_list *short_list, *long_list; struct dn_list *list3; unsigned int i; @@ -871,6 +872,14 @@ static bool list_intersect(struct ldb_context *ldb, return true; } + if (list->count > list2->count) { + short_list = list2; + long_list = list; + } else { + short_list = list; + long_list = list2; + } + list3 = talloc_zero(list, struct dn_list); if (list3 == NULL) { return false; @@ -883,10 +892,11 @@ static bool list_intersect(struct ldb_context *ldb, } list3->count = 0; - for (i=0;i<list->count;i++) { - if (ltdb_dn_list_find_val(ltdb, list2, - &list->dn[i]) != -1) { - list3->dn[list3->count] = list->dn[i]; + for (i=0;i<short_list->count;i++) { + /* For the GUID index case, this is a binary search */ + if (ltdb_dn_list_find_val(ltdb, long_list, + &short_list->dn[i]) != -1) { + list3->dn[list3->count] = short_list->dn[i]; list3->count++; } } |