git.sur5r.net Git - openldap/blob - servers/slapd/back-bdb/filterindex.c

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