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