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(
20 AttributeDescription *desc,
23 static int equality_candidates(
25 AttributeAssertion *ava,
28 static int approx_candidates(
30 AttributeAssertion *ava,
33 static int substring_candidates(
35 SubstringsAssertion *sub,
39 static int list_candidates(
47 bdb_filter_candidates(
54 Debug( LDAP_DEBUG_FILTER, "=> bdb_filter_candidates\n", 0, 0, 0 );
56 switch ( f->f_choice ) {
57 case SLAPD_FILTER_DN_ONE:
58 Debug( LDAP_DEBUG_FILTER, "\tDN ONE\n", 0, 0, 0 );
59 rc = bdb_dn2idl( be, f->f_dn, DN_ONE_PREFIX, ids );
62 case SLAPD_FILTER_DN_SUBTREE:
63 Debug( LDAP_DEBUG_FILTER, "\tDN SUBTREE\n", 0, 0, 0 );
64 rc = bdb_dn2idl( be, f->f_dn, DN_SUBTREE_PREFIX, ids );
67 case LDAP_FILTER_PRESENT:
68 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
69 rc = presence_candidates( be, f->f_desc, ids );
72 case LDAP_FILTER_EQUALITY:
73 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
74 rc = equality_candidates( be, f->f_ava, ids, tmp );
77 case LDAP_FILTER_APPROX:
78 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
79 rc = approx_candidates( be, f->f_ava, ids, tmp );
82 case LDAP_FILTER_SUBSTRINGS:
83 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
84 rc = substring_candidates( be, f->f_sub, ids, tmp );
88 /* no GE index, use pres */
89 Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
90 rc = presence_candidates( be, f->f_desc, ids );
94 /* no LE index, use pres */
95 Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
96 rc = presence_candidates( be, f->f_desc, ids );
100 /* no indexing to support NOT filters */
101 Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
104 case LDAP_FILTER_AND:
105 Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
106 rc = list_candidates( be,
107 f->f_and, LDAP_FILTER_AND, ids, tmp );
111 Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
112 rc = list_candidates( be,
113 f->f_or, LDAP_FILTER_OR, ids, tmp );
117 Debug( LDAP_DEBUG_FILTER, "\tUNKNOWN %d\n",
121 Debug( LDAP_DEBUG_FILTER,
122 "<= bdb_filter_candidates: id=%ld first=%ld last=%ld\n",
124 (long) BDB_IDL_FIRST( ids ),
125 (long) BDB_IDL_LAST( ids ) );
138 struct bdb_info *bdb = (struct bdb_info *) be->be_private;
142 /* Systems that can't increase thread stack size will die with these
143 * structures allocated on the stack. */
144 #if !defined(LDAP_PVT_THREAD_STACK_SIZE) || (LDAP_PVT_THREAD_STACK_SIZE == 0)
145 ID *save = ch_malloc(BDB_IDL_UM_SIZEOF);
147 ID save[BDB_IDL_UM_SIZE];
150 Debug( LDAP_DEBUG_FILTER, "=> bdb_list_candidates 0x%x\n", ftype, 0, 0 );
152 if ( ftype == LDAP_FILTER_OR ) {
153 BDB_IDL_ALL( bdb, save );
156 BDB_IDL_CPY( save, ids );
159 for ( f = flist; f != NULL; f = f->f_next ) {
160 rc = bdb_filter_candidates( be, f, save, tmp );
163 /* Error: treat as undefined */
167 if ( ftype == LDAP_FILTER_AND ) {
168 bdb_idl_intersection( ids, save );
169 if( BDB_IDL_IS_ZERO( ids ) )
172 bdb_idl_union( ids, save );
173 BDB_IDL_ALL( bdb, save );
176 #if !defined(LDAP_PVT_THREAD_STACK_SIZE) || (LDAP_PVT_THREAD_STACK_SIZE == 0)
180 Debug( LDAP_DEBUG_FILTER,
181 "<= bdb_list_candidates: id=%ld first=%ld last=%ld\n",
183 (long) BDB_IDL_FIRST(ids),
184 (long) BDB_IDL_LAST(ids) );
191 AttributeDescription *desc,
194 struct bdb_info *bdb = (struct bdb_info *) be->be_private;
198 struct berval prefix = {0};
200 Debug( LDAP_DEBUG_TRACE, "=> bdb_presence_candidates\n", 0, 0, 0 );
202 if( desc == slap_schema.si_ad_objectClass ) {
203 BDB_IDL_ALL( bdb, ids );
207 rc = bdb_index_param( be, desc, LDAP_FILTER_PRESENT,
208 &db, &mask, &prefix );
210 if( rc != LDAP_SUCCESS ) {
211 Debug( LDAP_DEBUG_TRACE,
212 "<= bdb_presence_candidates: index_param returned=%d\n",
219 Debug( LDAP_DEBUG_TRACE,
220 "<= bdb_presence_candidates: not indexed\n",
225 if( prefix.bv_val == NULL ) {
226 Debug( LDAP_DEBUG_TRACE,
227 "<= bdb_presence_candidates: no prefix\n",
232 rc = bdb_key_read( be, db, NULL, &prefix, ids );
234 if( rc == DB_NOTFOUND ) {
237 } else if( rc != LDAP_SUCCESS ) {
238 Debug( LDAP_DEBUG_TRACE,
239 "<= bdb_presense_candidates: key read failed (%d)\n",
244 Debug(LDAP_DEBUG_TRACE,
245 "<= bdb_presence_candidates: id=%ld first=%ld last=%ld\n",
247 (long) BDB_IDL_FIRST(ids),
248 (long) BDB_IDL_LAST(ids) );
257 AttributeAssertion *ava,
265 struct berval prefix = {0};
266 struct berval *keys = NULL;
269 Debug( LDAP_DEBUG_TRACE, "=> bdb_equality_candidates\n", 0, 0, 0 );
271 rc = bdb_index_param( be, ava->aa_desc, LDAP_FILTER_EQUALITY,
272 &db, &mask, &prefix );
274 if( rc != LDAP_SUCCESS ) {
275 Debug( LDAP_DEBUG_ANY,
276 "<= bdb_equality_candidates: index_param failed (%d)\n",
282 Debug( LDAP_DEBUG_ANY,
283 "<= bdb_equality_candidates: not indexed\n", 0, 0, 0 );
287 mr = ava->aa_desc->ad_type->sat_equality;
292 if( !mr->smr_filter ) {
296 rc = (mr->smr_filter)(
297 LDAP_FILTER_EQUALITY,
299 ava->aa_desc->ad_type->sat_syntax,
305 if( rc != LDAP_SUCCESS ) {
306 Debug( LDAP_DEBUG_TRACE,
307 "<= bdb_equality_candidates: MR filter failed (%d)\n",
313 Debug( LDAP_DEBUG_TRACE,
314 "<= bdb_equality_candidates: no keys\n",
319 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
320 rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
322 if( rc == DB_NOTFOUND ) {
325 } else if( rc != LDAP_SUCCESS ) {
326 Debug( LDAP_DEBUG_TRACE,
327 "<= bdb_equality_candidates key read failed (%d)\n",
332 if( BDB_IDL_IS_ZERO( tmp ) ) {
333 Debug( LDAP_DEBUG_TRACE,
334 "<= bdb_equality_candidates NULL\n",
340 bdb_idl_intersection( ids, tmp );
342 if( BDB_IDL_IS_ZERO( ids ) )
346 bvarray_free( keys );
348 Debug( LDAP_DEBUG_TRACE,
349 "<= bdb_equality_candidates id=%ld, first=%ld, last=%ld\n",
351 (long) BDB_IDL_FIRST(ids),
352 (long) BDB_IDL_LAST(ids) );
360 AttributeAssertion *ava,
368 struct berval prefix = {0};
369 struct berval *keys = NULL;
372 Debug( LDAP_DEBUG_TRACE, "=> bdb_approx_candidates\n", 0, 0, 0 );
374 rc = bdb_index_param( be, ava->aa_desc, LDAP_FILTER_APPROX,
375 &db, &mask, &prefix );
377 if( rc != LDAP_SUCCESS ) {
378 Debug( LDAP_DEBUG_ANY,
379 "<= bdb_approx_candidates: index_param failed (%d)\n",
385 Debug( LDAP_DEBUG_ANY,
386 "<= bdb_approx_candidates: not indexed\n", 0, 0, 0 );
390 mr = ava->aa_desc->ad_type->sat_approx;
392 /* no approx matching rule, try equality matching rule */
393 mr = ava->aa_desc->ad_type->sat_equality;
400 if( !mr->smr_filter ) {
404 rc = (mr->smr_filter)(
407 ava->aa_desc->ad_type->sat_syntax,
413 if( rc != LDAP_SUCCESS ) {
414 Debug( LDAP_DEBUG_TRACE,
415 "<= bdb_approx_candidates: (%s) MR filter failed (%d)\n",
416 prefix.bv_val, rc, 0 );
421 Debug( LDAP_DEBUG_TRACE,
422 "<= bdb_approx_candidates: no keys (%s)\n",
423 prefix.bv_val, 0, 0 );
427 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
428 rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
430 if( rc == DB_NOTFOUND ) {
434 } else if( rc != LDAP_SUCCESS ) {
435 Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates key read failed (%d)\n",
440 if( BDB_IDL_IS_ZERO( tmp ) ) {
441 Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates NULL\n",
447 bdb_idl_intersection( ids, tmp );
449 if( BDB_IDL_IS_ZERO( ids ) )
453 bvarray_free( keys );
455 Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates %ld, first=%ld, last=%ld\n",
457 (long) BDB_IDL_FIRST(ids),
458 (long) BDB_IDL_LAST(ids) );
464 substring_candidates(
466 SubstringsAssertion *sub,
474 struct berval prefix = {0};
475 struct berval *keys = NULL;
478 Debug( LDAP_DEBUG_TRACE, "=> bdb_substring_candidates\n", 0, 0, 0 );
480 rc = bdb_index_param( be, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
481 &db, &mask, &prefix );
483 if( rc != LDAP_SUCCESS ) {
484 Debug( LDAP_DEBUG_ANY,
485 "<= bdb_substring_candidates: index_param failed (%d)\n",
491 Debug( LDAP_DEBUG_ANY,
492 "<= bdb_substring_candidates not indexed\n",
497 mr = sub->sa_desc->ad_type->sat_substr;
503 if( !mr->smr_filter ) {
507 rc = (mr->smr_filter)(
508 LDAP_FILTER_SUBSTRINGS,
510 sub->sa_desc->ad_type->sat_syntax,
516 if( rc != LDAP_SUCCESS ) {
517 Debug( LDAP_DEBUG_TRACE,
518 "<= bdb_substring_candidates: (%s) MR filter failed (%d)\n",
519 sub->sa_desc->ad_cname.bv_val, rc, 0 );
524 Debug( LDAP_DEBUG_TRACE,
525 "<= bdb_substring_candidates: (0x%04lx) no keys (%s)\n",
526 mask, sub->sa_desc->ad_cname.bv_val, 0 );
530 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
531 rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
533 if( rc == DB_NOTFOUND ) {
537 } else if( rc != LDAP_SUCCESS ) {
538 Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates key read failed (%d)\n",
543 if( BDB_IDL_IS_ZERO( tmp ) ) {
544 Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates NULL\n",
550 bdb_idl_intersection( ids, tmp );
552 if( BDB_IDL_IS_ZERO( ids ) )
556 bvarray_free( keys );
558 Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates %ld, first=%ld, last=%ld\n",
560 (long) BDB_IDL_FIRST(ids),
561 (long) BDB_IDL_LAST(ids) );