git.sur5r.net Git - openldap/blob - servers/slapd/back-bdb/filterindex.c

   1 /* filterindex.c - generate the list of candidate entries from a filter */
   2 /* $OpenLDAP$ */
   3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
   4  *
   5  * Copyright 2000-2007 The OpenLDAP Foundation.
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted only as authorized by the OpenLDAP
  10  * Public License.
  11  *
  12  * A copy of this license is available in the file LICENSE in the
  13  * top-level directory of the distribution or, alternatively, at
  14  * <http://www.OpenLDAP.org/license.html>.
  15  */
  16
  17 #include "portable.h"
  18
  19 #include <stdio.h>
  20 #include <ac/string.h>
  21
  22 #include "back-bdb.h"
  23 #include "idl.h"
  24 #ifdef LDAP_COMP_MATCH
  25 #include <component.h>
  26 #endif
  27
  28 static int presence_candidates(
  29         Operation *op,
  30         AttributeDescription *desc,
  31         ID *ids );
  32
  33 static int equality_candidates(
  34         Operation *op,
  35         AttributeAssertion *ava,
  36         ID *ids,
  37         ID *tmp );
  38 static int inequality_candidates(
  39         Operation *op,
  40         AttributeAssertion *ava,
  41         ID *ids,
  42         ID *tmp,
  43         int gtorlt );
  44 static int approx_candidates(
  45         Operation *op,
  46         AttributeAssertion *ava,
  47         ID *ids,
  48         ID *tmp );
  49 static int substring_candidates(
  50         Operation *op,
  51         SubstringsAssertion *sub,
  52         ID *ids,
  53         ID *tmp );
  54
  55 static int list_candidates(
  56         Operation *op,
  57         Filter *flist,
  58         int ftype,
  59         ID *ids,
  60         ID *tmp,
  61         ID *stack );
  62
  63 #ifdef LDAP_COMP_MATCH
  64 static int
  65 ext_candidates(
  66         Operation *op,
  67         MatchingRuleAssertion *mra,
  68         ID *ids,
  69         ID *tmp,
  70         ID *stack);
  71
  72 static int
  73 comp_candidates (
  74         Operation *op,
  75         MatchingRuleAssertion *mra,
  76         ComponentFilter *f,
  77         ID *ids,
  78         ID *tmp,
  79         ID *stack);
  80
  81 static int
  82 ava_comp_candidates (
  83                 Operation *op,
  84                 AttributeAssertion *ava,
  85                 AttributeAliasing *aa,
  86                 ID *ids,
  87                 ID *tmp,
  88                 ID *stack);
  89 #endif
  90
  91 int
  92 bdb_filter_candidates(
  93         Operation *op,
  94         Filter  *f,
  95         ID *ids,
  96         ID *tmp,
  97         ID *stack )
  98 {
  99         int rc = 0;
 100 #ifdef LDAP_COMP_MATCH
 101         AttributeAliasing *aa;
 102 #endif
 103         Debug( LDAP_DEBUG_FILTER, "=> bdb_filter_candidates\n", 0, 0, 0 );
 104
 105         if ( f->f_choice & SLAPD_FILTER_UNDEFINED ) {
 106                 BDB_IDL_ZERO( ids );
 107                 goto out;
 108         }
 109
 110         switch ( f->f_choice ) {
 111         case SLAPD_FILTER_COMPUTED:
 112                 switch( f->f_result ) {
 113                 case SLAPD_COMPARE_UNDEFINED:
 114                 /* This technically is not the same as FALSE, but it
 115                  * certainly will produce no matches.
 116                  */
 117                 /* FALL THRU */
 118                 case LDAP_COMPARE_FALSE:
 119                         BDB_IDL_ZERO( ids );
 120                         break;
 121                 case LDAP_COMPARE_TRUE: {
 122                         struct bdb_info *bdb = (struct bdb_info *)op->o_bd->be_private;
 123                         BDB_IDL_ALL( bdb, ids );
 124                         } break;
 125                 case LDAP_SUCCESS:
 126                         /* this is a pre-computed scope, leave it alone */
 127                         break;
 128                 }
 129                 break;
 130         case LDAP_FILTER_PRESENT:
 131                 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
 132                 rc = presence_candidates( op, f->f_desc, ids );
 133                 break;
 134
 135         case LDAP_FILTER_EQUALITY:
 136                 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
 137 #ifdef LDAP_COMP_MATCH
 138                 if ( is_aliased_attribute && ( aa = is_aliased_attribute ( f->f_ava->aa_desc ) ) ) {
 139                         rc = ava_comp_candidates ( op, f->f_ava, aa, ids, tmp, stack );
 140                 }
 141                 else
 142 #endif
 143                 {
 144                         rc = equality_candidates( op, f->f_ava, ids, tmp );
 145                 }
 146                 break;
 147
 148         case LDAP_FILTER_APPROX:
 149                 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
 150                 rc = approx_candidates( op, f->f_ava, ids, tmp );
 151                 break;
 152
 153         case LDAP_FILTER_SUBSTRINGS:
 154                 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
 155                 rc = substring_candidates( op, f->f_sub, ids, tmp );
 156                 break;
 157
 158         case LDAP_FILTER_GE:
 159                 /* if no GE index, use pres */
 160                 Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
 161                 if( f->f_ava->aa_desc->ad_type->sat_ordering &&
 162                         ( f->f_ava->aa_desc->ad_type->sat_ordering->smr_usage & SLAP_MR_ORDERED_INDEX ) )
 163                         rc = inequality_candidates( op, f->f_ava, ids, tmp, LDAP_FILTER_GE );
 164                 else
 165                         rc = presence_candidates( op, f->f_ava->aa_desc, ids );
 166                 break;
 167
 168         case LDAP_FILTER_LE:
 169                 /* if no LE index, use pres */
 170                 Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
 171                 if( f->f_ava->aa_desc->ad_type->sat_ordering &&
 172                         ( f->f_ava->aa_desc->ad_type->sat_ordering->smr_usage & SLAP_MR_ORDERED_INDEX ) )
 173                         rc = inequality_candidates( op, f->f_ava, ids, tmp, LDAP_FILTER_LE );
 174                 else
 175                         rc = presence_candidates( op, f->f_ava->aa_desc, ids );
 176                 break;
 177
 178         case LDAP_FILTER_NOT:
 179                 /* no indexing to support NOT filters */
 180                 Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
 181                 { struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 182                 BDB_IDL_ALL( bdb, ids );
 183                 }
 184                 break;
 185
 186         case LDAP_FILTER_AND:
 187                 Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
 188                 rc = list_candidates( op,
 189                         f->f_and, LDAP_FILTER_AND, ids, tmp, stack );
 190                 break;
 191
 192         case LDAP_FILTER_OR:
 193                 Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
 194                 rc = list_candidates( op,
 195                         f->f_or, LDAP_FILTER_OR, ids, tmp, stack );
 196                 break;
 197 #ifdef LDAP_COMP_MATCH
 198         case LDAP_FILTER_EXT:
 199                 Debug( LDAP_DEBUG_FILTER, "\tEXT\n", 0, 0, 0 );
 200                 rc = ext_candidates( op, f->f_mra, ids, tmp, stack );
 201                 break;
 202 #endif
 203         default:
 204                 Debug( LDAP_DEBUG_FILTER, "\tUNKNOWN %lu\n",
 205                         (unsigned long) f->f_choice, 0, 0 );
 206                 /* Must not return NULL, otherwise extended filters break */
 207                 { struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 208                 BDB_IDL_ALL( bdb, ids );
 209                 }
 210         }
 211
 212 out:
 213         Debug( LDAP_DEBUG_FILTER,
 214                 "<= bdb_filter_candidates: id=%ld first=%ld last=%ld\n",
 215                 (long) ids[0],
 216                 (long) BDB_IDL_FIRST( ids ),
 217                 (long) BDB_IDL_LAST( ids ) );
 218
 219         return rc;
 220 }
 221
 222 #ifdef LDAP_COMP_MATCH
 223 static int
 224 comp_list_candidates(
 225         Operation *op,
 226         MatchingRuleAssertion* mra,
 227         ComponentFilter *flist,
 228         int     ftype,
 229         ID *ids,
 230         ID *tmp,
 231         ID *save )
 232 {
 233         int rc = 0;
 234         ComponentFilter *f;
 235
 236         Debug( LDAP_DEBUG_FILTER, "=> comp_list_candidates 0x%x\n", ftype, 0, 0 );
 237         for ( f = flist; f != NULL; f = f->cf_next ) {
 238                 /* ignore precomputed scopes */
 239                 if ( f->cf_choice == SLAPD_FILTER_COMPUTED &&
 240                      f->cf_result == LDAP_SUCCESS ) {
 241                         continue;
 242                 }
 243                 BDB_IDL_ZERO( save );
 244                 rc = comp_candidates( op, mra, f, save, tmp, save+BDB_IDL_UM_SIZE );
 245
 246                 if ( rc != 0 ) {
 247                         if ( ftype == LDAP_COMP_FILTER_AND ) {
 248                                 rc = 0;
 249                                 continue;
 250                         }
 251                         break;
 252                 }
 253
 254                 if ( ftype == LDAP_COMP_FILTER_AND ) {
 255                         if ( f == flist ) {
 256                                 BDB_IDL_CPY( ids, save );
 257                         } else {
 258                                 bdb_idl_intersection( ids, save );
 259                         }
 260                         if( BDB_IDL_IS_ZERO( ids ) )
 261                                 break;
 262                 } else {
 263                         if ( f == flist ) {
 264                                 BDB_IDL_CPY( ids, save );
 265                         } else {
 266                                 bdb_idl_union( ids, save );
 267                         }
 268                 }
 269         }
 270
 271         if( rc == LDAP_SUCCESS ) {
 272                 Debug( LDAP_DEBUG_FILTER,
 273                         "<= comp_list_candidates: id=%ld first=%ld last=%ld\n",
 274                         (long) ids[0],
 275                         (long) BDB_IDL_FIRST(ids),
 276                         (long) BDB_IDL_LAST(ids) );
 277
 278         } else {
 279                 Debug( LDAP_DEBUG_FILTER,
 280                         "<= comp_list_candidates: undefined rc=%d\n",
 281                         rc, 0, 0 );
 282         }
 283
 284         return rc;
 285 }
 286
 287 static int
 288 comp_equality_candidates (
 289         Operation *op,
 290         MatchingRuleAssertion *mra,
 291         ComponentAssertion *ca,
 292         ID *ids,
 293         ID *tmp,
 294         ID *stack)
 295 {
 296        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 297         DB      *db;
 298         int i;
 299         int rc;
 300         slap_mask_t mask;
 301         struct berval prefix = {0, NULL};
 302         struct berval *keys = NULL;
 303         MatchingRule *mr = mra->ma_rule;
 304         Syntax *sat_syntax;
 305         ComponentReference* cr_list, *cr;
 306         AttrInfo *ai;
 307
 308         BDB_IDL_ALL( bdb, ids );
 309
 310         if ( !ca->ca_comp_ref )
 311                 return 0;
 312
 313         ai = bdb_attr_mask( op->o_bd->be_private, mra->ma_desc );
 314         if( ai ) {
 315                 cr_list = ai->ai_cr;
 316         }
 317         else {
 318                 return 0;
 319         }
 320         /* find a component reference to be indexed */
 321         sat_syntax = ca->ca_ma_rule->smr_syntax;
 322         for ( cr = cr_list ; cr ; cr = cr->cr_next ) {
 323                 if ( cr->cr_string.bv_len == ca->ca_comp_ref->cr_string.bv_len &&
 324                         strncmp( cr->cr_string.bv_val, ca->ca_comp_ref->cr_string.bv_val,cr->cr_string.bv_len ) == 0 )
 325                         break;
 326         }
 327
 328         if ( !cr )
 329                 return 0;
 330
 331         rc = bdb_index_param( op->o_bd, mra->ma_desc, LDAP_FILTER_EQUALITY,
 332                 &db, &mask, &prefix );
 333
 334         if( rc != LDAP_SUCCESS ) {
 335                 return 0;
 336         }
 337         if ( db == NULL ) {
 338                 return 0;
 339         }
 340
 341         if( !mr ) {
 342                 return 0;
 343         }
 344
 345         if( !mr->smr_filter ) {
 346                 return 0;
 347         }
 348
 349         rc = (ca->ca_ma_rule->smr_filter)(
 350                 LDAP_FILTER_EQUALITY,
 351                 cr->cr_indexmask,
 352                 sat_syntax,
 353                 ca->ca_ma_rule,
 354                 &prefix,
 355                 &ca->ca_ma_value,
 356                 &keys, op->o_tmpmemctx );
 357
 358         if( rc != LDAP_SUCCESS ) {
 359                 return 0;
 360         }
 361
 362         if( keys == NULL ) {
 363                 return 0;
 364         }
 365         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 366                 rc = bdb_key_read( op->o_bd, db, NULL, &keys[i], tmp, NULL, 0 );
 367
 368                 if( rc == DB_NOTFOUND ) {
 369                         BDB_IDL_ZERO( ids );
 370                         rc = 0;
 371                         break;
 372                 } else if( rc != LDAP_SUCCESS ) {
 373                         break;
 374                 }
 375
 376                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 377                         BDB_IDL_ZERO( ids );
 378                         break;
 379                 }
 380
 381                 if ( i == 0 ) {
 382                         BDB_IDL_CPY( ids, tmp );
 383                 } else {
 384                         bdb_idl_intersection( ids, tmp );
 385                 }
 386
 387                 if( BDB_IDL_IS_ZERO( ids ) )
 388                         break;
 389         }
 390         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 391
 392         Debug( LDAP_DEBUG_TRACE,
 393                 "<= comp_equality_candidates: id=%ld, first=%ld, last=%ld\n",
 394                 (long) ids[0],
 395                 (long) BDB_IDL_FIRST(ids),
 396                 (long) BDB_IDL_LAST(ids) );
 397         return( rc );
 398 }
 399
 400 static int
 401 ava_comp_candidates (
 402         Operation *op,
 403         AttributeAssertion *ava,
 404         AttributeAliasing *aa,
 405         ID *ids,
 406         ID *tmp,
 407         ID *stack )
 408 {
 409         MatchingRuleAssertion mra;
 410
 411         mra.ma_rule = ava->aa_desc->ad_type->sat_equality;
 412         if ( !mra.ma_rule ) {
 413                 struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 414                 BDB_IDL_ALL( bdb, ids );
 415                 return 0;
 416         }
 417         mra.ma_desc = aa->aa_aliased_ad;
 418         mra.ma_rule = ava->aa_desc->ad_type->sat_equality;
 419
 420         return comp_candidates ( op, &mra, ava->aa_cf, ids, tmp, stack );
 421 }
 422
 423 static int
 424 comp_candidates (
 425         Operation *op,
 426         MatchingRuleAssertion *mra,
 427         ComponentFilter *f,
 428         ID *ids,
 429         ID *tmp,
 430         ID *stack)
 431 {
 432         int     rc;
 433
 434         if ( !f ) return LDAP_PROTOCOL_ERROR;
 435
 436         Debug( LDAP_DEBUG_FILTER, "comp_candidates\n", 0, 0, 0 );
 437         switch ( f->cf_choice ) {
 438         case SLAPD_FILTER_COMPUTED:
 439                 rc = f->cf_result;
 440                 break;
 441         case LDAP_COMP_FILTER_AND:
 442                 rc = comp_list_candidates( op, mra, f->cf_and, LDAP_COMP_FILTER_AND, ids, tmp, stack );
 443                 break;
 444         case LDAP_COMP_FILTER_OR:
 445                 rc = comp_list_candidates( op, mra, f->cf_or, LDAP_COMP_FILTER_OR, ids, tmp, stack );
 446                 break;
 447         case LDAP_COMP_FILTER_NOT:
 448                 /* No component indexing supported for NOT filter */
 449                 Debug( LDAP_DEBUG_FILTER, "\tComponent NOT\n", 0, 0, 0 );
 450                 {
 451                         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 452                         BDB_IDL_ALL( bdb, ids );
 453                 }
 454                 rc = LDAP_PROTOCOL_ERROR;
 455                 break;
 456         case LDAP_COMP_FILTER_ITEM:
 457                 rc = comp_equality_candidates( op, mra, f->cf_ca, ids, tmp, stack );
 458                 break;
 459         default:
 460                 {
 461                         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 462                         BDB_IDL_ALL( bdb, ids );
 463                 }
 464                 rc = LDAP_PROTOCOL_ERROR;
 465         }
 466
 467         return( rc );
 468 }
 469
 470 static int
 471 ext_candidates(
 472         Operation *op,
 473         MatchingRuleAssertion *mra,
 474         ID *ids,
 475         ID *tmp,
 476         ID *stack)
 477 {
 478         /*
 479          * Currently Only Component Indexing for componentFilterMatch is supported
 480          * Indexing for an extensible filter is not supported yet
 481          */
 482         if ( !mra->ma_cf ) {
 483                 struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 484                 BDB_IDL_ALL( bdb, ids );
 485                 return 0;
 486         }
 487
 488         return comp_candidates ( op, mra, mra->ma_cf, ids, tmp, stack);
 489 }
 490 #endif
 491
 492 static int
 493 list_candidates(
 494         Operation *op,
 495         Filter  *flist,
 496         int             ftype,
 497         ID *ids,
 498         ID *tmp,
 499         ID *save )
 500 {
 501         int rc = 0;
 502         Filter  *f;
 503
 504         Debug( LDAP_DEBUG_FILTER, "=> bdb_list_candidates 0x%x\n", ftype, 0, 0 );
 505         for ( f = flist; f != NULL; f = f->f_next ) {
 506                 /* ignore precomputed scopes */
 507                 if ( f->f_choice == SLAPD_FILTER_COMPUTED &&
 508                      f->f_result == LDAP_SUCCESS ) {
 509                         continue;
 510                 }
 511                 BDB_IDL_ZERO( save );
 512                 rc = bdb_filter_candidates( op, f, save, tmp,
 513                         save+BDB_IDL_UM_SIZE );
 514
 515                 if ( rc != 0 ) {
 516                         if ( ftype == LDAP_FILTER_AND ) {
 517                                 rc = 0;
 518                                 continue;
 519                         }
 520                         break;
 521                 }
 522
 523
 524                 if ( ftype == LDAP_FILTER_AND ) {
 525                         if ( f == flist ) {
 526                                 BDB_IDL_CPY( ids, save );
 527                         } else {
 528                                 bdb_idl_intersection( ids, save );
 529                         }
 530                         if( BDB_IDL_IS_ZERO( ids ) )
 531                                 break;
 532                 } else {
 533                         if ( f == flist ) {
 534                                 BDB_IDL_CPY( ids, save );
 535                         } else {
 536                                 bdb_idl_union( ids, save );
 537                         }
 538                 }
 539         }
 540
 541         if( rc == LDAP_SUCCESS ) {
 542                 Debug( LDAP_DEBUG_FILTER,
 543                         "<= bdb_list_candidates: id=%ld first=%ld last=%ld\n",
 544                         (long) ids[0],
 545                         (long) BDB_IDL_FIRST(ids),
 546                         (long) BDB_IDL_LAST(ids) );
 547
 548         } else {
 549                 Debug( LDAP_DEBUG_FILTER,
 550                         "<= bdb_list_candidates: undefined rc=%d\n",
 551                         rc, 0, 0 );
 552         }
 553
 554         return rc;
 555 }
 556
 557 static int
 558 presence_candidates(
 559         Operation *op,
 560         AttributeDescription *desc,
 561         ID *ids )
 562 {
 563         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 564         DB *db;
 565         int rc;
 566         slap_mask_t mask;
 567         struct berval prefix = {0, NULL};
 568
 569         Debug( LDAP_DEBUG_TRACE, "=> bdb_presence_candidates (%s)\n",
 570                         desc->ad_cname.bv_val, 0, 0 );
 571
 572         BDB_IDL_ALL( bdb, ids );
 573
 574         if( desc == slap_schema.si_ad_objectClass ) {
 575                 return 0;
 576         }
 577
 578         rc = bdb_index_param( op->o_bd, desc, LDAP_FILTER_PRESENT,
 579                 &db, &mask, &prefix );
 580
 581         if( rc != LDAP_SUCCESS ) {
 582                 Debug( LDAP_DEBUG_TRACE,
 583                         "<= bdb_presence_candidates: (%s) index_param "
 584                         "returned=%d\n",
 585                         desc->ad_cname.bv_val, rc, 0 );
 586                 return 0;
 587         }
 588
 589         if( db == NULL ) {
 590                 /* not indexed */
 591                 Debug( LDAP_DEBUG_TRACE,
 592                         "<= bdb_presence_candidates: (%s) not indexed\n",
 593                         desc->ad_cname.bv_val, 0, 0 );
 594                 return 0;
 595         }
 596
 597         if( prefix.bv_val == NULL ) {
 598                 Debug( LDAP_DEBUG_TRACE,
 599                         "<= bdb_presence_candidates: (%s) no prefix\n",
 600                         desc->ad_cname.bv_val, 0, 0 );
 601                 return -1;
 602         }
 603
 604         rc = bdb_key_read( op->o_bd, db, NULL, &prefix, ids, NULL, 0 );
 605
 606         if( rc == DB_NOTFOUND ) {
 607                 BDB_IDL_ZERO( ids );
 608                 rc = 0;
 609         } else if( rc != LDAP_SUCCESS ) {
 610                 Debug( LDAP_DEBUG_TRACE,
 611                         "<= bdb_presense_candidates: (%s) "
 612                         "key read failed (%d)\n",
 613                         desc->ad_cname.bv_val, rc, 0 );
 614                 goto done;
 615         }
 616
 617         Debug(LDAP_DEBUG_TRACE,
 618                 "<= bdb_presence_candidates: id=%ld first=%ld last=%ld\n",
 619                 (long) ids[0],
 620                 (long) BDB_IDL_FIRST(ids),
 621                 (long) BDB_IDL_LAST(ids) );
 622
 623 done:
 624         return rc;
 625 }
 626
 627 static int
 628 equality_candidates(
 629         Operation *op,
 630         AttributeAssertion *ava,
 631         ID *ids,
 632         ID *tmp )
 633 {
 634         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 635         DB      *db;
 636         int i;
 637         int rc;
 638         slap_mask_t mask;
 639         struct berval prefix = {0, NULL};
 640         struct berval *keys = NULL;
 641         MatchingRule *mr;
 642
 643         Debug( LDAP_DEBUG_TRACE, "=> bdb_equality_candidates (%s)\n",
 644                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 645
 646         BDB_IDL_ALL( bdb, ids );
 647
 648         rc = bdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_EQUALITY,
 649                 &db, &mask, &prefix );
 650
 651         if( rc != LDAP_SUCCESS ) {
 652                 Debug( LDAP_DEBUG_ANY,
 653                         "<= bdb_equality_candidates: (%s) "
 654                         "index_param failed (%d)\n",
 655                         ava->aa_desc->ad_cname.bv_val, rc, 0 );
 656                 return 0;
 657         }
 658
 659         if ( db == NULL ) {
 660                 Debug( LDAP_DEBUG_ANY,
 661                         "<= bdb_equality_candidates: (%s) not indexed\n",
 662                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 663                 return 0;
 664         }
 665
 666         mr = ava->aa_desc->ad_type->sat_equality;
 667         if( !mr ) {
 668                 return 0;
 669         }
 670
 671         if( !mr->smr_filter ) {
 672                 return 0;
 673         }
 674
 675         rc = (mr->smr_filter)(
 676                 LDAP_FILTER_EQUALITY,
 677                 mask,
 678                 ava->aa_desc->ad_type->sat_syntax,
 679                 mr,
 680                 &prefix,
 681                 &ava->aa_value,
 682                 &keys, op->o_tmpmemctx );
 683
 684         if( rc != LDAP_SUCCESS ) {
 685                 Debug( LDAP_DEBUG_TRACE,
 686                         "<= bdb_equality_candidates: (%s, %s) "
 687                         "MR filter failed (%d)\n",
 688                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
 689                 return 0;
 690         }
 691
 692         if( keys == NULL ) {
 693                 Debug( LDAP_DEBUG_TRACE,
 694                         "<= bdb_equality_candidates: (%s) no keys\n",
 695                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 696                 return 0;
 697         }
 698
 699         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 700                 rc = bdb_key_read( op->o_bd, db, NULL, &keys[i], tmp, NULL, 0 );
 701
 702                 if( rc == DB_NOTFOUND ) {
 703                         BDB_IDL_ZERO( ids );
 704                         rc = 0;
 705                         break;
 706                 } else if( rc != LDAP_SUCCESS ) {
 707                         Debug( LDAP_DEBUG_TRACE,
 708                                 "<= bdb_equality_candidates: (%s) "
 709                                 "key read failed (%d)\n",
 710                                 ava->aa_desc->ad_cname.bv_val, rc, 0 );
 711                         break;
 712                 }
 713
 714                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 715                         Debug( LDAP_DEBUG_TRACE,
 716                                 "<= bdb_equality_candidates: (%s) NULL\n",
 717                                 ava->aa_desc->ad_cname.bv_val, 0, 0 );
 718                         BDB_IDL_ZERO( ids );
 719                         break;
 720                 }
 721
 722                 if ( i == 0 ) {
 723                         BDB_IDL_CPY( ids, tmp );
 724                 } else {
 725                         bdb_idl_intersection( ids, tmp );
 726                 }
 727
 728                 if( BDB_IDL_IS_ZERO( ids ) )
 729                         break;
 730         }
 731
 732         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 733
 734         Debug( LDAP_DEBUG_TRACE,
 735                 "<= bdb_equality_candidates: id=%ld, first=%ld, last=%ld\n",
 736                 (long) ids[0],
 737                 (long) BDB_IDL_FIRST(ids),
 738                 (long) BDB_IDL_LAST(ids) );
 739         return( rc );
 740 }
 741
 742
 743 static int
 744 approx_candidates(
 745         Operation *op,
 746         AttributeAssertion *ava,
 747         ID *ids,
 748         ID *tmp )
 749 {
 750         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 751         DB      *db;
 752         int i;
 753         int rc;
 754         slap_mask_t mask;
 755         struct berval prefix = {0, NULL};
 756         struct berval *keys = NULL;
 757         MatchingRule *mr;
 758
 759         Debug( LDAP_DEBUG_TRACE, "=> bdb_approx_candidates (%s)\n",
 760                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 761
 762         BDB_IDL_ALL( bdb, ids );
 763
 764         rc = bdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_APPROX,
 765                 &db, &mask, &prefix );
 766
 767         if( rc != LDAP_SUCCESS ) {
 768                 Debug( LDAP_DEBUG_ANY,
 769                         "<= bdb_approx_candidates: (%s) "
 770                         "index_param failed (%d)\n",
 771                         ava->aa_desc->ad_cname.bv_val, rc, 0 );
 772                 return 0;
 773         }
 774
 775         if ( db == NULL ) {
 776                 Debug( LDAP_DEBUG_ANY,
 777                         "<= bdb_approx_candidates: (%s) not indexed\n",
 778                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 779                 return 0;
 780         }
 781
 782         mr = ava->aa_desc->ad_type->sat_approx;
 783         if( !mr ) {
 784                 /* no approx matching rule, try equality matching rule */
 785                 mr = ava->aa_desc->ad_type->sat_equality;
 786         }
 787
 788         if( !mr ) {
 789                 return 0;
 790         }
 791
 792         if( !mr->smr_filter ) {
 793                 return 0;
 794         }
 795
 796         rc = (mr->smr_filter)(
 797                 LDAP_FILTER_APPROX,
 798                 mask,
 799                 ava->aa_desc->ad_type->sat_syntax,
 800                 mr,
 801                 &prefix,
 802                 &ava->aa_value,
 803                 &keys, op->o_tmpmemctx );
 804
 805         if( rc != LDAP_SUCCESS ) {
 806                 Debug( LDAP_DEBUG_TRACE,
 807                         "<= bdb_approx_candidates: (%s, %s) "
 808                         "MR filter failed (%d)\n",
 809                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
 810                 return 0;
 811         }
 812
 813         if( keys == NULL ) {
 814                 Debug( LDAP_DEBUG_TRACE,
 815                         "<= bdb_approx_candidates: (%s) no keys (%s)\n",
 816                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, 0 );
 817                 return 0;
 818         }
 819
 820         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 821                 rc = bdb_key_read( op->o_bd, db, NULL, &keys[i], tmp, NULL, 0 );
 822
 823                 if( rc == DB_NOTFOUND ) {
 824                         BDB_IDL_ZERO( ids );
 825                         rc = 0;
 826                         break;
 827                 } else if( rc != LDAP_SUCCESS ) {
 828                         Debug( LDAP_DEBUG_TRACE,
 829                                 "<= bdb_approx_candidates: (%s) "
 830                                 "key read failed (%d)\n",
 831                                 ava->aa_desc->ad_cname.bv_val, rc, 0 );
 832                         break;
 833                 }
 834
 835                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 836                         Debug( LDAP_DEBUG_TRACE,
 837                                 "<= bdb_approx_candidates: (%s) NULL\n",
 838                                 ava->aa_desc->ad_cname.bv_val, 0, 0 );
 839                         BDB_IDL_ZERO( ids );
 840                         break;
 841                 }
 842
 843                 if ( i == 0 ) {
 844                         BDB_IDL_CPY( ids, tmp );
 845                 } else {
 846                         bdb_idl_intersection( ids, tmp );
 847                 }
 848
 849                 if( BDB_IDL_IS_ZERO( ids ) )
 850                         break;
 851         }
 852
 853         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 854
 855         Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates %ld, first=%ld, last=%ld\n",
 856                 (long) ids[0],
 857                 (long) BDB_IDL_FIRST(ids),
 858                 (long) BDB_IDL_LAST(ids) );
 859         return( rc );
 860 }
 861
 862 static int
 863 substring_candidates(
 864         Operation *op,
 865         SubstringsAssertion     *sub,
 866         ID *ids,
 867         ID *tmp )
 868 {
 869         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 870         DB      *db;
 871         int i;
 872         int rc;
 873         slap_mask_t mask;
 874         struct berval prefix = {0, NULL};
 875         struct berval *keys = NULL;
 876         MatchingRule *mr;
 877
 878         Debug( LDAP_DEBUG_TRACE, "=> bdb_substring_candidates (%s)\n",
 879                         sub->sa_desc->ad_cname.bv_val, 0, 0 );
 880
 881         BDB_IDL_ALL( bdb, ids );
 882
 883         rc = bdb_index_param( op->o_bd, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
 884                 &db, &mask, &prefix );
 885
 886         if( rc != LDAP_SUCCESS ) {
 887                 Debug( LDAP_DEBUG_ANY,
 888                         "<= bdb_substring_candidates: (%s) "
 889                         "index_param failed (%d)\n",
 890                         sub->sa_desc->ad_cname.bv_val, rc, 0 );
 891                 return 0;
 892         }
 893
 894         if ( db == NULL ) {
 895                 Debug( LDAP_DEBUG_ANY,
 896                         "<= bdb_substring_candidates: (%s) not indexed\n",
 897                         sub->sa_desc->ad_cname.bv_val, 0, 0 );
 898                 return 0;
 899         }
 900
 901         mr = sub->sa_desc->ad_type->sat_substr;
 902
 903         if( !mr ) {
 904                 return 0;
 905         }
 906
 907         if( !mr->smr_filter ) {
 908                 return 0;
 909         }
 910
 911         rc = (mr->smr_filter)(
 912                 LDAP_FILTER_SUBSTRINGS,
 913                 mask,
 914                 sub->sa_desc->ad_type->sat_syntax,
 915                 mr,
 916                 &prefix,
 917                 sub,
 918                 &keys, op->o_tmpmemctx );
 919
 920         if( rc != LDAP_SUCCESS ) {
 921                 Debug( LDAP_DEBUG_TRACE,
 922                         "<= bdb_substring_candidates: (%s) "
 923                         "MR filter failed (%d)\n",
 924                         sub->sa_desc->ad_cname.bv_val, rc, 0 );
 925                 return 0;
 926         }
 927
 928         if( keys == NULL ) {
 929                 Debug( LDAP_DEBUG_TRACE,
 930                         "<= bdb_substring_candidates: (0x%04lx) no keys (%s)\n",
 931                         mask, sub->sa_desc->ad_cname.bv_val, 0 );
 932                 return 0;
 933         }
 934
 935         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 936                 rc = bdb_key_read( op->o_bd, db, NULL, &keys[i], tmp, NULL, 0 );
 937
 938                 if( rc == DB_NOTFOUND ) {
 939                         BDB_IDL_ZERO( ids );
 940                         rc = 0;
 941                         break;
 942                 } else if( rc != LDAP_SUCCESS ) {
 943                         Debug( LDAP_DEBUG_TRACE,
 944                                 "<= bdb_substring_candidates: (%s) "
 945                                 "key read failed (%d)\n",
 946                                 sub->sa_desc->ad_cname.bv_val, rc, 0 );
 947                         break;
 948                 }
 949
 950                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 951                         Debug( LDAP_DEBUG_TRACE,
 952                                 "<= bdb_substring_candidates: (%s) NULL\n",
 953                                 sub->sa_desc->ad_cname.bv_val, 0, 0 );
 954                         BDB_IDL_ZERO( ids );
 955                         break;
 956                 }
 957
 958                 if ( i == 0 ) {
 959                         BDB_IDL_CPY( ids, tmp );
 960                 } else {
 961                         bdb_idl_intersection( ids, tmp );
 962                 }
 963
 964                 if( BDB_IDL_IS_ZERO( ids ) )
 965                         break;
 966         }
 967
 968         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 969
 970         Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates: %ld, first=%ld, last=%ld\n",
 971                 (long) ids[0],
 972                 (long) BDB_IDL_FIRST(ids),
 973                 (long) BDB_IDL_LAST(ids) );
 974         return( rc );
 975 }
 976
 977 static int
 978 inequality_candidates(
 979         Operation *op,
 980         AttributeAssertion *ava,
 981         ID *ids,
 982         ID *tmp,
 983         int gtorlt )
 984 {
 985         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 986         DB      *db;
 987         int rc;
 988         slap_mask_t mask;
 989         struct berval prefix = {0, NULL};
 990         struct berval *keys = NULL;
 991         MatchingRule *mr;
 992         DBC * cursor = NULL;
 993
 994         Debug( LDAP_DEBUG_TRACE, "=> bdb_inequality_candidates (%s)\n",
 995                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 996
 997         BDB_IDL_ALL( bdb, ids );
 998
 999         rc = bdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_EQUALITY,
1000                 &db, &mask, &prefix );
1001
1002         if( rc != LDAP_SUCCESS ) {
1003                 Debug( LDAP_DEBUG_ANY,
1004                         "<= bdb_inequality_candidates: (%s) "
1005                         "index_param failed (%d)\n",
1006                         ava->aa_desc->ad_cname.bv_val, rc, 0 );
1007                 return 0;
1008         }
1009
1010         if ( db == NULL ) {
1011                 Debug( LDAP_DEBUG_ANY,
1012                         "<= bdb_inequality_candidates: (%s) not indexed\n",
1013                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
1014                 return 0;
1015         }
1016
1017         mr = ava->aa_desc->ad_type->sat_equality;
1018         if( !mr ) {
1019                 return 0;
1020         }
1021
1022         if( !mr->smr_filter ) {
1023                 return 0;
1024         }
1025
1026         rc = (mr->smr_filter)(
1027                 LDAP_FILTER_EQUALITY,
1028                 mask,
1029                 ava->aa_desc->ad_type->sat_syntax,
1030                 mr,
1031                 &prefix,
1032                 &ava->aa_value,
1033                 &keys, op->o_tmpmemctx );
1034
1035         if( rc != LDAP_SUCCESS ) {
1036                 Debug( LDAP_DEBUG_TRACE,
1037                         "<= bdb_inequality_candidates: (%s, %s) "
1038                         "MR filter failed (%d)\n",
1039                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
1040                 return 0;
1041         }
1042
1043         if( keys == NULL ) {
1044                 Debug( LDAP_DEBUG_TRACE,
1045                         "<= bdb_inequality_candidates: (%s) no keys\n",
1046                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
1047                 return 0;
1048         }
1049
1050         BDB_IDL_ZERO( ids );
1051         while(1) {
1052                 rc = bdb_key_read( op->o_bd, db, NULL, &keys[0], tmp, &cursor, gtorlt );
1053
1054                 if( rc == DB_NOTFOUND ) {
1055                         rc = 0;
1056                         break;
1057                 } else if( rc != LDAP_SUCCESS ) {
1058                         Debug( LDAP_DEBUG_TRACE,
1059                                "<= bdb_inequality_candidates: (%s) "
1060                                "key read failed (%d)\n",
1061                                ava->aa_desc->ad_cname.bv_val, rc, 0 );
1062                         break;
1063                 }
1064
1065                 if( BDB_IDL_IS_ZERO( tmp ) ) {
1066                         Debug( LDAP_DEBUG_TRACE,
1067                                "<= bdb_inequality_candidates: (%s) NULL\n",
1068                                ava->aa_desc->ad_cname.bv_val, 0, 0 );
1069                         break;
1070                 }
1071
1072                 bdb_idl_union( ids, tmp );
1073
1074                 if( op->ors_limit && op->ors_limit->lms_s_unchecked != -1 &&
1075                         BDB_IDL_N( ids ) >= (unsigned) op->ors_limit->lms_s_unchecked ) {
1076                         cursor->c_close( cursor );
1077                         break;
1078                 }
1079         }
1080         ber_bvarray_free_x( keys, op->o_tmpmemctx );
1081
1082         Debug( LDAP_DEBUG_TRACE,
1083                 "<= bdb_inequality_candidates: id=%ld, first=%ld, last=%ld\n",
1084                 (long) ids[0],
1085                 (long) BDB_IDL_FIRST(ids),
1086                 (long) BDB_IDL_LAST(ids) );
1087         return( rc );
1088 }