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