1 /* filterindex.c - generate the list of candidate entries from a filter */
4 * Copyright 1998-2000 The OpenLDAP Foundation, All Rights Reserved.
5 * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
12 #include <ac/socket.h>
13 #include <ac/string.h>
16 #include "back-ldbm.h"
18 static ID_BLOCK *presence_candidates(
20 AttributeDescription *desc );
21 static ID_BLOCK *equality_candidates(
22 Backend *be, AttributeAssertion *ava );
23 static ID_BLOCK *approx_candidates(
24 Backend *be, AttributeAssertion *ava );
25 static ID_BLOCK *substring_candidates(
27 SubstringsAssertion *sub );
28 static ID_BLOCK *list_candidates(
39 ID_BLOCK *result, *tmp1, *tmp2;
42 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY, "filter_candidates: enter\n"));
44 Debug( LDAP_DEBUG_TRACE, "=> filter_candidates\n", 0, 0, 0 );
49 switch ( f->f_choice ) {
50 case SLAPD_FILTER_DN_ONE:
52 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
53 "filter_candidates: DN ONE (%s)\n", f->f_dn ));
55 Debug( LDAP_DEBUG_FILTER, "\tDN ONE\n", 0, 0, 0 );
58 /* an error is treated as an empty list */
59 if ( dn2idl( be, f->f_dn, DN_ONE_PREFIX, &result ) != 0
66 case SLAPD_FILTER_DN_SUBTREE:
68 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
69 "filter_candidates: DN SUBTREE (%s)\n", f->f_dn ));
71 Debug( LDAP_DEBUG_FILTER, "\tDN SUBTREE\n", 0, 0, 0 );
74 /* an error is treated as an empty list */
75 if ( dn2idl( be, f->f_dn, DN_SUBTREE_PREFIX, &result ) != 0
82 case LDAP_FILTER_PRESENT:
84 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
85 "filter_candidates: Present (%s)\n", f->f_desc->ad_cname.bv_val ));
87 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
90 result = presence_candidates( be, f->f_desc );
93 case LDAP_FILTER_EQUALITY:
95 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
96 "filter_candidates: EQUALITY (%s),(%s)\n",
97 f->f_ava->aa_desc->ad_cname.bv_val,
98 f->f_ava->aa_value->bv_val ));
100 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
103 result = equality_candidates( be, f->f_ava );
106 case LDAP_FILTER_APPROX:
108 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
109 "filter_candidates: APPROX (%s), (%s)\n",
110 f->f_ava->aa_desc->ad_cname.bv_val,
111 f->f_ava->aa_value->bv_val ));
113 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
116 result = approx_candidates( be, f->f_ava );
119 case LDAP_FILTER_SUBSTRINGS:
121 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
122 "filter_candidates: SUBSTRINGS\n"));
124 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
127 result = substring_candidates( be, f->f_sub );
132 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
133 "filter_candidates: GE\n"));
135 Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
138 result = idl_allids( be );
143 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
144 "filter_candidates: LE\n" ));
146 Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
149 result = idl_allids( be );
152 case LDAP_FILTER_AND:
154 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
155 "filter_candidates: AND\n" ));
157 Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
160 result = list_candidates( be, f->f_and, LDAP_FILTER_AND );
165 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
166 "filter_candidates: OR\n" ));
168 Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
171 result = list_candidates( be, f->f_or, LDAP_FILTER_OR );
174 case LDAP_FILTER_NOT:
176 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
177 "filter_candidates: NOT\n" ));
179 Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
182 tmp1 = idl_allids( be );
183 tmp2 = filter_candidates( be, f->f_not );
184 result = idl_notin( be, tmp1, tmp2 );
191 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
192 "filter_candidates: return %ld\n",
193 result ? ID_BLOCK_NIDS(result) : 0 ));
195 Debug( LDAP_DEBUG_TRACE, "<= filter_candidates %ld\n",
196 result ? ID_BLOCK_NIDS(result) : 0, 0, 0 );
205 AttributeDescription *desc
213 struct berval *prefix;
216 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
217 "presence_candidates: enter\n" ));
219 Debug( LDAP_DEBUG_TRACE, "=> presence_candidates\n", 0, 0, 0 );
223 idl = idl_allids( be );
225 rc = index_param( be, desc, LDAP_FILTER_PRESENT,
226 &dbname, &mask, &prefix );
228 if( rc != LDAP_SUCCESS ) {
230 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
231 "presence_candidates: index_param returned %d\n",
234 Debug( LDAP_DEBUG_TRACE,
235 "<= presence_candidates: index_param returned=%d\n",
242 if( dbname == NULL ) {
245 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
246 "presence_candidates: not indexed\n" ));
248 Debug( LDAP_DEBUG_TRACE,
249 "<= presense_candidates: not indexed\n",
253 ber_bvfree( prefix );
257 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
261 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
262 "presence_candidates: db open failed (%s%s)\n",
263 dbname, LDBM_SUFFIX ));
265 Debug( LDAP_DEBUG_ANY,
266 "<= presense_candidates db open failed (%s%s)\n",
267 dbname, LDBM_SUFFIX, 0 );
270 ber_bvfree( prefix );
274 if( prefix != NULL ) {
278 rc = key_read( be, db, prefix, &idl );
280 if( rc != LDAP_SUCCESS ) {
282 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
283 "presence_candidates: key read failed (%d)\n", rc ));
285 Debug( LDAP_DEBUG_TRACE,
286 "<= presense_candidates key read failed (%d)\n",
291 } else if( idl == NULL ) {
293 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
294 "presence_candidates: NULL\n" ));
296 Debug( LDAP_DEBUG_TRACE,
297 "<= presense_candidates NULL\n",
304 ldbm_cache_close( be, db );
305 ber_bvfree( prefix );
308 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
309 "presence_candidates: return %ld\n",
310 idl ? ID_BLOCK_NIDS(idl) : 0 ));
312 Debug( LDAP_DEBUG_TRACE, "<= presence_candidates %ld\n",
313 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
322 AttributeAssertion *ava
331 struct berval *prefix;
332 struct berval **keys = NULL;
336 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
337 "equality_candidates: enter\n" ));
339 Debug( LDAP_DEBUG_TRACE, "=> equality_candidates\n", 0, 0, 0 );
343 idl = idl_allids( be );
345 rc = index_param( be, ava->aa_desc, LDAP_FILTER_EQUALITY,
346 &dbname, &mask, &prefix );
348 if( rc != LDAP_SUCCESS ) {
350 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
351 "equality_candidates: index_param returned %d\n", rc ));
353 Debug( LDAP_DEBUG_TRACE,
354 "<= equality_candidates: index_param returned=%d\n",
361 if( dbname == NULL ) {
364 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
365 "equality_candidates: not indexed\n" ));
367 Debug( LDAP_DEBUG_TRACE,
368 "<= equality_candidates: not indexed\n",
372 ber_bvfree( prefix );
376 mr = ava->aa_desc->ad_type->sat_equality;
378 ber_bvfree( prefix );
382 if( !mr->smr_filter ) {
383 ber_bvfree( prefix );
387 rc = (mr->smr_filter)(
388 LDAP_FILTER_EQUALITY,
390 ava->aa_desc->ad_type->sat_syntax,
396 ber_bvfree( prefix );
398 if( rc != LDAP_SUCCESS ) {
400 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
401 "equality_candidates: (%s%s) MR filter failed (%d\n",
402 dbname, LDBM_SUFFIX, rc ));
404 Debug( LDAP_DEBUG_TRACE,
405 "<= equality_candidates: (%s%s) MR filter failed (%d)\n",
406 dbname, LDBM_SUFFIX, rc );
414 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
415 "equality_candidates: no keys (%s%s)\n",
416 dbname, LDBM_SUFFIX ));
418 Debug( LDAP_DEBUG_TRACE,
419 "<= equality_candidates: no keys (%s%s)\n",
420 dbname, LDBM_SUFFIX, 0 );
426 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
430 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
431 "equality_candidates: db open failed (%s%s)\n",
432 dbname, LDBM_SUFFIX ));
434 Debug( LDAP_DEBUG_ANY,
435 "<= equality_candidates db open failed (%s%s)\n",
436 dbname, LDBM_SUFFIX, 0 );
442 for ( i= 0; keys[i] != NULL; i++ ) {
446 rc = key_read( be, db, keys[i], &tmp );
448 if( rc != LDAP_SUCCESS ) {
452 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
453 "equality_candidates: key read failed (%d)\n", rc ));
455 Debug( LDAP_DEBUG_TRACE,
456 "<= equality_candidates key read failed (%d)\n",
467 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
468 "equality_candidates NULL\n" ));
470 Debug( LDAP_DEBUG_TRACE,
471 "<= equality_candidates NULL\n",
479 idl = idl_intersection( be, idl, tmp );
483 if( idl == NULL ) break;
486 ber_bvecfree( keys );
488 ldbm_cache_close( be, db );
492 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
493 "equality_candidates: return %ld\n",
494 idl ? ID_BLOCK_NIDS(idl) : 0 ));
496 Debug( LDAP_DEBUG_TRACE, "<= equality_candidates %ld\n",
497 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
506 AttributeAssertion *ava
515 struct berval *prefix;
516 struct berval **keys = NULL;
520 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
521 "approx_candidates: enter\n" ));
523 Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 );
527 idl = idl_allids( be );
529 rc = index_param( be, ava->aa_desc, LDAP_FILTER_APPROX,
530 &dbname, &mask, &prefix );
532 if( rc != LDAP_SUCCESS ) {
534 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
535 "approx_candidates: index_param returned %d\n", rc ));
537 Debug( LDAP_DEBUG_TRACE,
538 "<= approx_candidates: index_param returned=%d\n",
545 if( dbname == NULL ) {
548 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
549 "approx_candidates: not indexed\n" ));
551 Debug( LDAP_DEBUG_ANY,
552 "<= approx_candidates: not indexed\n",
556 ber_bvfree( prefix );
560 mr = ava->aa_desc->ad_type->sat_approx;
562 /* no approx matching rule, try equality matching rule */
563 mr = ava->aa_desc->ad_type->sat_equality;
567 ber_bvfree( prefix );
571 if( !mr->smr_filter ) {
572 ber_bvfree( prefix );
576 rc = (mr->smr_filter)(
579 ava->aa_desc->ad_type->sat_syntax,
585 ber_bvfree( prefix );
587 if( rc != LDAP_SUCCESS ) {
589 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
590 "approx_candidates: (%s%s) MR filter failed (%d)\n",
591 dbname, LDBM_SUFFIX, rc ));
593 Debug( LDAP_DEBUG_TRACE,
594 "<= approx_candidates: (%s%s) MR filter failed (%d)\n",
595 dbname, LDBM_SUFFIX, rc );
603 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
604 "approx_candidates: no keys (%s%s)\n",
605 dbname, LDBM_SUFFIX ));
607 Debug( LDAP_DEBUG_TRACE,
608 "<= approx_candidates: no keys (%s%s)\n",
609 dbname, LDBM_SUFFIX, 0 );
615 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
619 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
620 "approx_candidates db open failed (%s%s)\n",
621 dbname, LDBM_SUFFIX ));
623 Debug( LDAP_DEBUG_ANY,
624 "<= approx_candidates db open failed (%s%s)\n",
625 dbname, LDBM_SUFFIX, 0 );
631 for ( i= 0; keys[i] != NULL; i++ ) {
635 rc = key_read( be, db, keys[i], &tmp );
637 if( rc != LDAP_SUCCESS ) {
641 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
642 "approx_candidates: key read failed (%d)\n", rc ));
644 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates key read failed (%d)\n",
655 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
656 "approx_candidates: NULL\n" ));
658 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n",
666 idl = idl_intersection( be, idl, tmp );
670 if( idl == NULL ) break;
673 ber_bvecfree( keys );
675 ldbm_cache_close( be, db );
678 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
679 "approx_candidates: return %ld\n",
680 idl ? ID_BLOCK_NIDS(idl) : 0 ));
682 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %ld\n",
683 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
696 ID_BLOCK *idl, *tmp, *tmp2;
700 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
701 "list_candidates: 0x%x\n", ftype ));
703 Debug( LDAP_DEBUG_TRACE, "=> list_candidates 0x%x\n", ftype, 0, 0 );
708 for ( f = flist; f != NULL; f = f->f_next ) {
709 if ( (tmp = filter_candidates( be, f )) == NULL &&
710 ftype == LDAP_FILTER_AND ) {
712 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
713 "list_candidates: NULL\n" ));
715 Debug( LDAP_DEBUG_TRACE,
716 "<= list_candidates NULL\n", 0, 0, 0 );
726 } else if ( ftype == LDAP_FILTER_AND ) {
727 idl = idl_intersection( be, idl, tmp );
731 idl = idl_union( be, idl, tmp );
738 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
739 "list_candidates: return %ld\n",
740 idl ? ID_BLOCK_NIDS(idl) : 0 ));
742 Debug( LDAP_DEBUG_TRACE, "<= list_candidates %ld\n",
743 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
750 substring_candidates(
752 SubstringsAssertion *sub
761 struct berval *prefix;
762 struct berval **keys = NULL;
766 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
767 "substrings_candidates: enter\n" ));
769 Debug( LDAP_DEBUG_TRACE, "=> substrings_candidates\n", 0, 0, 0 );
773 idl = idl_allids( be );
775 rc = index_param( be, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
776 &dbname, &mask, &prefix );
778 if( rc != LDAP_SUCCESS ) {
780 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
781 "substrings_candidates: index_param returned %d\n", rc ));
783 Debug( LDAP_DEBUG_TRACE,
784 "<= substrings_candidates: index_param returned=%d\n",
791 if( dbname == NULL ) {
794 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
795 "substrings_candidates: not indexed\n" ));
797 Debug( LDAP_DEBUG_ANY,
798 "<= substrings_candidates: not indexed\n",
802 ber_bvfree( prefix );
806 mr = sub->sa_desc->ad_type->sat_substr;
809 ber_bvfree( prefix );
813 if( !mr->smr_filter ) {
814 ber_bvfree( prefix );
818 rc = (mr->smr_filter)(
819 LDAP_FILTER_SUBSTRINGS,
821 sub->sa_desc->ad_type->sat_syntax,
827 ber_bvfree( prefix );
829 if( rc != LDAP_SUCCESS ) {
831 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
832 "substrings_candidates: (%s%s) MR filter failed (%d)\n",
833 dbname, LDBM_SUFFIX, rc ));
835 Debug( LDAP_DEBUG_TRACE,
836 "<= substrings_candidates: (%s%s) MR filter failed (%d)\n",
837 dbname, LDBM_SUFFIX, rc );
845 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
846 "substrings_candidates: (0x%04lx) no keys (%s%s)\n",
847 mask, dbname, LDBM_SUFFIX ));
849 Debug( LDAP_DEBUG_TRACE,
850 "<= substrings_candidates: (0x%04lx) no keys (%s%s)\n",
851 mask, dbname, LDBM_SUFFIX );
857 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
861 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
862 "substrings_candidates: db open failed (%s%s)\n",
863 dbname, LDBM_SUFFIX ));
865 Debug( LDAP_DEBUG_ANY,
866 "<= substrings_candidates db open failed (%s%s)\n",
867 dbname, LDBM_SUFFIX, 0 );
873 for ( i= 0; keys[i] != NULL; i++ ) {
877 rc = key_read( be, db, keys[i], &tmp );
879 if( rc != LDAP_SUCCESS ) {
883 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
884 "substrings_candidates: key read failed (%d)\n",
887 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates key read failed (%d)\n",
898 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
899 "substrings_candidates: NULL\n" ));
901 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates NULL\n",
909 idl = idl_intersection( be, idl, tmp );
913 if( idl == NULL ) break;
916 ber_bvecfree( keys );
918 ldbm_cache_close( be, db );
921 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
922 "substrings_candidates: return %ld\n",
923 idl ? ID_BLOCK_NIDS(idl) : 0 ));
925 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates %ld\n",
926 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );