Back to index

openldap  2.4.31
filterindex.c
Go to the documentation of this file.
00001 /* filterindex.c - generate the list of candidate entries from a filter */
00002 /* $OpenLDAP$ */
00003 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
00004  *
00005  * Copyright 2000-2012 The OpenLDAP Foundation.
00006  * All rights reserved.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted only as authorized by the OpenLDAP
00010  * Public License.
00011  *
00012  * A copy of this license is available in the file LICENSE in the
00013  * top-level directory of the distribution or, alternatively, at
00014  * <http://www.OpenLDAP.org/license.html>.
00015  */
00016 
00017 #include "portable.h"
00018 
00019 #include <stdio.h>
00020 #include <ac/string.h>
00021 
00022 #include "back-bdb.h"
00023 #include "idl.h"
00024 #ifdef LDAP_COMP_MATCH
00025 #include <component.h>
00026 #endif
00027 
00028 static int presence_candidates(
00029        Operation *op,
00030        DB_TXN *rtxn,
00031        AttributeDescription *desc,
00032        ID *ids );
00033 
00034 static int equality_candidates(
00035        Operation *op,
00036        DB_TXN *rtxn,
00037        AttributeAssertion *ava,
00038        ID *ids,
00039        ID *tmp );
00040 static int inequality_candidates(
00041        Operation *op,
00042        DB_TXN *rtxn,
00043        AttributeAssertion *ava,
00044        ID *ids,
00045        ID *tmp,
00046        int gtorlt );
00047 static int approx_candidates(
00048        Operation *op,
00049        DB_TXN *rtxn,
00050        AttributeAssertion *ava,
00051        ID *ids,
00052        ID *tmp );
00053 static int substring_candidates(
00054        Operation *op,
00055        DB_TXN *rtxn,
00056        SubstringsAssertion *sub,
00057        ID *ids,
00058        ID *tmp );
00059 
00060 static int list_candidates(
00061        Operation *op,
00062        DB_TXN *rtxn,
00063        Filter *flist,
00064        int ftype,
00065        ID *ids,
00066        ID *tmp,
00067        ID *stack );
00068 
00069 static int
00070 ext_candidates(
00071         Operation *op,
00072               DB_TXN *rtxn,
00073         MatchingRuleAssertion *mra,
00074         ID *ids,
00075         ID *tmp,
00076         ID *stack);
00077 
00078 #ifdef LDAP_COMP_MATCH
00079 static int
00080 comp_candidates (
00081        Operation *op,
00082        DB_TXN *rtxn,
00083        MatchingRuleAssertion *mra,
00084        ComponentFilter *f,
00085        ID *ids,
00086        ID *tmp,
00087        ID *stack);
00088 
00089 static int
00090 ava_comp_candidates (
00091               Operation *op,
00092               DB_TXN *rtxn,
00093               AttributeAssertion *ava,
00094               AttributeAliasing *aa,
00095               ID *ids,
00096               ID *tmp,
00097               ID *stack);
00098 #endif
00099 
00100 int
00101 bdb_filter_candidates(
00102        Operation *op,
00103        DB_TXN *rtxn,
00104        Filter *f,
00105        ID *ids,
00106        ID *tmp,
00107        ID *stack )
00108 {
00109        int rc = 0;
00110 #ifdef LDAP_COMP_MATCH
00111        AttributeAliasing *aa;
00112 #endif
00113        Debug( LDAP_DEBUG_FILTER, "=> bdb_filter_candidates\n", 0, 0, 0 );
00114 
00115        if ( f->f_choice & SLAPD_FILTER_UNDEFINED ) {
00116               BDB_IDL_ZERO( ids );
00117               goto out;
00118        }
00119 
00120        switch ( f->f_choice ) {
00121        case SLAPD_FILTER_COMPUTED:
00122               switch( f->f_result ) {
00123               case SLAPD_COMPARE_UNDEFINED:
00124               /* This technically is not the same as FALSE, but it
00125                * certainly will produce no matches.
00126                */
00127               /* FALL THRU */
00128               case LDAP_COMPARE_FALSE:
00129                      BDB_IDL_ZERO( ids );
00130                      break;
00131               case LDAP_COMPARE_TRUE: {
00132                      struct bdb_info *bdb = (struct bdb_info *)op->o_bd->be_private;
00133                      BDB_IDL_ALL( bdb, ids );
00134                      } break;
00135               case LDAP_SUCCESS:
00136                      /* this is a pre-computed scope, leave it alone */
00137                      break;
00138               }
00139               break;
00140        case LDAP_FILTER_PRESENT:
00141               Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
00142               rc = presence_candidates( op, rtxn, f->f_desc, ids );
00143               break;
00144 
00145        case LDAP_FILTER_EQUALITY:
00146               Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
00147 #ifdef LDAP_COMP_MATCH
00148               if ( is_aliased_attribute && ( aa = is_aliased_attribute ( f->f_ava->aa_desc ) ) ) {
00149                      rc = ava_comp_candidates ( op, rtxn, f->f_ava, aa, ids, tmp, stack );
00150               }
00151               else
00152 #endif
00153               {
00154                      rc = equality_candidates( op, rtxn, f->f_ava, ids, tmp );
00155               }
00156               break;
00157 
00158        case LDAP_FILTER_APPROX:
00159               Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
00160               rc = approx_candidates( op, rtxn, f->f_ava, ids, tmp );
00161               break;
00162 
00163        case LDAP_FILTER_SUBSTRINGS:
00164               Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
00165               rc = substring_candidates( op, rtxn, f->f_sub, ids, tmp );
00166               break;
00167 
00168        case LDAP_FILTER_GE:
00169               /* if no GE index, use pres */
00170               Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
00171               if( f->f_ava->aa_desc->ad_type->sat_ordering &&
00172                      ( f->f_ava->aa_desc->ad_type->sat_ordering->smr_usage & SLAP_MR_ORDERED_INDEX ) )
00173                      rc = inequality_candidates( op, rtxn, f->f_ava, ids, tmp, LDAP_FILTER_GE );
00174               else
00175                      rc = presence_candidates( op, rtxn, f->f_ava->aa_desc, ids );
00176               break;
00177 
00178        case LDAP_FILTER_LE:
00179               /* if no LE index, use pres */
00180               Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
00181               if( f->f_ava->aa_desc->ad_type->sat_ordering &&
00182                      ( f->f_ava->aa_desc->ad_type->sat_ordering->smr_usage & SLAP_MR_ORDERED_INDEX ) )
00183                      rc = inequality_candidates( op, rtxn, f->f_ava, ids, tmp, LDAP_FILTER_LE );
00184               else
00185                      rc = presence_candidates( op, rtxn, f->f_ava->aa_desc, ids );
00186               break;
00187 
00188        case LDAP_FILTER_NOT:
00189               /* no indexing to support NOT filters */
00190               Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
00191               { struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
00192               BDB_IDL_ALL( bdb, ids );
00193               }
00194               break;
00195 
00196        case LDAP_FILTER_AND:
00197               Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
00198               rc = list_candidates( op, rtxn, 
00199                      f->f_and, LDAP_FILTER_AND, ids, tmp, stack );
00200               break;
00201 
00202        case LDAP_FILTER_OR:
00203               Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
00204               rc = list_candidates( op, rtxn,
00205                      f->f_or, LDAP_FILTER_OR, ids, tmp, stack );
00206               break;
00207        case LDAP_FILTER_EXT:
00208                 Debug( LDAP_DEBUG_FILTER, "\tEXT\n", 0, 0, 0 );
00209                 rc = ext_candidates( op, rtxn, f->f_mra, ids, tmp, stack );
00210                 break;
00211        default:
00212               Debug( LDAP_DEBUG_FILTER, "\tUNKNOWN %lu\n",
00213                      (unsigned long) f->f_choice, 0, 0 );
00214               /* Must not return NULL, otherwise extended filters break */
00215               { struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
00216               BDB_IDL_ALL( bdb, ids );
00217               }
00218        }
00219 
00220 out:
00221        Debug( LDAP_DEBUG_FILTER,
00222               "<= bdb_filter_candidates: id=%ld first=%ld last=%ld\n",
00223               (long) ids[0],
00224               (long) BDB_IDL_FIRST( ids ),
00225               (long) BDB_IDL_LAST( ids ) );
00226 
00227        return rc;
00228 }
00229 
00230 #ifdef LDAP_COMP_MATCH
00231 static int
00232 comp_list_candidates(
00233        Operation *op,
00234        DB_TXN *rtxn,
00235        MatchingRuleAssertion* mra,
00236        ComponentFilter      *flist,
00237        int    ftype,
00238        ID *ids,
00239        ID *tmp,
00240        ID *save )
00241 {
00242        int rc = 0;
00243        ComponentFilter      *f;
00244 
00245        Debug( LDAP_DEBUG_FILTER, "=> comp_list_candidates 0x%x\n", ftype, 0, 0 );
00246        for ( f = flist; f != NULL; f = f->cf_next ) {
00247               /* ignore precomputed scopes */
00248               if ( f->cf_choice == SLAPD_FILTER_COMPUTED &&
00249                    f->cf_result == LDAP_SUCCESS ) {
00250                      continue;
00251               }
00252               BDB_IDL_ZERO( save );
00253               rc = comp_candidates( op, rtxn, mra, f, save, tmp, save+BDB_IDL_UM_SIZE );
00254 
00255               if ( rc != 0 ) {
00256                      if ( ftype == LDAP_COMP_FILTER_AND ) {
00257                             rc = 0;
00258                             continue;
00259                      }
00260                      break;
00261               }
00262               
00263               if ( ftype == LDAP_COMP_FILTER_AND ) {
00264                      if ( f == flist ) {
00265                             BDB_IDL_CPY( ids, save );
00266                      } else {
00267                             bdb_idl_intersection( ids, save );
00268                      }
00269                      if( BDB_IDL_IS_ZERO( ids ) )
00270                             break;
00271               } else {
00272                      if ( f == flist ) {
00273                             BDB_IDL_CPY( ids, save );
00274                      } else {
00275                             bdb_idl_union( ids, save );
00276                      }
00277               }
00278        }
00279 
00280        if( rc == LDAP_SUCCESS ) {
00281               Debug( LDAP_DEBUG_FILTER,
00282                      "<= comp_list_candidates: id=%ld first=%ld last=%ld\n",
00283                      (long) ids[0],
00284                      (long) BDB_IDL_FIRST(ids),
00285                      (long) BDB_IDL_LAST(ids) );
00286 
00287        } else {
00288               Debug( LDAP_DEBUG_FILTER,
00289                      "<= comp_list_candidates: undefined rc=%d\n",
00290                      rc, 0, 0 );
00291        }
00292 
00293        return rc;
00294 }
00295 
00296 static int
00297 comp_equality_candidates (
00298         Operation *op,
00299        DB_TXN *rtxn,
00300         MatchingRuleAssertion *mra,
00301        ComponentAssertion *ca,
00302         ID *ids,
00303         ID *tmp,
00304         ID *stack)
00305 {
00306        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
00307         DB      *db;
00308         int i;
00309         int rc;
00310         slap_mask_t mask;
00311         struct berval prefix = {0, NULL};
00312         struct berval *keys = NULL;
00313         MatchingRule *mr = mra->ma_rule;
00314         Syntax *sat_syntax;
00315        ComponentReference* cr_list, *cr;
00316        AttrInfo *ai;
00317 
00318         BDB_IDL_ALL( bdb, ids );
00319 
00320        if ( !ca->ca_comp_ref )
00321               return 0;
00322 
00323        ai = bdb_attr_mask( op->o_bd->be_private, mra->ma_desc );
00324        if( ai ) {
00325               cr_list = ai->ai_cr;
00326        }
00327        else {
00328               return 0;
00329        }
00330        /* find a component reference to be indexed */
00331        sat_syntax = ca->ca_ma_rule->smr_syntax;
00332        for ( cr = cr_list ; cr ; cr = cr->cr_next ) {
00333               if ( cr->cr_string.bv_len == ca->ca_comp_ref->cr_string.bv_len &&
00334                      strncmp( cr->cr_string.bv_val, ca->ca_comp_ref->cr_string.bv_val,cr->cr_string.bv_len ) == 0 )
00335                      break;
00336        }
00337        
00338        if ( !cr )
00339               return 0;
00340 
00341         rc = bdb_index_param( op->o_bd, mra->ma_desc, LDAP_FILTER_EQUALITY,
00342                 &db, &mask, &prefix );
00343 
00344         if( rc != LDAP_SUCCESS ) {
00345                 return 0;
00346         }
00347 
00348         if( !mr ) {
00349                 return 0;
00350         }
00351 
00352         if( !mr->smr_filter ) {
00353                 return 0;
00354         }
00355 
00356        rc = (ca->ca_ma_rule->smr_filter)(
00357                 LDAP_FILTER_EQUALITY,
00358                 cr->cr_indexmask,
00359                 sat_syntax,
00360                 ca->ca_ma_rule,
00361                 &prefix,
00362                 &ca->ca_ma_value,
00363                 &keys, op->o_tmpmemctx );
00364 
00365         if( rc != LDAP_SUCCESS ) {
00366                 return 0;
00367         }
00368 
00369         if( keys == NULL ) {
00370                 return 0;
00371         }
00372         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
00373                 rc = bdb_key_read( op->o_bd, db, rtxn, &keys[i], tmp, NULL, 0 );
00374 
00375                 if( rc == DB_NOTFOUND ) {
00376                         BDB_IDL_ZERO( ids );
00377                         rc = 0;
00378                         break;
00379                 } else if( rc != LDAP_SUCCESS ) {
00380                         break;
00381                 }
00382 
00383                 if( BDB_IDL_IS_ZERO( tmp ) ) {
00384                         BDB_IDL_ZERO( ids );
00385                         break;
00386                 }
00387 
00388                 if ( i == 0 ) {
00389                         BDB_IDL_CPY( ids, tmp );
00390                 } else {
00391                         bdb_idl_intersection( ids, tmp );
00392                 }
00393 
00394                 if( BDB_IDL_IS_ZERO( ids ) )
00395                         break;
00396         }
00397         ber_bvarray_free_x( keys, op->o_tmpmemctx );
00398 
00399         Debug( LDAP_DEBUG_TRACE,
00400                 "<= comp_equality_candidates: id=%ld, first=%ld, last=%ld\n",
00401                 (long) ids[0],
00402                 (long) BDB_IDL_FIRST(ids),
00403                 (long) BDB_IDL_LAST(ids) );
00404         return( rc );
00405 }
00406 
00407 static int
00408 ava_comp_candidates (
00409        Operation *op,
00410        DB_TXN *rtxn,
00411        AttributeAssertion *ava,
00412        AttributeAliasing *aa,
00413        ID *ids,
00414        ID *tmp,
00415        ID *stack )
00416 {
00417        MatchingRuleAssertion mra;
00418        
00419        mra.ma_rule = ava->aa_desc->ad_type->sat_equality;
00420        if ( !mra.ma_rule ) {
00421               struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
00422               BDB_IDL_ALL( bdb, ids );
00423               return 0;
00424        }
00425        mra.ma_desc = aa->aa_aliased_ad;
00426        mra.ma_rule = ava->aa_desc->ad_type->sat_equality;
00427        
00428        return comp_candidates ( op, rtxn, &mra, ava->aa_cf, ids, tmp, stack );
00429 }
00430 
00431 static int
00432 comp_candidates (
00433        Operation *op,
00434        DB_TXN *rtxn,
00435        MatchingRuleAssertion *mra,
00436        ComponentFilter *f,
00437        ID *ids,
00438        ID *tmp,
00439        ID *stack)
00440 {
00441        int    rc;
00442 
00443        if ( !f ) return LDAP_PROTOCOL_ERROR;
00444 
00445        Debug( LDAP_DEBUG_FILTER, "comp_candidates\n", 0, 0, 0 );
00446        switch ( f->cf_choice ) {
00447        case SLAPD_FILTER_COMPUTED:
00448               rc = f->cf_result;
00449               break;
00450        case LDAP_COMP_FILTER_AND:
00451               rc = comp_list_candidates( op, rtxn, mra, f->cf_and, LDAP_COMP_FILTER_AND, ids, tmp, stack );
00452               break;
00453        case LDAP_COMP_FILTER_OR:
00454               rc = comp_list_candidates( op, rtxn, mra, f->cf_or, LDAP_COMP_FILTER_OR, ids, tmp, stack );
00455               break;
00456        case LDAP_COMP_FILTER_NOT:
00457               /* No component indexing supported for NOT filter */
00458               Debug( LDAP_DEBUG_FILTER, "\tComponent NOT\n", 0, 0, 0 );
00459               {
00460                      struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
00461                      BDB_IDL_ALL( bdb, ids );
00462               }
00463               rc = LDAP_PROTOCOL_ERROR;
00464               break;
00465        case LDAP_COMP_FILTER_ITEM:
00466               rc = comp_equality_candidates( op, rtxn, mra, f->cf_ca, ids, tmp, stack );
00467               break;
00468        default:
00469               {
00470                      struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
00471                      BDB_IDL_ALL( bdb, ids );
00472               }
00473               rc = LDAP_PROTOCOL_ERROR;
00474        }
00475 
00476        return( rc );
00477 }
00478 #endif
00479 
00480 static int
00481 ext_candidates(
00482         Operation *op,
00483               DB_TXN *rtxn,
00484         MatchingRuleAssertion *mra,
00485         ID *ids,
00486         ID *tmp,
00487         ID *stack)
00488 {
00489        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
00490 
00491 #ifdef LDAP_COMP_MATCH
00492        /*
00493         * Currently Only Component Indexing for componentFilterMatch is supported
00494         * Indexing for an extensible filter is not supported yet
00495         */
00496        if ( mra->ma_cf ) {
00497               return comp_candidates ( op, rtxn, mra, mra->ma_cf, ids, tmp, stack);
00498        }
00499 #endif
00500        if ( mra->ma_desc == slap_schema.si_ad_entryDN ) {
00501               int rc;
00502               EntryInfo *ei;
00503 
00504               BDB_IDL_ZERO( ids );
00505               if ( mra->ma_rule == slap_schema.si_mr_distinguishedNameMatch ) {
00506                      ei = NULL;
00507                      rc = bdb_cache_find_ndn( op, rtxn, &mra->ma_value, &ei );
00508                      if ( rc == LDAP_SUCCESS )
00509                             bdb_idl_insert( ids, ei->bei_id );
00510                      if ( ei )
00511                             bdb_cache_entryinfo_unlock( ei );
00512                      return 0;
00513               } else if ( mra->ma_rule && mra->ma_rule->smr_match ==
00514                      dnRelativeMatch && dnIsSuffix( &mra->ma_value,
00515                             op->o_bd->be_nsuffix )) {
00516                      int scope;
00517                      if ( mra->ma_rule == slap_schema.si_mr_dnSuperiorMatch ) {
00518                             struct berval pdn;
00519                             ei = NULL;
00520                             dnParent( &mra->ma_value, &pdn );
00521                             bdb_cache_find_ndn( op, rtxn, &pdn, &ei );
00522                             if ( ei ) {
00523                                    bdb_cache_entryinfo_unlock( ei );
00524                                    while ( ei && ei->bei_id ) {
00525                                           bdb_idl_insert( ids, ei->bei_id );
00526                                           ei = ei->bei_parent;
00527                                    }
00528                             }
00529                             return 0;
00530                      }
00531                      if ( mra->ma_rule == slap_schema.si_mr_dnSubtreeMatch )
00532                             scope = LDAP_SCOPE_SUBTREE;
00533                      else if ( mra->ma_rule == slap_schema.si_mr_dnOneLevelMatch )
00534                             scope = LDAP_SCOPE_ONELEVEL;
00535                      else if ( mra->ma_rule == slap_schema.si_mr_dnSubordinateMatch )
00536                             scope = LDAP_SCOPE_SUBORDINATE;
00537                      else
00538                             scope = LDAP_SCOPE_BASE;
00539                      if ( scope > LDAP_SCOPE_BASE ) {
00540                             ei = NULL;
00541                             rc = bdb_cache_find_ndn( op, rtxn, &mra->ma_value, &ei );
00542                             if ( ei )
00543                                    bdb_cache_entryinfo_unlock( ei );
00544                             if ( rc == LDAP_SUCCESS ) {
00545                                    int sc = op->ors_scope;
00546                                    op->ors_scope = scope;
00547                                    rc = bdb_dn2idl( op, rtxn, &mra->ma_value, ei, ids,
00548                                           stack );
00549                                    op->ors_scope = sc;
00550                             }
00551                             return 0;
00552                      }
00553               }
00554        }
00555 
00556        BDB_IDL_ALL( bdb, ids );
00557        return 0;
00558 }
00559 
00560 static int
00561 list_candidates(
00562        Operation *op,
00563        DB_TXN *rtxn,
00564        Filter *flist,
00565        int           ftype,
00566        ID *ids,
00567        ID *tmp,
00568        ID *save )
00569 {
00570        int rc = 0;
00571        Filter *f;
00572 
00573        Debug( LDAP_DEBUG_FILTER, "=> bdb_list_candidates 0x%x\n", ftype, 0, 0 );
00574        for ( f = flist; f != NULL; f = f->f_next ) {
00575               /* ignore precomputed scopes */
00576               if ( f->f_choice == SLAPD_FILTER_COMPUTED &&
00577                    f->f_result == LDAP_SUCCESS ) {
00578                      continue;
00579               }
00580               BDB_IDL_ZERO( save );
00581               rc = bdb_filter_candidates( op, rtxn, f, save, tmp,
00582                      save+BDB_IDL_UM_SIZE );
00583 
00584               if ( rc != 0 ) {
00585                      if ( rc == DB_LOCK_DEADLOCK )
00586                             return rc;
00587 
00588                      if ( ftype == LDAP_FILTER_AND ) {
00589                             rc = 0;
00590                             continue;
00591                      }
00592                      break;
00593               }
00594 
00595               
00596               if ( ftype == LDAP_FILTER_AND ) {
00597                      if ( f == flist ) {
00598                             BDB_IDL_CPY( ids, save );
00599                      } else {
00600                             bdb_idl_intersection( ids, save );
00601                      }
00602                      if( BDB_IDL_IS_ZERO( ids ) )
00603                             break;
00604               } else {
00605                      if ( f == flist ) {
00606                             BDB_IDL_CPY( ids, save );
00607                      } else {
00608                             bdb_idl_union( ids, save );
00609                      }
00610               }
00611        }
00612 
00613        if( rc == LDAP_SUCCESS ) {
00614               Debug( LDAP_DEBUG_FILTER,
00615                      "<= bdb_list_candidates: id=%ld first=%ld last=%ld\n",
00616                      (long) ids[0],
00617                      (long) BDB_IDL_FIRST(ids),
00618                      (long) BDB_IDL_LAST(ids) );
00619 
00620        } else {
00621               Debug( LDAP_DEBUG_FILTER,
00622                      "<= bdb_list_candidates: undefined rc=%d\n",
00623                      rc, 0, 0 );
00624        }
00625 
00626        return rc;
00627 }
00628 
00629 static int
00630 presence_candidates(
00631        Operation *op,
00632        DB_TXN *rtxn,
00633        AttributeDescription *desc,
00634        ID *ids )
00635 {
00636        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
00637        DB *db;
00638        int rc;
00639        slap_mask_t mask;
00640        struct berval prefix = {0, NULL};
00641 
00642        Debug( LDAP_DEBUG_TRACE, "=> bdb_presence_candidates (%s)\n",
00643                      desc->ad_cname.bv_val, 0, 0 );
00644 
00645        BDB_IDL_ALL( bdb, ids );
00646 
00647        if( desc == slap_schema.si_ad_objectClass ) {
00648               return 0;
00649        }
00650 
00651        rc = bdb_index_param( op->o_bd, desc, LDAP_FILTER_PRESENT,
00652               &db, &mask, &prefix );
00653 
00654        if( rc == LDAP_INAPPROPRIATE_MATCHING ) {
00655               /* not indexed */
00656               Debug( LDAP_DEBUG_TRACE,
00657                      "<= bdb_presence_candidates: (%s) not indexed\n",
00658                      desc->ad_cname.bv_val, 0, 0 );
00659               return 0;
00660        }
00661 
00662        if( rc != LDAP_SUCCESS ) {
00663               Debug( LDAP_DEBUG_TRACE,
00664                      "<= bdb_presence_candidates: (%s) index_param "
00665                      "returned=%d\n",
00666                      desc->ad_cname.bv_val, rc, 0 );
00667               return 0;
00668        }
00669 
00670        if( prefix.bv_val == NULL ) {
00671               Debug( LDAP_DEBUG_TRACE,
00672                      "<= bdb_presence_candidates: (%s) no prefix\n",
00673                      desc->ad_cname.bv_val, 0, 0 );
00674               return -1;
00675        }
00676 
00677        rc = bdb_key_read( op->o_bd, db, rtxn, &prefix, ids, NULL, 0 );
00678 
00679        if( rc == DB_NOTFOUND ) {
00680               BDB_IDL_ZERO( ids );
00681               rc = 0;
00682        } else if( rc != LDAP_SUCCESS ) {
00683               Debug( LDAP_DEBUG_TRACE,
00684                      "<= bdb_presense_candidates: (%s) "
00685                      "key read failed (%d)\n",
00686                      desc->ad_cname.bv_val, rc, 0 );
00687               goto done;
00688        }
00689 
00690        Debug(LDAP_DEBUG_TRACE,
00691               "<= bdb_presence_candidates: id=%ld first=%ld last=%ld\n",
00692               (long) ids[0],
00693               (long) BDB_IDL_FIRST(ids),
00694               (long) BDB_IDL_LAST(ids) );
00695 
00696 done:
00697        return rc;
00698 }
00699 
00700 static int
00701 equality_candidates(
00702        Operation *op,
00703        DB_TXN *rtxn,
00704        AttributeAssertion *ava,
00705        ID *ids,
00706        ID *tmp )
00707 {
00708        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
00709        DB     *db;
00710        int i;
00711        int rc;
00712        slap_mask_t mask;
00713        struct berval prefix = {0, NULL};
00714        struct berval *keys = NULL;
00715        MatchingRule *mr;
00716 
00717        Debug( LDAP_DEBUG_TRACE, "=> bdb_equality_candidates (%s)\n",
00718                      ava->aa_desc->ad_cname.bv_val, 0, 0 );
00719 
00720        if ( ava->aa_desc == slap_schema.si_ad_entryDN ) {
00721               EntryInfo *ei = NULL;
00722               rc = bdb_cache_find_ndn( op, rtxn, &ava->aa_value, &ei );
00723               if ( rc == LDAP_SUCCESS ) {
00724                      /* exactly one ID can match */
00725                      ids[0] = 1;
00726                      ids[1] = ei->bei_id;
00727               }
00728               if ( ei ) {
00729                      bdb_cache_entryinfo_unlock( ei );
00730               }
00731               return rc;
00732        }
00733 
00734        BDB_IDL_ALL( bdb, ids );
00735 
00736        rc = bdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_EQUALITY,
00737               &db, &mask, &prefix );
00738 
00739        if ( rc == LDAP_INAPPROPRIATE_MATCHING ) {
00740               Debug( LDAP_DEBUG_ANY,
00741                      "<= bdb_equality_candidates: (%s) not indexed\n", 
00742                      ava->aa_desc->ad_cname.bv_val, 0, 0 );
00743               return 0;
00744        }
00745 
00746        if( rc != LDAP_SUCCESS ) {
00747               Debug( LDAP_DEBUG_ANY,
00748                      "<= bdb_equality_candidates: (%s) "
00749                      "index_param failed (%d)\n",
00750                      ava->aa_desc->ad_cname.bv_val, rc, 0 );
00751               return 0;
00752        }
00753 
00754        mr = ava->aa_desc->ad_type->sat_equality;
00755        if( !mr ) {
00756               return 0;
00757        }
00758 
00759        if( !mr->smr_filter ) {
00760               return 0;
00761        }
00762 
00763        rc = (mr->smr_filter)(
00764               LDAP_FILTER_EQUALITY,
00765               mask,
00766               ava->aa_desc->ad_type->sat_syntax,
00767               mr,
00768               &prefix,
00769               &ava->aa_value,
00770               &keys, op->o_tmpmemctx );
00771 
00772        if( rc != LDAP_SUCCESS ) {
00773               Debug( LDAP_DEBUG_TRACE,
00774                      "<= bdb_equality_candidates: (%s, %s) "
00775                      "MR filter failed (%d)\n",
00776                      prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
00777               return 0;
00778        }
00779 
00780        if( keys == NULL ) {
00781               Debug( LDAP_DEBUG_TRACE,
00782                      "<= bdb_equality_candidates: (%s) no keys\n",
00783                      ava->aa_desc->ad_cname.bv_val, 0, 0 );
00784               return 0;
00785        }
00786 
00787        for ( i= 0; keys[i].bv_val != NULL; i++ ) {
00788               rc = bdb_key_read( op->o_bd, db, rtxn, &keys[i], tmp, NULL, 0 );
00789 
00790               if( rc == DB_NOTFOUND ) {
00791                      BDB_IDL_ZERO( ids );
00792                      rc = 0;
00793                      break;
00794               } else if( rc != LDAP_SUCCESS ) {
00795                      Debug( LDAP_DEBUG_TRACE,
00796                             "<= bdb_equality_candidates: (%s) "
00797                             "key read failed (%d)\n",
00798                             ava->aa_desc->ad_cname.bv_val, rc, 0 );
00799                      break;
00800               }
00801 
00802               if( BDB_IDL_IS_ZERO( tmp ) ) {
00803                      Debug( LDAP_DEBUG_TRACE,
00804                             "<= bdb_equality_candidates: (%s) NULL\n", 
00805                             ava->aa_desc->ad_cname.bv_val, 0, 0 );
00806                      BDB_IDL_ZERO( ids );
00807                      break;
00808               }
00809 
00810               if ( i == 0 ) {
00811                      BDB_IDL_CPY( ids, tmp );
00812               } else {
00813                      bdb_idl_intersection( ids, tmp );
00814               }
00815 
00816               if( BDB_IDL_IS_ZERO( ids ) )
00817                      break;
00818        }
00819 
00820        ber_bvarray_free_x( keys, op->o_tmpmemctx );
00821 
00822        Debug( LDAP_DEBUG_TRACE,
00823               "<= bdb_equality_candidates: id=%ld, first=%ld, last=%ld\n",
00824               (long) ids[0],
00825               (long) BDB_IDL_FIRST(ids),
00826               (long) BDB_IDL_LAST(ids) );
00827        return( rc );
00828 }
00829 
00830 
00831 static int
00832 approx_candidates(
00833        Operation *op,
00834        DB_TXN *rtxn,
00835        AttributeAssertion *ava,
00836        ID *ids,
00837        ID *tmp )
00838 {
00839        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
00840        DB     *db;
00841        int i;
00842        int rc;
00843        slap_mask_t mask;
00844        struct berval prefix = {0, NULL};
00845        struct berval *keys = NULL;
00846        MatchingRule *mr;
00847 
00848        Debug( LDAP_DEBUG_TRACE, "=> bdb_approx_candidates (%s)\n",
00849                      ava->aa_desc->ad_cname.bv_val, 0, 0 );
00850 
00851        BDB_IDL_ALL( bdb, ids );
00852 
00853        rc = bdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_APPROX,
00854               &db, &mask, &prefix );
00855 
00856        if ( rc == LDAP_INAPPROPRIATE_MATCHING ) {
00857               Debug( LDAP_DEBUG_ANY,
00858                      "<= bdb_approx_candidates: (%s) not indexed\n",
00859                      ava->aa_desc->ad_cname.bv_val, 0, 0 );
00860               return 0;
00861        }
00862 
00863        if( rc != LDAP_SUCCESS ) {
00864               Debug( LDAP_DEBUG_ANY,
00865                      "<= bdb_approx_candidates: (%s) "
00866                      "index_param failed (%d)\n",
00867                      ava->aa_desc->ad_cname.bv_val, rc, 0 );
00868               return 0;
00869        }
00870 
00871        mr = ava->aa_desc->ad_type->sat_approx;
00872        if( !mr ) {
00873               /* no approx matching rule, try equality matching rule */
00874               mr = ava->aa_desc->ad_type->sat_equality;
00875        }
00876 
00877        if( !mr ) {
00878               return 0;
00879        }
00880 
00881        if( !mr->smr_filter ) {
00882               return 0;
00883        }
00884 
00885        rc = (mr->smr_filter)(
00886               LDAP_FILTER_APPROX,
00887               mask,
00888               ava->aa_desc->ad_type->sat_syntax,
00889               mr,
00890               &prefix,
00891               &ava->aa_value,
00892               &keys, op->o_tmpmemctx );
00893 
00894        if( rc != LDAP_SUCCESS ) {
00895               Debug( LDAP_DEBUG_TRACE,
00896                      "<= bdb_approx_candidates: (%s, %s) "
00897                      "MR filter failed (%d)\n",
00898                      prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
00899               return 0;
00900        }
00901 
00902        if( keys == NULL ) {
00903               Debug( LDAP_DEBUG_TRACE,
00904                      "<= bdb_approx_candidates: (%s) no keys (%s)\n",
00905                      prefix.bv_val, ava->aa_desc->ad_cname.bv_val, 0 );
00906               return 0;
00907        }
00908 
00909        for ( i= 0; keys[i].bv_val != NULL; i++ ) {
00910               rc = bdb_key_read( op->o_bd, db, rtxn, &keys[i], tmp, NULL, 0 );
00911 
00912               if( rc == DB_NOTFOUND ) {
00913                      BDB_IDL_ZERO( ids );
00914                      rc = 0;
00915                      break;
00916               } else if( rc != LDAP_SUCCESS ) {
00917                      Debug( LDAP_DEBUG_TRACE,
00918                             "<= bdb_approx_candidates: (%s) "
00919                             "key read failed (%d)\n",
00920                             ava->aa_desc->ad_cname.bv_val, rc, 0 );
00921                      break;
00922               }
00923 
00924               if( BDB_IDL_IS_ZERO( tmp ) ) {
00925                      Debug( LDAP_DEBUG_TRACE,
00926                             "<= bdb_approx_candidates: (%s) NULL\n",
00927                             ava->aa_desc->ad_cname.bv_val, 0, 0 );
00928                      BDB_IDL_ZERO( ids );
00929                      break;
00930               }
00931 
00932               if ( i == 0 ) {
00933                      BDB_IDL_CPY( ids, tmp );
00934               } else {
00935                      bdb_idl_intersection( ids, tmp );
00936               }
00937 
00938               if( BDB_IDL_IS_ZERO( ids ) )
00939                      break;
00940        }
00941 
00942        ber_bvarray_free_x( keys, op->o_tmpmemctx );
00943 
00944        Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates %ld, first=%ld, last=%ld\n",
00945               (long) ids[0],
00946               (long) BDB_IDL_FIRST(ids),
00947               (long) BDB_IDL_LAST(ids) );
00948        return( rc );
00949 }
00950 
00951 static int
00952 substring_candidates(
00953        Operation *op,
00954        DB_TXN *rtxn,
00955        SubstringsAssertion  *sub,
00956        ID *ids,
00957        ID *tmp )
00958 {
00959        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
00960        DB     *db;
00961        int i;
00962        int rc;
00963        slap_mask_t mask;
00964        struct berval prefix = {0, NULL};
00965        struct berval *keys = NULL;
00966        MatchingRule *mr;
00967 
00968        Debug( LDAP_DEBUG_TRACE, "=> bdb_substring_candidates (%s)\n",
00969                      sub->sa_desc->ad_cname.bv_val, 0, 0 );
00970 
00971        BDB_IDL_ALL( bdb, ids );
00972 
00973        rc = bdb_index_param( op->o_bd, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
00974               &db, &mask, &prefix );
00975 
00976        if ( rc == LDAP_INAPPROPRIATE_MATCHING ) {
00977               Debug( LDAP_DEBUG_ANY,
00978                      "<= bdb_substring_candidates: (%s) not indexed\n",
00979                      sub->sa_desc->ad_cname.bv_val, 0, 0 );
00980               return 0;
00981        }
00982 
00983        if( rc != LDAP_SUCCESS ) {
00984               Debug( LDAP_DEBUG_ANY,
00985                      "<= bdb_substring_candidates: (%s) "
00986                      "index_param failed (%d)\n",
00987                      sub->sa_desc->ad_cname.bv_val, rc, 0 );
00988               return 0;
00989        }
00990 
00991        mr = sub->sa_desc->ad_type->sat_substr;
00992 
00993        if( !mr ) {
00994               return 0;
00995        }
00996 
00997        if( !mr->smr_filter ) {
00998               return 0;
00999        }
01000 
01001        rc = (mr->smr_filter)(
01002               LDAP_FILTER_SUBSTRINGS,
01003               mask,
01004               sub->sa_desc->ad_type->sat_syntax,
01005               mr,
01006               &prefix,
01007               sub,
01008               &keys, op->o_tmpmemctx );
01009 
01010        if( rc != LDAP_SUCCESS ) {
01011               Debug( LDAP_DEBUG_TRACE,
01012                      "<= bdb_substring_candidates: (%s) "
01013                      "MR filter failed (%d)\n",
01014                      sub->sa_desc->ad_cname.bv_val, rc, 0 );
01015               return 0;
01016        }
01017 
01018        if( keys == NULL ) {
01019               Debug( LDAP_DEBUG_TRACE,
01020                      "<= bdb_substring_candidates: (0x%04lx) no keys (%s)\n",
01021                      mask, sub->sa_desc->ad_cname.bv_val, 0 );
01022               return 0;
01023        }
01024 
01025        for ( i= 0; keys[i].bv_val != NULL; i++ ) {
01026               rc = bdb_key_read( op->o_bd, db, rtxn, &keys[i], tmp, NULL, 0 );
01027 
01028               if( rc == DB_NOTFOUND ) {
01029                      BDB_IDL_ZERO( ids );
01030                      rc = 0;
01031                      break;
01032               } else if( rc != LDAP_SUCCESS ) {
01033                      Debug( LDAP_DEBUG_TRACE,
01034                             "<= bdb_substring_candidates: (%s) "
01035                             "key read failed (%d)\n",
01036                             sub->sa_desc->ad_cname.bv_val, rc, 0 );
01037                      break;
01038               }
01039 
01040               if( BDB_IDL_IS_ZERO( tmp ) ) {
01041                      Debug( LDAP_DEBUG_TRACE,
01042                             "<= bdb_substring_candidates: (%s) NULL\n",
01043                             sub->sa_desc->ad_cname.bv_val, 0, 0 );
01044                      BDB_IDL_ZERO( ids );
01045                      break;
01046               }
01047 
01048               if ( i == 0 ) {
01049                      BDB_IDL_CPY( ids, tmp );
01050               } else {
01051                      bdb_idl_intersection( ids, tmp );
01052               }
01053 
01054               if( BDB_IDL_IS_ZERO( ids ) )
01055                      break;
01056        }
01057 
01058        ber_bvarray_free_x( keys, op->o_tmpmemctx );
01059 
01060        Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates: %ld, first=%ld, last=%ld\n",
01061               (long) ids[0],
01062               (long) BDB_IDL_FIRST(ids),
01063               (long) BDB_IDL_LAST(ids) );
01064        return( rc );
01065 }
01066 
01067 static int
01068 inequality_candidates(
01069        Operation *op,
01070        DB_TXN *rtxn,
01071        AttributeAssertion *ava,
01072        ID *ids,
01073        ID *tmp,
01074        int gtorlt )
01075 {
01076        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
01077        DB     *db;
01078        int rc;
01079        slap_mask_t mask;
01080        struct berval prefix = {0, NULL};
01081        struct berval *keys = NULL;
01082        MatchingRule *mr;
01083        DBC * cursor = NULL;
01084 
01085        Debug( LDAP_DEBUG_TRACE, "=> bdb_inequality_candidates (%s)\n",
01086                      ava->aa_desc->ad_cname.bv_val, 0, 0 );
01087 
01088        BDB_IDL_ALL( bdb, ids );
01089 
01090        rc = bdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_EQUALITY,
01091               &db, &mask, &prefix );
01092 
01093        if ( rc == LDAP_INAPPROPRIATE_MATCHING ) {
01094               Debug( LDAP_DEBUG_ANY,
01095                      "<= bdb_inequality_candidates: (%s) not indexed\n", 
01096                      ava->aa_desc->ad_cname.bv_val, 0, 0 );
01097               return 0;
01098        }
01099 
01100        if( rc != LDAP_SUCCESS ) {
01101               Debug( LDAP_DEBUG_ANY,
01102                      "<= bdb_inequality_candidates: (%s) "
01103                      "index_param failed (%d)\n",
01104                      ava->aa_desc->ad_cname.bv_val, rc, 0 );
01105               return 0;
01106        }
01107 
01108        mr = ava->aa_desc->ad_type->sat_equality;
01109        if( !mr ) {
01110               return 0;
01111        }
01112 
01113        if( !mr->smr_filter ) {
01114               return 0;
01115        }
01116 
01117        rc = (mr->smr_filter)(
01118               LDAP_FILTER_EQUALITY,
01119               mask,
01120               ava->aa_desc->ad_type->sat_syntax,
01121               mr,
01122               &prefix,
01123               &ava->aa_value,
01124               &keys, op->o_tmpmemctx );
01125 
01126        if( rc != LDAP_SUCCESS ) {
01127               Debug( LDAP_DEBUG_TRACE,
01128                      "<= bdb_inequality_candidates: (%s, %s) "
01129                      "MR filter failed (%d)\n",
01130                      prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
01131               return 0;
01132        }
01133 
01134        if( keys == NULL ) {
01135               Debug( LDAP_DEBUG_TRACE,
01136                      "<= bdb_inequality_candidates: (%s) no keys\n",
01137                      ava->aa_desc->ad_cname.bv_val, 0, 0 );
01138               return 0;
01139        }
01140 
01141        BDB_IDL_ZERO( ids );
01142        while(1) {
01143               rc = bdb_key_read( op->o_bd, db, rtxn, &keys[0], tmp, &cursor, gtorlt );
01144 
01145               if( rc == DB_NOTFOUND ) {
01146                      rc = 0;
01147                      break;
01148               } else if( rc != LDAP_SUCCESS ) {
01149                      Debug( LDAP_DEBUG_TRACE,
01150                             "<= bdb_inequality_candidates: (%s) "
01151                             "key read failed (%d)\n",
01152                             ava->aa_desc->ad_cname.bv_val, rc, 0 );
01153                      break;
01154               }
01155 
01156               if( BDB_IDL_IS_ZERO( tmp ) ) {
01157                      Debug( LDAP_DEBUG_TRACE,
01158                             "<= bdb_inequality_candidates: (%s) NULL\n", 
01159                             ava->aa_desc->ad_cname.bv_val, 0, 0 );
01160                      break;
01161               }
01162 
01163               bdb_idl_union( ids, tmp );
01164 
01165               if( op->ors_limit && op->ors_limit->lms_s_unchecked != -1 &&
01166                      BDB_IDL_N( ids ) >= (unsigned) op->ors_limit->lms_s_unchecked ) {
01167                      cursor->c_close( cursor );
01168                      break;
01169               }
01170        }
01171        ber_bvarray_free_x( keys, op->o_tmpmemctx );
01172 
01173        Debug( LDAP_DEBUG_TRACE,
01174               "<= bdb_inequality_candidates: id=%ld, first=%ld, last=%ld\n",
01175               (long) ids[0],
01176               (long) BDB_IDL_FIRST(ids),
01177               (long) BDB_IDL_LAST(ids) );
01178        return( rc );
01179 }