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