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                 return 0;
 425         return comp_candidates ( op, mra, mra->ma_cf, ids, tmp, stack);
 426 }
 427 #endif
 428
 429 static int
 430 list_candidates(
 431         Operation *op,
 432         Filter  *flist,
 433         int             ftype,
 434         ID *ids,
 435         ID *tmp,
 436         ID *save )
 437 {
 438         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 439         int rc = 0;
 440         Filter  *f;
 441
 442         Debug( LDAP_DEBUG_FILTER, "=> bdb_list_candidates 0x%x\n", ftype, 0, 0 );
 443         for ( f = flist; f != NULL; f = f->f_next ) {
 444                 /* ignore precomputed scopes */
 445                 if ( f->f_choice == SLAPD_FILTER_COMPUTED &&
 446                      f->f_result == LDAP_SUCCESS ) {
 447                         continue;
 448                 }
 449                 BDB_IDL_ZERO( save );
 450                 rc = bdb_filter_candidates( op, f, save, tmp,
 451                         save+BDB_IDL_UM_SIZE );
 452
 453                 if ( rc != 0 ) {
 454                         if ( ftype == LDAP_FILTER_AND ) {
 455                                 rc = 0;
 456                                 continue;
 457                         }
 458                         break;
 459                 }
 460
 461
 462                 if ( ftype == LDAP_FILTER_AND ) {
 463                         if ( f == flist ) {
 464                                 BDB_IDL_CPY( ids, save );
 465                         } else {
 466                                 bdb_idl_intersection( ids, save );
 467                         }
 468                         if( BDB_IDL_IS_ZERO( ids ) )
 469                                 break;
 470                 } else {
 471                         if ( f == flist ) {
 472                                 BDB_IDL_CPY( ids, save );
 473                         } else {
 474                                 bdb_idl_union( ids, save );
 475                         }
 476                 }
 477         }
 478
 479         if( rc == LDAP_SUCCESS ) {
 480                 Debug( LDAP_DEBUG_FILTER,
 481                         "<= bdb_list_candidates: id=%ld first=%ld last=%ld\n",
 482                         (long) ids[0],
 483                         (long) BDB_IDL_FIRST(ids),
 484                         (long) BDB_IDL_LAST(ids) );
 485
 486         } else {
 487                 Debug( LDAP_DEBUG_FILTER,
 488                         "<= bdb_list_candidates: undefined rc=%d\n",
 489                         rc, 0, 0 );
 490         }
 491
 492         return rc;
 493 }
 494
 495 static int
 496 presence_candidates(
 497         Operation *op,
 498         AttributeDescription *desc,
 499         ID *ids )
 500 {
 501         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 502         DB *db;
 503         int rc;
 504         slap_mask_t mask;
 505         struct berval prefix = {0, NULL};
 506
 507         Debug( LDAP_DEBUG_TRACE, "=> bdb_presence_candidates (%s)\n",
 508                         desc->ad_cname.bv_val, 0, 0 );
 509
 510         BDB_IDL_ALL( bdb, ids );
 511
 512         if( desc == slap_schema.si_ad_objectClass ) {
 513                 return 0;
 514         }
 515
 516         rc = bdb_index_param( op->o_bd, desc, LDAP_FILTER_PRESENT,
 517                 &db, &mask, &prefix );
 518
 519         if( rc != LDAP_SUCCESS ) {
 520                 Debug( LDAP_DEBUG_TRACE,
 521                         "<= bdb_presence_candidates: (%s) index_param "
 522                         "returned=%d\n",
 523                         desc->ad_cname.bv_val, rc, 0 );
 524                 return 0;
 525         }
 526
 527         if( db == NULL ) {
 528                 /* not indexed */
 529                 Debug( LDAP_DEBUG_TRACE,
 530                         "<= bdb_presence_candidates: (%s) not indexed\n",
 531                         desc->ad_cname.bv_val, 0, 0 );
 532                 return 0;
 533         }
 534
 535         if( prefix.bv_val == NULL ) {
 536                 Debug( LDAP_DEBUG_TRACE,
 537                         "<= bdb_presence_candidates: (%s) no prefix\n",
 538                         desc->ad_cname.bv_val, 0, 0 );
 539                 return -1;
 540         }
 541
 542         rc = bdb_key_read( op->o_bd, db, NULL, &prefix, ids, NULL, 0 );
 543
 544         if( rc == DB_NOTFOUND ) {
 545                 BDB_IDL_ZERO( ids );
 546                 rc = 0;
 547         } else if( rc != LDAP_SUCCESS ) {
 548                 Debug( LDAP_DEBUG_TRACE,
 549                         "<= bdb_presense_candidates: (%s) "
 550                         "key read failed (%d)\n",
 551                         desc->ad_cname.bv_val, rc, 0 );
 552                 goto done;
 553         }
 554
 555         Debug(LDAP_DEBUG_TRACE,
 556                 "<= bdb_presence_candidates: id=%ld first=%ld last=%ld\n",
 557                 (long) ids[0],
 558                 (long) BDB_IDL_FIRST(ids),
 559                 (long) BDB_IDL_LAST(ids) );
 560
 561 done:
 562         return rc;
 563 }
 564
 565 static int
 566 equality_candidates(
 567         Operation *op,
 568         AttributeAssertion *ava,
 569         ID *ids,
 570         ID *tmp )
 571 {
 572         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 573         DB      *db;
 574         int i;
 575         int rc;
 576         slap_mask_t mask;
 577         struct berval prefix = {0, NULL};
 578         struct berval *keys = NULL;
 579         MatchingRule *mr;
 580
 581         Debug( LDAP_DEBUG_TRACE, "=> bdb_equality_candidates (%s)\n",
 582                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 583
 584         BDB_IDL_ALL( bdb, ids );
 585
 586         rc = bdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_EQUALITY,
 587                 &db, &mask, &prefix );
 588
 589         if( rc != LDAP_SUCCESS ) {
 590                 Debug( LDAP_DEBUG_ANY,
 591                         "<= bdb_equality_candidates: (%s) "
 592                         "index_param failed (%d)\n",
 593                         ava->aa_desc->ad_cname.bv_val, rc, 0 );
 594                 return 0;
 595         }
 596
 597         if ( db == NULL ) {
 598                 Debug( LDAP_DEBUG_ANY,
 599                         "<= bdb_equality_candidates: (%s) not indexed\n",
 600                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 601                 return 0;
 602         }
 603
 604         mr = ava->aa_desc->ad_type->sat_equality;
 605         if( !mr ) {
 606                 return 0;
 607         }
 608
 609         if( !mr->smr_filter ) {
 610                 return 0;
 611         }
 612
 613         rc = (mr->smr_filter)(
 614                 LDAP_FILTER_EQUALITY,
 615                 mask,
 616                 ava->aa_desc->ad_type->sat_syntax,
 617                 mr,
 618                 &prefix,
 619                 &ava->aa_value,
 620                 &keys, op->o_tmpmemctx );
 621
 622         if( rc != LDAP_SUCCESS ) {
 623                 Debug( LDAP_DEBUG_TRACE,
 624                         "<= bdb_equality_candidates: (%s, %s) "
 625                         "MR filter failed (%d)\n",
 626                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
 627                 return 0;
 628         }
 629
 630         if( keys == NULL ) {
 631                 Debug( LDAP_DEBUG_TRACE,
 632                         "<= bdb_equality_candidates: (%s) no keys\n",
 633                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 634                 return 0;
 635         }
 636
 637         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 638                 rc = bdb_key_read( op->o_bd, db, NULL, &keys[i], tmp, NULL, 0 );
 639
 640                 if( rc == DB_NOTFOUND ) {
 641                         BDB_IDL_ZERO( ids );
 642                         rc = 0;
 643                         break;
 644                 } else if( rc != LDAP_SUCCESS ) {
 645                         Debug( LDAP_DEBUG_TRACE,
 646                                 "<= bdb_equality_candidates: (%s) "
 647                                 "key read failed (%d)\n",
 648                                 ava->aa_desc->ad_cname.bv_val, rc, 0 );
 649                         break;
 650                 }
 651
 652                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 653                         Debug( LDAP_DEBUG_TRACE,
 654                                 "<= bdb_equality_candidates: (%s) NULL\n",
 655                                 ava->aa_desc->ad_cname.bv_val, 0, 0 );
 656                         BDB_IDL_ZERO( ids );
 657                         break;
 658                 }
 659
 660                 if ( i == 0 ) {
 661                         BDB_IDL_CPY( ids, tmp );
 662                 } else {
 663                         bdb_idl_intersection( ids, tmp );
 664                 }
 665
 666                 if( BDB_IDL_IS_ZERO( ids ) )
 667                         break;
 668         }
 669
 670         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 671
 672         Debug( LDAP_DEBUG_TRACE,
 673                 "<= bdb_equality_candidates: id=%ld, first=%ld, last=%ld\n",
 674                 (long) ids[0],
 675                 (long) BDB_IDL_FIRST(ids),
 676                 (long) BDB_IDL_LAST(ids) );
 677         return( rc );
 678 }
 679
 680
 681 static int
 682 approx_candidates(
 683         Operation *op,
 684         AttributeAssertion *ava,
 685         ID *ids,
 686         ID *tmp )
 687 {
 688         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 689         DB      *db;
 690         int i;
 691         int rc;
 692         slap_mask_t mask;
 693         struct berval prefix = {0, NULL};
 694         struct berval *keys = NULL;
 695         MatchingRule *mr;
 696
 697         Debug( LDAP_DEBUG_TRACE, "=> bdb_approx_candidates (%s)\n",
 698                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 699
 700         BDB_IDL_ALL( bdb, ids );
 701
 702         rc = bdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_APPROX,
 703                 &db, &mask, &prefix );
 704
 705         if( rc != LDAP_SUCCESS ) {
 706                 Debug( LDAP_DEBUG_ANY,
 707                         "<= bdb_approx_candidates: (%s) "
 708                         "index_param failed (%d)\n",
 709                         ava->aa_desc->ad_cname.bv_val, rc, 0 );
 710                 return 0;
 711         }
 712
 713         if ( db == NULL ) {
 714                 Debug( LDAP_DEBUG_ANY,
 715                         "<= bdb_approx_candidates: (%s) not indexed\n",
 716                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 717                 return 0;
 718         }
 719
 720         mr = ava->aa_desc->ad_type->sat_approx;
 721         if( !mr ) {
 722                 /* no approx matching rule, try equality matching rule */
 723                 mr = ava->aa_desc->ad_type->sat_equality;
 724         }
 725
 726         if( !mr ) {
 727                 return 0;
 728         }
 729
 730         if( !mr->smr_filter ) {
 731                 return 0;
 732         }
 733
 734         rc = (mr->smr_filter)(
 735                 LDAP_FILTER_APPROX,
 736                 mask,
 737                 ava->aa_desc->ad_type->sat_syntax,
 738                 mr,
 739                 &prefix,
 740                 &ava->aa_value,
 741                 &keys, op->o_tmpmemctx );
 742
 743         if( rc != LDAP_SUCCESS ) {
 744                 Debug( LDAP_DEBUG_TRACE,
 745                         "<= bdb_approx_candidates: (%s, %s) "
 746                         "MR filter failed (%d)\n",
 747                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
 748                 return 0;
 749         }
 750
 751         if( keys == NULL ) {
 752                 Debug( LDAP_DEBUG_TRACE,
 753                         "<= bdb_approx_candidates: (%s) no keys (%s)\n",
 754                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, 0 );
 755                 return 0;
 756         }
 757
 758         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 759                 rc = bdb_key_read( op->o_bd, db, NULL, &keys[i], tmp, NULL, 0 );
 760
 761                 if( rc == DB_NOTFOUND ) {
 762                         BDB_IDL_ZERO( ids );
 763                         rc = 0;
 764                         break;
 765                 } else if( rc != LDAP_SUCCESS ) {
 766                         Debug( LDAP_DEBUG_TRACE,
 767                                 "<= bdb_approx_candidates: (%s) "
 768                                 "key read failed (%d)\n",
 769                                 ava->aa_desc->ad_cname.bv_val, rc, 0 );
 770                         break;
 771                 }
 772
 773                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 774                         Debug( LDAP_DEBUG_TRACE,
 775                                 "<= bdb_approx_candidates: (%s) NULL\n",
 776                                 ava->aa_desc->ad_cname.bv_val, 0, 0 );
 777                         BDB_IDL_ZERO( ids );
 778                         break;
 779                 }
 780
 781                 if ( i == 0 ) {
 782                         BDB_IDL_CPY( ids, tmp );
 783                 } else {
 784                         bdb_idl_intersection( ids, tmp );
 785                 }
 786
 787                 if( BDB_IDL_IS_ZERO( ids ) )
 788                         break;
 789         }
 790
 791         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 792
 793         Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates %ld, first=%ld, last=%ld\n",
 794                 (long) ids[0],
 795                 (long) BDB_IDL_FIRST(ids),
 796                 (long) BDB_IDL_LAST(ids) );
 797         return( rc );
 798 }
 799
 800 static int
 801 substring_candidates(
 802         Operation *op,
 803         SubstringsAssertion     *sub,
 804         ID *ids,
 805         ID *tmp )
 806 {
 807         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 808         DB      *db;
 809         int i;
 810         int rc;
 811         slap_mask_t mask;
 812         struct berval prefix = {0, NULL};
 813         struct berval *keys = NULL;
 814         MatchingRule *mr;
 815
 816         Debug( LDAP_DEBUG_TRACE, "=> bdb_substring_candidates (%s)\n",
 817                         sub->sa_desc->ad_cname.bv_val, 0, 0 );
 818
 819         BDB_IDL_ALL( bdb, ids );
 820
 821         rc = bdb_index_param( op->o_bd, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
 822                 &db, &mask, &prefix );
 823
 824         if( rc != LDAP_SUCCESS ) {
 825                 Debug( LDAP_DEBUG_ANY,
 826                         "<= bdb_substring_candidates: (%s) "
 827                         "index_param failed (%d)\n",
 828                         sub->sa_desc->ad_cname.bv_val, rc, 0 );
 829                 return 0;
 830         }
 831
 832         if ( db == NULL ) {
 833                 Debug( LDAP_DEBUG_ANY,
 834                         "<= bdb_substring_candidates: (%s) not indexed\n",
 835                         sub->sa_desc->ad_cname.bv_val, 0, 0 );
 836                 return 0;
 837         }
 838
 839         mr = sub->sa_desc->ad_type->sat_substr;
 840
 841         if( !mr ) {
 842                 return 0;
 843         }
 844
 845         if( !mr->smr_filter ) {
 846                 return 0;
 847         }
 848
 849         rc = (mr->smr_filter)(
 850                 LDAP_FILTER_SUBSTRINGS,
 851                 mask,
 852                 sub->sa_desc->ad_type->sat_syntax,
 853                 mr,
 854                 &prefix,
 855                 sub,
 856                 &keys, op->o_tmpmemctx );
 857
 858         if( rc != LDAP_SUCCESS ) {
 859                 Debug( LDAP_DEBUG_TRACE,
 860                         "<= bdb_substring_candidates: (%s) "
 861                         "MR filter failed (%d)\n",
 862                         sub->sa_desc->ad_cname.bv_val, rc, 0 );
 863                 return 0;
 864         }
 865
 866         if( keys == NULL ) {
 867                 Debug( LDAP_DEBUG_TRACE,
 868                         "<= bdb_substring_candidates: (0x%04lx) no keys (%s)\n",
 869                         mask, sub->sa_desc->ad_cname.bv_val, 0 );
 870                 return 0;
 871         }
 872
 873         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 874                 rc = bdb_key_read( op->o_bd, db, NULL, &keys[i], tmp, NULL, 0 );
 875
 876                 if( rc == DB_NOTFOUND ) {
 877                         BDB_IDL_ZERO( ids );
 878                         rc = 0;
 879                         break;
 880                 } else if( rc != LDAP_SUCCESS ) {
 881                         Debug( LDAP_DEBUG_TRACE,
 882                                 "<= bdb_substring_candidates: (%s) "
 883                                 "key read failed (%d)\n",
 884                                 sub->sa_desc->ad_cname.bv_val, rc, 0 );
 885                         break;
 886                 }
 887
 888                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 889                         Debug( LDAP_DEBUG_TRACE,
 890                                 "<= bdb_substring_candidates: (%s) NULL\n",
 891                                 sub->sa_desc->ad_cname.bv_val, 0, 0 );
 892                         BDB_IDL_ZERO( ids );
 893                         break;
 894                 }
 895
 896                 if ( i == 0 ) {
 897                         BDB_IDL_CPY( ids, tmp );
 898                 } else {
 899                         bdb_idl_intersection( ids, tmp );
 900                 }
 901
 902                 if( BDB_IDL_IS_ZERO( ids ) )
 903                         break;
 904         }
 905
 906         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 907
 908         Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates: %ld, first=%ld, last=%ld\n",
 909                 (long) ids[0],
 910                 (long) BDB_IDL_FIRST(ids),
 911                 (long) BDB_IDL_LAST(ids) );
 912         return( rc );
 913 }
 914
 915 static int
 916 inequality_candidates(
 917         Operation *op,
 918         AttributeAssertion *ava,
 919         ID *ids,
 920         ID *tmp,
 921         int gtorlt )
 922 {
 923         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 924         DB      *db;
 925         int i;
 926         int rc;
 927         slap_mask_t mask;
 928         struct berval prefix = {0, NULL};
 929         struct berval *keys = NULL;
 930         MatchingRule *mr;
 931         DBC * cursor = NULL;
 932
 933         Debug( LDAP_DEBUG_TRACE, "=> bdb_inequality_candidates (%s)\n",
 934                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 935
 936         BDB_IDL_ALL( bdb, ids );
 937
 938         rc = bdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_EQUALITY,
 939                 &db, &mask, &prefix );
 940
 941         if( rc != LDAP_SUCCESS ) {
 942                 Debug( LDAP_DEBUG_ANY,
 943                         "<= bdb_inequality_candidates: (%s) "
 944                         "index_param failed (%d)\n",
 945                         ava->aa_desc->ad_cname.bv_val, rc, 0 );
 946                 return 0;
 947         }
 948
 949         if ( db == NULL ) {
 950                 Debug( LDAP_DEBUG_ANY,
 951                         "<= bdb_inequality_candidates: (%s) not indexed\n",
 952                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 953                 return 0;
 954         }
 955
 956         mr = ava->aa_desc->ad_type->sat_equality;
 957         if( !mr ) {
 958                 return 0;
 959         }
 960
 961         if( !mr->smr_filter ) {
 962                 return 0;
 963         }
 964
 965         rc = (mr->smr_filter)(
 966                 LDAP_FILTER_EQUALITY,
 967                 mask,
 968                 ava->aa_desc->ad_type->sat_syntax,
 969                 mr,
 970                 &prefix,
 971                 &ava->aa_value,
 972                 &keys, op->o_tmpmemctx );
 973
 974         if( rc != LDAP_SUCCESS ) {
 975                 Debug( LDAP_DEBUG_TRACE,
 976                         "<= bdb_inequality_candidates: (%s, %s) "
 977                         "MR filter failed (%d)\n",
 978                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
 979                 return 0;
 980         }
 981
 982         if( keys == NULL ) {
 983                 Debug( LDAP_DEBUG_TRACE,
 984                         "<= bdb_inequality_candidates: (%s) no keys\n",
 985                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 986                 return 0;
 987         }
 988
 989         BDB_IDL_ZERO( ids );
 990         while(1) {
 991                 rc = bdb_key_read( op->o_bd, db, NULL, &keys[0], tmp, &cursor, gtorlt );
 992
 993                 if( rc == DB_NOTFOUND ) {
 994                         rc = 0;
 995                         break;
 996                 } else if( rc != LDAP_SUCCESS ) {
 997                         Debug( LDAP_DEBUG_TRACE,
 998                                "<= bdb_inequality_candidates: (%s) "
 999                                "key read failed (%d)\n",
1000                                ava->aa_desc->ad_cname.bv_val, rc, 0 );
1001                         break;
1002                 }
1003
1004                 if( BDB_IDL_IS_ZERO( tmp ) ) {
1005                         Debug( LDAP_DEBUG_TRACE,
1006                                "<= bdb_inequality_candidates: (%s) NULL\n",
1007                                ava->aa_desc->ad_cname.bv_val, 0, 0 );
1008                         break;
1009                 }
1010
1011                 bdb_idl_union( ids, tmp );
1012
1013                 if( BDB_IDL_IS_ZERO( ids ) )
1014                         break;
1015                 i++;
1016         }
1017         ber_bvarray_free_x( keys, op->o_tmpmemctx );
1018
1019         Debug( LDAP_DEBUG_TRACE,
1020                 "<= bdb_inequality_candidates: id=%ld, first=%ld, last=%ld\n",
1021                 (long) ids[0],
1022                 (long) BDB_IDL_FIRST(ids),
1023                 (long) BDB_IDL_LAST(ids) );
1024         return( rc );
1025 }