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 int
  61 bdb_filter_candidates(
  62         Operation *op,
  63         Filter  *f,
  64         ID *ids,
  65         ID *tmp,
  66         ID *stack )
  67 {
  68         int rc = 0;
  69         Debug( LDAP_DEBUG_FILTER, "=> bdb_filter_candidates\n", 0, 0, 0 );
  70
  71         switch ( f->f_choice ) {
  72         case SLAPD_FILTER_COMPUTED:
  73                 switch( f->f_result ) {
  74                 case SLAPD_COMPARE_UNDEFINED:
  75                 /* This technically is not the same as FALSE, but it
  76                  * certainly will produce no matches.
  77                  */
  78                 /* FALL THRU */
  79                 case LDAP_COMPARE_FALSE:
  80                         BDB_IDL_ZERO( ids );
  81                         break;
  82                 case LDAP_COMPARE_TRUE: {
  83                         struct bdb_info *bdb = (struct bdb_info *)op->o_bd->be_private;
  84                         BDB_IDL_ALL( bdb, ids );
  85                         } break;
  86                 case LDAP_SUCCESS:
  87                         /* this is a pre-computed scope, leave it alone */
  88                         break;
  89                 }
  90                 break;
  91         case LDAP_FILTER_PRESENT:
  92                 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
  93                 rc = presence_candidates( op, f->f_desc, ids );
  94                 break;
  95
  96         case LDAP_FILTER_EQUALITY:
  97                 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
  98                 rc = equality_candidates( op, f->f_ava, ids, tmp );
  99                 break;
 100
 101         case LDAP_FILTER_APPROX:
 102                 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
 103                 rc = approx_candidates( op, f->f_ava, ids, tmp );
 104                 break;
 105
 106         case LDAP_FILTER_SUBSTRINGS:
 107                 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
 108                 rc = substring_candidates( op, f->f_sub, ids, tmp );
 109                 break;
 110
 111         case LDAP_FILTER_GE:
 112                 /* if no GE index, use pres */
 113                 Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
 114                 if( f->f_ava->aa_desc->ad_type->sat_ordering &&
 115                         ( f->f_ava->aa_desc->ad_type->sat_ordering->smr_usage && SLAP_MR_ORDERED_INDEX ) )
 116                         rc = inequality_candidates( op, f->f_ava, ids, tmp, LDAP_FILTER_GE );
 117                 else
 118                         rc = presence_candidates( op, f->f_ava->aa_desc, ids );
 119                 break;
 120
 121         case LDAP_FILTER_LE:
 122                 /* if no LE index, use pres */
 123                 Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
 124                 if( f->f_ava->aa_desc->ad_type->sat_ordering &&
 125                         ( f->f_ava->aa_desc->ad_type->sat_ordering->smr_usage && SLAP_MR_ORDERED_INDEX ) )
 126                         rc = inequality_candidates( op, f->f_ava, ids, tmp, LDAP_FILTER_LE );
 127                 else
 128                         rc = presence_candidates( op, f->f_ava->aa_desc, ids );
 129                 break;
 130
 131         case LDAP_FILTER_NOT:
 132                 /* no indexing to support NOT filters */
 133                 Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
 134                 { struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 135                 BDB_IDL_ALL( bdb, ids );
 136                 }
 137                 break;
 138
 139         case LDAP_FILTER_AND:
 140                 Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
 141                 rc = list_candidates( op,
 142                         f->f_and, LDAP_FILTER_AND, ids, tmp, stack );
 143                 break;
 144
 145         case LDAP_FILTER_OR:
 146                 Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
 147                 rc = list_candidates( op,
 148                         f->f_or, LDAP_FILTER_OR, ids, tmp, stack );
 149                 break;
 150
 151         default:
 152                 Debug( LDAP_DEBUG_FILTER, "\tUNKNOWN %lu\n",
 153                         (unsigned long) f->f_choice, 0, 0 );
 154                 /* Must not return NULL, otherwise extended filters break */
 155                 { struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 156                 BDB_IDL_ALL( bdb, ids );
 157                 }
 158         }
 159
 160         Debug( LDAP_DEBUG_FILTER,
 161                 "<= bdb_filter_candidates: id=%ld first=%ld last=%ld\n",
 162                 (long) ids[0],
 163                 (long) BDB_IDL_FIRST( ids ),
 164                 (long) BDB_IDL_LAST( ids ) );
 165
 166         return rc;
 167 }
 168
 169 static int
 170 list_candidates(
 171         Operation *op,
 172         Filter  *flist,
 173         int             ftype,
 174         ID *ids,
 175         ID *tmp,
 176         ID *save )
 177 {
 178         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 179         int rc = 0;
 180         Filter  *f;
 181
 182         Debug( LDAP_DEBUG_FILTER, "=> bdb_list_candidates 0x%x\n", ftype, 0, 0 );
 183         for ( f = flist; f != NULL; f = f->f_next ) {
 184                 /* ignore precomputed scopes */
 185                 if ( f->f_choice == SLAPD_FILTER_COMPUTED &&
 186                      f->f_result == LDAP_SUCCESS ) {
 187                         continue;
 188                 }
 189                 BDB_IDL_ZERO( save );
 190                 rc = bdb_filter_candidates( op, f, save, tmp,
 191                         save+BDB_IDL_UM_SIZE );
 192
 193                 if ( rc != 0 ) {
 194                         if ( ftype == LDAP_FILTER_AND ) {
 195                                 rc = 0;
 196                                 continue;
 197                         }
 198                         break;
 199                 }
 200
 201
 202                 if ( ftype == LDAP_FILTER_AND ) {
 203                         if ( f == flist ) {
 204                                 BDB_IDL_CPY( ids, save );
 205                         } else {
 206                                 bdb_idl_intersection( ids, save );
 207                         }
 208                         if( BDB_IDL_IS_ZERO( ids ) )
 209                                 break;
 210                 } else {
 211                         if ( f == flist ) {
 212                                 BDB_IDL_CPY( ids, save );
 213                         } else {
 214                                 bdb_idl_union( ids, save );
 215                         }
 216                 }
 217         }
 218
 219         if( rc == LDAP_SUCCESS ) {
 220                 Debug( LDAP_DEBUG_FILTER,
 221                         "<= bdb_list_candidates: id=%ld first=%ld last=%ld\n",
 222                         (long) ids[0],
 223                         (long) BDB_IDL_FIRST(ids),
 224                         (long) BDB_IDL_LAST(ids) );
 225
 226         } else {
 227                 Debug( LDAP_DEBUG_FILTER,
 228                         "<= bdb_list_candidates: undefined rc=%d\n",
 229                         rc, 0, 0 );
 230         }
 231
 232         return rc;
 233 }
 234
 235 static int
 236 presence_candidates(
 237         Operation *op,
 238         AttributeDescription *desc,
 239         ID *ids )
 240 {
 241         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 242         DB *db;
 243         int rc;
 244         slap_mask_t mask;
 245         struct berval prefix = {0, NULL};
 246
 247         Debug( LDAP_DEBUG_TRACE, "=> bdb_presence_candidates (%s)\n",
 248                         desc->ad_cname.bv_val, 0, 0 );
 249
 250         BDB_IDL_ALL( bdb, ids );
 251
 252         if( desc == slap_schema.si_ad_objectClass ) {
 253                 return 0;
 254         }
 255
 256         rc = bdb_index_param( op->o_bd, desc, LDAP_FILTER_PRESENT,
 257                 &db, &mask, &prefix );
 258
 259         if( rc != LDAP_SUCCESS ) {
 260                 Debug( LDAP_DEBUG_TRACE,
 261                         "<= bdb_presence_candidates: (%s) index_param "
 262                         "returned=%d\n",
 263                         desc->ad_cname.bv_val, rc, 0 );
 264                 return 0;
 265         }
 266
 267         if( db == NULL ) {
 268                 /* not indexed */
 269                 Debug( LDAP_DEBUG_TRACE,
 270                         "<= bdb_presence_candidates: (%s) not indexed\n",
 271                         desc->ad_cname.bv_val, 0, 0 );
 272                 return 0;
 273         }
 274
 275         if( prefix.bv_val == NULL ) {
 276                 Debug( LDAP_DEBUG_TRACE,
 277                         "<= bdb_presence_candidates: (%s) no prefix\n",
 278                         desc->ad_cname.bv_val, 0, 0 );
 279                 return -1;
 280         }
 281
 282         rc = bdb_key_read( op->o_bd, db, NULL, &prefix, ids, NULL, 0 );
 283
 284         if( rc == DB_NOTFOUND ) {
 285                 BDB_IDL_ZERO( ids );
 286                 rc = 0;
 287         } else if( rc != LDAP_SUCCESS ) {
 288                 Debug( LDAP_DEBUG_TRACE,
 289                         "<= bdb_presense_candidates: (%s) "
 290                         "key read failed (%d)\n",
 291                         desc->ad_cname.bv_val, rc, 0 );
 292                 goto done;
 293         }
 294
 295         Debug(LDAP_DEBUG_TRACE,
 296                 "<= bdb_presence_candidates: id=%ld first=%ld last=%ld\n",
 297                 (long) ids[0],
 298                 (long) BDB_IDL_FIRST(ids),
 299                 (long) BDB_IDL_LAST(ids) );
 300
 301 done:
 302         return rc;
 303 }
 304
 305 static int
 306 equality_candidates(
 307         Operation *op,
 308         AttributeAssertion *ava,
 309         ID *ids,
 310         ID *tmp )
 311 {
 312         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 313         DB      *db;
 314         int i;
 315         int rc;
 316         slap_mask_t mask;
 317         struct berval prefix = {0, NULL};
 318         struct berval *keys = NULL;
 319         MatchingRule *mr;
 320
 321         Debug( LDAP_DEBUG_TRACE, "=> bdb_equality_candidates (%s)\n",
 322                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 323
 324         BDB_IDL_ALL( bdb, ids );
 325
 326         rc = bdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_EQUALITY,
 327                 &db, &mask, &prefix );
 328
 329         if( rc != LDAP_SUCCESS ) {
 330                 Debug( LDAP_DEBUG_ANY,
 331                         "<= bdb_equality_candidates: (%s) "
 332                         "index_param failed (%d)\n",
 333                         ava->aa_desc->ad_cname.bv_val, rc, 0 );
 334                 return 0;
 335         }
 336
 337         if ( db == NULL ) {
 338                 Debug( LDAP_DEBUG_ANY,
 339                         "<= bdb_equality_candidates: (%s) not indexed\n",
 340                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 341                 return 0;
 342         }
 343
 344         mr = ava->aa_desc->ad_type->sat_equality;
 345         if( !mr ) {
 346                 return 0;
 347         }
 348
 349         if( !mr->smr_filter ) {
 350                 return 0;
 351         }
 352
 353         rc = (mr->smr_filter)(
 354                 LDAP_FILTER_EQUALITY,
 355                 mask,
 356                 ava->aa_desc->ad_type->sat_syntax,
 357                 mr,
 358                 &prefix,
 359                 &ava->aa_value,
 360                 &keys, op->o_tmpmemctx );
 361
 362         if( rc != LDAP_SUCCESS ) {
 363                 Debug( LDAP_DEBUG_TRACE,
 364                         "<= bdb_equality_candidates: (%s, %s) "
 365                         "MR filter failed (%d)\n",
 366                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
 367                 return 0;
 368         }
 369
 370         if( keys == NULL ) {
 371                 Debug( LDAP_DEBUG_TRACE,
 372                         "<= bdb_equality_candidates: (%s) no keys\n",
 373                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 374                 return 0;
 375         }
 376
 377         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 378                 rc = bdb_key_read( op->o_bd, db, NULL, &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                         Debug( LDAP_DEBUG_TRACE,
 386                                 "<= bdb_equality_candidates: (%s) "
 387                                 "key read failed (%d)\n",
 388                                 ava->aa_desc->ad_cname.bv_val, rc, 0 );
 389                         break;
 390                 }
 391
 392                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 393                         Debug( LDAP_DEBUG_TRACE,
 394                                 "<= bdb_equality_candidates: (%s) NULL\n",
 395                                 ava->aa_desc->ad_cname.bv_val, 0, 0 );
 396                         BDB_IDL_ZERO( ids );
 397                         break;
 398                 }
 399
 400                 if ( i == 0 ) {
 401                         BDB_IDL_CPY( ids, tmp );
 402                 } else {
 403                         bdb_idl_intersection( ids, tmp );
 404                 }
 405
 406                 if( BDB_IDL_IS_ZERO( ids ) )
 407                         break;
 408         }
 409
 410         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 411
 412         Debug( LDAP_DEBUG_TRACE,
 413                 "<= bdb_equality_candidates: id=%ld, first=%ld, last=%ld\n",
 414                 (long) ids[0],
 415                 (long) BDB_IDL_FIRST(ids),
 416                 (long) BDB_IDL_LAST(ids) );
 417         return( rc );
 418 }
 419
 420
 421 static int
 422 approx_candidates(
 423         Operation *op,
 424         AttributeAssertion *ava,
 425         ID *ids,
 426         ID *tmp )
 427 {
 428         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 429         DB      *db;
 430         int i;
 431         int rc;
 432         slap_mask_t mask;
 433         struct berval prefix = {0, NULL};
 434         struct berval *keys = NULL;
 435         MatchingRule *mr;
 436
 437         Debug( LDAP_DEBUG_TRACE, "=> bdb_approx_candidates (%s)\n",
 438                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 439
 440         BDB_IDL_ALL( bdb, ids );
 441
 442         rc = bdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_APPROX,
 443                 &db, &mask, &prefix );
 444
 445         if( rc != LDAP_SUCCESS ) {
 446                 Debug( LDAP_DEBUG_ANY,
 447                         "<= bdb_approx_candidates: (%s) "
 448                         "index_param failed (%d)\n",
 449                         ava->aa_desc->ad_cname.bv_val, rc, 0 );
 450                 return 0;
 451         }
 452
 453         if ( db == NULL ) {
 454                 Debug( LDAP_DEBUG_ANY,
 455                         "<= bdb_approx_candidates: (%s) not indexed\n",
 456                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 457                 return 0;
 458         }
 459
 460         mr = ava->aa_desc->ad_type->sat_approx;
 461         if( !mr ) {
 462                 /* no approx matching rule, try equality matching rule */
 463                 mr = ava->aa_desc->ad_type->sat_equality;
 464         }
 465
 466         if( !mr ) {
 467                 return 0;
 468         }
 469
 470         if( !mr->smr_filter ) {
 471                 return 0;
 472         }
 473
 474         rc = (mr->smr_filter)(
 475                 LDAP_FILTER_APPROX,
 476                 mask,
 477                 ava->aa_desc->ad_type->sat_syntax,
 478                 mr,
 479                 &prefix,
 480                 &ava->aa_value,
 481                 &keys, op->o_tmpmemctx );
 482
 483         if( rc != LDAP_SUCCESS ) {
 484                 Debug( LDAP_DEBUG_TRACE,
 485                         "<= bdb_approx_candidates: (%s, %s) "
 486                         "MR filter failed (%d)\n",
 487                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
 488                 return 0;
 489         }
 490
 491         if( keys == NULL ) {
 492                 Debug( LDAP_DEBUG_TRACE,
 493                         "<= bdb_approx_candidates: (%s) no keys (%s)\n",
 494                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, 0 );
 495                 return 0;
 496         }
 497
 498         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 499                 rc = bdb_key_read( op->o_bd, db, NULL, &keys[i], tmp, NULL, 0 );
 500
 501                 if( rc == DB_NOTFOUND ) {
 502                         BDB_IDL_ZERO( ids );
 503                         rc = 0;
 504                         break;
 505                 } else if( rc != LDAP_SUCCESS ) {
 506                         Debug( LDAP_DEBUG_TRACE,
 507                                 "<= bdb_approx_candidates: (%s) "
 508                                 "key read failed (%d)\n",
 509                                 ava->aa_desc->ad_cname.bv_val, rc, 0 );
 510                         break;
 511                 }
 512
 513                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 514                         Debug( LDAP_DEBUG_TRACE,
 515                                 "<= bdb_approx_candidates: (%s) NULL\n",
 516                                 ava->aa_desc->ad_cname.bv_val, 0, 0 );
 517                         BDB_IDL_ZERO( ids );
 518                         break;
 519                 }
 520
 521                 if ( i == 0 ) {
 522                         BDB_IDL_CPY( ids, tmp );
 523                 } else {
 524                         bdb_idl_intersection( ids, tmp );
 525                 }
 526
 527                 if( BDB_IDL_IS_ZERO( ids ) )
 528                         break;
 529         }
 530
 531         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 532
 533         Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates %ld, first=%ld, last=%ld\n",
 534                 (long) ids[0],
 535                 (long) BDB_IDL_FIRST(ids),
 536                 (long) BDB_IDL_LAST(ids) );
 537         return( rc );
 538 }
 539
 540 static int
 541 substring_candidates(
 542         Operation *op,
 543         SubstringsAssertion     *sub,
 544         ID *ids,
 545         ID *tmp )
 546 {
 547         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 548         DB      *db;
 549         int i;
 550         int rc;
 551         slap_mask_t mask;
 552         struct berval prefix = {0, NULL};
 553         struct berval *keys = NULL;
 554         MatchingRule *mr;
 555
 556         Debug( LDAP_DEBUG_TRACE, "=> bdb_substring_candidates (%s)\n",
 557                         sub->sa_desc->ad_cname.bv_val, 0, 0 );
 558
 559         BDB_IDL_ALL( bdb, ids );
 560
 561         rc = bdb_index_param( op->o_bd, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
 562                 &db, &mask, &prefix );
 563
 564         if( rc != LDAP_SUCCESS ) {
 565                 Debug( LDAP_DEBUG_ANY,
 566                         "<= bdb_substring_candidates: (%s) "
 567                         "index_param failed (%d)\n",
 568                         sub->sa_desc->ad_cname.bv_val, rc, 0 );
 569                 return 0;
 570         }
 571
 572         if ( db == NULL ) {
 573                 Debug( LDAP_DEBUG_ANY,
 574                         "<= bdb_substring_candidates: (%s) not indexed\n",
 575                         sub->sa_desc->ad_cname.bv_val, 0, 0 );
 576                 return 0;
 577         }
 578
 579         mr = sub->sa_desc->ad_type->sat_substr;
 580
 581         if( !mr ) {
 582                 return 0;
 583         }
 584
 585         if( !mr->smr_filter ) {
 586                 return 0;
 587         }
 588
 589         rc = (mr->smr_filter)(
 590                 LDAP_FILTER_SUBSTRINGS,
 591                 mask,
 592                 sub->sa_desc->ad_type->sat_syntax,
 593                 mr,
 594                 &prefix,
 595                 sub,
 596                 &keys, op->o_tmpmemctx );
 597
 598         if( rc != LDAP_SUCCESS ) {
 599                 Debug( LDAP_DEBUG_TRACE,
 600                         "<= bdb_substring_candidates: (%s) "
 601                         "MR filter failed (%d)\n",
 602                         sub->sa_desc->ad_cname.bv_val, rc, 0 );
 603                 return 0;
 604         }
 605
 606         if( keys == NULL ) {
 607                 Debug( LDAP_DEBUG_TRACE,
 608                         "<= bdb_substring_candidates: (0x%04lx) no keys (%s)\n",
 609                         mask, sub->sa_desc->ad_cname.bv_val, 0 );
 610                 return 0;
 611         }
 612
 613         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 614                 rc = bdb_key_read( op->o_bd, db, NULL, &keys[i], tmp, NULL, 0 );
 615
 616                 if( rc == DB_NOTFOUND ) {
 617                         BDB_IDL_ZERO( ids );
 618                         rc = 0;
 619                         break;
 620                 } else if( rc != LDAP_SUCCESS ) {
 621                         Debug( LDAP_DEBUG_TRACE,
 622                                 "<= bdb_substring_candidates: (%s) "
 623                                 "key read failed (%d)\n",
 624                                 sub->sa_desc->ad_cname.bv_val, rc, 0 );
 625                         break;
 626                 }
 627
 628                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 629                         Debug( LDAP_DEBUG_TRACE,
 630                                 "<= bdb_substring_candidates: (%s) NULL\n",
 631                                 sub->sa_desc->ad_cname.bv_val, 0, 0 );
 632                         BDB_IDL_ZERO( ids );
 633                         break;
 634                 }
 635
 636                 if ( i == 0 ) {
 637                         BDB_IDL_CPY( ids, tmp );
 638                 } else {
 639                         bdb_idl_intersection( ids, tmp );
 640                 }
 641
 642                 if( BDB_IDL_IS_ZERO( ids ) )
 643                         break;
 644         }
 645
 646         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 647
 648         Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates: %ld, first=%ld, last=%ld\n",
 649                 (long) ids[0],
 650                 (long) BDB_IDL_FIRST(ids),
 651                 (long) BDB_IDL_LAST(ids) );
 652         return( rc );
 653 }
 654
 655 static int
 656 inequality_candidates(
 657         Operation *op,
 658         AttributeAssertion *ava,
 659         ID *ids,
 660         ID *tmp,
 661         int gtorlt )
 662 {
 663         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 664         DB      *db;
 665         int i;
 666         int rc;
 667         slap_mask_t mask;
 668         struct berval prefix = {0, NULL};
 669         struct berval *keys = NULL;
 670         MatchingRule *mr;
 671         DBC * cursor = NULL;
 672
 673         Debug( LDAP_DEBUG_TRACE, "=> bdb_inequality_candidates (%s)\n",
 674                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 675
 676         BDB_IDL_ALL( bdb, ids );
 677
 678         rc = bdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_EQUALITY,
 679                 &db, &mask, &prefix );
 680
 681         if( rc != LDAP_SUCCESS ) {
 682                 Debug( LDAP_DEBUG_ANY,
 683                         "<= bdb_inequality_candidates: (%s) "
 684                         "index_param failed (%d)\n",
 685                         ava->aa_desc->ad_cname.bv_val, rc, 0 );
 686                 return 0;
 687         }
 688
 689         if ( db == NULL ) {
 690                 Debug( LDAP_DEBUG_ANY,
 691                         "<= bdb_inequality_candidates: (%s) not indexed\n",
 692                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 693                 return 0;
 694         }
 695
 696         mr = ava->aa_desc->ad_type->sat_equality;
 697         if( !mr ) {
 698                 return 0;
 699         }
 700
 701         if( !mr->smr_filter ) {
 702                 return 0;
 703         }
 704
 705         rc = (mr->smr_filter)(
 706                 LDAP_FILTER_EQUALITY,
 707                 mask,
 708                 ava->aa_desc->ad_type->sat_syntax,
 709                 mr,
 710                 &prefix,
 711                 &ava->aa_value,
 712                 &keys, op->o_tmpmemctx );
 713
 714         if( rc != LDAP_SUCCESS ) {
 715                 Debug( LDAP_DEBUG_TRACE,
 716                         "<= bdb_inequality_candidates: (%s, %s) "
 717                         "MR filter failed (%d)\n",
 718                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
 719                 return 0;
 720         }
 721
 722         if( keys == NULL ) {
 723                 Debug( LDAP_DEBUG_TRACE,
 724                         "<= bdb_inequality_candidates: (%s) no keys\n",
 725                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 726                 return 0;
 727         }
 728
 729         BDB_IDL_ZERO( ids );
 730         while(1) {
 731                 rc = bdb_key_read( op->o_bd, db, NULL, &keys[0], tmp, &cursor, gtorlt );
 732
 733                 if( rc == DB_NOTFOUND ) {
 734                         rc = 0;
 735                         break;
 736                 } else if( rc != LDAP_SUCCESS ) {
 737                         Debug( LDAP_DEBUG_TRACE,
 738                                "<= bdb_inequality_candidates: (%s) "
 739                                "key read failed (%d)\n",
 740                                ava->aa_desc->ad_cname.bv_val, rc, 0 );
 741                         break;
 742                 }
 743
 744                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 745                         Debug( LDAP_DEBUG_TRACE,
 746                                "<= bdb_inequality_candidates: (%s) NULL\n",
 747                                ava->aa_desc->ad_cname.bv_val, 0, 0 );
 748                         break;
 749                 }
 750
 751                 bdb_idl_union( ids, tmp );
 752
 753                 if( BDB_IDL_IS_ZERO( ids ) )
 754                         break;
 755                 i++;
 756         }
 757         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 758
 759         Debug( LDAP_DEBUG_TRACE,
 760                 "<= bdb_inequality_candidates: id=%ld, first=%ld, last=%ld\n",
 761                 (long) ids[0],
 762                 (long) BDB_IDL_FIRST(ids),
 763                 (long) BDB_IDL_LAST(ids) );
 764         return( rc );
 765 }