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