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 ltdb_context *ac)
672 struct ldb_message *msg;
675 for (i = 0; i < dn_list->count; i++) {
679 msg = ldb_msg_new(ac);
681 return LDB_ERR_OPERATIONS_ERROR;
684 dn = ldb_dn_new(msg, ac->module->ldb, dn_list->dn[i]);
687 return LDB_ERR_OPERATIONS_ERROR;
690 ret = ltdb_search_dn1(ac->module, dn, msg);
692 if (ret == LDB_ERR_NO_SUCH_OBJECT) {
693 /* the record has disappeared? yes, this can happen */
698 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
699 /* an internal error */
701 return LDB_ERR_OPERATIONS_ERROR;
704 if (!ldb_match_msg(ac->module->ldb, msg,
705 ac->tree, ac->base, ac->scope)) {
710 /* filter the attributes that the user wants */
711 ret = ltdb_filter_attrs(msg, ac->attrs);
715 return LDB_ERR_OPERATIONS_ERROR;
718 ret = ldb_module_send_entry(ac->req, msg);
719 if (ret != LDB_SUCCESS) {
720 ac->callback_failed = true;
729 search the database with a LDAP-like expression using indexes
730 returns -1 if an indexed search is not possible, in which
731 case the caller should call ltdb_search_full()
733 int ltdb_search_indexed(struct ltdb_context *ac)
735 struct ltdb_private *ltdb = talloc_get_type(ac->module->private_data, struct ltdb_private);
736 struct dn_list *dn_list;
737 int ret, idxattr, idxone;
739 idxattr = idxone = 0;
740 ret = ldb_msg_find_idx(ltdb->cache->indexlist, NULL, NULL, LTDB_IDXATTR);
745 /* We do one level indexing only if requested */
746 ret = ldb_msg_find_idx(ltdb->cache->indexlist, NULL, NULL, LTDB_IDXONE);
751 if ((ac->scope == LDB_SCOPE_ONELEVEL && (idxattr+idxone == 0)) ||
752 (ac->scope == LDB_SCOPE_SUBTREE && idxattr == 0)) {
753 /* no indexes? must do full search */
754 return LDB_ERR_OPERATIONS_ERROR;
757 ret = LDB_ERR_OPERATIONS_ERROR;
759 dn_list = talloc_zero(ac, struct dn_list);
760 if (dn_list == NULL) {
761 return LDB_ERR_OPERATIONS_ERROR;
764 if (ac->scope == LDB_SCOPE_BASE) {
765 /* with BASE searches only one DN can match */
766 dn_list->dn = talloc_array(dn_list, char *, 1);
767 if (dn_list->dn == NULL) {
768 ldb_oom(ac->module->ldb);
769 return LDB_ERR_OPERATIONS_ERROR;
771 dn_list->dn[0] = ldb_dn_alloc_linearized(dn_list, ac->base);
772 if (dn_list->dn[0] == NULL) {
773 ldb_oom(ac->module->ldb);
774 return LDB_ERR_OPERATIONS_ERROR;
780 if (ac->scope != LDB_SCOPE_BASE && idxattr == 1) {
781 ret = ltdb_index_dn(ac->module, ac->tree, ltdb->cache->indexlist, dn_list);
783 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
784 talloc_free(dn_list);
789 if (ac->scope == LDB_SCOPE_ONELEVEL && idxone == 1) {
790 ret = ltdb_index_dn_one(ac->module, ac->base, dn_list);
793 if (ret == LDB_SUCCESS) {
794 /* we've got a candidate list - now filter by the full tree
795 and extract the needed attributes */
796 ret = ltdb_index_filter(dn_list, ac);
799 talloc_free(dn_list);
805 add a index element where this is the first indexed DN for this value
807 static int ltdb_index_add1_new(struct ldb_context *ldb,
808 struct ldb_message *msg,
811 struct ldb_message_element *el;
813 /* add another entry */
814 el = talloc_realloc(msg, msg->elements,
815 struct ldb_message_element, msg->num_elements+1);
817 return LDB_ERR_OPERATIONS_ERROR;
821 msg->elements[msg->num_elements].name = talloc_strdup(msg->elements, LTDB_IDX);
822 if (!msg->elements[msg->num_elements].name) {
823 return LDB_ERR_OPERATIONS_ERROR;
825 msg->elements[msg->num_elements].num_values = 0;
826 msg->elements[msg->num_elements].values = talloc(msg->elements, struct ldb_val);
827 if (!msg->elements[msg->num_elements].values) {
828 return LDB_ERR_OPERATIONS_ERROR;
830 msg->elements[msg->num_elements].values[0].length = strlen(dn);
831 msg->elements[msg->num_elements].values[0].data = discard_const_p(uint8_t, dn);
832 msg->elements[msg->num_elements].num_values = 1;
840 add a index element where this is not the first indexed DN for this
843 static int ltdb_index_add1_add(struct ldb_context *ldb,
844 struct ldb_message *msg,
851 /* for multi-valued attributes we can end up with repeats */
852 for (i=0;i<msg->elements[idx].num_values;i++) {
853 if (strcmp(dn, (char *)msg->elements[idx].values[i].data) == 0) {
858 v2 = talloc_realloc(msg->elements, msg->elements[idx].values,
860 msg->elements[idx].num_values+1);
862 return LDB_ERR_OPERATIONS_ERROR;
864 msg->elements[idx].values = v2;
866 msg->elements[idx].values[msg->elements[idx].num_values].length = strlen(dn);
867 msg->elements[idx].values[msg->elements[idx].num_values].data = discard_const_p(uint8_t, dn);
868 msg->elements[idx].num_values++;
874 add an index entry for one message element
876 static int ltdb_index_add1(struct ldb_module *module, const char *dn,
877 struct ldb_message_element *el, int v_idx)
879 struct ldb_context *ldb = module->ldb;
880 struct ldb_message *msg;
881 struct ldb_dn *dn_key;
885 msg = talloc(module, struct ldb_message);
888 return LDB_ERR_OPERATIONS_ERROR;
891 dn_key = ltdb_index_key(ldb, el->name, &el->values[v_idx]);
894 return LDB_ERR_OPERATIONS_ERROR;
896 talloc_steal(msg, dn_key);
898 ret = ltdb_search_dn1(module, dn_key, msg);
899 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
904 if (ret == LDB_ERR_NO_SUCH_OBJECT) {
906 msg->num_elements = 0;
907 msg->elements = NULL;
910 for (i=0;i<msg->num_elements;i++) {
911 if (strcmp(LTDB_IDX, msg->elements[i].name) == 0) {
916 if (i == msg->num_elements) {
917 ret = ltdb_index_add1_new(ldb, msg, dn);
919 ret = ltdb_index_add1_add(ldb, msg, i, dn);
922 if (ret == LDB_SUCCESS) {
923 ret = ltdb_store(module, msg, TDB_REPLACE);
931 static int ltdb_index_add0(struct ldb_module *module, const char *dn,
932 struct ldb_message_element *elements, int num_el)
934 struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
942 if (ltdb->cache->indexlist->num_elements == 0) {
943 /* no indexed fields */
947 for (i = 0; i < num_el; i++) {
948 ret = ldb_msg_find_idx(ltdb->cache->indexlist, elements[i].name,
953 for (j = 0; j < elements[i].num_values; j++) {
954 ret = ltdb_index_add1(module, dn, &elements[i], j);
955 if (ret != LDB_SUCCESS) {
965 add the index entries for a new record
967 int ltdb_index_add(struct ldb_module *module, const struct ldb_message *msg)
972 dn = ldb_dn_get_linearized(msg->dn);
974 return LDB_ERR_OPERATIONS_ERROR;
977 ret = ltdb_index_add0(module, dn, msg->elements, msg->num_elements);
984 delete an index entry for one message element
986 int ltdb_index_del_value(struct ldb_module *module, const char *dn,
987 struct ldb_message_element *el, int v_idx)
989 struct ldb_context *ldb = module->ldb;
990 struct ldb_message *msg;
991 struct ldb_dn *dn_key;
999 dn_key = ltdb_index_key(ldb, el->name, &el->values[v_idx]);
1001 return LDB_ERR_OPERATIONS_ERROR;
1004 msg = talloc(dn_key, struct ldb_message);
1006 talloc_free(dn_key);
1007 return LDB_ERR_OPERATIONS_ERROR;
1010 ret = ltdb_search_dn1(module, dn_key, msg);
1011 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
1012 talloc_free(dn_key);
1016 if (ret == LDB_ERR_NO_SUCH_OBJECT) {
1017 /* it wasn't indexed. Did we have an earlier error? If we did then
1019 talloc_free(dn_key);
1023 i = ldb_msg_find_idx(msg, dn, &j, LTDB_IDX);
1025 ldb_debug(ldb, LDB_DEBUG_ERROR,
1026 "ERROR: dn %s not found in %s\n", dn,
1027 ldb_dn_get_linearized(dn_key));
1028 /* it ain't there. hmmm */
1029 talloc_free(dn_key);
1033 if (j != msg->elements[i].num_values - 1) {
1034 memmove(&msg->elements[i].values[j],
1035 &msg->elements[i].values[j+1],
1036 (msg->elements[i].num_values-(j+1)) *
1037 sizeof(msg->elements[i].values[0]));
1039 msg->elements[i].num_values--;
1041 if (msg->elements[i].num_values == 0) {
1042 ret = ltdb_delete_noindex(module, dn_key);
1044 ret = ltdb_store(module, msg, TDB_REPLACE);
1047 talloc_free(dn_key);
1053 delete the index entries for a record
1054 return -1 on failure
1056 int ltdb_index_del(struct ldb_module *module, const struct ldb_message *msg)
1058 struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
1063 /* find the list of indexed fields */
1064 if (ltdb->cache->indexlist->num_elements == 0) {
1065 /* no indexed fields */
1069 if (ldb_dn_is_special(msg->dn)) {
1073 dn = ldb_dn_get_linearized(msg->dn);
1075 return LDB_ERR_OPERATIONS_ERROR;
1078 for (i = 0; i < msg->num_elements; i++) {
1079 ret = ldb_msg_find_idx(ltdb->cache->indexlist, msg->elements[i].name,
1080 NULL, LTDB_IDXATTR);
1084 for (j = 0; j < msg->elements[i].num_values; j++) {
1085 ret = ltdb_index_del_value(module, dn, &msg->elements[i], j);
1086 if (ret != LDB_SUCCESS) {
1096 handle special index for one level searches
1098 int ltdb_index_one(struct ldb_module *module, const struct ldb_message *msg, int add)
1100 struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
1101 struct ldb_message_element el;
1107 /* We index for ONE Level only if requested */
1108 ret = ldb_msg_find_idx(ltdb->cache->indexlist, NULL, NULL, LTDB_IDXONE);
1113 pdn = ldb_dn_get_parent(module, msg->dn);
1115 return LDB_ERR_OPERATIONS_ERROR;
1118 dn = ldb_dn_get_linearized(msg->dn);
1121 return LDB_ERR_OPERATIONS_ERROR;
1124 val.data = (uint8_t *)((uintptr_t)ldb_dn_get_casefold(pdn));
1125 if (val.data == NULL) {
1127 return LDB_ERR_OPERATIONS_ERROR;
1130 val.length = strlen((char *)val.data);
1131 el.name = LTDB_IDXONE;
1136 ret = ltdb_index_add1(module, dn, &el, 0);
1137 } else { /* delete */
1138 ret = ltdb_index_del_value(module, dn, &el, 0);
1148 traversal function that deletes all @INDEX records
1150 static int delete_index(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *state)
1152 const char *dn = "DN=" LTDB_INDEX ":";
1153 if (strncmp((char *)key.dptr, dn, strlen(dn)) == 0) {
1154 return tdb_delete(tdb, key);
1160 traversal function that adds @INDEX records during a re index
1162 static int re_index(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *state)
1164 struct ldb_module *module = (struct ldb_module *)state;
1165 struct ldb_message *msg;
1166 const char *dn = NULL;
1170 if (strncmp((char *)key.dptr, "DN=@", 4) == 0 ||
1171 strncmp((char *)key.dptr, "DN=", 3) != 0) {
1175 msg = talloc(module, struct ldb_message);
1180 ret = ltdb_unpack_data(module, &data, msg);
1186 /* check if the DN key has changed, perhaps due to the
1187 case insensitivity of an element changing */
1188 key2 = ltdb_key(module, msg->dn);
1189 if (key2.dptr == NULL) {
1190 /* probably a corrupt record ... darn */
1191 ldb_debug(module->ldb, LDB_DEBUG_ERROR, "Invalid DN in re_index: %s\n",
1192 ldb_dn_get_linearized(msg->dn));
1196 if (strcmp((char *)key2.dptr, (char *)key.dptr) != 0) {
1197 tdb_delete(tdb, key);
1198 tdb_store(tdb, key2, data, 0);
1200 talloc_free(key2.dptr);
1202 if (msg->dn == NULL) {
1203 dn = (char *)key.dptr + 3;
1205 dn = ldb_dn_get_linearized(msg->dn);
1208 ret = ltdb_index_one(module, msg, 1);
1209 if (ret == LDB_SUCCESS) {
1210 ret = ltdb_index_add0(module, dn, msg->elements, msg->num_elements);
1212 ldb_debug(module->ldb, LDB_DEBUG_ERROR,
1213 "Adding special ONE LEVEL index failed (%s)!\n",
1214 ldb_dn_get_linearized(msg->dn));
1219 if (ret != LDB_SUCCESS) return -1;
1225 force a complete reindex of the database
1227 int ltdb_reindex(struct ldb_module *module)
1229 struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
1232 if (ltdb_cache_reload(module) != 0) {
1233 return LDB_ERR_OPERATIONS_ERROR;
1236 /* first traverse the database deleting any @INDEX records */
1237 ret = tdb_traverse(ltdb->tdb, delete_index, NULL);
1239 return LDB_ERR_OPERATIONS_ERROR;
1242 /* if we don't have indexes we have nothing todo */
1243 if (ltdb->cache->indexlist->num_elements == 0) {
1247 /* now traverse adding any indexes for normal LDB records */
1248 ret = tdb_traverse(ltdb->tdb, re_index, module);
1250 return LDB_ERR_OPERATIONS_ERROR;