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