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 result = dn2idl( be, f->f_dn, DN_ONE_PREFIX );
61 case SLAPD_FILTER_DN_SUBTREE:
63 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
64 "filter_candidates: DN SUBTREE (%s)\n", f->f_dn ));
66 Debug( LDAP_DEBUG_FILTER, "\tDN SUBTREE\n", 0, 0, 0 );
69 result = dn2idl( be, f->f_dn, DN_SUBTREE_PREFIX );
72 case LDAP_FILTER_PRESENT:
74 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
75 "filter_candidates: Present (%s)\n", f->f_desc->ad_cname->bv_val ));
77 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
80 result = presence_candidates( be, f->f_desc );
83 case LDAP_FILTER_EQUALITY:
85 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
86 "filter_candidates: EQUALITY (%s),(%s)\n",
87 f->f_ava->aa_desc->ad_cname->bv_val,
88 f->f_ava->aa_value->bv_val ));
90 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
93 result = equality_candidates( be, f->f_ava );
96 case LDAP_FILTER_APPROX:
98 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
99 "filter_candidates: APPROX (%s), (%s)\n",
100 f->f_ava->aa_desc->ad_cname->bv_val,
101 f->f_ava->aa_value->bv_val ));
103 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
106 result = approx_candidates( be, f->f_ava );
109 case LDAP_FILTER_SUBSTRINGS:
111 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
112 "filter_candidates: SUBSTRINGS\n"));
114 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
117 result = substring_candidates( be, f->f_sub );
122 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
123 "filter_candidates: GE\n"));
125 Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
128 result = idl_allids( be );
133 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
134 "filter_candidates: LE\n" ));
136 Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
139 result = idl_allids( be );
142 case LDAP_FILTER_AND:
144 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
145 "filter_candidates: AND\n" ));
147 Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
150 result = list_candidates( be, f->f_and, LDAP_FILTER_AND );
155 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
156 "filter_candidates: OR\n" ));
158 Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
161 result = list_candidates( be, f->f_or, LDAP_FILTER_OR );
164 case LDAP_FILTER_NOT:
166 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
167 "filter_candidates: NOT\n" ));
169 Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
172 tmp1 = idl_allids( be );
173 tmp2 = filter_candidates( be, f->f_not );
174 result = idl_notin( be, tmp1, tmp2 );
181 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
182 "filter_candidates: return %ld\n",
183 result ? ID_BLOCK_NIDS(result) : 0 ));
185 Debug( LDAP_DEBUG_TRACE, "<= filter_candidates %ld\n",
186 result ? ID_BLOCK_NIDS(result) : 0, 0, 0 );
195 AttributeDescription *desc
203 struct berval *prefix;
206 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
207 "presence_candidates: enter\n" ));
209 Debug( LDAP_DEBUG_TRACE, "=> presence_candidates\n", 0, 0, 0 );
213 idl = idl_allids( be );
215 rc = index_param( be, desc, LDAP_FILTER_PRESENT,
216 &dbname, &mask, &prefix );
218 if( rc != LDAP_SUCCESS ) {
220 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
221 "presence_candidates: index_param returned %d\n",
224 Debug( LDAP_DEBUG_TRACE,
225 "<= presence_candidates: index_param returned=%d\n",
232 if( dbname == NULL ) {
235 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
236 "presence_candidates: not indexed\n" ));
238 Debug( LDAP_DEBUG_TRACE,
239 "<= presense_candidates: not indexed\n",
243 ber_bvfree( prefix );
247 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_READER );
251 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
252 "presence_candidates: db open failed (%s%s)\n",
253 dbname, LDBM_SUFFIX ));
255 Debug( LDAP_DEBUG_ANY,
256 "<= presense_candidates db open failed (%s%s)\n",
257 dbname, LDBM_SUFFIX, 0 );
260 ber_bvfree( prefix );
264 if( prefix != NULL ) {
268 rc = key_read( be, db, prefix, &idl );
270 if( rc != LDAP_SUCCESS ) {
272 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
273 "presence_candidates: key read failed (%d)\n", rc ));
275 Debug( LDAP_DEBUG_TRACE,
276 "<= presense_candidates key read failed (%d)\n",
281 } else if( idl == NULL ) {
283 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
284 "presence_candidates: NULL\n" ));
286 Debug( LDAP_DEBUG_TRACE,
287 "<= presense_candidates NULL\n",
294 ldbm_cache_close( be, db );
295 ber_bvfree( prefix );
298 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
299 "presence_candidates: return %ld\n",
300 idl ? ID_BLOCK_NIDS(idl) : 0 ));
302 Debug( LDAP_DEBUG_TRACE, "<= presence_candidates %ld\n",
303 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
312 AttributeAssertion *ava
321 struct berval *prefix;
322 struct berval **keys = NULL;
326 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
327 "equality_candidates: enter\n" ));
329 Debug( LDAP_DEBUG_TRACE, "=> equality_candidates\n", 0, 0, 0 );
333 idl = idl_allids( be );
335 rc = index_param( be, ava->aa_desc, LDAP_FILTER_EQUALITY,
336 &dbname, &mask, &prefix );
338 if( rc != LDAP_SUCCESS ) {
340 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
341 "equality_candidates: index_param returned %d\n", rc ));
343 Debug( LDAP_DEBUG_TRACE,
344 "<= equality_candidates: index_param returned=%d\n",
351 if( dbname == NULL ) {
354 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
355 "equality_candidates: not indexed\n" ));
357 Debug( LDAP_DEBUG_TRACE,
358 "<= equality_candidates: not indexed\n",
362 ber_bvfree( prefix );
366 mr = ava->aa_desc->ad_type->sat_equality;
368 ber_bvfree( prefix );
372 if( !mr->smr_filter ) {
373 ber_bvfree( prefix );
377 rc = (mr->smr_filter)(
378 LDAP_FILTER_EQUALITY,
380 ava->aa_desc->ad_type->sat_syntax,
386 ber_bvfree( prefix );
388 if( rc != LDAP_SUCCESS ) {
390 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
391 "equality_candidates: (%s%s) MR filter failed (%d\n",
392 dbname, LDBM_SUFFIX, rc ));
394 Debug( LDAP_DEBUG_TRACE,
395 "<= equality_candidates: (%s%s) MR filter failed (%d)\n",
396 dbname, LDBM_SUFFIX, rc );
404 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
405 "equality_candidates: no keys (%s%s)\n",
406 dbname, LDBM_SUFFIX ));
408 Debug( LDAP_DEBUG_TRACE,
409 "<= equality_candidates: no keys (%s%s)\n",
410 dbname, LDBM_SUFFIX, 0 );
416 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_READER );
420 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
421 "equality_candidates: db open failed (%s%s)\n",
422 dbname, LDBM_SUFFIX ));
424 Debug( LDAP_DEBUG_ANY,
425 "<= equality_candidates db open failed (%s%s)\n",
426 dbname, LDBM_SUFFIX, 0 );
432 for ( i= 0; keys[i] != NULL; i++ ) {
436 rc = key_read( be, db, keys[i], &tmp );
438 if( rc != LDAP_SUCCESS ) {
442 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
443 "equality_candidates: key read failed (%d)\n", rc ));
445 Debug( LDAP_DEBUG_TRACE,
446 "<= equality_candidates key read failed (%d)\n",
457 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
458 "equality_candidates NULL\n" ));
460 Debug( LDAP_DEBUG_TRACE,
461 "<= equality_candidates NULL\n",
469 idl = idl_intersection( be, idl, tmp );
473 if( idl == NULL ) break;
476 ber_bvecfree( keys );
478 ldbm_cache_close( be, db );
482 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
483 "equality_candidates: return %ld\n",
484 idl ? ID_BLOCK_NIDS(idl) : 0 ));
486 Debug( LDAP_DEBUG_TRACE, "<= equality_candidates %ld\n",
487 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
496 AttributeAssertion *ava
505 struct berval *prefix;
506 struct berval **keys = NULL;
510 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
511 "approx_candidates: enter\n" ));
513 Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 );
517 idl = idl_allids( be );
519 rc = index_param( be, ava->aa_desc, LDAP_FILTER_APPROX,
520 &dbname, &mask, &prefix );
522 if( rc != LDAP_SUCCESS ) {
524 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
525 "approx_candidates: index_param returned %d\n", rc ));
527 Debug( LDAP_DEBUG_TRACE,
528 "<= approx_candidates: index_param returned=%d\n",
535 if( dbname == NULL ) {
538 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
539 "approx_candidates: not indexed\n" ));
541 Debug( LDAP_DEBUG_ANY,
542 "<= approx_candidates: not indexed\n",
546 ber_bvfree( prefix );
550 mr = ava->aa_desc->ad_type->sat_approx;
552 /* no approx matching rule, try equality matching rule */
553 mr = ava->aa_desc->ad_type->sat_equality;
557 ber_bvfree( prefix );
561 if( !mr->smr_filter ) {
562 ber_bvfree( prefix );
566 rc = (mr->smr_filter)(
569 ava->aa_desc->ad_type->sat_syntax,
575 ber_bvfree( prefix );
577 if( rc != LDAP_SUCCESS ) {
579 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
580 "approx_candidates: (%s%s) MR filter failed (%d)\n",
581 dbname, LDBM_SUFFIX, rc ));
583 Debug( LDAP_DEBUG_TRACE,
584 "<= approx_candidates: (%s%s) MR filter failed (%d)\n",
585 dbname, LDBM_SUFFIX, rc );
593 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
594 "approx_candidates: no keys (%s%s)\n",
595 dbname, LDBM_SUFFIX ));
597 Debug( LDAP_DEBUG_TRACE,
598 "<= approx_candidates: no keys (%s%s)\n",
599 dbname, LDBM_SUFFIX, 0 );
605 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_READER );
609 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
610 "approx_candidates db open failed (%s%s)\n",
611 dbname, LDBM_SUFFIX ));
613 Debug( LDAP_DEBUG_ANY,
614 "<= approx_candidates db open failed (%s%s)\n",
615 dbname, LDBM_SUFFIX, 0 );
621 for ( i= 0; keys[i] != NULL; i++ ) {
625 rc = key_read( be, db, keys[i], &tmp );
627 if( rc != LDAP_SUCCESS ) {
631 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
632 "approx_candidates: key read failed (%d)\n", rc ));
634 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates key read failed (%d)\n",
645 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
646 "approx_candidates: NULL\n" ));
648 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n",
656 idl = idl_intersection( be, idl, tmp );
659 if( idl == NULL ) break;
662 ber_bvecfree( keys );
664 ldbm_cache_close( be, db );
667 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
668 "approx_candidates: return %ld\n",
669 idl ? ID_BLOCK_NIDS(idl) : 0 ));
671 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %ld\n",
672 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
685 ID_BLOCK *idl, *tmp, *tmp2;
689 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
690 "list_candidates: 0x%x\n", ftype ));
692 Debug( LDAP_DEBUG_TRACE, "=> list_candidates 0x%x\n", ftype, 0, 0 );
697 for ( f = flist; f != NULL; f = f->f_next ) {
698 if ( (tmp = filter_candidates( be, f )) == NULL &&
699 ftype == LDAP_FILTER_AND ) {
701 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
702 "list_candidates: NULL\n" ));
704 Debug( LDAP_DEBUG_TRACE,
705 "<= list_candidates NULL\n", 0, 0, 0 );
715 } else if ( ftype == LDAP_FILTER_AND ) {
716 idl = idl_intersection( be, idl, tmp );
720 idl = idl_union( be, idl, tmp );
727 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
728 "list_candidates: return %ld\n",
729 idl ? ID_BLOCK_NIDS(idl) : 0 ));
731 Debug( LDAP_DEBUG_TRACE, "<= list_candidates %ld\n",
732 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
739 substring_candidates(
741 SubstringsAssertion *sub
750 struct berval *prefix;
751 struct berval **keys = NULL;
755 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
756 "substrings_candidates: enter\n" ));
758 Debug( LDAP_DEBUG_TRACE, "=> substrings_candidates\n", 0, 0, 0 );
762 idl = idl_allids( be );
764 rc = index_param( be, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
765 &dbname, &mask, &prefix );
767 if( rc != LDAP_SUCCESS ) {
769 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
770 "substrings_candidates: index_param returned %d\n", rc ));
772 Debug( LDAP_DEBUG_TRACE,
773 "<= substrings_candidates: index_param returned=%d\n",
780 if( dbname == NULL ) {
783 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
784 "substrings_candidates: not indexed\n" ));
786 Debug( LDAP_DEBUG_ANY,
787 "<= substrings_candidates: not indexed\n",
791 ber_bvfree( prefix );
795 mr = sub->sa_desc->ad_type->sat_substr;
798 ber_bvfree( prefix );
802 if( !mr->smr_filter ) {
803 ber_bvfree( prefix );
807 rc = (mr->smr_filter)(
808 LDAP_FILTER_SUBSTRINGS,
810 sub->sa_desc->ad_type->sat_syntax,
816 ber_bvfree( prefix );
818 if( rc != LDAP_SUCCESS ) {
820 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
821 "substrings_candidates: (%s%s) MR filter failed (%d)\n",
822 dbname, LDBM_SUFFIX, rc ));
824 Debug( LDAP_DEBUG_TRACE,
825 "<= substrings_candidates: (%s%s) MR filter failed (%d)\n",
826 dbname, LDBM_SUFFIX, rc );
834 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
835 "substrings_candidates: (0x%04lx) no keys (%s%s)\n",
836 mask, dbname, LDBM_SUFFIX ));
838 Debug( LDAP_DEBUG_TRACE,
839 "<= substrings_candidates: (0x%04lx) no keys (%s%s)\n",
840 mask, dbname, LDBM_SUFFIX );
846 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_READER );
850 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
851 "substrings_candidates: db open failed (%s%s)\n",
852 dbname, LDBM_SUFFIX ));
854 Debug( LDAP_DEBUG_ANY,
855 "<= substrings_candidates db open failed (%s%s)\n",
856 dbname, LDBM_SUFFIX, 0 );
862 for ( i= 0; keys[i] != NULL; i++ ) {
866 rc = key_read( be, db, keys[i], &tmp );
868 if( rc != LDAP_SUCCESS ) {
872 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
873 "substrings_candidates: key read failed (%d)\n",
876 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates key read failed (%d)\n",
887 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
888 "substrings_candidates: NULL\n" ));
890 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates NULL\n",
898 idl = idl_intersection( be, idl, tmp );
901 if( idl == NULL ) break;
904 ber_bvecfree( keys );
906 ldbm_cache_close( be, db );
909 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
910 "substrings_candidates: return %ld\n",
911 idl ? ID_BLOCK_NIDS(idl) : 0 ));
913 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates %ld\n",
914 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );