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