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 /*
   4  * Copyright 1998-2003 The OpenLDAP Foundation, All Rights Reserved.
   5  * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
   6  */
   7
   8 #include "portable.h"
   9
  10 #include <stdio.h>
  11 #include <ac/string.h>
  12
  13 #include "back-bdb.h"
  14 #include "idl.h"
  15
  16 static int presence_candidates(
  17         Operation *op,
  18         AttributeDescription *desc,
  19         ID *ids );
  20
  21 static int equality_candidates(
  22         Operation *op,
  23         AttributeAssertion *ava,
  24         ID *ids,
  25         ID *tmp );
  26 static int approx_candidates(
  27         Operation *op,
  28         AttributeAssertion *ava,
  29         ID *ids,
  30         ID *tmp );
  31 static int substring_candidates(
  32         Operation *op,
  33         SubstringsAssertion *sub,
  34         ID *ids,
  35         ID *tmp );
  36
  37 static int list_candidates(
  38         Operation *op,
  39         Filter *flist,
  40         int ftype,
  41         ID *ids,
  42         ID *tmp,
  43         ID *stack );
  44
  45 int
  46 bdb_filter_candidates(
  47         Operation *op,
  48         Filter  *f,
  49         ID *ids,
  50         ID *tmp,
  51         ID *stack )
  52 {
  53         int rc = 0;
  54 #ifdef NEW_LOGGING
  55         LDAP_LOG ( INDEX, ENTRY, "=> bdb_filter_candidates\n", 0, 0, 0 );
  56 #else
  57         Debug( LDAP_DEBUG_FILTER, "=> bdb_filter_candidates\n", 0, 0, 0 );
  58 #endif
  59
  60         switch ( f->f_choice ) {
  61         case SLAPD_FILTER_COMPUTED:
  62                 break;
  63
  64         case SLAPD_FILTER_DN_ONE:
  65 #ifdef NEW_LOGGING
  66                 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tDN ONE\n", 0, 0, 0 );
  67 #else
  68                 Debug( LDAP_DEBUG_FILTER, "\tDN ONE\n", 0, 0, 0 );
  69 #endif
  70                 rc = bdb_dn2idl( op->o_bd, f->f_dn, DN_ONE_PREFIX, ids );
  71                 if( rc == DB_NOTFOUND ) {
  72                         BDB_IDL_ZERO( ids );
  73                         rc = 0;
  74                 }
  75                 break;
  76
  77         case SLAPD_FILTER_DN_SUBTREE:
  78 #ifdef NEW_LOGGING
  79                 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tDN SUBTREE\n", 0, 0, 0 );
  80 #else
  81                 Debug( LDAP_DEBUG_FILTER, "\tDN SUBTREE\n", 0, 0, 0 );
  82 #endif
  83                 rc = bdb_dn2idl( op->o_bd, f->f_dn, DN_SUBTREE_PREFIX, ids );
  84                 break;
  85
  86         case LDAP_FILTER_PRESENT:
  87 #ifdef NEW_LOGGING
  88                 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tPRESENT\n", 0, 0, 0 );
  89 #else
  90                 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
  91 #endif
  92                 rc = presence_candidates( op, f->f_desc, ids );
  93                 break;
  94
  95         case LDAP_FILTER_EQUALITY:
  96 #ifdef NEW_LOGGING
  97                 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tEQUALITY\n", 0, 0, 0 );
  98 #else
  99                 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
 100 #endif
 101                 rc = equality_candidates( op, f->f_ava, ids, tmp );
 102                 break;
 103
 104         case LDAP_FILTER_APPROX:
 105 #ifdef NEW_LOGGING
 106                 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tAPPROX\n", 0, 0, 0 );
 107 #else
 108                 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
 109 #endif
 110                 rc = approx_candidates( op, f->f_ava, ids, tmp );
 111                 break;
 112
 113         case LDAP_FILTER_SUBSTRINGS:
 114 #ifdef NEW_LOGGING
 115                 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tSUBSTRINGS\n", 0, 0, 0 );
 116 #else
 117                 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
 118 #endif
 119                 rc = substring_candidates( op, f->f_sub, ids, tmp );
 120                 break;
 121
 122         case LDAP_FILTER_GE:
 123                 /* no GE index, use pres */
 124 #ifdef NEW_LOGGING
 125                 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tGE\n", 0, 0, 0 );
 126 #else
 127                 Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
 128 #endif
 129                 rc = presence_candidates( op, f->f_ava->aa_desc, ids );
 130                 break;
 131
 132         case LDAP_FILTER_LE:
 133                 /* no LE index, use pres */
 134 #ifdef NEW_LOGGING
 135                 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tLE\n", 0, 0, 0 );
 136 #else
 137                 Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
 138 #endif
 139                 rc = presence_candidates( op, f->f_ava->aa_desc, ids );
 140                 break;
 141
 142         case LDAP_FILTER_NOT:
 143                 /* no indexing to support NOT filters */
 144 #ifdef NEW_LOGGING
 145                 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tNOT\n",0, 0, 0 );
 146 #else
 147                 Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
 148 #endif
 149                 { struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 150                 BDB_IDL_ALL( bdb, ids );
 151                 }
 152                 break;
 153
 154         case LDAP_FILTER_AND:
 155 #ifdef NEW_LOGGING
 156                 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tAND\n", 0, 0, 0 );
 157 #else
 158                 Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
 159 #endif
 160                 rc = list_candidates( op,
 161                         f->f_and, LDAP_FILTER_AND, ids, tmp, stack );
 162                 break;
 163
 164         case LDAP_FILTER_OR:
 165 #ifdef NEW_LOGGING
 166                 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tOR\n", 0, 0, 0 );
 167 #else
 168                 Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
 169 #endif
 170                 rc = list_candidates( op,
 171                         f->f_or, LDAP_FILTER_OR, ids, tmp, stack );
 172                 break;
 173
 174         default:
 175 #ifdef NEW_LOGGING
 176                 LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tUNKNOWN\n", 0, 0, 0 );
 177 #else
 178                 Debug( LDAP_DEBUG_FILTER, "\tUNKNOWN %lu\n",
 179                         (unsigned long) f->f_choice, 0, 0 );
 180 #endif
 181                 /* Must not return NULL, otherwise extended filters break */
 182                 { struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 183                 BDB_IDL_ALL( bdb, ids );
 184                 }
 185         }
 186
 187 #ifdef NEW_LOGGING
 188         LDAP_LOG ( INDEX, RESULTS,
 189                 "<= bdb_filter_candidates: id=%ld first=%ld last=%ld\n",
 190                 (long)ids[0], (long)BDB_IDL_FIRST( ids ), (long) BDB_IDL_LAST( ids ));
 191 #else
 192         Debug( LDAP_DEBUG_FILTER,
 193                 "<= bdb_filter_candidates: id=%ld first=%ld last=%ld\n",
 194                 (long) ids[0],
 195                 (long) BDB_IDL_FIRST( ids ),
 196                 (long) BDB_IDL_LAST( ids ) );
 197 #endif
 198
 199         return rc;
 200 }
 201
 202 static int
 203 list_candidates(
 204         Operation *op,
 205         Filter  *flist,
 206         int             ftype,
 207         ID *ids,
 208         ID *tmp,
 209         ID *save )
 210 {
 211         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 212         int rc = 0;
 213         Filter  *f;
 214
 215 #ifdef NEW_LOGGING
 216         LDAP_LOG ( INDEX, ARGS, "=> bdb_list_candidates: 0x%x\n", ftype, 0 , 0 );
 217 #else
 218         Debug( LDAP_DEBUG_FILTER, "=> bdb_list_candidates 0x%x\n", ftype, 0, 0 );
 219 #endif
 220
 221         /* Copy so we can propagate pre-computed IDLs */
 222         BDB_IDL_CPY( save, ids );
 223
 224         for ( f = flist; f != NULL; f = f->f_next ) {
 225                 rc = bdb_filter_candidates( op, f, save, tmp,
 226                         save+BDB_IDL_UM_SIZE );
 227
 228                 if ( rc != 0 ) {
 229                         if ( ftype == LDAP_FILTER_AND ) {
 230                                 rc = 0;
 231                                 continue;
 232                         }
 233                         break;
 234                 }
 235
 236
 237                 if ( ftype == LDAP_FILTER_AND ) {
 238                         if ( f == flist ) {
 239                                 BDB_IDL_CPY( ids, save );
 240                         } else {
 241                                 bdb_idl_intersection( ids, save );
 242                         }
 243                         if( BDB_IDL_IS_ZERO( ids ) )
 244                                 break;
 245                 } else {
 246                         if ( f == flist ) {
 247                                 BDB_IDL_CPY( ids, save );
 248                         } else {
 249                                 bdb_idl_union( ids, save );
 250                         }
 251                 }
 252         }
 253
 254         if( rc == LDAP_SUCCESS ) {
 255 #ifdef NEW_LOGGING
 256                 LDAP_LOG ( INDEX, RESULTS,
 257                         "<= bdb_list_candidates: id=%ld first=%ld last=%ld\n",
 258                         (long) ids[0], (long) BDB_IDL_FIRST( ids ),
 259                         (long) BDB_IDL_LAST( ids ) );
 260 #else
 261                 Debug( LDAP_DEBUG_FILTER,
 262                         "<= bdb_list_candidates: id=%ld first=%ld last=%ld\n",
 263                         (long) ids[0],
 264                         (long) BDB_IDL_FIRST(ids),
 265                         (long) BDB_IDL_LAST(ids) );
 266 #endif
 267
 268         } else {
 269 #ifdef NEW_LOGGING
 270                 LDAP_LOG ( INDEX, ARGS, "<= bdb_list_candidates: rc=%d\n", rc, 0, 0 );
 271 #else
 272                 Debug( LDAP_DEBUG_FILTER,
 273                         "<= bdb_list_candidates: undefined rc=%d\n",
 274                         rc, 0, 0 );
 275 #endif
 276         }
 277
 278         return rc;
 279 }
 280
 281 static int
 282 presence_candidates(
 283         Operation *op,
 284         AttributeDescription *desc,
 285         ID *ids )
 286 {
 287         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 288         DB *db;
 289         int rc;
 290         slap_mask_t mask;
 291         struct berval prefix = {0, NULL};
 292
 293 #ifdef NEW_LOGGING
 294         LDAP_LOG ( INDEX, ENTRY, "=> bdb_presence_candidates (%s)\n",
 295                         desc->ad_cname.bv_val, 0, 0 );
 296 #else
 297         Debug( LDAP_DEBUG_TRACE, "=> bdb_presence_candidates (%s)\n",
 298                         desc->ad_cname.bv_val, 0, 0 );
 299 #endif
 300
 301         if( desc == slap_schema.si_ad_objectClass ) {
 302                 BDB_IDL_ALL( bdb, ids );
 303                 return 0;
 304         }
 305
 306         rc = bdb_index_param( op->o_bd, desc, LDAP_FILTER_PRESENT,
 307                 &db, &mask, &prefix );
 308
 309         if( rc != LDAP_SUCCESS ) {
 310 #ifdef NEW_LOGGING
 311                 LDAP_LOG ( INDEX, RESULTS,
 312                         "<= bdb_presence_candidates: (%s) index_param "
 313                         "returned=%d\n",
 314                         desc->ad_cname.bv_val, rc, 0 );
 315 #else
 316                 Debug( LDAP_DEBUG_TRACE,
 317                         "<= bdb_presence_candidates: (%s) index_param "
 318                         "returned=%d\n",
 319                         desc->ad_cname.bv_val, rc, 0 );
 320 #endif
 321                 return 0;
 322         }
 323
 324         if( db == NULL ) {
 325                 /* not indexed */
 326 #ifdef NEW_LOGGING
 327                 LDAP_LOG(INDEX, RESULTS,
 328                         "<= bdb_presence_candidates: (%s) not indexed\n",
 329                         desc->ad_cname.bv_val, 0, 0 );
 330 #else
 331                 Debug( LDAP_DEBUG_TRACE,
 332                         "<= bdb_presence_candidates: (%s) not indexed\n",
 333                         desc->ad_cname.bv_val, 0, 0 );
 334 #endif
 335                 return 0;
 336         }
 337
 338         if( prefix.bv_val == NULL ) {
 339 #ifdef NEW_LOGGING
 340                 LDAP_LOG(INDEX, RESULTS,
 341                         "<= bdb_presence_candidates: (%s) no prefix\n",
 342                         desc->ad_cname.bv_val, 0, 0 );
 343 #else
 344                 Debug( LDAP_DEBUG_TRACE,
 345                         "<= bdb_presence_candidates: (%s) no prefix\n",
 346                         desc->ad_cname.bv_val, 0, 0 );
 347 #endif
 348                 return 0;
 349         }
 350
 351         rc = bdb_key_read( op->o_bd, db, NULL, &prefix, ids );
 352
 353         if( rc == DB_NOTFOUND ) {
 354                 BDB_IDL_ZERO( ids );
 355                 rc = 0;
 356         } else if( rc != LDAP_SUCCESS ) {
 357 #ifdef NEW_LOGGING
 358                 LDAP_LOG ( INDEX, RESULTS,
 359                         "<= bdb_presence_candidates: (%s) "
 360                         "key read failed (%d)\n",
 361                         desc->ad_cname.bv_val, rc, 0 );
 362 #else
 363                 Debug( LDAP_DEBUG_TRACE,
 364                         "<= bdb_presense_candidates: (%s) "
 365                         "key read failed (%d)\n",
 366                         desc->ad_cname.bv_val, rc, 0 );
 367 #endif
 368                 goto done;
 369         }
 370
 371 #ifdef NEW_LOGGING
 372         LDAP_LOG ( INDEX, RESULTS,
 373                 "<= bdb_presence_candidates: id=%ld first=%ld last=%ld\n",
 374                 (long)ids[0], (long)BDB_IDL_FIRST( ids ), (long)BDB_IDL_LAST( ids ) );
 375 #else
 376         Debug(LDAP_DEBUG_TRACE,
 377                 "<= bdb_presence_candidates: id=%ld first=%ld last=%ld\n",
 378                 (long) ids[0],
 379                 (long) BDB_IDL_FIRST(ids),
 380                 (long) BDB_IDL_LAST(ids) );
 381 #endif
 382
 383 done:
 384         return rc;
 385 }
 386
 387 static int
 388 equality_candidates(
 389         Operation *op,
 390         AttributeAssertion *ava,
 391         ID *ids,
 392         ID *tmp )
 393 {
 394         DB      *db;
 395         int i;
 396         int rc;
 397         slap_mask_t mask;
 398         struct berval prefix = {0, NULL};
 399         struct berval *keys = NULL;
 400         MatchingRule *mr;
 401
 402 #ifdef NEW_LOGGING
 403         LDAP_LOG ( INDEX, ENTRY, "=> bdb_equality_candidates (%s)\n",
 404                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 405 #else
 406         Debug( LDAP_DEBUG_TRACE, "=> bdb_equality_candidates (%s)\n",
 407                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 408 #endif
 409
 410         rc = bdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_EQUALITY,
 411                 &db, &mask, &prefix );
 412
 413         if( rc != LDAP_SUCCESS ) {
 414 #ifdef NEW_LOGGING
 415                 LDAP_LOG ( INDEX, RESULTS,
 416                         "<= bdb_equality_candidates: (%s) "
 417                         "index_param failed (%d)\n",
 418                         ava->aa_desc->ad_cname.bv_val, rc, 0);
 419 #else
 420                 Debug( LDAP_DEBUG_ANY,
 421                         "<= bdb_equality_candidates: (%s) "
 422                         "index_param failed (%d)\n",
 423                         ava->aa_desc->ad_cname.bv_val, rc, 0 );
 424 #endif
 425                 return rc;
 426         }
 427
 428         if ( db == NULL ) {
 429 #ifdef NEW_LOGGING
 430                 LDAP_LOG(INDEX, RESULTS,
 431                         "<= bdb_equality_candidates: (%s) not indexed\n",
 432                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 433 #else
 434                 Debug( LDAP_DEBUG_ANY,
 435                         "<= bdb_equality_candidates: (%s) not indexed\n",
 436                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 437 #endif
 438                 return -1;
 439         }
 440
 441         mr = ava->aa_desc->ad_type->sat_equality;
 442         if( !mr ) {
 443                 return -1;
 444         }
 445
 446         if( !mr->smr_filter ) {
 447                 return -1;
 448         }
 449
 450         rc = (mr->smr_filter)(
 451                 LDAP_FILTER_EQUALITY,
 452                 mask,
 453                 ava->aa_desc->ad_type->sat_syntax,
 454                 mr,
 455                 &prefix,
 456                 &ava->aa_value,
 457                 &keys, op->o_tmpmemctx );
 458
 459         if( rc != LDAP_SUCCESS ) {
 460 #ifdef NEW_LOGGING
 461                 LDAP_LOG ( INDEX, RESULTS,
 462                         "<= bdb_equality_candidates: (%s, %s) "
 463                         "MR filter failed (%d)\n",
 464                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
 465 #else
 466                 Debug( LDAP_DEBUG_TRACE,
 467                         "<= bdb_equality_candidates: (%s, %s) "
 468                         "MR filter failed (%d)\n",
 469                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
 470 #endif
 471                 return rc;
 472         }
 473
 474         if( keys == NULL ) {
 475 #ifdef NEW_LOGGING
 476                 LDAP_LOG ( INDEX, RESULTS,
 477                         "<= bdb_equality_candidates: (%s) no keys\n",
 478                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 479 #else
 480                 Debug( LDAP_DEBUG_TRACE,
 481                         "<= bdb_equality_candidates: (%s) no keys\n",
 482                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 483 #endif
 484                 return 0;
 485         }
 486
 487         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 488                 rc = bdb_key_read( op->o_bd, db, NULL, &keys[i], tmp );
 489
 490                 if( rc == DB_NOTFOUND ) {
 491                         BDB_IDL_ZERO( ids );
 492                         rc = 0;
 493                         break;
 494                 } else if( rc != LDAP_SUCCESS ) {
 495 #ifdef NEW_LOGGING
 496                         LDAP_LOG ( INDEX, RESULTS,
 497                                 "<= bdb_equality_candidates: (%s) "
 498                                 "key read failed (%d)\n",
 499                                 ava->aa_desc->ad_cname.bv_val, rc, 0 );
 500 #else
 501                         Debug( LDAP_DEBUG_TRACE,
 502                                 "<= bdb_equality_candidates: (%s) "
 503                                 "key read failed (%d)\n",
 504                                 ava->aa_desc->ad_cname.bv_val, rc, 0 );
 505 #endif
 506                         break;
 507                 }
 508
 509                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 510 #ifdef NEW_LOGGING
 511                         LDAP_LOG ( INDEX, RESULTS,
 512                                 "<= bdb_equality_candidates: (%s) NULL\n",
 513                                 ava->aa_desc->ad_cname.bv_val, 0, 0);
 514 #else
 515                         Debug( LDAP_DEBUG_TRACE,
 516                                 "<= bdb_equality_candidates: (%s) NULL\n",
 517                                 ava->aa_desc->ad_cname.bv_val, 0, 0 );
 518 #endif
 519                         BDB_IDL_ZERO( ids );
 520                         break;
 521                 }
 522
 523                 if ( i == 0 ) {
 524                         BDB_IDL_CPY( ids, tmp );
 525                 } else {
 526                         bdb_idl_intersection( ids, tmp );
 527                 }
 528
 529                 if( BDB_IDL_IS_ZERO( ids ) )
 530                         break;
 531         }
 532
 533         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 534
 535 #ifdef NEW_LOGGING
 536         LDAP_LOG ( INDEX, RESULTS,
 537                 "<= bdb_equality_candidates: id=%ld first=%ld last=%ld\n",
 538                 (long) ids[0], (long) BDB_IDL_FIRST( ids ),
 539                 (long) BDB_IDL_LAST( ids ) );
 540 #else
 541         Debug( LDAP_DEBUG_TRACE,
 542                 "<= bdb_equality_candidates: id=%ld, first=%ld, last=%ld\n",
 543                 (long) ids[0],
 544                 (long) BDB_IDL_FIRST(ids),
 545                 (long) BDB_IDL_LAST(ids) );
 546 #endif
 547         return( rc );
 548 }
 549
 550
 551 static int
 552 approx_candidates(
 553         Operation *op,
 554         AttributeAssertion *ava,
 555         ID *ids,
 556         ID *tmp )
 557 {
 558         DB      *db;
 559         int i;
 560         int rc;
 561         slap_mask_t mask;
 562         struct berval prefix = {0, NULL};
 563         struct berval *keys = NULL;
 564         MatchingRule *mr;
 565
 566 #ifdef NEW_LOGGING
 567         LDAP_LOG ( INDEX, ENTRY, "=> bdb_approx_candidates (%s)\n",
 568                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 569 #else
 570         Debug( LDAP_DEBUG_TRACE, "=> bdb_approx_candidates (%s)\n",
 571                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 572 #endif
 573
 574         rc = bdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_APPROX,
 575                 &db, &mask, &prefix );
 576
 577         if( rc != LDAP_SUCCESS ) {
 578 #ifdef NEW_LOGGING
 579                 LDAP_LOG ( INDEX, RESULTS,
 580                         "<= bdb_approx_candidates: (%s) "
 581                         "index_param failed (%d)\n",
 582                         ava->aa_desc->ad_cname.bv_val, rc, 0 );
 583 #else
 584                 Debug( LDAP_DEBUG_ANY,
 585                         "<= bdb_approx_candidates: (%s) "
 586                         "index_param failed (%d)\n",
 587                         ava->aa_desc->ad_cname.bv_val, rc, 0 );
 588 #endif
 589                 return rc;
 590         }
 591
 592         if ( db == NULL ) {
 593 #ifdef NEW_LOGGING
 594                 LDAP_LOG(INDEX, RESULTS,
 595                         "<= bdb_approx_candidates: (%s) not indexed\n",
 596                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 597 #else
 598                 Debug( LDAP_DEBUG_ANY,
 599                         "<= bdb_approx_candidates: (%s) not indexed\n",
 600                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 601 #endif
 602                 return -1;
 603         }
 604
 605         mr = ava->aa_desc->ad_type->sat_approx;
 606         if( !mr ) {
 607                 /* no approx matching rule, try equality matching rule */
 608                 mr = ava->aa_desc->ad_type->sat_equality;
 609         }
 610
 611         if( !mr ) {
 612                 return -1;
 613         }
 614
 615         if( !mr->smr_filter ) {
 616                 return -1;
 617         }
 618
 619         rc = (mr->smr_filter)(
 620                 LDAP_FILTER_APPROX,
 621                 mask,
 622                 ava->aa_desc->ad_type->sat_syntax,
 623                 mr,
 624                 &prefix,
 625                 &ava->aa_value,
 626                 &keys, op->o_tmpmemctx );
 627
 628         if( rc != LDAP_SUCCESS ) {
 629 #ifdef NEW_LOGGING
 630                 LDAP_LOG ( INDEX, RESULTS,
 631                         "<= bdb_approx_candidates: (%s, %s) "
 632                         "MR filter failed (%d)\n",
 633                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
 634 #else
 635                 Debug( LDAP_DEBUG_TRACE,
 636                         "<= bdb_approx_candidates: (%s, %s) "
 637                         "MR filter failed (%d)\n",
 638                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
 639 #endif
 640                 return rc;
 641         }
 642
 643         if( keys == NULL ) {
 644 #ifdef NEW_LOGGING
 645                 LDAP_LOG ( INDEX, RESULTS,
 646                         "<= bdb_approx_candidates: (%s) no keys (%s)\n",
 647                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, 0 );
 648 #else
 649                 Debug( LDAP_DEBUG_TRACE,
 650                         "<= bdb_approx_candidates: (%s) no keys (%s)\n",
 651                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, 0 );
 652 #endif
 653                 return 0;
 654         }
 655
 656         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 657                 rc = bdb_key_read( op->o_bd, db, NULL, &keys[i], tmp );
 658
 659                 if( rc == DB_NOTFOUND ) {
 660                         BDB_IDL_ZERO( ids );
 661                         rc = 0;
 662                         break;
 663                 } else if( rc != LDAP_SUCCESS ) {
 664 #ifdef NEW_LOGGING
 665                         LDAP_LOG ( INDEX, RESULTS,
 666                                 "<= bdb_approx_candidates: (%s) "
 667                                 "key read failed (%d)\n",
 668                                 ava->aa_desc->ad_cname.bv_val, rc, 0);
 669 #else
 670                         Debug( LDAP_DEBUG_TRACE,
 671                                 "<= bdb_approx_candidates: (%s) "
 672                                 "key read failed (%d)\n",
 673                                 ava->aa_desc->ad_cname.bv_val, rc, 0 );
 674 #endif
 675                         break;
 676                 }
 677
 678                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 679 #ifdef NEW_LOGGING
 680                         LDAP_LOG ( INDEX, RESULTS,
 681                                 "<= bdb_approx_candidates: (%s) NULL\n",
 682                                 ava->aa_desc->ad_cname.bv_val, 0, 0 );
 683 #else
 684                         Debug( LDAP_DEBUG_TRACE,
 685                                 "<= bdb_approx_candidates: (%s) NULL\n",
 686                                 ava->aa_desc->ad_cname.bv_val, 0, 0 );
 687 #endif
 688                         BDB_IDL_ZERO( ids );
 689                         break;
 690                 }
 691
 692                 if ( i == 0 ) {
 693                         BDB_IDL_CPY( ids, tmp );
 694                 } else {
 695                         bdb_idl_intersection( ids, tmp );
 696                 }
 697
 698                 if( BDB_IDL_IS_ZERO( ids ) )
 699                         break;
 700         }
 701
 702         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 703
 704 #ifdef NEW_LOGGING
 705         LDAP_LOG ( INDEX, RESULTS,
 706                 "<= bdb_approx_candidates: id=%ld first=%ld last=%ld\n",
 707                 (long) ids[0], (long) BDB_IDL_FIRST( ids ),
 708                 (long) BDB_IDL_LAST( ids ) );
 709 #else
 710         Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates %ld, first=%ld, last=%ld\n",
 711                 (long) ids[0],
 712                 (long) BDB_IDL_FIRST(ids),
 713                 (long) BDB_IDL_LAST(ids) );
 714 #endif
 715         return( rc );
 716 }
 717
 718 static int
 719 substring_candidates(
 720         Operation *op,
 721         SubstringsAssertion     *sub,
 722         ID *ids,
 723         ID *tmp )
 724 {
 725         DB      *db;
 726         int i;
 727         int rc;
 728         slap_mask_t mask;
 729         struct berval prefix = {0, NULL};
 730         struct berval *keys = NULL;
 731         MatchingRule *mr;
 732
 733 #ifdef NEW_LOGGING
 734         LDAP_LOG ( INDEX, ENTRY, "=> bdb_substring_candidates (%s)\n",
 735                         sub->sa_desc->ad_cname.bv_val, 0, 0 );
 736 #else
 737         Debug( LDAP_DEBUG_TRACE, "=> bdb_substring_candidates (%s)\n",
 738                         sub->sa_desc->ad_cname.bv_val, 0, 0 );
 739 #endif
 740
 741         rc = bdb_index_param( op->o_bd, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
 742                 &db, &mask, &prefix );
 743
 744         if( rc != LDAP_SUCCESS ) {
 745 #ifdef NEW_LOGGING
 746                 LDAP_LOG ( INDEX, RESULTS,
 747                         "<= bdb_substring_candidates: (%s) "
 748                         "index_param failed (%d)\n",
 749                         sub->sa_desc->ad_cname.bv_val, rc, 0);
 750 #else
 751                 Debug( LDAP_DEBUG_ANY,
 752                         "<= bdb_substring_candidates: (%s) "
 753                         "index_param failed (%d)\n",
 754                         sub->sa_desc->ad_cname.bv_val, rc, 0 );
 755 #endif
 756                 return rc;
 757         }
 758
 759         if ( db == NULL ) {
 760 #ifdef NEW_LOGGING
 761                 LDAP_LOG ( INDEX, RESULTS,
 762                         "<= bdb_substring_candidates: (%s) not indexed\n",
 763                         sub->sa_desc->ad_cname.bv_val, 0, 0 );
 764 #else
 765                 Debug( LDAP_DEBUG_ANY,
 766                         "<= bdb_substring_candidates: (%s) not indexed\n",
 767                         sub->sa_desc->ad_cname.bv_val, 0, 0 );
 768 #endif
 769                 return -1;
 770         }
 771
 772         mr = sub->sa_desc->ad_type->sat_substr;
 773
 774         if( !mr ) {
 775                 return -1;
 776         }
 777
 778         if( !mr->smr_filter ) {
 779                 return -1;
 780         }
 781
 782         rc = (mr->smr_filter)(
 783                 LDAP_FILTER_SUBSTRINGS,
 784                 mask,
 785                 sub->sa_desc->ad_type->sat_syntax,
 786                 mr,
 787                 &prefix,
 788                 sub,
 789                 &keys, op->o_tmpmemctx );
 790
 791         if( rc != LDAP_SUCCESS ) {
 792 #ifdef NEW_LOGGING
 793                 LDAP_LOG ( INDEX, RESULTS,
 794                         "<= bdb_substring_candidates: (%s) "
 795                         "MR filter failed (%d)\n",
 796                         sub->sa_desc->ad_cname.bv_val, rc, 0 );
 797 #else
 798                 Debug( LDAP_DEBUG_TRACE,
 799                         "<= bdb_substring_candidates: (%s) "
 800                         "MR filter failed (%d)\n",
 801                         sub->sa_desc->ad_cname.bv_val, rc, 0 );
 802 #endif
 803                 return rc;
 804         }
 805
 806         if( keys == NULL ) {
 807 #ifdef NEW_LOGGING
 808                 LDAP_LOG ( INDEX, RESULTS,
 809                         "<= bdb_substring_candidates: (0x%04lx) no keys (%s)\n",
 810                         mask, sub->sa_desc->ad_cname.bv_val, 0 );
 811 #else
 812                 Debug( LDAP_DEBUG_TRACE,
 813                         "<= bdb_substring_candidates: (0x%04lx) no keys (%s)\n",
 814                         mask, sub->sa_desc->ad_cname.bv_val, 0 );
 815 #endif
 816                 return 0;
 817         }
 818
 819         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 820                 rc = bdb_key_read( op->o_bd, db, NULL, &keys[i], tmp );
 821
 822                 if( rc == DB_NOTFOUND ) {
 823                         BDB_IDL_ZERO( ids );
 824                         rc = 0;
 825                         break;
 826                 } else if( rc != LDAP_SUCCESS ) {
 827 #ifdef NEW_LOGGING
 828                         LDAP_LOG ( INDEX, RESULTS,
 829                                 "<= bdb_substring_candidates: (%s) "
 830                                 "key read failed (%d)\n",
 831                                 sub->sa_desc->ad_cname.bv_val, rc, 0 );
 832 #else
 833                         Debug( LDAP_DEBUG_TRACE,
 834                                 "<= bdb_substring_candidates: (%s) "
 835                                 "key read failed (%d)\n",
 836                                 sub->sa_desc->ad_cname.bv_val, rc, 0 );
 837 #endif
 838                         break;
 839                 }
 840
 841                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 842 #ifdef NEW_LOGGING
 843                         LDAP_LOG ( INDEX, RESULTS,
 844                                 "<= bdb_substring_candidates: (%s) NULL\n",
 845                                 sub->sa_desc->ad_cname.bv_val, 0, 0 );
 846 #else
 847                         Debug( LDAP_DEBUG_TRACE,
 848                                 "<= bdb_substring_candidates: (%s) NULL\n",
 849                                 sub->sa_desc->ad_cname.bv_val, 0, 0 );
 850 #endif
 851                         BDB_IDL_ZERO( ids );
 852                         break;
 853                 }
 854
 855                 if ( i == 0 ) {
 856                         BDB_IDL_CPY( ids, tmp );
 857                 } else {
 858                         bdb_idl_intersection( ids, tmp );
 859                 }
 860
 861                 if( BDB_IDL_IS_ZERO( ids ) )
 862                         break;
 863         }
 864
 865         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 866
 867 #ifdef NEW_LOGGING
 868         LDAP_LOG ( INDEX, RESULTS,
 869                 "<= bdb_substring_candidates: id=%ld first=%ld last=%ld\n",
 870                 (long) ids[0], (long) BDB_IDL_FIRST( ids ),
 871                 (long) BDB_IDL_LAST( ids ) );
 872 #else
 873         Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates: %ld, first=%ld, last=%ld\n",
 874                 (long) ids[0],
 875                 (long) BDB_IDL_FIRST(ids),
 876                 (long) BDB_IDL_LAST(ids) );
 877 #endif
 878         return( 0 );
 879 }
 880