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
11 #include <ac/string.h>
16 #ifdef BDB_FILTER_INDICES
18 static int presence_candidates(
21 AttributeDescription *desc,
23 static int equality_candidates(
26 AttributeAssertion *ava,
28 static int approx_candidates(
31 AttributeAssertion *ava,
33 static int substring_candidates(
36 SubstringsAssertion *sub,
39 static int list_candidates(
48 bdb_filter_candidates(
55 Debug( LDAP_DEBUG_FILTER, "=> bdb_filter_candidates\n", 0, 0, 0 );
57 switch ( f->f_choice ) {
58 case SLAPD_FILTER_DN_ONE:
59 Debug( LDAP_DEBUG_FILTER, "\tDN ONE\n", 0, 0, 0 );
60 rc = bdb_dn2idl( be, f->f_dn, DN_ONE_PREFIX, ids );
63 case SLAPD_FILTER_DN_SUBTREE:
64 Debug( LDAP_DEBUG_FILTER, "\tDN SUBTREE\n", 0, 0, 0 );
65 rc = bdb_dn2idl( be, f->f_dn, DN_SUBTREE_PREFIX, ids );
68 case LDAP_FILTER_PRESENT:
69 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
70 rc = presence_candidates( be, range, f->f_desc, ids );
74 case LDAP_FILTER_EQUALITY:
75 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
76 rc = equality_candidates( be, range, f->f_ava, ids );
79 case LDAP_FILTER_APPROX:
80 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
81 rc = approx_candidates( be, range, f->f_ava, ids );
84 case LDAP_FILTER_SUBSTRINGS:
85 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
86 rc = substring_candidates( be, range, f->f_sub, ids );
91 Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
96 Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
100 case LDAP_FILTER_NOT: {
101 ID tmp[BDB_IDL_SIZE];
103 Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
104 rc = bdb_filter_candidates( be, range, f->f_not, tmp );
106 rc = bdb_idl_notin( range, tmp, ids );
110 case LDAP_FILTER_AND:
111 Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
112 rc = list_candidates( be, range,
113 f->f_and, LDAP_FILTER_AND, ids );
117 Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
118 rc = list_candidates( be, range,
119 f->f_or, LDAP_FILTER_OR, ids );
123 Debug( LDAP_DEBUG_FILTER, "\tUNKNOWN %d\n",
128 BDB_IDL_CPY( ids, range );
131 Debug( LDAP_DEBUG_FILTER,
132 "<= bdb_filter_candidates: id=%ld first=%ld last=%ld\n",
134 BDB_IDL_IS_RANGE( ids ) ? ids[2] : ids[ids[0]] );
150 Debug( LDAP_DEBUG_FILTER, "=> bdb_list_candidates 0x%x\n", ftype, 0, 0 );
152 if( ftype == LDAP_FILTER_AND ) {
153 BDB_IDL_CPY( ids, range );
158 for ( f = flist; f != NULL; f = f->f_next ) {
159 ID tmp[BDB_IDL_SIZE];
160 ID result[BDB_IDL_SIZE];
161 rc = bdb_filter_candidates( be, range, f, tmp );
164 /* Error: treat as undefined */
165 if( ftype == LDAP_FILTER_AND ) {
168 BDB_IDL_CPY( ids, range );
173 if ( ftype == LDAP_FILTER_AND ) {
174 bdb_idl_intersection( tmp, ids, result );
175 if( BDB_IDL_IS_ZERO( result ) ) {
180 bdb_idl_union( tmp, ids, result );
181 if( BDB_IDL_IS_ALL( range, result ) ) {
182 BDB_IDL_CPY( ids, range );
187 BDB_IDL_CPY( ids, result );
190 Debug( LDAP_DEBUG_FILTER,
191 "<= bdb_list_candidates: id=%ld first=%ld last=%ld\n",
192 ids[0], BDB_IDL_FIRST(ids), BDB_IDL_LAST(ids) );
200 AttributeDescription *desc,
206 struct berval *prefix;
208 Debug( LDAP_DEBUG_TRACE, "=> bdb_presence_candidates\n", 0, 0, 0 );
211 rc = bdb_index_param( be, desc, LDAP_FILTER_PRESENT,
212 &db, &mask, &prefix );
214 if( rc != LDAP_SUCCESS ) {
215 Debug( LDAP_DEBUG_TRACE,
216 "<= bdb_presence_candidates: index_param returned=%d\n",
223 Debug( LDAP_DEBUG_TRACE,
224 "<= bdb_presense_candidates: not indexed\n",
230 if( prefix == NULL ) {
231 Debug( LDAP_DEBUG_TRACE,
232 "<= bdb_presense_candidates: no prefix\n",
238 rc = bdb_key_read( be, db, prefix, ids );
240 if( rc == DB_NOTFOUND ) {
243 } else if( rc != LDAP_SUCCESS ) {
244 Debug( LDAP_DEBUG_TRACE,
245 "<= bdb_presense_candidates: key read failed (%d)\n",
250 Debug(LDAP_DEBUG_TRACE,
251 "<= bdb_presence_candidates: id=%ld first=%ld last=%ld\n",
252 ids[0], BDB_IDL_FIRST(ids), BDB_IDL_LAST(ids) );
255 ber_bvfree( prefix );
263 AttributeAssertion *ava,
271 struct berval *prefix;
272 struct berval **keys = NULL;
275 Debug( LDAP_DEBUG_TRACE, "=> bdb_equality_candidates\n", 0, 0, 0 );
277 BDB_IDL_RANGE_CPY( range, ids );
279 rc = bdb_index_param( be, ava->aa_desc, LDAP_FILTER_EQUALITY,
280 &db, &mask, &prefix );
282 if( rc != LDAP_SUCCESS ) {
283 Debug( LDAP_DEBUG_ANY,
284 "<= equality_candidates: index_param failed (%d)\n",
289 mr = ava->aa_desc->ad_type->sat_equality;
291 ber_bvfree( prefix );
295 if( !mr->smr_filter ) {
296 ber_bvfree( prefix );
300 rc = (mr->smr_filter)(
301 LDAP_FILTER_EQUALITY,
303 ava->aa_desc->ad_type->sat_syntax,
309 ber_bvfree( prefix );
311 if( rc != LDAP_SUCCESS ) {
312 Debug( LDAP_DEBUG_TRACE,
313 "<= bdb_equality_candidates: (%s%s) MR filter failed (%d)\n",
319 Debug( LDAP_DEBUG_TRACE,
320 "<= bdb_equality_candidates: no keys (%s%s)\n",
325 for ( i= 0; keys[i] != NULL; i++ ) {
326 ID save[BDB_IDL_SIZE];
327 ID tmp[BDB_IDL_SIZE];
329 rc = bdb_key_read( be, db, keys[i], tmp );
331 if( rc != LDAP_SUCCESS ) {
332 Debug( LDAP_DEBUG_TRACE,
333 "<= bdb_equality_candidates key read failed (%d)\n",
339 Debug( LDAP_DEBUG_TRACE,
340 "<= bdb_equality_candidates NULL\n",
346 idl = idl_intersection( be, idl, tmp );
350 if( idl == NULL ) break;
353 ber_bvecfree( keys );
355 Debug( LDAP_DEBUG_TRACE,
356 "<= bdb_equality_candidates %ld\n",
357 ids[0], BDB_IDL_FIRST(ids), BDB_IDL_LAST(ids) );
366 AttributeAssertion *ava,
375 struct berval *prefix;
376 struct berval **keys = NULL;
379 Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 );
381 rc = bdb_index_param( be, ava->aa_desc, LDAP_FILTER_APPROX,
382 &db, &mask, &prefix );
384 if( rc != LDAP_SUCCESS ) {
385 Debug( LDAP_DEBUG_ANY,
386 "<= approx_candidates: index_param failed (%d)\n",
391 mr = ava->aa_desc->ad_type->sat_approx;
393 /* no approx matching rule, try equality matching rule */
394 mr = ava->aa_desc->ad_type->sat_equality;
398 ber_bvfree( prefix );
402 if( !mr->smr_filter ) {
403 ber_bvfree( prefix );
407 rc = (mr->smr_filter)(
410 ava->aa_desc->ad_type->sat_syntax,
416 ber_bvfree( prefix );
418 if( rc != LDAP_SUCCESS ) {
419 Debug( LDAP_DEBUG_TRACE,
420 "<= approx_candidates: (%s%s) MR filter failed (%d)\n",
421 dbname, LDBM_SUFFIX, rc );
426 Debug( LDAP_DEBUG_TRACE,
427 "<= approx_candidates: no keys (%s%s)\n",
428 dbname, LDBM_SUFFIX, 0 );
433 Debug( LDAP_DEBUG_ANY,
434 "<= approx_candidates db open failed (%s%s)\n",
435 dbname, LDBM_SUFFIX, 0 );
439 for ( i= 0; keys[i] != NULL; i++ ) {
443 rc = key_read( be, db, keys[i], &tmp );
445 if( rc != LDAP_SUCCESS ) {
448 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates key read failed (%d)\n",
456 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n",
462 idl = idl_intersection( be, idl, tmp );
465 if( idl == NULL ) break;
468 ber_bvecfree( keys );
470 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %ld\n",
471 ids[0], BDB_IDL_FIRST(ids), BDB_IDL_LAST(ids) );
477 substring_candidates(
480 SubstringsAssertion *sub,
488 struct berval *prefix;
489 struct berval **keys = NULL;
492 Debug( LDAP_DEBUG_TRACE, "=> substrings_candidates\n", 0, 0, 0 );
494 idl = idl_allids( be );
496 rc = bdb_index_param( be, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
497 &db, &mask, &prefix );
499 if( rc != LDAP_SUCCESS ) {
500 Debug( LDAP_DEBUG_ANY,
501 "<= substrings_candidates: index_param failed (%d)\n",
506 if( dbname == NULL ) {
508 Debug( LDAP_DEBUG_ANY,
509 "<= substrings_candidates: not indexed\n",
511 ber_bvfree( prefix );
515 mr = sub->sa_desc->ad_type->sat_substr;
518 ber_bvfree( prefix );
522 if( !mr->smr_filter ) {
523 ber_bvfree( prefix );
527 rc = (mr->smr_filter)(
528 LDAP_FILTER_SUBSTRINGS,
530 sub->sa_desc->ad_type->sat_syntax,
536 ber_bvfree( prefix );
538 if( rc != LDAP_SUCCESS ) {
539 Debug( LDAP_DEBUG_TRACE,
540 "<= substrings_candidates: (%s%s) MR filter failed (%d)\n",
541 dbname, LDBM_SUFFIX, rc );
546 Debug( LDAP_DEBUG_TRACE,
547 "<= substrings_candidates: (0x%04lx) no keys (%s%s)\n",
548 mask, dbname, LDBM_SUFFIX );
552 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_READER );
555 Debug( LDAP_DEBUG_ANY,
556 "<= substrings_candidates db open failed (%s%s)\n",
557 dbname, LDBM_SUFFIX, 0 );
561 for ( i= 0; keys[i] != NULL; i++ ) {
565 rc = key_read( be, db, keys[i], &tmp );
567 if( rc != LDAP_SUCCESS ) {
570 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates key read failed (%d)\n",
578 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates NULL\n",
584 idl = idl_intersection( be, idl, tmp );
587 if( idl == NULL ) break;
590 ber_bvecfree( keys );
592 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates %ld\n",
593 ids[0], BDB_IDL_FIRST(ids), BDB_IDL_LAST(ids) );