4 Copyright (C) Andrew Tridgell 2004
6 ** NOTE! The following LGPL license applies to the ldb
7 ** library. This does NOT imply that all of Samba is released
10 This library is free software; you can redistribute it and/or
11 modify it under the terms of the GNU Lesser General Public
12 License as published by the Free Software Foundation; either
13 version 3 of the License, or (at your option) any later version.
15 This library is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 Lesser General Public License for more details.
20 You should have received a copy of the GNU Lesser General Public
21 License along with this library; if not, see <http://www.gnu.org/licenses/>.
27 * Component: ldb tdb backend - indexing
29 * Description: indexing routines for ldb tdb backend
31 * Author: Andrew Tridgell
34 #include "ldb_includes.h"
39 find an element in a list, using the given comparison function and
40 assuming that the list is already sorted using comp_fn
42 return -1 if not found, or the index of the first occurance of needle if found
44 static int ldb_list_find(const void *needle,
45 const void *base, size_t nmemb, size_t size,
46 comparison_fn_t comp_fn)
48 const char *base_p = (const char *)base;
49 size_t min_i, max_i, test_i;
58 while (min_i < max_i) {
61 test_i = (min_i + max_i) / 2;
62 /* the following cast looks strange, but is
63 correct. The key to understanding it is that base_p
64 is a pointer to an array of pointers, so we have to
65 dereference it after casting to void **. The strange
66 const in the middle gives us the right type of pointer
67 after the dereference (tridge) */
68 r = comp_fn(needle, *(void * const *)(base_p + (size * test_i)));
70 /* scan back for first element */
72 comp_fn(needle, *(void * const *)(base_p + (size * (test_i-1)))) == 0) {
88 if (comp_fn(needle, *(void * const *)(base_p + (size * min_i))) == 0) {
101 return the dn key to be used for an index
104 static struct ldb_dn *ltdb_index_key(struct ldb_context *ldb,
105 const char *attr, const struct ldb_val *value)
109 const struct ldb_schema_attribute *a;
113 attr_folded = ldb_attr_casefold(ldb, attr);
118 a = ldb_schema_attribute_by_name(ldb, attr);
119 r = a->syntax->canonicalise_fn(ldb, ldb, value, &v);
120 if (r != LDB_SUCCESS) {
121 const char *errstr = ldb_errstring(ldb);
122 /* canonicalisation can be refused. For example,
123 a attribute that takes wildcards will refuse to canonicalise
124 if the value contains a wildcard */
125 ldb_asprintf_errstring(ldb, "Failed to create index key for attribute '%s':%s%s%s",
126 attr, ldb_strerror(r), (errstr?":":""), (errstr?errstr:""));
127 talloc_free(attr_folded);
130 if (ldb_should_b64_encode(&v)) {
131 char *vstr = ldb_base64_encode(ldb, (char *)v.data, v.length);
132 if (!vstr) return NULL;
133 ret = ldb_dn_new_fmt(ldb, ldb, "%s:%s::%s", LTDB_INDEX, attr_folded, vstr);
136 ret = ldb_dn_new_fmt(ldb, ldb, "%s:%s:%.*s", LTDB_INDEX, attr_folded, (int)v.length, (char *)v.data);
139 if (v.data != value->data) {
142 talloc_free(attr_folded);
148 see if a attribute value is in the list of indexed attributes
150 static int ldb_msg_find_idx(const struct ldb_message *msg, const char *attr,
151 unsigned int *v_idx, const char *key)
154 for (i=0;i<msg->num_elements;i++) {
155 if (ldb_attr_cmp(msg->elements[i].name, key) == 0) {
156 const struct ldb_message_element *el = &msg->elements[i];
159 /* in this case we are just looking to see if key is present,
160 we are not spearching for a specific index */
164 for (j=0;j<el->num_values;j++) {
165 if (ldb_attr_cmp((char *)el->values[j].data, attr) == 0) {
177 /* used in sorting dn lists */
178 static int list_cmp(const char **s1, const char **s2)
180 return strcmp(*s1, *s2);
184 return a list of dn's that might match a simple indexed search or
186 static int ltdb_index_dn_simple(struct ldb_module *module,
187 const struct ldb_parse_tree *tree,
188 const struct ldb_message *index_list,
189 struct dn_list *list)
191 struct ldb_context *ldb = module->ldb;
195 struct ldb_message *msg;
200 /* if the attribute isn't in the list of indexed attributes then
201 this node needs a full search */
202 if (ldb_msg_find_idx(index_list, tree->u.equality.attr, NULL, LTDB_IDXATTR) == -1) {
203 return LDB_ERR_OPERATIONS_ERROR;
206 /* the attribute is indexed. Pull the list of DNs that match the
208 dn = ltdb_index_key(ldb, tree->u.equality.attr, &tree->u.equality.value);
209 if (!dn) return LDB_ERR_OPERATIONS_ERROR;
211 msg = talloc(list, struct ldb_message);
213 return LDB_ERR_OPERATIONS_ERROR;
216 ret = ltdb_search_dn1(module, dn, msg);
218 if (ret != LDB_SUCCESS) {
222 for (i=0;i<msg->num_elements;i++) {
223 struct ldb_message_element *el;
225 if (strcmp(msg->elements[i].name, LTDB_IDX) != 0) {
229 el = &msg->elements[i];
231 list->dn = talloc_array(list, char *, el->num_values);
234 return LDB_ERR_OPERATIONS_ERROR;
237 for (j=0;j<el->num_values;j++) {
238 list->dn[list->count] =
239 talloc_strdup(list->dn, (char *)el->values[j].data);
240 if (!list->dn[list->count]) {
242 return LDB_ERR_OPERATIONS_ERROR;
250 if (list->count > 1) {
251 qsort(list->dn, list->count, sizeof(char *), (comparison_fn_t) list_cmp);
258 static int list_union(struct ldb_context *, struct dn_list *, const struct dn_list *);
261 return a list of dn's that might match a leaf indexed search
263 static int ltdb_index_dn_leaf(struct ldb_module *module,
264 const struct ldb_parse_tree *tree,
265 const struct ldb_message *index_list,
266 struct dn_list *list)
268 if (ldb_attr_dn(tree->u.equality.attr) == 0) {
269 list->dn = talloc_array(list, char *, 1);
270 if (list->dn == NULL) {
271 ldb_oom(module->ldb);
272 return LDB_ERR_OPERATIONS_ERROR;
274 list->dn[0] = talloc_strdup(list->dn, (char *)tree->u.equality.value.data);
275 if (list->dn[0] == NULL) {
276 ldb_oom(module->ldb);
277 return LDB_ERR_OPERATIONS_ERROR;
282 return ltdb_index_dn_simple(module, tree, index_list, list);
289 relies on the lists being sorted
291 static int list_intersect(struct ldb_context *ldb,
292 struct dn_list *list, const struct dn_list *list2)
294 struct dn_list *list3;
297 if (list->count == 0 || list2->count == 0) {
299 return LDB_ERR_NO_SUCH_OBJECT;
302 list3 = talloc(ldb, struct dn_list);
304 return LDB_ERR_OPERATIONS_ERROR;
307 list3->dn = talloc_array(list3, char *, list->count);
310 return LDB_ERR_OPERATIONS_ERROR;
314 for (i=0;i<list->count;i++) {
315 if (ldb_list_find(list->dn[i], list2->dn, list2->count,
316 sizeof(char *), (comparison_fn_t)strcmp) != -1) {
317 list3->dn[list3->count] = talloc_move(list3->dn, &list->dn[i]);
320 talloc_free(list->dn[i]);
324 talloc_free(list->dn);
325 list->dn = talloc_move(list, &list3->dn);
326 list->count = list3->count;
329 return LDB_ERR_NO_SUCH_OBJECT;
336 relies on the lists being sorted
338 static int list_union(struct ldb_context *ldb,
339 struct dn_list *list, const struct dn_list *list2)
343 unsigned int count = list->count;
345 if (list->count == 0 && list2->count == 0) {
347 return LDB_ERR_NO_SUCH_OBJECT;
350 d = talloc_realloc(list, list->dn, char *, list->count + list2->count);
352 return LDB_ERR_OPERATIONS_ERROR;
356 for (i=0;i<list2->count;i++) {
357 if (ldb_list_find(list2->dn[i], list->dn, count,
358 sizeof(char *), (comparison_fn_t)strcmp) == -1) {
359 list->dn[list->count] = talloc_strdup(list->dn, list2->dn[i]);
360 if (!list->dn[list->count]) {
361 return LDB_ERR_OPERATIONS_ERROR;
367 if (list->count != count) {
368 qsort(list->dn, list->count, sizeof(char *), (comparison_fn_t)list_cmp);
371 return LDB_ERR_NO_SUCH_OBJECT;
374 static int ltdb_index_dn(struct ldb_module *module,
375 const struct ldb_parse_tree *tree,
376 const struct ldb_message *index_list,
377 struct dn_list *list);
383 static int ltdb_index_dn_or(struct ldb_module *module,
384 const struct ldb_parse_tree *tree,
385 const struct ldb_message *index_list,
386 struct dn_list *list)
388 struct ldb_context *ldb = module->ldb;
392 ret = LDB_ERR_OPERATIONS_ERROR;
396 for (i=0;i<tree->u.list.num_elements;i++) {
397 struct dn_list *list2;
400 list2 = talloc(module, struct dn_list);
402 return LDB_ERR_OPERATIONS_ERROR;
405 v = ltdb_index_dn(module, tree->u.list.elements[i], index_list, list2);
407 if (v == LDB_ERR_NO_SUCH_OBJECT) {
409 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
416 if (v != LDB_SUCCESS && v != LDB_ERR_NO_SUCH_OBJECT) {
418 talloc_free(list->dn);
423 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
425 list->dn = talloc_move(list, &list2->dn);
426 list->count = list2->count;
428 if (list_union(ldb, list, list2) == -1) {
430 return LDB_ERR_OPERATIONS_ERROR;
437 if (list->count == 0) {
438 return LDB_ERR_NO_SUCH_OBJECT;
448 static int ltdb_index_dn_not(struct ldb_module *module,
449 const struct ldb_parse_tree *tree,
450 const struct ldb_message *index_list,
451 struct dn_list *list)
453 /* the only way to do an indexed not would be if we could
454 negate the not via another not or if we knew the total
455 number of database elements so we could know that the
456 existing expression covered the whole database.
458 instead, we just give up, and rely on a full index scan
459 (unless an outer & manages to reduce the list)
461 return LDB_ERR_OPERATIONS_ERROR;
465 AND two index results
467 static int ltdb_index_dn_and(struct ldb_module *module,
468 const struct ldb_parse_tree *tree,
469 const struct ldb_message *index_list,
470 struct dn_list *list)
472 struct ldb_context *ldb = module->ldb;
476 ret = LDB_ERR_OPERATIONS_ERROR;
480 for (i=0;i<tree->u.list.num_elements;i++) {
481 struct dn_list *list2;
484 list2 = talloc(module, struct dn_list);
486 return LDB_ERR_OPERATIONS_ERROR;
489 v = ltdb_index_dn(module, tree->u.list.elements[i], index_list, list2);
491 if (v == LDB_ERR_NO_SUCH_OBJECT) {
493 talloc_free(list->dn);
495 return LDB_ERR_NO_SUCH_OBJECT;
498 if (v != LDB_SUCCESS && v != LDB_ERR_NO_SUCH_OBJECT) {
503 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
505 talloc_free(list->dn);
506 list->dn = talloc_move(list, &list2->dn);
507 list->count = list2->count;
509 if (list_intersect(ldb, list, list2) == -1) {
511 return LDB_ERR_OPERATIONS_ERROR;
517 if (list->count == 0) {
518 talloc_free(list->dn);
519 return LDB_ERR_NO_SUCH_OBJECT;
527 AND index results and ONE level special index
529 static int ltdb_index_dn_one(struct ldb_module *module,
530 struct ldb_dn *parent_dn,
531 struct dn_list *list)
533 struct ldb_context *ldb = module->ldb;
534 struct dn_list *list2;
535 struct ldb_message *msg;
541 list2 = talloc_zero(module, struct dn_list);
543 return LDB_ERR_OPERATIONS_ERROR;
546 /* the attribute is indexed. Pull the list of DNs that match the
548 val.data = (uint8_t *)((uintptr_t)ldb_dn_get_casefold(parent_dn));
549 val.length = strlen((char *)val.data);
550 key = ltdb_index_key(ldb, LTDB_IDXONE, &val);
553 return LDB_ERR_OPERATIONS_ERROR;
556 msg = talloc(list2, struct ldb_message);
559 return LDB_ERR_OPERATIONS_ERROR;
562 ret = ltdb_search_dn1(module, key, msg);
564 if (ret != LDB_SUCCESS) {
568 for (i = 0; i < msg->num_elements; i++) {
569 struct ldb_message_element *el;
571 if (strcmp(msg->elements[i].name, LTDB_IDX) != 0) {
575 el = &msg->elements[i];
577 list2->dn = talloc_array(list2, char *, el->num_values);
580 return LDB_ERR_OPERATIONS_ERROR;
583 for (j = 0; j < el->num_values; j++) {
584 list2->dn[list2->count] = talloc_strdup(list2->dn, (char *)el->values[j].data);
585 if (!list2->dn[list2->count]) {
587 return LDB_ERR_OPERATIONS_ERROR;
593 if (list2->count == 0) {
595 return LDB_ERR_NO_SUCH_OBJECT;
598 if (list2->count > 1) {
599 qsort(list2->dn, list2->count, sizeof(char *), (comparison_fn_t) list_cmp);
602 if (list->count > 0) {
603 if (list_intersect(ldb, list, list2) == -1) {
605 return LDB_ERR_OPERATIONS_ERROR;
608 if (list->count == 0) {
609 talloc_free(list->dn);
611 return LDB_ERR_NO_SUCH_OBJECT;
614 list->dn = talloc_move(list, &list2->dn);
615 list->count = list2->count;
624 return a list of dn's that might match a indexed search or
625 an error. return LDB_ERR_NO_SUCH_OBJECT for no matches, or LDB_SUCCESS for matches
627 static int ltdb_index_dn(struct ldb_module *module,
628 const struct ldb_parse_tree *tree,
629 const struct ldb_message *index_list,
630 struct dn_list *list)
632 int ret = LDB_ERR_OPERATIONS_ERROR;
634 switch (tree->operation) {
636 ret = ltdb_index_dn_and(module, tree, index_list, list);
640 ret = ltdb_index_dn_or(module, tree, index_list, list);
644 ret = ltdb_index_dn_not(module, tree, index_list, list);
647 case LDB_OP_EQUALITY:
648 ret = ltdb_index_dn_leaf(module, tree, index_list, list);
651 case LDB_OP_SUBSTRING:
656 case LDB_OP_EXTENDED:
657 /* we can't index with fancy bitops yet */
658 ret = LDB_ERR_OPERATIONS_ERROR;
666 filter a candidate dn_list from an indexed search into a set of results
667 extracting just the given attributes
669 static int ltdb_index_filter(const struct dn_list *dn_list,
670 struct ldb_handle *handle)
672 struct ltdb_context *ac = talloc_get_type(handle->private_data, struct ltdb_context);
673 struct ldb_reply *ares = NULL;
676 for (i = 0; i < dn_list->count; i++) {
680 ares = talloc_zero(ac, struct ldb_reply);
682 handle->status = LDB_ERR_OPERATIONS_ERROR;
683 handle->state = LDB_ASYNC_DONE;
684 return LDB_ERR_OPERATIONS_ERROR;
687 ares->message = ldb_msg_new(ares);
688 if (!ares->message) {
689 handle->status = LDB_ERR_OPERATIONS_ERROR;
690 handle->state = LDB_ASYNC_DONE;
692 return LDB_ERR_OPERATIONS_ERROR;
696 dn = ldb_dn_new(ares->message, ac->module->ldb, dn_list->dn[i]);
699 return LDB_ERR_OPERATIONS_ERROR;
702 ret = ltdb_search_dn1(ac->module, dn, ares->message);
704 if (ret == LDB_ERR_NO_SUCH_OBJECT) {
705 /* the record has disappeared? yes, this can happen */
710 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
711 /* an internal error */
713 return LDB_ERR_OPERATIONS_ERROR;
716 if (!ldb_match_msg(ac->module->ldb, ares->message, ac->tree, ac->base, ac->scope)) {
721 /* filter the attributes that the user wants */
722 ret = ltdb_filter_attrs(ares->message, ac->attrs);
725 handle->status = LDB_ERR_OPERATIONS_ERROR;
726 handle->state = LDB_ASYNC_DONE;
728 return LDB_ERR_OPERATIONS_ERROR;
731 ares->type = LDB_REPLY_ENTRY;
732 handle->state = LDB_ASYNC_PENDING;
733 handle->status = ac->callback(ac->module->ldb, ac->context, ares);
735 if (handle->status != LDB_SUCCESS) {
736 handle->state = LDB_ASYNC_DONE;
737 return handle->status;
745 search the database with a LDAP-like expression using indexes
746 returns -1 if an indexed search is not possible, in which
747 case the caller should call ltdb_search_full()
749 int ltdb_search_indexed(struct ldb_handle *handle)
751 struct ltdb_context *ac = talloc_get_type(handle->private_data, struct ltdb_context);
752 struct ltdb_private *ltdb = talloc_get_type(ac->module->private_data, struct ltdb_private);
753 struct dn_list *dn_list;
754 int ret, idxattr, idxone;
756 idxattr = idxone = 0;
757 ret = ldb_msg_find_idx(ltdb->cache->indexlist, NULL, NULL, LTDB_IDXATTR);
762 /* We do one level indexing only if requested */
763 ret = ldb_msg_find_idx(ltdb->cache->indexlist, NULL, NULL, LTDB_IDXONE);
768 if ((ac->scope == LDB_SCOPE_ONELEVEL && (idxattr+idxone == 0)) ||
769 (ac->scope == LDB_SCOPE_SUBTREE && idxattr == 0)) {
770 /* no indexs? must do full search */
771 return LDB_ERR_OPERATIONS_ERROR;
774 ret = LDB_ERR_OPERATIONS_ERROR;
776 dn_list = talloc_zero(handle, struct dn_list);
777 if (dn_list == NULL) {
778 return LDB_ERR_OPERATIONS_ERROR;
781 if (ac->scope == LDB_SCOPE_BASE) {
782 /* with BASE searches only one DN can match */
783 dn_list->dn = talloc_array(dn_list, char *, 1);
784 if (dn_list->dn == NULL) {
785 ldb_oom(ac->module->ldb);
786 return LDB_ERR_OPERATIONS_ERROR;
788 dn_list->dn[0] = ldb_dn_alloc_linearized(dn_list, ac->base);
789 if (dn_list->dn[0] == NULL) {
790 ldb_oom(ac->module->ldb);
791 return LDB_ERR_OPERATIONS_ERROR;
797 if (ac->scope != LDB_SCOPE_BASE && idxattr == 1) {
798 ret = ltdb_index_dn(ac->module, ac->tree, ltdb->cache->indexlist, dn_list);
800 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
801 talloc_free(dn_list);
806 if (ac->scope == LDB_SCOPE_ONELEVEL && idxone == 1) {
807 ret = ltdb_index_dn_one(ac->module, ac->base, dn_list);
810 if (ret == LDB_SUCCESS) {
811 /* we've got a candidate list - now filter by the full tree
812 and extract the needed attributes */
813 ret = ltdb_index_filter(dn_list, handle);
814 handle->status = ret;
815 handle->state = LDB_ASYNC_DONE;
818 talloc_free(dn_list);
824 add a index element where this is the first indexed DN for this value
826 static int ltdb_index_add1_new(struct ldb_context *ldb,
827 struct ldb_message *msg,
830 struct ldb_message_element *el;
832 /* add another entry */
833 el = talloc_realloc(msg, msg->elements,
834 struct ldb_message_element, msg->num_elements+1);
836 return LDB_ERR_OPERATIONS_ERROR;
840 msg->elements[msg->num_elements].name = talloc_strdup(msg->elements, LTDB_IDX);
841 if (!msg->elements[msg->num_elements].name) {
842 return LDB_ERR_OPERATIONS_ERROR;
844 msg->elements[msg->num_elements].num_values = 0;
845 msg->elements[msg->num_elements].values = talloc(msg->elements, struct ldb_val);
846 if (!msg->elements[msg->num_elements].values) {
847 return LDB_ERR_OPERATIONS_ERROR;
849 msg->elements[msg->num_elements].values[0].length = strlen(dn);
850 msg->elements[msg->num_elements].values[0].data = discard_const_p(uint8_t, dn);
851 msg->elements[msg->num_elements].num_values = 1;
859 add a index element where this is not the first indexed DN for this
862 static int ltdb_index_add1_add(struct ldb_context *ldb,
863 struct ldb_message *msg,
870 /* for multi-valued attributes we can end up with repeats */
871 for (i=0;i<msg->elements[idx].num_values;i++) {
872 if (strcmp(dn, (char *)msg->elements[idx].values[i].data) == 0) {
877 v2 = talloc_realloc(msg->elements, msg->elements[idx].values,
879 msg->elements[idx].num_values+1);
881 return LDB_ERR_OPERATIONS_ERROR;
883 msg->elements[idx].values = v2;
885 msg->elements[idx].values[msg->elements[idx].num_values].length = strlen(dn);
886 msg->elements[idx].values[msg->elements[idx].num_values].data = discard_const_p(uint8_t, dn);
887 msg->elements[idx].num_values++;
893 add an index entry for one message element
895 static int ltdb_index_add1(struct ldb_module *module, const char *dn,
896 struct ldb_message_element *el, int v_idx)
898 struct ldb_context *ldb = module->ldb;
899 struct ldb_message *msg;
900 struct ldb_dn *dn_key;
904 msg = talloc(module, struct ldb_message);
907 return LDB_ERR_OPERATIONS_ERROR;
910 dn_key = ltdb_index_key(ldb, el->name, &el->values[v_idx]);
913 return LDB_ERR_OPERATIONS_ERROR;
915 talloc_steal(msg, dn_key);
917 ret = ltdb_search_dn1(module, dn_key, msg);
918 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
923 if (ret == LDB_ERR_NO_SUCH_OBJECT) {
925 msg->num_elements = 0;
926 msg->elements = NULL;
929 for (i=0;i<msg->num_elements;i++) {
930 if (strcmp(LTDB_IDX, msg->elements[i].name) == 0) {
935 if (i == msg->num_elements) {
936 ret = ltdb_index_add1_new(ldb, msg, dn);
938 ret = ltdb_index_add1_add(ldb, msg, i, dn);
941 if (ret == LDB_SUCCESS) {
942 ret = ltdb_store(module, msg, TDB_REPLACE);
950 static int ltdb_index_add0(struct ldb_module *module, const char *dn,
951 struct ldb_message_element *elements, int num_el)
953 struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
961 if (ltdb->cache->indexlist->num_elements == 0) {
962 /* no indexed fields */
966 for (i = 0; i < num_el; i++) {
967 ret = ldb_msg_find_idx(ltdb->cache->indexlist, elements[i].name,
972 for (j = 0; j < elements[i].num_values; j++) {
973 ret = ltdb_index_add1(module, dn, &elements[i], j);
974 if (ret != LDB_SUCCESS) {
984 add the index entries for a new record
986 int ltdb_index_add(struct ldb_module *module, const struct ldb_message *msg)
991 dn = ldb_dn_get_linearized(msg->dn);
993 return LDB_ERR_OPERATIONS_ERROR;
996 ret = ltdb_index_add0(module, dn, msg->elements, msg->num_elements);
1003 delete an index entry for one message element
1005 int ltdb_index_del_value(struct ldb_module *module, const char *dn,
1006 struct ldb_message_element *el, int v_idx)
1008 struct ldb_context *ldb = module->ldb;
1009 struct ldb_message *msg;
1010 struct ldb_dn *dn_key;
1018 dn_key = ltdb_index_key(ldb, el->name, &el->values[v_idx]);
1020 return LDB_ERR_OPERATIONS_ERROR;
1023 msg = talloc(dn_key, struct ldb_message);
1025 talloc_free(dn_key);
1026 return LDB_ERR_OPERATIONS_ERROR;
1029 ret = ltdb_search_dn1(module, dn_key, msg);
1030 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
1031 talloc_free(dn_key);
1035 if (ret == LDB_ERR_NO_SUCH_OBJECT) {
1036 /* it wasn't indexed. Did we have an earlier error? If we did then
1038 talloc_free(dn_key);
1042 i = ldb_msg_find_idx(msg, dn, &j, LTDB_IDX);
1044 ldb_debug(ldb, LDB_DEBUG_ERROR,
1045 "ERROR: dn %s not found in %s\n", dn,
1046 ldb_dn_get_linearized(dn_key));
1047 /* it ain't there. hmmm */
1048 talloc_free(dn_key);
1052 if (j != msg->elements[i].num_values - 1) {
1053 memmove(&msg->elements[i].values[j],
1054 &msg->elements[i].values[j+1],
1055 (msg->elements[i].num_values-(j+1)) *
1056 sizeof(msg->elements[i].values[0]));
1058 msg->elements[i].num_values--;
1060 if (msg->elements[i].num_values == 0) {
1061 ret = ltdb_delete_noindex(module, dn_key);
1063 ret = ltdb_store(module, msg, TDB_REPLACE);
1066 talloc_free(dn_key);
1072 delete the index entries for a record
1073 return -1 on failure
1075 int ltdb_index_del(struct ldb_module *module, const struct ldb_message *msg)
1077 struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
1082 /* find the list of indexed fields */
1083 if (ltdb->cache->indexlist->num_elements == 0) {
1084 /* no indexed fields */
1088 if (ldb_dn_is_special(msg->dn)) {
1092 dn = ldb_dn_get_linearized(msg->dn);
1094 return LDB_ERR_OPERATIONS_ERROR;
1097 for (i = 0; i < msg->num_elements; i++) {
1098 ret = ldb_msg_find_idx(ltdb->cache->indexlist, msg->elements[i].name,
1099 NULL, LTDB_IDXATTR);
1103 for (j = 0; j < msg->elements[i].num_values; j++) {
1104 ret = ltdb_index_del_value(module, dn, &msg->elements[i], j);
1105 if (ret != LDB_SUCCESS) {
1115 handle special index for one level searches
1117 int ltdb_index_one(struct ldb_module *module, const struct ldb_message *msg, int add)
1119 struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
1120 struct ldb_message_element el;
1126 /* We index for ONE Level only if requested */
1127 ret = ldb_msg_find_idx(ltdb->cache->indexlist, NULL, NULL, LTDB_IDXONE);
1132 pdn = ldb_dn_get_parent(module, msg->dn);
1134 return LDB_ERR_OPERATIONS_ERROR;
1137 dn = ldb_dn_get_linearized(msg->dn);
1140 return LDB_ERR_OPERATIONS_ERROR;
1143 val.data = (uint8_t *)((uintptr_t)ldb_dn_get_casefold(pdn));
1144 if (val.data == NULL) {
1146 return LDB_ERR_OPERATIONS_ERROR;
1149 val.length = strlen((char *)val.data);
1150 el.name = LTDB_IDXONE;
1155 ret = ltdb_index_add1(module, dn, &el, 0);
1156 } else { /* delete */
1157 ret = ltdb_index_del_value(module, dn, &el, 0);
1167 traversal function that deletes all @INDEX records
1169 static int delete_index(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *state)
1171 const char *dn = "DN=" LTDB_INDEX ":";
1172 if (strncmp((char *)key.dptr, dn, strlen(dn)) == 0) {
1173 return tdb_delete(tdb, key);
1179 traversal function that adds @INDEX records during a re index
1181 static int re_index(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *state)
1183 struct ldb_module *module = (struct ldb_module *)state;
1184 struct ldb_message *msg;
1185 const char *dn = NULL;
1189 if (strncmp((char *)key.dptr, "DN=@", 4) == 0 ||
1190 strncmp((char *)key.dptr, "DN=", 3) != 0) {
1194 msg = talloc(module, struct ldb_message);
1199 ret = ltdb_unpack_data(module, &data, msg);
1205 /* check if the DN key has changed, perhaps due to the
1206 case insensitivity of an element changing */
1207 key2 = ltdb_key(module, msg->dn);
1208 if (key2.dptr == NULL) {
1209 /* probably a corrupt record ... darn */
1210 ldb_debug(module->ldb, LDB_DEBUG_ERROR, "Invalid DN in re_index: %s\n",
1211 ldb_dn_get_linearized(msg->dn));
1215 if (strcmp((char *)key2.dptr, (char *)key.dptr) != 0) {
1216 tdb_delete(tdb, key);
1217 tdb_store(tdb, key2, data, 0);
1219 talloc_free(key2.dptr);
1221 if (msg->dn == NULL) {
1222 dn = (char *)key.dptr + 3;
1224 dn = ldb_dn_get_linearized(msg->dn);
1227 ret = ltdb_index_one(module, msg, 1);
1228 if (ret == LDB_SUCCESS) {
1229 ret = ltdb_index_add0(module, dn, msg->elements, msg->num_elements);
1231 ldb_debug(module->ldb, LDB_DEBUG_ERROR,
1232 "Adding special ONE LEVEL index failed (%s)!\n",
1233 ldb_dn_get_linearized(msg->dn));
1238 if (ret != LDB_SUCCESS) return -1;
1244 force a complete reindex of the database
1246 int ltdb_reindex(struct ldb_module *module)
1248 struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
1251 if (ltdb_cache_reload(module) != 0) {
1252 return LDB_ERR_OPERATIONS_ERROR;
1255 /* first traverse the database deleting any @INDEX records */
1256 ret = tdb_traverse(ltdb->tdb, delete_index, NULL);
1258 return LDB_ERR_OPERATIONS_ERROR;
1261 /* if we don't have indexes we have nothing todo */
1262 if (ltdb->cache->indexlist->num_elements == 0) {
1266 /* now traverse adding any indexes for normal LDB records */
1267 ret = tdb_traverse(ltdb->tdb, re_index, module);
1269 return LDB_ERR_OPERATIONS_ERROR;