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