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;
41 Debug( LDAP_DEBUG_TRACE, "=> filter_candidates\n", 0, 0, 0 );
44 switch ( f->f_choice ) {
45 case SLAPD_FILTER_DN_ONE:
46 Debug( LDAP_DEBUG_FILTER, "\tDN ONE\n", 0, 0, 0 );
47 result = dn2idl( be, f->f_dn, DN_ONE_PREFIX );
50 case SLAPD_FILTER_DN_SUBTREE:
51 Debug( LDAP_DEBUG_FILTER, "\tDN SUBTREE\n", 0, 0, 0 );
52 result = dn2idl( be, f->f_dn, DN_SUBTREE_PREFIX );
55 case LDAP_FILTER_PRESENT:
56 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
57 result = presence_candidates( be, f->f_desc );
60 case LDAP_FILTER_EQUALITY:
61 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
62 result = equality_candidates( be, f->f_ava );
65 case LDAP_FILTER_APPROX:
66 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
67 result = approx_candidates( be, f->f_ava );
70 case LDAP_FILTER_SUBSTRINGS:
71 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
72 result = substring_candidates( be, f->f_sub );
76 Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
77 result = idl_allids( be );
81 Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
82 result = idl_allids( be );
86 Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
87 result = list_candidates( be, f->f_and, LDAP_FILTER_AND );
91 Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
92 result = list_candidates( be, f->f_or, LDAP_FILTER_OR );
96 Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
97 tmp1 = idl_allids( be );
98 tmp2 = filter_candidates( be, f->f_not );
99 result = idl_notin( be, tmp1, tmp2 );
105 Debug( LDAP_DEBUG_TRACE, "<= filter_candidates %ld\n",
106 result ? ID_BLOCK_NIDS(result) : 0, 0, 0 );
113 AttributeDescription *desc
121 struct berval *prefix;
123 Debug( LDAP_DEBUG_TRACE, "=> presence_candidates\n", 0, 0, 0 );
125 idl = idl_allids( be );
127 rc = index_param( be, desc, LDAP_FILTER_PRESENT,
128 &dbname, &mask, &prefix );
130 if( rc != LDAP_SUCCESS ) {
131 Debug( LDAP_DEBUG_TRACE,
132 "<= presence_candidates: index_param returned=%d\n",
137 if( dbname == NULL ) {
139 Debug( LDAP_DEBUG_TRACE,
140 "<= presense_candidates: not indexed\n",
142 ber_bvfree( prefix );
146 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_READER );
149 Debug( LDAP_DEBUG_ANY,
150 "<= presense_candidates db open failed (%s%s)\n",
151 dbname, LDBM_SUFFIX, 0 );
152 ber_bvfree( prefix );
156 if( prefix != NULL ) {
160 rc = key_read( be, db, prefix, &idl );
162 if( rc != LDAP_SUCCESS ) {
163 Debug( LDAP_DEBUG_TRACE,
164 "<= presense_candidates key read failed (%d)\n",
167 } else if( idl == NULL ) {
168 Debug( LDAP_DEBUG_TRACE,
169 "<= presense_candidates NULL\n",
174 ldbm_cache_close( be, db );
175 ber_bvfree( prefix );
177 Debug( LDAP_DEBUG_TRACE, "<= presence_candidates %ld\n",
178 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
185 AttributeAssertion *ava
194 struct berval *prefix;
195 struct berval **keys = NULL;
198 Debug( LDAP_DEBUG_TRACE, "=> equality_candidates\n", 0, 0, 0 );
200 idl = idl_allids( be );
202 rc = index_param( be, ava->aa_desc, LDAP_FILTER_EQUALITY,
203 &dbname, &mask, &prefix );
205 if( rc != LDAP_SUCCESS ) {
206 Debug( LDAP_DEBUG_TRACE,
207 "<= equality_candidates: index_param returned=%d\n",
212 if( dbname == NULL ) {
214 Debug( LDAP_DEBUG_TRACE,
215 "<= equality_candidates: not indexed\n",
217 ber_bvfree( prefix );
221 mr = ava->aa_desc->ad_type->sat_equality;
223 ber_bvfree( prefix );
227 if( !mr->smr_filter ) {
228 ber_bvfree( prefix );
232 rc = (mr->smr_filter)(
233 LDAP_FILTER_EQUALITY,
235 ava->aa_desc->ad_type->sat_syntax,
241 ber_bvfree( prefix );
243 if( rc != LDAP_SUCCESS ) {
244 Debug( LDAP_DEBUG_TRACE,
245 "<= equality_candidates: (%s%s) MR filter failed (%d)\n",
246 dbname, LDBM_SUFFIX, rc );
251 Debug( LDAP_DEBUG_TRACE,
252 "<= equality_candidates: no keys (%s%s)\n",
253 dbname, LDBM_SUFFIX, 0 );
257 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_READER );
260 Debug( LDAP_DEBUG_ANY,
261 "<= equality_candidates db open failed (%s%s)\n",
262 dbname, LDBM_SUFFIX, 0 );
266 for ( i= 0; keys[i] != NULL; i++ ) {
270 rc = key_read( be, db, keys[i], &tmp );
272 if( rc != LDAP_SUCCESS ) {
275 Debug( LDAP_DEBUG_TRACE,
276 "<= equality_candidates key read failed (%d)\n",
284 Debug( LDAP_DEBUG_TRACE,
285 "<= equality_candidates NULL\n",
291 idl = idl_intersection( be, idl, tmp );
295 if( idl == NULL ) break;
298 ber_bvecfree( keys );
300 ldbm_cache_close( be, db );
303 Debug( LDAP_DEBUG_TRACE, "<= equality_candidates %ld\n",
304 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
311 AttributeAssertion *ava
320 struct berval *prefix;
321 struct berval **keys = NULL;
324 Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 );
326 idl = idl_allids( be );
328 rc = index_param( be, ava->aa_desc, LDAP_FILTER_APPROX,
329 &dbname, &mask, &prefix );
331 if( rc != LDAP_SUCCESS ) {
332 Debug( LDAP_DEBUG_TRACE,
333 "<= approx_candidates: index_param returned=%d\n",
338 if( dbname == NULL ) {
340 Debug( LDAP_DEBUG_ANY,
341 "<= approx_candidates: not indexed\n",
343 ber_bvfree( prefix );
347 mr = ava->aa_desc->ad_type->sat_approx;
349 /* no approx matching rule, try equality matching rule */
350 mr = ava->aa_desc->ad_type->sat_equality;
354 ber_bvfree( prefix );
358 if( !mr->smr_filter ) {
359 ber_bvfree( prefix );
363 rc = (mr->smr_filter)(
366 ava->aa_desc->ad_type->sat_syntax,
372 ber_bvfree( prefix );
374 if( rc != LDAP_SUCCESS ) {
375 Debug( LDAP_DEBUG_TRACE,
376 "<= approx_candidates: (%s%s) MR filter failed (%d)\n",
377 dbname, LDBM_SUFFIX, rc );
382 Debug( LDAP_DEBUG_TRACE,
383 "<= approx_candidates: no keys (%s%s)\n",
384 dbname, LDBM_SUFFIX, 0 );
388 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_READER );
391 Debug( LDAP_DEBUG_ANY,
392 "<= approx_candidates db open failed (%s%s)\n",
393 dbname, LDBM_SUFFIX, 0 );
397 for ( i= 0; keys[i] != NULL; i++ ) {
401 rc = key_read( be, db, keys[i], &tmp );
403 if( rc != LDAP_SUCCESS ) {
406 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates key read failed (%d)\n",
414 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n",
420 idl = idl_intersection( be, idl, tmp );
423 if( idl == NULL ) break;
426 ber_bvecfree( keys );
428 ldbm_cache_close( be, db );
430 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %ld\n",
431 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
442 ID_BLOCK *idl, *tmp, *tmp2;
445 Debug( LDAP_DEBUG_TRACE, "=> list_candidates 0x%x\n", ftype, 0, 0 );
448 for ( f = flist; f != NULL; f = f->f_next ) {
449 if ( (tmp = filter_candidates( be, f )) == NULL &&
450 ftype == LDAP_FILTER_AND ) {
451 Debug( LDAP_DEBUG_TRACE,
452 "<= list_candidates NULL\n", 0, 0, 0 );
460 } else if ( ftype == LDAP_FILTER_AND ) {
461 idl = idl_intersection( be, idl, tmp );
465 idl = idl_union( be, idl, tmp );
471 Debug( LDAP_DEBUG_TRACE, "<= list_candidates %ld\n",
472 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
477 substring_candidates(
479 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 = index_param( be, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
497 &dbname, &mask, &prefix );
499 if( rc != LDAP_SUCCESS ) {
500 Debug( LDAP_DEBUG_TRACE,
501 "<= substrings_candidates: index_param returned=%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 ldbm_cache_close( be, db );
594 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates %ld\n",
595 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );