1 /* filterindex.c - generate the list of candidate entries from a filter */
4 * Copyright 1998-2002 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 );
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};
280 LDAP_LOG ( INDEX, ENTRY, "=> bdb_presence_candidates\n", 0, 0, 0 );
282 Debug( LDAP_DEBUG_TRACE, "=> bdb_presence_candidates\n", 0, 0, 0 );
285 if( desc == slap_schema.si_ad_objectClass ) {
286 BDB_IDL_ALL( bdb, ids );
290 rc = bdb_index_param( be, desc, LDAP_FILTER_PRESENT,
291 &db, &mask, &prefix );
293 if( rc != LDAP_SUCCESS ) {
295 LDAP_LOG ( INDEX, RESULTS,
296 "=> bdb_presence_candidates: index_parm returned=%d\n", rc, 0, 0 );
298 Debug( LDAP_DEBUG_TRACE,
299 "<= bdb_presence_candidates: index_param returned=%d\n",
308 LDAP_LOG(INDEX, RESULTS,
309 "<= bdb_presence_candidates: not indexed\n", 0, 0, 0 );
311 Debug( LDAP_DEBUG_TRACE,
312 "<= bdb_presence_candidates: not indexed\n",
318 if( prefix.bv_val == NULL ) {
320 LDAP_LOG(INDEX, RESULTS,
321 "<= bdb_presence_candidates: no prefix\n", 0, 0, 0 );
323 Debug( LDAP_DEBUG_TRACE,
324 "<= bdb_presence_candidates: no prefix\n",
330 rc = bdb_key_read( be, db, NULL, &prefix, ids );
332 if( rc == DB_NOTFOUND ) {
335 } else if( rc != LDAP_SUCCESS ) {
337 LDAP_LOG ( INDEX, RESULTS,
338 "<= bdb_presence_candidates: key read failed (%d)\n", rc, 0, 0 );
340 Debug( LDAP_DEBUG_TRACE,
341 "<= bdb_presense_candidates: key read failed (%d)\n",
348 LDAP_LOG ( INDEX, RESULTS,
349 "<= bdb_presence_candidates: id=%ld first=%ld last=%ld\n",
350 (long)ids[0], (long)BDB_IDL_FIRST( ids ), (long)BDB_IDL_LAST( ids ) );
352 Debug(LDAP_DEBUG_TRACE,
353 "<= bdb_presence_candidates: id=%ld first=%ld last=%ld\n",
355 (long) BDB_IDL_FIRST(ids),
356 (long) BDB_IDL_LAST(ids) );
366 AttributeAssertion *ava,
374 struct berval prefix = {0};
375 struct berval *keys = NULL;
379 LDAP_LOG ( INDEX, ENTRY, "=> equality_candidates\n", 0, 0, 0 );
381 Debug( LDAP_DEBUG_TRACE, "=> bdb_equality_candidates\n", 0, 0, 0 );
384 rc = bdb_index_param( be, ava->aa_desc, LDAP_FILTER_EQUALITY,
385 &db, &mask, &prefix );
387 if( rc != LDAP_SUCCESS ) {
389 LDAP_LOG ( INDEX, RESULTS,
390 "=> bdb_equality_candidates: index_param failed (%d)\n", rc, 0, 0);
392 Debug( LDAP_DEBUG_ANY,
393 "<= bdb_equality_candidates: index_param failed (%d)\n",
401 LDAP_LOG(INDEX, RESULTS,
402 "=> bdb_equality_candidates: not indexed\n", 0, 0, 0 );
404 Debug( LDAP_DEBUG_ANY,
405 "<= bdb_equality_candidates: not indexed\n", 0, 0, 0 );
410 mr = ava->aa_desc->ad_type->sat_equality;
415 if( !mr->smr_filter ) {
419 rc = (mr->smr_filter)(
420 LDAP_FILTER_EQUALITY,
422 ava->aa_desc->ad_type->sat_syntax,
428 if( rc != LDAP_SUCCESS ) {
430 LDAP_LOG ( INDEX, RESULTS,
431 "=> bdb_equality_candidates: MR filter failed (%d)\n", rc, 0, 0);
433 Debug( LDAP_DEBUG_TRACE,
434 "<= bdb_equality_candidates: MR filter failed (%d)\n",
442 LDAP_LOG ( INDEX, RESULTS,
443 "=> bdb_equality_candidates: no keys\n", 0, 0, 0 );
445 Debug( LDAP_DEBUG_TRACE,
446 "<= bdb_equality_candidates: no keys\n",
452 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
453 rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
455 if( rc == DB_NOTFOUND ) {
458 } else if( rc != LDAP_SUCCESS ) {
460 LDAP_LOG ( INDEX, RESULTS,
461 "<= bdb_equality_candidates: key read failed (%d)\n", rc, 0, 0);
463 Debug( LDAP_DEBUG_TRACE,
464 "<= bdb_equality_candidates key read failed (%d)\n",
470 if( BDB_IDL_IS_ZERO( tmp ) ) {
472 LDAP_LOG ( INDEX, RESULTS, "=> bdb_equality_candidates: NULL\n", 0, 0, 0);
474 Debug( LDAP_DEBUG_TRACE,
475 "<= bdb_equality_candidates NULL\n",
482 bdb_idl_intersection( ids, tmp );
484 if( BDB_IDL_IS_ZERO( ids ) )
488 ber_bvarray_free( keys );
491 LDAP_LOG ( INDEX, RESULTS,
492 "<= bdb_equality_candidates: id=%ld first=%ld last=%ld\n",
493 (long) ids[0], (long) BDB_IDL_FIRST( ids ),
494 (long) BDB_IDL_LAST( ids ) );
496 Debug( LDAP_DEBUG_TRACE,
497 "<= bdb_equality_candidates id=%ld, first=%ld, last=%ld\n",
499 (long) BDB_IDL_FIRST(ids),
500 (long) BDB_IDL_LAST(ids) );
509 AttributeAssertion *ava,
517 struct berval prefix = {0};
518 struct berval *keys = NULL;
522 LDAP_LOG ( INDEX, ENTRY, "=> bdb_approx_candidates\n", 0, 0, 0 );
524 Debug( LDAP_DEBUG_TRACE, "=> bdb_approx_candidates\n", 0, 0, 0 );
527 rc = bdb_index_param( be, ava->aa_desc, LDAP_FILTER_APPROX,
528 &db, &mask, &prefix );
530 if( rc != LDAP_SUCCESS ) {
532 LDAP_LOG ( INDEX, RESULTS,
533 "<= bdb_approx_candidates: index_param failed (%d)\n", rc, 0, 0 );
535 Debug( LDAP_DEBUG_ANY,
536 "<= bdb_approx_candidates: index_param failed (%d)\n",
544 LDAP_LOG(INDEX, RESULTS,
545 "<= bdb_approx_candidates: not indexed\n",0, 0, 0 );
547 Debug( LDAP_DEBUG_ANY,
548 "<= bdb_approx_candidates: not indexed\n", 0, 0, 0 );
553 mr = ava->aa_desc->ad_type->sat_approx;
555 /* no approx matching rule, try equality matching rule */
556 mr = ava->aa_desc->ad_type->sat_equality;
563 if( !mr->smr_filter ) {
567 rc = (mr->smr_filter)(
570 ava->aa_desc->ad_type->sat_syntax,
576 if( rc != LDAP_SUCCESS ) {
578 LDAP_LOG ( INDEX, RESULTS,
579 "<= bdb_approx_candidates: MR filter failed (%d)\n", rc, 0, 0 );
581 Debug( LDAP_DEBUG_TRACE,
582 "<= bdb_approx_candidates: (%s) MR filter failed (%d)\n",
583 prefix.bv_val, rc, 0 );
590 LDAP_LOG ( INDEX, RESULTS,
591 "<= bdb_approx_candidates: no keys (%s)\n", prefix.bv_val, 0, 0 );
593 Debug( LDAP_DEBUG_TRACE,
594 "<= bdb_approx_candidates: no keys (%s)\n",
595 prefix.bv_val, 0, 0 );
600 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
601 rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
603 if( rc == DB_NOTFOUND ) {
607 } else if( rc != LDAP_SUCCESS ) {
609 LDAP_LOG ( INDEX, RESULTS,
610 "<= bdb_approx_candidates: key read failed (%d)\n", rc, 0, 0);
612 Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates key read failed (%d)\n",
618 if( BDB_IDL_IS_ZERO( tmp ) ) {
620 LDAP_LOG ( INDEX, RESULTS,
621 "<= bdb_approx_candidates: NULL\n", 0, 0, 0 );
623 Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates NULL\n",
630 bdb_idl_intersection( ids, tmp );
632 if( BDB_IDL_IS_ZERO( ids ) )
636 ber_bvarray_free( keys );
639 LDAP_LOG ( INDEX, RESULTS,
640 "<= bdb_approx_candidates: id=%ld first=%ld last=%ld\n",
641 (long) ids[0], (long) BDB_IDL_FIRST( ids ),
642 (long) BDB_IDL_LAST( ids ) );
644 Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates %ld, first=%ld, last=%ld\n",
646 (long) BDB_IDL_FIRST(ids),
647 (long) BDB_IDL_LAST(ids) );
653 substring_candidates(
655 SubstringsAssertion *sub,
663 struct berval prefix = {0};
664 struct berval *keys = NULL;
668 LDAP_LOG ( INDEX, ENTRY, "=> bdb_substring_candidates\n", 0, 0, 0 );
670 Debug( LDAP_DEBUG_TRACE, "=> bdb_substring_candidates\n", 0, 0, 0 );
673 rc = bdb_index_param( be, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
674 &db, &mask, &prefix );
676 if( rc != LDAP_SUCCESS ) {
678 LDAP_LOG ( INDEX, RESULTS,
679 "<= bdb_substring_candidates: index_param failed (%d)\n", rc, 0, 0);
681 Debug( LDAP_DEBUG_ANY,
682 "<= bdb_substring_candidates: index_param failed (%d)\n",
690 LDAP_LOG ( INDEX, RESULTS,
691 "<= bdb_substring_candidates: not indexed\n", 0, 0, 0 );
693 Debug( LDAP_DEBUG_ANY,
694 "<= bdb_substring_candidates not indexed\n",
700 mr = sub->sa_desc->ad_type->sat_substr;
706 if( !mr->smr_filter ) {
710 rc = (mr->smr_filter)(
711 LDAP_FILTER_SUBSTRINGS,
713 sub->sa_desc->ad_type->sat_syntax,
719 if( rc != LDAP_SUCCESS ) {
721 LDAP_LOG ( INDEX, RESULTS,
722 "<= bdb_substring_candidates: (%s) MR filter failed (%d)\n",
723 sub->sa_desc->ad_cname.bv_val, rc, 0 );
725 Debug( LDAP_DEBUG_TRACE,
726 "<= bdb_substring_candidates: (%s) MR filter failed (%d)\n",
727 sub->sa_desc->ad_cname.bv_val, rc, 0 );
734 LDAP_LOG ( INDEX, RESULTS,
735 "<= bdb_substring_candidates: (%d) MR filter failed (%s)\n",
736 mask, sub->sa_desc->ad_cname.bv_val, 0 );
738 Debug( LDAP_DEBUG_TRACE,
739 "<= bdb_substring_candidates: (0x%04lx) no keys (%s)\n",
740 mask, sub->sa_desc->ad_cname.bv_val, 0 );
745 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
746 rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
748 if( rc == DB_NOTFOUND ) {
752 } else if( rc != LDAP_SUCCESS ) {
754 LDAP_LOG ( INDEX, RESULTS,
755 "<= bdb_substring_candidates: key read failed (%d)\n", rc, 0,0);
757 Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates key read failed (%d)\n",
763 if( BDB_IDL_IS_ZERO( tmp ) ) {
765 LDAP_LOG ( INDEX, RESULTS,
766 "<= bdb_substring_candidates: NULL \n", 0, 0, 0 );
768 Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates NULL\n",
775 bdb_idl_intersection( ids, tmp );
777 if( BDB_IDL_IS_ZERO( ids ) )
781 ber_bvarray_free( keys );
784 LDAP_LOG ( INDEX, RESULTS,
785 "<= bdb_substring_candidates: id=%ld first=%ld last=%ld\n",
786 (long) ids[0], (long) BDB_IDL_FIRST( ids ),
787 (long) BDB_IDL_LAST( ids ) );
789 Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates %ld, first=%ld, last=%ld\n",
791 (long) BDB_IDL_FIRST(ids),
792 (long) BDB_IDL_LAST(ids) );