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