1 /* filterindex.c - generate the list of candidate entries from a filter */
4 * Copyright 1998-2003 The OpenLDAP Foundation, All Rights Reserved.
5 * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
11 #include <ac/string.h>
16 static int presence_candidates(
18 AttributeDescription *desc,
21 static int equality_candidates(
23 AttributeAssertion *ava,
26 static int approx_candidates(
28 AttributeAssertion *ava,
31 static int substring_candidates(
33 SubstringsAssertion *sub,
37 static int list_candidates(
46 bdb_filter_candidates(
55 LDAP_LOG ( INDEX, ENTRY, "=> bdb_filter_candidates\n", 0, 0, 0 );
57 Debug( LDAP_DEBUG_FILTER, "=> bdb_filter_candidates\n", 0, 0, 0 );
60 switch ( f->f_choice ) {
61 case SLAPD_FILTER_DN_ONE:
63 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tDN ONE\n", 0, 0, 0 );
65 Debug( LDAP_DEBUG_FILTER, "\tDN ONE\n", 0, 0, 0 );
67 rc = bdb_dn2idl( be, f->f_dn, DN_ONE_PREFIX, ids );
68 if( rc == DB_NOTFOUND ) {
74 case SLAPD_FILTER_DN_SUBTREE:
76 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tDN SUBTREE\n", 0, 0, 0 );
78 Debug( LDAP_DEBUG_FILTER, "\tDN SUBTREE\n", 0, 0, 0 );
80 rc = bdb_dn2idl( be, f->f_dn, DN_SUBTREE_PREFIX, ids );
83 case LDAP_FILTER_PRESENT:
85 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tPRESENT\n", 0, 0, 0 );
87 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
89 rc = presence_candidates( be, f->f_desc, ids );
92 case LDAP_FILTER_EQUALITY:
94 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tEQUALITY\n", 0, 0, 0 );
96 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
98 rc = equality_candidates( be, f->f_ava, ids, tmp );
101 case LDAP_FILTER_APPROX:
103 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tAPPROX\n", 0, 0, 0 );
105 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
107 rc = approx_candidates( be, f->f_ava, ids, tmp );
110 case LDAP_FILTER_SUBSTRINGS:
112 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tSUBSTRINGS\n", 0, 0, 0 );
114 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
116 rc = substring_candidates( be, f->f_sub, ids, tmp );
120 /* no GE index, use pres */
122 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tGE\n", 0, 0, 0 );
124 Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
126 rc = presence_candidates( be, f->f_ava->aa_desc, ids );
130 /* no LE index, use pres */
132 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tLE\n", 0, 0, 0 );
134 Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
136 rc = presence_candidates( be, f->f_ava->aa_desc, ids );
139 case LDAP_FILTER_NOT:
140 /* no indexing to support NOT filters */
142 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tNOT\n",0, 0, 0 );
144 Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
148 case LDAP_FILTER_AND:
150 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tAND\n", 0, 0, 0 );
152 Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
154 rc = list_candidates( be,
155 f->f_and, LDAP_FILTER_AND, ids, tmp, stack );
160 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tOR\n", 0, 0, 0 );
162 Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
164 rc = list_candidates( be,
165 f->f_or, LDAP_FILTER_OR, ids, tmp, stack );
170 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tUNKNOWN\n", 0, 0, 0 );
172 Debug( LDAP_DEBUG_FILTER, "\tUNKNOWN %lu\n",
173 (unsigned long) f->f_choice, 0, 0 );
178 LDAP_LOG ( INDEX, RESULTS,
179 "<= bdb_filter_candidates: id=%ld first=%ld last=%ld\n",
180 (long)ids[0], (long)BDB_IDL_FIRST( ids ), (long) BDB_IDL_LAST( ids ));
182 Debug( LDAP_DEBUG_FILTER,
183 "<= bdb_filter_candidates: id=%ld first=%ld last=%ld\n",
185 (long) BDB_IDL_FIRST( ids ),
186 (long) BDB_IDL_LAST( ids ) );
201 struct bdb_info *bdb = (struct bdb_info *) be->be_private;
206 LDAP_LOG ( INDEX, ARGS, "=> bdb_list_candidates: 0x%x\n", ftype, 0 , 0 );
208 Debug( LDAP_DEBUG_FILTER, "=> bdb_list_candidates 0x%x\n", ftype, 0, 0 );
211 if ( ftype == LDAP_FILTER_OR ) {
212 BDB_IDL_ALL( bdb, save );
215 BDB_IDL_CPY( save, ids );
218 for ( f = flist; f != NULL; f = f->f_next ) {
219 rc = bdb_filter_candidates( be, f, save, tmp,
220 save+BDB_IDL_UM_SIZE );
223 if ( ftype == LDAP_FILTER_AND ) {
230 if ( ftype == LDAP_FILTER_AND ) {
231 bdb_idl_intersection( ids, save );
232 if( BDB_IDL_IS_ZERO( ids ) )
235 bdb_idl_union( ids, save );
236 BDB_IDL_ALL( bdb, save );
240 if( rc == LDAP_SUCCESS ) {
242 LDAP_LOG ( INDEX, RESULTS,
243 "<= bdb_list_candidates: id=%ld first=%ld last=%ld\n",
244 (long) ids[0], (long) BDB_IDL_FIRST( ids ),
245 (long) BDB_IDL_LAST( ids ) );
247 Debug( LDAP_DEBUG_FILTER,
248 "<= bdb_list_candidates: id=%ld first=%ld last=%ld\n",
250 (long) BDB_IDL_FIRST(ids),
251 (long) BDB_IDL_LAST(ids) );
256 LDAP_LOG ( INDEX, ARGS, "<= bdb_list_candidates: rc=%d\n", rc, 0, 0 );
258 Debug( LDAP_DEBUG_FILTER,
259 "<= bdb_list_candidates: undefined rc=%d\n",
270 AttributeDescription *desc,
273 struct bdb_info *bdb = (struct bdb_info *) be->be_private;
277 struct berval prefix = {0, NULL};
280 LDAP_LOG ( INDEX, ENTRY, "=> bdb_presence_candidates (%s)\n",
281 desc->ad_cname.bv_val, 0, 0 );
283 Debug( LDAP_DEBUG_TRACE, "=> bdb_presence_candidates (%s)\n",
284 desc->ad_cname.bv_val, 0, 0 );
287 if( desc == slap_schema.si_ad_objectClass ) {
288 BDB_IDL_ALL( bdb, ids );
292 rc = bdb_index_param( be, desc, LDAP_FILTER_PRESENT,
293 &db, &mask, &prefix );
295 if( rc != LDAP_SUCCESS ) {
297 LDAP_LOG ( INDEX, RESULTS,
298 "<= bdb_presence_candidates: (%s) index_param "
300 desc->ad_cname.bv_val, rc, 0 );
302 Debug( LDAP_DEBUG_TRACE,
303 "<= bdb_presence_candidates: (%s) index_param "
305 desc->ad_cname.bv_val, rc, 0 );
313 LDAP_LOG(INDEX, RESULTS,
314 "<= bdb_presence_candidates: (%s) not indexed\n",
315 desc->ad_cname.bv_val, 0, 0 );
317 Debug( LDAP_DEBUG_TRACE,
318 "<= bdb_presence_candidates: (%s) not indexed\n",
319 desc->ad_cname.bv_val, 0, 0 );
324 if( prefix.bv_val == NULL ) {
326 LDAP_LOG(INDEX, RESULTS,
327 "<= bdb_presence_candidates: (%s) no prefix\n",
328 desc->ad_cname.bv_val, 0, 0 );
330 Debug( LDAP_DEBUG_TRACE,
331 "<= bdb_presence_candidates: (%s) no prefix\n",
332 desc->ad_cname.bv_val, 0, 0 );
337 rc = bdb_key_read( be, db, NULL, &prefix, ids );
339 if( rc == DB_NOTFOUND ) {
342 } else if( rc != LDAP_SUCCESS ) {
344 LDAP_LOG ( INDEX, RESULTS,
345 "<= bdb_presence_candidates: (%s) "
346 "key read failed (%d)\n",
347 desc->ad_cname.bv_val, rc, 0 );
349 Debug( LDAP_DEBUG_TRACE,
350 "<= bdb_presense_candidates: (%s) "
351 "key read failed (%d)\n",
352 desc->ad_cname.bv_val, rc, 0 );
358 LDAP_LOG ( INDEX, RESULTS,
359 "<= bdb_presence_candidates: id=%ld first=%ld last=%ld\n",
360 (long)ids[0], (long)BDB_IDL_FIRST( ids ), (long)BDB_IDL_LAST( ids ) );
362 Debug(LDAP_DEBUG_TRACE,
363 "<= bdb_presence_candidates: id=%ld first=%ld last=%ld\n",
365 (long) BDB_IDL_FIRST(ids),
366 (long) BDB_IDL_LAST(ids) );
376 AttributeAssertion *ava,
384 struct berval prefix = {0, NULL};
385 struct berval *keys = NULL;
389 LDAP_LOG ( INDEX, ENTRY, "=> bdb_equality_candidates (%s)\n",
390 ava->aa_desc->ad_cname.bv_val, 0, 0 );
392 Debug( LDAP_DEBUG_TRACE, "=> bdb_equality_candidates (%s)\n",
393 ava->aa_desc->ad_cname.bv_val, 0, 0 );
396 rc = bdb_index_param( be, ava->aa_desc, LDAP_FILTER_EQUALITY,
397 &db, &mask, &prefix );
399 if( rc != LDAP_SUCCESS ) {
401 LDAP_LOG ( INDEX, RESULTS,
402 "<= bdb_equality_candidates: (%s) "
403 "index_param failed (%d)\n",
404 ava->aa_desc->ad_cname.bv_val, rc, 0);
406 Debug( LDAP_DEBUG_ANY,
407 "<= bdb_equality_candidates: (%s) "
408 "index_param failed (%d)\n",
409 ava->aa_desc->ad_cname.bv_val, rc, 0 );
416 LDAP_LOG(INDEX, RESULTS,
417 "<= bdb_equality_candidates: (%s) not indexed\n",
418 ava->aa_desc->ad_cname.bv_val, 0, 0 );
420 Debug( LDAP_DEBUG_ANY,
421 "<= bdb_equality_candidates: (%s) not indexed\n",
422 ava->aa_desc->ad_cname.bv_val, 0, 0 );
427 mr = ava->aa_desc->ad_type->sat_equality;
432 if( !mr->smr_filter ) {
436 rc = (mr->smr_filter)(
437 LDAP_FILTER_EQUALITY,
439 ava->aa_desc->ad_type->sat_syntax,
445 if( rc != LDAP_SUCCESS ) {
447 LDAP_LOG ( INDEX, RESULTS,
448 "<= bdb_equality_candidates: (%s, %s) "
449 "MR filter failed (%d)\n",
450 prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
452 Debug( LDAP_DEBUG_TRACE,
453 "<= bdb_equality_candidates: (%s, %s) "
454 "MR filter failed (%d)\n",
455 prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
462 LDAP_LOG ( INDEX, RESULTS,
463 "<= bdb_equality_candidates: (%s) no keys\n",
464 ava->aa_desc->ad_cname.bv_val, 0, 0 );
466 Debug( LDAP_DEBUG_TRACE,
467 "<= bdb_equality_candidates: (%s) no keys\n",
468 ava->aa_desc->ad_cname.bv_val, 0, 0 );
473 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
474 rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
476 if( rc == DB_NOTFOUND ) {
479 } else if( rc != LDAP_SUCCESS ) {
481 LDAP_LOG ( INDEX, RESULTS,
482 "<= bdb_equality_candidates: (%s) "
483 "key read failed (%d)\n",
484 ava->aa_desc->ad_cname.bv_val, rc, 0 );
486 Debug( LDAP_DEBUG_TRACE,
487 "<= bdb_equality_candidates: (%s) "
488 "key read failed (%d)\n",
489 ava->aa_desc->ad_cname.bv_val, rc, 0 );
494 if( BDB_IDL_IS_ZERO( tmp ) ) {
496 LDAP_LOG ( INDEX, RESULTS,
497 "<= bdb_equality_candidates: (%s) NULL\n",
498 ava->aa_desc->ad_cname.bv_val, 0, 0);
500 Debug( LDAP_DEBUG_TRACE,
501 "<= bdb_equality_candidates: (%s) NULL\n",
502 ava->aa_desc->ad_cname.bv_val, 0, 0 );
508 bdb_idl_intersection( ids, tmp );
510 if( BDB_IDL_IS_ZERO( ids ) )
514 ber_bvarray_free( keys );
517 LDAP_LOG ( INDEX, RESULTS,
518 "<= bdb_equality_candidates: id=%ld first=%ld last=%ld\n",
519 (long) ids[0], (long) BDB_IDL_FIRST( ids ),
520 (long) BDB_IDL_LAST( ids ) );
522 Debug( LDAP_DEBUG_TRACE,
523 "<= bdb_equality_candidates: id=%ld, first=%ld, last=%ld\n",
525 (long) BDB_IDL_FIRST(ids),
526 (long) BDB_IDL_LAST(ids) );
535 AttributeAssertion *ava,
543 struct berval prefix = {0, NULL};
544 struct berval *keys = NULL;
548 LDAP_LOG ( INDEX, ENTRY, "=> bdb_approx_candidates (%s)\n",
549 ava->aa_desc->ad_cname.bv_val, 0, 0 );
551 Debug( LDAP_DEBUG_TRACE, "=> bdb_approx_candidates (%s)\n",
552 ava->aa_desc->ad_cname.bv_val, 0, 0 );
555 rc = bdb_index_param( be, ava->aa_desc, LDAP_FILTER_APPROX,
556 &db, &mask, &prefix );
558 if( rc != LDAP_SUCCESS ) {
560 LDAP_LOG ( INDEX, RESULTS,
561 "<= bdb_approx_candidates: (%s) "
562 "index_param failed (%d)\n",
563 ava->aa_desc->ad_cname.bv_val, rc, 0 );
565 Debug( LDAP_DEBUG_ANY,
566 "<= bdb_approx_candidates: (%s) "
567 "index_param failed (%d)\n",
568 ava->aa_desc->ad_cname.bv_val, rc, 0 );
575 LDAP_LOG(INDEX, RESULTS,
576 "<= bdb_approx_candidates: (%s) not indexed\n",
577 ava->aa_desc->ad_cname.bv_val, 0, 0 );
579 Debug( LDAP_DEBUG_ANY,
580 "<= bdb_approx_candidates: (%s) not indexed\n",
581 ava->aa_desc->ad_cname.bv_val, 0, 0 );
586 mr = ava->aa_desc->ad_type->sat_approx;
588 /* no approx matching rule, try equality matching rule */
589 mr = ava->aa_desc->ad_type->sat_equality;
596 if( !mr->smr_filter ) {
600 rc = (mr->smr_filter)(
603 ava->aa_desc->ad_type->sat_syntax,
609 if( rc != LDAP_SUCCESS ) {
611 LDAP_LOG ( INDEX, RESULTS,
612 "<= bdb_approx_candidates: (%s, %s) "
613 "MR filter failed (%d)\n",
614 prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
616 Debug( LDAP_DEBUG_TRACE,
617 "<= bdb_approx_candidates: (%s, %s) "
618 "MR filter failed (%d)\n",
619 prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
626 LDAP_LOG ( INDEX, RESULTS,
627 "<= bdb_approx_candidates: (%s) no keys (%s)\n",
628 prefix.bv_val, ava->aa_desc->ad_cname.bv_val, 0 );
630 Debug( LDAP_DEBUG_TRACE,
631 "<= bdb_approx_candidates: (%s) no keys (%s)\n",
632 prefix.bv_val, ava->aa_desc->ad_cname.bv_val, 0 );
637 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
638 rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
640 if( rc == DB_NOTFOUND ) {
644 } else if( rc != LDAP_SUCCESS ) {
646 LDAP_LOG ( INDEX, RESULTS,
647 "<= bdb_approx_candidates: (%s) "
648 "key read failed (%d)\n",
649 ava->aa_desc->ad_cname.bv_val, rc, 0);
651 Debug( LDAP_DEBUG_TRACE,
652 "<= bdb_approx_candidates: (%s) "
653 "key read failed (%d)\n",
654 ava->aa_desc->ad_cname.bv_val, rc, 0 );
659 if( BDB_IDL_IS_ZERO( tmp ) ) {
661 LDAP_LOG ( INDEX, RESULTS,
662 "<= bdb_approx_candidates: (%s) NULL\n",
663 ava->aa_desc->ad_cname.bv_val, 0, 0 );
665 Debug( LDAP_DEBUG_TRACE,
666 "<= bdb_approx_candidates: (%s) NULL\n",
667 ava->aa_desc->ad_cname.bv_val, 0, 0 );
673 bdb_idl_intersection( ids, tmp );
675 if( BDB_IDL_IS_ZERO( ids ) )
679 ber_bvarray_free( keys );
682 LDAP_LOG ( INDEX, RESULTS,
683 "<= bdb_approx_candidates: id=%ld first=%ld last=%ld\n",
684 (long) ids[0], (long) BDB_IDL_FIRST( ids ),
685 (long) BDB_IDL_LAST( ids ) );
687 Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates %ld, first=%ld, last=%ld\n",
689 (long) BDB_IDL_FIRST(ids),
690 (long) BDB_IDL_LAST(ids) );
696 substring_candidates(
698 SubstringsAssertion *sub,
706 struct berval prefix = {0, NULL};
707 struct berval *keys = NULL;
711 LDAP_LOG ( INDEX, ENTRY, "=> bdb_substring_candidates (%s)\n",
712 sub->sa_desc->ad_cname.bv_val, 0, 0 );
714 Debug( LDAP_DEBUG_TRACE, "=> bdb_substring_candidates (%s)\n",
715 sub->sa_desc->ad_cname.bv_val, 0, 0 );
718 rc = bdb_index_param( be, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
719 &db, &mask, &prefix );
721 if( rc != LDAP_SUCCESS ) {
723 LDAP_LOG ( INDEX, RESULTS,
724 "<= bdb_substring_candidates: (%s) "
725 "index_param failed (%d)\n",
726 sub->sa_desc->ad_cname.bv_val, rc, 0);
728 Debug( LDAP_DEBUG_ANY,
729 "<= bdb_substring_candidates: (%s) "
730 "index_param failed (%d)\n",
731 sub->sa_desc->ad_cname.bv_val, rc, 0 );
738 LDAP_LOG ( INDEX, RESULTS,
739 "<= bdb_substring_candidates: (%s) not indexed\n",
740 sub->sa_desc->ad_cname.bv_val, 0, 0 );
742 Debug( LDAP_DEBUG_ANY,
743 "<= bdb_substring_candidates: (%s) not indexed\n",
744 sub->sa_desc->ad_cname.bv_val, 0, 0 );
749 mr = sub->sa_desc->ad_type->sat_substr;
755 if( !mr->smr_filter ) {
759 rc = (mr->smr_filter)(
760 LDAP_FILTER_SUBSTRINGS,
762 sub->sa_desc->ad_type->sat_syntax,
768 if( rc != LDAP_SUCCESS ) {
770 LDAP_LOG ( INDEX, RESULTS,
771 "<= bdb_substring_candidates: (%s) "
772 "MR filter failed (%d)\n",
773 sub->sa_desc->ad_cname.bv_val, rc, 0 );
775 Debug( LDAP_DEBUG_TRACE,
776 "<= bdb_substring_candidates: (%s) "
777 "MR filter failed (%d)\n",
778 sub->sa_desc->ad_cname.bv_val, rc, 0 );
785 LDAP_LOG ( INDEX, RESULTS,
786 "<= bdb_substring_candidates: (0x%04lx) no keys (%s)\n",
787 mask, sub->sa_desc->ad_cname.bv_val, 0 );
789 Debug( LDAP_DEBUG_TRACE,
790 "<= bdb_substring_candidates: (0x%04lx) no keys (%s)\n",
791 mask, sub->sa_desc->ad_cname.bv_val, 0 );
796 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
797 rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
799 if( rc == DB_NOTFOUND ) {
803 } else if( rc != LDAP_SUCCESS ) {
805 LDAP_LOG ( INDEX, RESULTS,
806 "<= bdb_substring_candidates: (%s) "
807 "key read failed (%d)\n",
808 sub->sa_desc->ad_cname.bv_val, rc, 0 );
810 Debug( LDAP_DEBUG_TRACE,
811 "<= bdb_substring_candidates: (%s) "
812 "key read failed (%d)\n",
813 sub->sa_desc->ad_cname.bv_val, rc, 0 );
818 if( BDB_IDL_IS_ZERO( tmp ) ) {
820 LDAP_LOG ( INDEX, RESULTS,
821 "<= bdb_substring_candidates: (%s) NULL\n",
822 sub->sa_desc->ad_cname.bv_val, 0, 0 );
824 Debug( LDAP_DEBUG_TRACE,
825 "<= bdb_substring_candidates: (%s) NULL\n",
826 sub->sa_desc->ad_cname.bv_val, 0, 0 );
832 bdb_idl_intersection( ids, tmp );
834 if( BDB_IDL_IS_ZERO( ids ) )
838 ber_bvarray_free( keys );
841 LDAP_LOG ( INDEX, RESULTS,
842 "<= bdb_substring_candidates: id=%ld first=%ld last=%ld\n",
843 (long) ids[0], (long) BDB_IDL_FIRST( ids ),
844 (long) BDB_IDL_LAST( ids ) );
846 Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates: %ld, first=%ld, last=%ld\n",
848 (long) BDB_IDL_FIRST(ids),
849 (long) BDB_IDL_LAST(ids) );