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 2 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, write to the Free Software
22 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
28 * Component: ldb tdb backend - indexing
30 * Description: indexing routines for ldb tdb backend
32 * Author: Andrew Tridgell
35 #include "ldb_includes.h"
40 find an element in a list, using the given comparison function and
41 assuming that the list is already sorted using comp_fn
43 return -1 if not found, or the index of the first occurance of needle if found
45 static int ldb_list_find(const void *needle,
46 const void *base, size_t nmemb, size_t size,
47 comparison_fn_t comp_fn)
49 const char *base_p = base;
50 size_t min_i, max_i, test_i;
59 while (min_i < max_i) {
62 test_i = (min_i + max_i) / 2;
63 /* the following cast looks strange, but is
64 correct. The key to understanding it is that base_p
65 is a pointer to an array of pointers, so we have to
66 dereference it after casting to void **. The strange
67 const in the middle gives us the right type of pointer
68 after the dereference (tridge) */
69 r = comp_fn(needle, *(void * const *)(base_p + (size * test_i)));
71 /* scan back for first element */
73 comp_fn(needle, *(void * const *)(base_p + (size * (test_i-1)))) == 0) {
89 if (comp_fn(needle, *(void * const *)(base_p + (size * min_i))) == 0) {
102 return the dn key to be used for an index
105 static struct ldb_dn *ltdb_index_key(struct ldb_context *ldb,
106 const char *attr, const struct ldb_val *value)
110 const struct ldb_schema_attribute *a;
114 attr_folded = ldb_attr_casefold(ldb, attr);
119 a = ldb_schema_attribute_by_name(ldb, attr);
120 r = a->syntax->canonicalise_fn(ldb, ldb, value, &v);
121 if (r != LDB_SUCCESS) {
122 const char *errstr = ldb_errstring(ldb);
123 /* canonicalisation can be refused. For example,
124 a attribute that takes wildcards will refuse to canonicalise
125 if the value contains a wildcard */
126 ldb_asprintf_errstring(ldb, "Failed to create index key for attribute '%s':%s%s%s",
127 attr, ldb_strerror(r), (errstr?":":""), (errstr?errstr:""));
128 talloc_free(attr_folded);
131 if (ldb_should_b64_encode(&v)) {
132 char *vstr = ldb_base64_encode(ldb, (char *)v.data, v.length);
133 if (!vstr) return NULL;
134 ret = ldb_dn_new_fmt(ldb, ldb, "%s:%s::%s", LTDB_INDEX, attr_folded, vstr);
137 ret = ldb_dn_new_fmt(ldb, ldb, "%s:%s:%.*s", LTDB_INDEX, attr_folded, (int)v.length, (char *)v.data);
140 if (v.data != value->data) {
143 talloc_free(attr_folded);
149 see if a attribute value is in the list of indexed attributes
151 static int ldb_msg_find_idx(const struct ldb_message *msg, const char *attr,
152 unsigned int *v_idx, const char *key)
155 for (i=0;i<msg->num_elements;i++) {
156 if (ldb_attr_cmp(msg->elements[i].name, key) == 0) {
157 const struct ldb_message_element *el = &msg->elements[i];
160 /* in this case we are just looking to see if key is present,
161 we are not spearching for a specific index */
165 for (j=0;j<el->num_values;j++) {
166 if (ldb_attr_cmp((char *)el->values[j].data, attr) == 0) {
178 /* used in sorting dn lists */
179 static int list_cmp(const char **s1, const char **s2)
181 return strcmp(*s1, *s2);
185 return a list of dn's that might match a simple indexed search or
187 static int ltdb_index_dn_simple(struct ldb_module *module,
188 const struct ldb_parse_tree *tree,
189 const struct ldb_message *index_list,
190 struct dn_list *list)
192 struct ldb_context *ldb = module->ldb;
196 struct ldb_message *msg;
201 /* if the attribute isn't in the list of indexed attributes then
202 this node needs a full search */
203 if (ldb_msg_find_idx(index_list, tree->u.equality.attr, NULL, LTDB_IDXATTR) == -1) {
204 return LDB_ERR_OPERATIONS_ERROR;
207 /* the attribute is indexed. Pull the list of DNs that match the
209 dn = ltdb_index_key(ldb, tree->u.equality.attr, &tree->u.equality.value);
210 if (!dn) return LDB_ERR_OPERATIONS_ERROR;
212 msg = talloc(list, struct ldb_message);
214 return LDB_ERR_OPERATIONS_ERROR;
217 ret = ltdb_search_dn1(module, dn, msg);
219 if (ret != LDB_SUCCESS) {
223 for (i=0;i<msg->num_elements;i++) {
224 struct ldb_message_element *el;
226 if (strcmp(msg->elements[i].name, LTDB_IDX) != 0) {
230 el = &msg->elements[i];
232 list->dn = talloc_array(list, char *, el->num_values);
235 return LDB_ERR_OPERATIONS_ERROR;
238 for (j=0;j<el->num_values;j++) {
239 list->dn[list->count] =
240 talloc_strdup(list->dn, (char *)el->values[j].data);
241 if (!list->dn[list->count]) {
243 return LDB_ERR_OPERATIONS_ERROR;
251 if (list->count > 1) {
252 qsort(list->dn, list->count, sizeof(char *), (comparison_fn_t) list_cmp);
259 static int list_union(struct ldb_context *, struct dn_list *, const struct dn_list *);
262 return a list of dn's that might match a simple indexed search on
263 the special objectclass attribute
265 static int ltdb_index_dn_objectclass(struct ldb_module *module,
266 const struct ldb_parse_tree *tree,
267 const struct ldb_message *index_list,
268 struct dn_list *list)
270 struct ldb_context *ldb = module->ldb;
273 const char *target = (const char *)tree->u.equality.value.data;
274 const char **subclasses;
279 ret = ltdb_index_dn_simple(module, tree, index_list, list);
281 subclasses = ldb_subclass_list(module->ldb, target);
283 if (subclasses == NULL) {
287 for (i=0;subclasses[i];i++) {
288 struct ldb_parse_tree tree2;
289 struct dn_list *list2;
290 tree2.operation = LDB_OP_EQUALITY;
291 tree2.u.equality.attr = LTDB_OBJECTCLASS;
292 if (!tree2.u.equality.attr) {
293 return LDB_ERR_OPERATIONS_ERROR;
295 tree2.u.equality.value.data =
296 (uint8_t *)talloc_strdup(list, subclasses[i]);
297 if (tree2.u.equality.value.data == NULL) {
298 return LDB_ERR_OPERATIONS_ERROR;
300 tree2.u.equality.value.length = strlen(subclasses[i]);
301 list2 = talloc(list, struct dn_list);
303 talloc_free(tree2.u.equality.value.data);
304 return LDB_ERR_OPERATIONS_ERROR;
306 if (ltdb_index_dn_objectclass(module, &tree2,
307 index_list, list2) == LDB_SUCCESS) {
308 if (list->count == 0) {
312 list_union(ldb, list, list2);
316 talloc_free(tree2.u.equality.value.data);
323 return a list of dn's that might match a leaf indexed search
325 static int ltdb_index_dn_leaf(struct ldb_module *module,
326 const struct ldb_parse_tree *tree,
327 const struct ldb_message *index_list,
328 struct dn_list *list)
330 if (ldb_attr_cmp(tree->u.equality.attr, LTDB_OBJECTCLASS) == 0) {
331 return ltdb_index_dn_objectclass(module, tree, index_list, list);
333 if (ldb_attr_dn(tree->u.equality.attr) == 0) {
334 list->dn = talloc_array(list, char *, 1);
335 if (list->dn == NULL) {
336 ldb_oom(module->ldb);
337 return LDB_ERR_OPERATIONS_ERROR;
339 list->dn[0] = talloc_strdup(list->dn, (char *)tree->u.equality.value.data);
340 if (list->dn[0] == NULL) {
341 ldb_oom(module->ldb);
342 return LDB_ERR_OPERATIONS_ERROR;
347 return ltdb_index_dn_simple(module, tree, index_list, list);
354 relies on the lists being sorted
356 static int list_intersect(struct ldb_context *ldb,
357 struct dn_list *list, const struct dn_list *list2)
359 struct dn_list *list3;
362 if (list->count == 0 || list2->count == 0) {
364 return LDB_ERR_NO_SUCH_OBJECT;
367 list3 = talloc(ldb, struct dn_list);
369 return LDB_ERR_OPERATIONS_ERROR;
372 list3->dn = talloc_array(list3, char *, list->count);
375 return LDB_ERR_OPERATIONS_ERROR;
379 for (i=0;i<list->count;i++) {
380 if (ldb_list_find(list->dn[i], list2->dn, list2->count,
381 sizeof(char *), (comparison_fn_t)strcmp) != -1) {
382 list3->dn[list3->count] = talloc_move(list3->dn, &list->dn[i]);
385 talloc_free(list->dn[i]);
389 talloc_free(list->dn);
390 list->dn = talloc_move(list, &list3->dn);
391 list->count = list3->count;
394 return LDB_ERR_NO_SUCH_OBJECT;
401 relies on the lists being sorted
403 static int list_union(struct ldb_context *ldb,
404 struct dn_list *list, const struct dn_list *list2)
408 unsigned int count = list->count;
410 if (list->count == 0 && list2->count == 0) {
412 return LDB_ERR_NO_SUCH_OBJECT;
415 d = talloc_realloc(list, list->dn, char *, list->count + list2->count);
417 return LDB_ERR_OPERATIONS_ERROR;
421 for (i=0;i<list2->count;i++) {
422 if (ldb_list_find(list2->dn[i], list->dn, count,
423 sizeof(char *), (comparison_fn_t)strcmp) == -1) {
424 list->dn[list->count] = talloc_strdup(list->dn, list2->dn[i]);
425 if (!list->dn[list->count]) {
426 return LDB_ERR_OPERATIONS_ERROR;
432 if (list->count != count) {
433 qsort(list->dn, list->count, sizeof(char *), (comparison_fn_t)list_cmp);
436 return LDB_ERR_NO_SUCH_OBJECT;
439 static int ltdb_index_dn(struct ldb_module *module,
440 const struct ldb_parse_tree *tree,
441 const struct ldb_message *index_list,
442 struct dn_list *list);
448 static int ltdb_index_dn_or(struct ldb_module *module,
449 const struct ldb_parse_tree *tree,
450 const struct ldb_message *index_list,
451 struct dn_list *list)
453 struct ldb_context *ldb = module->ldb;
457 ret = LDB_ERR_OPERATIONS_ERROR;
461 for (i=0;i<tree->u.list.num_elements;i++) {
462 struct dn_list *list2;
465 list2 = talloc(module, struct dn_list);
467 return LDB_ERR_OPERATIONS_ERROR;
470 v = ltdb_index_dn(module, tree->u.list.elements[i], index_list, list2);
472 if (v == LDB_ERR_NO_SUCH_OBJECT) {
474 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
481 if (v != LDB_SUCCESS && v != LDB_ERR_NO_SUCH_OBJECT) {
483 talloc_free(list->dn);
488 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
490 list->dn = talloc_move(list, &list2->dn);
491 list->count = list2->count;
493 if (list_union(ldb, list, list2) == -1) {
495 return LDB_ERR_OPERATIONS_ERROR;
502 if (list->count == 0) {
503 return LDB_ERR_NO_SUCH_OBJECT;
513 static int ltdb_index_dn_not(struct ldb_module *module,
514 const struct ldb_parse_tree *tree,
515 const struct ldb_message *index_list,
516 struct dn_list *list)
518 /* the only way to do an indexed not would be if we could
519 negate the not via another not or if we knew the total
520 number of database elements so we could know that the
521 existing expression covered the whole database.
523 instead, we just give up, and rely on a full index scan
524 (unless an outer & manages to reduce the list)
526 return LDB_ERR_OPERATIONS_ERROR;
530 AND two index results
532 static int ltdb_index_dn_and(struct ldb_module *module,
533 const struct ldb_parse_tree *tree,
534 const struct ldb_message *index_list,
535 struct dn_list *list)
537 struct ldb_context *ldb = module->ldb;
541 ret = LDB_ERR_OPERATIONS_ERROR;
545 for (i=0;i<tree->u.list.num_elements;i++) {
546 struct dn_list *list2;
549 list2 = talloc(module, struct dn_list);
551 return LDB_ERR_OPERATIONS_ERROR;
554 v = ltdb_index_dn(module, tree->u.list.elements[i], index_list, list2);
556 if (v == LDB_ERR_NO_SUCH_OBJECT) {
558 talloc_free(list->dn);
560 return LDB_ERR_NO_SUCH_OBJECT;
563 if (v != LDB_SUCCESS && v != LDB_ERR_NO_SUCH_OBJECT) {
568 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
570 talloc_free(list->dn);
571 list->dn = talloc_move(list, &list2->dn);
572 list->count = list2->count;
574 if (list_intersect(ldb, list, list2) == -1) {
576 return LDB_ERR_OPERATIONS_ERROR;
582 if (list->count == 0) {
583 talloc_free(list->dn);
584 return LDB_ERR_NO_SUCH_OBJECT;
592 AND index results and ONE level special index
594 static int ltdb_index_dn_one(struct ldb_module *module,
595 struct ldb_dn *parent_dn,
596 struct dn_list *list)
598 struct ldb_context *ldb = module->ldb;
599 struct dn_list *list2;
600 struct ldb_message *msg;
606 list2 = talloc_zero(module, struct dn_list);
608 return LDB_ERR_OPERATIONS_ERROR;
611 /* the attribute is indexed. Pull the list of DNs that match the
613 val.data = (uint8_t *)((intptr_t)ldb_dn_get_casefold(parent_dn));
614 val.length = strlen((char *)val.data);
615 key = ltdb_index_key(ldb, LTDB_IDXONE, &val);
618 return LDB_ERR_OPERATIONS_ERROR;
621 msg = talloc(list2, struct ldb_message);
624 return LDB_ERR_OPERATIONS_ERROR;
627 ret = ltdb_search_dn1(module, key, msg);
629 if (ret != LDB_SUCCESS) {
633 for (i = 0; i < msg->num_elements; i++) {
634 struct ldb_message_element *el;
636 if (strcmp(msg->elements[i].name, LTDB_IDX) != 0) {
640 el = &msg->elements[i];
642 list2->dn = talloc_array(list2, char *, el->num_values);
645 return LDB_ERR_OPERATIONS_ERROR;
648 for (j = 0; j < el->num_values; j++) {
649 list2->dn[list2->count] = talloc_strdup(list2->dn, (char *)el->values[j].data);
650 if (!list2->dn[list2->count]) {
652 return LDB_ERR_OPERATIONS_ERROR;
658 if (list2->count == 0) {
660 return LDB_ERR_NO_SUCH_OBJECT;
663 if (list2->count > 1) {
664 qsort(list2->dn, list2->count, sizeof(char *), (comparison_fn_t) list_cmp);
667 if (list->count > 0) {
668 if (list_intersect(ldb, list, list2) == -1) {
670 return LDB_ERR_OPERATIONS_ERROR;
673 if (list->count == 0) {
674 talloc_free(list->dn);
676 return LDB_ERR_NO_SUCH_OBJECT;
679 list->dn = talloc_move(list, &list2->dn);
680 list->count = list2->count;
689 return a list of dn's that might match a indexed search or
690 an error. return LDB_ERR_NO_SUCH_OBJECT for no matches, or LDB_SUCCESS for matches
692 static int ltdb_index_dn(struct ldb_module *module,
693 const struct ldb_parse_tree *tree,
694 const struct ldb_message *index_list,
695 struct dn_list *list)
697 int ret = LDB_ERR_OPERATIONS_ERROR;
699 switch (tree->operation) {
701 ret = ltdb_index_dn_and(module, tree, index_list, list);
705 ret = ltdb_index_dn_or(module, tree, index_list, list);
709 ret = ltdb_index_dn_not(module, tree, index_list, list);
712 case LDB_OP_EQUALITY:
713 ret = ltdb_index_dn_leaf(module, tree, index_list, list);
716 case LDB_OP_SUBSTRING:
721 case LDB_OP_EXTENDED:
722 /* we can't index with fancy bitops yet */
723 ret = LDB_ERR_OPERATIONS_ERROR;
731 filter a candidate dn_list from an indexed search into a set of results
732 extracting just the given attributes
734 static int ltdb_index_filter(const struct dn_list *dn_list,
735 struct ldb_handle *handle)
737 struct ltdb_context *ac = talloc_get_type(handle->private_data, struct ltdb_context);
738 struct ldb_reply *ares = NULL;
741 for (i = 0; i < dn_list->count; i++) {
745 ares = talloc_zero(ac, struct ldb_reply);
747 handle->status = LDB_ERR_OPERATIONS_ERROR;
748 handle->state = LDB_ASYNC_DONE;
749 return LDB_ERR_OPERATIONS_ERROR;
752 ares->message = ldb_msg_new(ares);
753 if (!ares->message) {
754 handle->status = LDB_ERR_OPERATIONS_ERROR;
755 handle->state = LDB_ASYNC_DONE;
757 return LDB_ERR_OPERATIONS_ERROR;
761 dn = ldb_dn_new(ares->message, ac->module->ldb, dn_list->dn[i]);
764 return LDB_ERR_OPERATIONS_ERROR;
767 ret = ltdb_search_dn1(ac->module, dn, ares->message);
769 if (ret == LDB_ERR_NO_SUCH_OBJECT) {
770 /* the record has disappeared? yes, this can happen */
775 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
776 /* an internal error */
778 return LDB_ERR_OPERATIONS_ERROR;
781 if (!ldb_match_msg(ac->module->ldb, ares->message, ac->tree, ac->base, ac->scope)) {
786 /* filter the attributes that the user wants */
787 ret = ltdb_filter_attrs(ares->message, ac->attrs);
790 handle->status = LDB_ERR_OPERATIONS_ERROR;
791 handle->state = LDB_ASYNC_DONE;
793 return LDB_ERR_OPERATIONS_ERROR;
796 ares->type = LDB_REPLY_ENTRY;
797 handle->state = LDB_ASYNC_PENDING;
798 handle->status = ac->callback(ac->module->ldb, ac->context, ares);
800 if (handle->status != LDB_SUCCESS) {
801 handle->state = LDB_ASYNC_DONE;
802 return handle->status;
810 search the database with a LDAP-like expression using indexes
811 returns -1 if an indexed search is not possible, in which
812 case the caller should call ltdb_search_full()
814 int ltdb_search_indexed(struct ldb_handle *handle)
816 struct ltdb_context *ac = talloc_get_type(handle->private_data, struct ltdb_context);
817 struct ltdb_private *ltdb = talloc_get_type(ac->module->private_data, struct ltdb_private);
818 struct dn_list *dn_list;
819 int ret, idxattr, idxone;
821 idxattr = idxone = 0;
822 ret = ldb_msg_find_idx(ltdb->cache->indexlist, NULL, NULL, LTDB_IDXATTR);
827 /* We do one level indexing only if requested */
828 ret = ldb_msg_find_idx(ltdb->cache->indexlist, NULL, NULL, LTDB_IDXONE);
833 if ((ac->scope == LDB_SCOPE_ONELEVEL && (idxattr+idxone == 0)) ||
834 (ac->scope == LDB_SCOPE_SUBTREE && idxattr == 0)) {
835 /* no indexs? must do full search */
836 return LDB_ERR_OPERATIONS_ERROR;
839 ret = LDB_ERR_OPERATIONS_ERROR;
841 dn_list = talloc_zero(handle, struct dn_list);
842 if (dn_list == NULL) {
843 return LDB_ERR_OPERATIONS_ERROR;
846 if (ac->scope == LDB_SCOPE_BASE) {
847 /* with BASE searches only one DN can match */
848 dn_list->dn = talloc_array(dn_list, char *, 1);
849 if (dn_list->dn == NULL) {
850 ldb_oom(ac->module->ldb);
851 return LDB_ERR_OPERATIONS_ERROR;
853 dn_list->dn[0] = ldb_dn_alloc_linearized(dn_list, ac->base);
854 if (dn_list->dn[0] == NULL) {
855 ldb_oom(ac->module->ldb);
856 return LDB_ERR_OPERATIONS_ERROR;
862 if (ac->scope != LDB_SCOPE_BASE && idxattr == 1) {
863 ret = ltdb_index_dn(ac->module, ac->tree, ltdb->cache->indexlist, dn_list);
865 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
866 talloc_free(dn_list);
871 if (ac->scope == LDB_SCOPE_ONELEVEL && idxone == 1) {
872 ret = ltdb_index_dn_one(ac->module, ac->base, dn_list);
875 if (ret == LDB_SUCCESS) {
876 /* we've got a candidate list - now filter by the full tree
877 and extract the needed attributes */
878 ret = ltdb_index_filter(dn_list, handle);
879 handle->status = ret;
880 handle->state = LDB_ASYNC_DONE;
883 talloc_free(dn_list);
889 add a index element where this is the first indexed DN for this value
891 static int ltdb_index_add1_new(struct ldb_context *ldb,
892 struct ldb_message *msg,
895 struct ldb_message_element *el;
897 /* add another entry */
898 el = talloc_realloc(msg, msg->elements,
899 struct ldb_message_element, msg->num_elements+1);
901 return LDB_ERR_OPERATIONS_ERROR;
905 msg->elements[msg->num_elements].name = talloc_strdup(msg->elements, LTDB_IDX);
906 if (!msg->elements[msg->num_elements].name) {
907 return LDB_ERR_OPERATIONS_ERROR;
909 msg->elements[msg->num_elements].num_values = 0;
910 msg->elements[msg->num_elements].values = talloc(msg->elements, struct ldb_val);
911 if (!msg->elements[msg->num_elements].values) {
912 return LDB_ERR_OPERATIONS_ERROR;
914 msg->elements[msg->num_elements].values[0].length = strlen(dn);
915 msg->elements[msg->num_elements].values[0].data = discard_const_p(uint8_t, dn);
916 msg->elements[msg->num_elements].num_values = 1;
924 add a index element where this is not the first indexed DN for this
927 static int ltdb_index_add1_add(struct ldb_context *ldb,
928 struct ldb_message *msg,
935 /* for multi-valued attributes we can end up with repeats */
936 for (i=0;i<msg->elements[idx].num_values;i++) {
937 if (strcmp(dn, (char *)msg->elements[idx].values[i].data) == 0) {
942 v2 = talloc_realloc(msg->elements, msg->elements[idx].values,
944 msg->elements[idx].num_values+1);
946 return LDB_ERR_OPERATIONS_ERROR;
948 msg->elements[idx].values = v2;
950 msg->elements[idx].values[msg->elements[idx].num_values].length = strlen(dn);
951 msg->elements[idx].values[msg->elements[idx].num_values].data = discard_const_p(uint8_t, dn);
952 msg->elements[idx].num_values++;
958 add an index entry for one message element
960 static int ltdb_index_add1(struct ldb_module *module, const char *dn,
961 struct ldb_message_element *el, int v_idx)
963 struct ldb_context *ldb = module->ldb;
964 struct ldb_message *msg;
965 struct ldb_dn *dn_key;
969 msg = talloc(module, struct ldb_message);
972 return LDB_ERR_OPERATIONS_ERROR;
975 dn_key = ltdb_index_key(ldb, el->name, &el->values[v_idx]);
978 return LDB_ERR_OPERATIONS_ERROR;
980 talloc_steal(msg, dn_key);
982 ret = ltdb_search_dn1(module, dn_key, msg);
983 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
988 if (ret == LDB_ERR_NO_SUCH_OBJECT) {
990 msg->num_elements = 0;
991 msg->elements = NULL;
994 for (i=0;i<msg->num_elements;i++) {
995 if (strcmp(LTDB_IDX, msg->elements[i].name) == 0) {
1000 if (i == msg->num_elements) {
1001 ret = ltdb_index_add1_new(ldb, msg, dn);
1003 ret = ltdb_index_add1_add(ldb, msg, i, dn);
1006 if (ret == LDB_SUCCESS) {
1007 ret = ltdb_store(module, msg, TDB_REPLACE);
1015 static int ltdb_index_add0(struct ldb_module *module, const char *dn,
1016 struct ldb_message_element *elements, int num_el)
1018 struct ltdb_private *ltdb = module->private_data;
1026 if (ltdb->cache->indexlist->num_elements == 0) {
1027 /* no indexed fields */
1031 for (i = 0; i < num_el; i++) {
1032 ret = ldb_msg_find_idx(ltdb->cache->indexlist, elements[i].name,
1033 NULL, LTDB_IDXATTR);
1037 for (j = 0; j < elements[i].num_values; j++) {
1038 ret = ltdb_index_add1(module, dn, &elements[i], j);
1039 if (ret != LDB_SUCCESS) {
1049 add the index entries for a new record
1051 int ltdb_index_add(struct ldb_module *module, const struct ldb_message *msg)
1056 dn = ldb_dn_get_linearized(msg->dn);
1058 return LDB_ERR_OPERATIONS_ERROR;
1061 ret = ltdb_index_add0(module, dn, msg->elements, msg->num_elements);
1068 delete an index entry for one message element
1070 int ltdb_index_del_value(struct ldb_module *module, const char *dn,
1071 struct ldb_message_element *el, int v_idx)
1073 struct ldb_context *ldb = module->ldb;
1074 struct ldb_message *msg;
1075 struct ldb_dn *dn_key;
1083 dn_key = ltdb_index_key(ldb, el->name, &el->values[v_idx]);
1085 return LDB_ERR_OPERATIONS_ERROR;
1088 msg = talloc(dn_key, struct ldb_message);
1090 talloc_free(dn_key);
1091 return LDB_ERR_OPERATIONS_ERROR;
1094 ret = ltdb_search_dn1(module, dn_key, msg);
1095 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
1096 talloc_free(dn_key);
1100 if (ret == LDB_ERR_NO_SUCH_OBJECT) {
1101 /* it wasn't indexed. Did we have an earlier error? If we did then
1103 talloc_free(dn_key);
1107 i = ldb_msg_find_idx(msg, dn, &j, LTDB_IDX);
1109 ldb_debug(ldb, LDB_DEBUG_ERROR,
1110 "ERROR: dn %s not found in %s\n", dn,
1111 ldb_dn_get_linearized(dn_key));
1112 /* it ain't there. hmmm */
1113 talloc_free(dn_key);
1117 if (j != msg->elements[i].num_values - 1) {
1118 memmove(&msg->elements[i].values[j],
1119 &msg->elements[i].values[j+1],
1120 (msg->elements[i].num_values-(j+1)) *
1121 sizeof(msg->elements[i].values[0]));
1123 msg->elements[i].num_values--;
1125 if (msg->elements[i].num_values == 0) {
1126 ret = ltdb_delete_noindex(module, dn_key);
1128 ret = ltdb_store(module, msg, TDB_REPLACE);
1131 talloc_free(dn_key);
1137 delete the index entries for a record
1138 return -1 on failure
1140 int ltdb_index_del(struct ldb_module *module, const struct ldb_message *msg)
1142 struct ltdb_private *ltdb = module->private_data;
1147 /* find the list of indexed fields */
1148 if (ltdb->cache->indexlist->num_elements == 0) {
1149 /* no indexed fields */
1153 if (ldb_dn_is_special(msg->dn)) {
1157 dn = ldb_dn_get_linearized(msg->dn);
1159 return LDB_ERR_OPERATIONS_ERROR;
1162 for (i = 0; i < msg->num_elements; i++) {
1163 ret = ldb_msg_find_idx(ltdb->cache->indexlist, msg->elements[i].name,
1164 NULL, LTDB_IDXATTR);
1168 for (j = 0; j < msg->elements[i].num_values; j++) {
1169 ret = ltdb_index_del_value(module, dn, &msg->elements[i], j);
1170 if (ret != LDB_SUCCESS) {
1180 handle special index for one level searches
1182 int ltdb_index_one(struct ldb_module *module, const struct ldb_message *msg, int add)
1184 struct ltdb_private *ltdb = module->private_data;
1185 struct ldb_message_element el;
1191 /* We index for ONE Level only if requested */
1192 ret = ldb_msg_find_idx(ltdb->cache->indexlist, NULL, NULL, LTDB_IDXONE);
1197 pdn = ldb_dn_get_parent(module, msg->dn);
1199 return LDB_ERR_OPERATIONS_ERROR;
1202 dn = ldb_dn_get_linearized(msg->dn);
1205 return LDB_ERR_OPERATIONS_ERROR;
1208 val.data = (uint8_t *)((intptr_t)ldb_dn_get_casefold(pdn));
1209 if (val.data == NULL) {
1211 return LDB_ERR_OPERATIONS_ERROR;
1214 val.length = strlen((char *)val.data);
1215 el.name = LTDB_IDXONE;
1220 ret = ltdb_index_add1(module, dn, &el, 0);
1221 } else { /* delete */
1222 ret = ltdb_index_del_value(module, dn, &el, 0);
1232 traversal function that deletes all @INDEX records
1234 static int delete_index(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *state)
1236 const char *dn = "DN=" LTDB_INDEX ":";
1237 if (strncmp((char *)key.dptr, dn, strlen(dn)) == 0) {
1238 return tdb_delete(tdb, key);
1244 traversal function that adds @INDEX records during a re index
1246 static int re_index(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *state)
1248 struct ldb_module *module = state;
1249 struct ldb_message *msg;
1250 const char *dn = NULL;
1254 if (strncmp((char *)key.dptr, "DN=@", 4) == 0 ||
1255 strncmp((char *)key.dptr, "DN=", 3) != 0) {
1259 msg = talloc(module, struct ldb_message);
1264 ret = ltdb_unpack_data(module, &data, msg);
1270 /* check if the DN key has changed, perhaps due to the
1271 case insensitivity of an element changing */
1272 key2 = ltdb_key(module, msg->dn);
1273 if (key2.dptr == NULL) {
1274 /* probably a corrupt record ... darn */
1275 ldb_debug(module->ldb, LDB_DEBUG_ERROR, "Invalid DN in re_index: %s\n",
1276 ldb_dn_get_linearized(msg->dn));
1280 if (strcmp((char *)key2.dptr, (char *)key.dptr) != 0) {
1281 tdb_delete(tdb, key);
1282 tdb_store(tdb, key2, data, 0);
1284 talloc_free(key2.dptr);
1286 if (msg->dn == NULL) {
1287 dn = (char *)key.dptr + 3;
1289 dn = ldb_dn_get_linearized(msg->dn);
1292 ret = ltdb_index_one(module, msg, 1);
1293 if (ret == LDB_SUCCESS) {
1294 ret = ltdb_index_add0(module, dn, msg->elements, msg->num_elements);
1296 ldb_debug(module->ldb, LDB_DEBUG_ERROR,
1297 "Adding special ONE LEVEL index failed (%s)!\n",
1298 ldb_dn_get_linearized(msg->dn));
1303 if (ret != LDB_SUCCESS) return -1;
1309 force a complete reindex of the database
1311 int ltdb_reindex(struct ldb_module *module)
1313 struct ltdb_private *ltdb = module->private_data;
1316 if (ltdb_cache_reload(module) != 0) {
1317 return LDB_ERR_OPERATIONS_ERROR;
1320 /* first traverse the database deleting any @INDEX records */
1321 ret = tdb_traverse(ltdb->tdb, delete_index, NULL);
1323 return LDB_ERR_OPERATIONS_ERROR;
1326 /* if we don't have indexes we have nothing todo */
1327 if (ltdb->cache->indexlist->num_elements == 0) {
1331 /* now traverse adding any indexes for normal LDB records */
1332 ret = tdb_traverse(ltdb->tdb, re_index, module);
1334 return LDB_ERR_OPERATIONS_ERROR;