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