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 (%s)\n",
 281                         desc->ad_cname.bv_val, 0, 0 );
 282 #else
 283         Debug( LDAP_DEBUG_TRACE, "=> bdb_presence_candidates (%s)\n",
 284                         desc->ad_cname.bv_val, 0, 0 );
 285 #endif
 286
 287         if( desc == slap_schema.si_ad_objectClass ) {
 288                 BDB_IDL_ALL( bdb, ids );
 289                 return 0;
 290         }
 291
 292         rc = bdb_index_param( be, desc, LDAP_FILTER_PRESENT,
 293                 &db, &mask, &prefix );
 294
 295         if( rc != LDAP_SUCCESS ) {
 296 #ifdef NEW_LOGGING
 297                 LDAP_LOG ( INDEX, RESULTS,
 298                         "<= bdb_presence_candidates: (%s) index_param "
 299                         "returned=%d\n",
 300                         desc->ad_cname.bv_val, rc, 0 );
 301 #else
 302                 Debug( LDAP_DEBUG_TRACE,
 303                         "<= bdb_presence_candidates: (%s) index_param "
 304                         "returned=%d\n",
 305                         desc->ad_cname.bv_val, rc, 0 );
 306 #endif
 307                 return 0;
 308         }
 309
 310         if( db == NULL ) {
 311                 /* not indexed */
 312 #ifdef NEW_LOGGING
 313                 LDAP_LOG(INDEX, RESULTS,
 314                         "<= bdb_presence_candidates: (%s) not indexed\n",
 315                         desc->ad_cname.bv_val, 0, 0 );
 316 #else
 317                 Debug( LDAP_DEBUG_TRACE,
 318                         "<= bdb_presence_candidates: (%s) not indexed\n",
 319                         desc->ad_cname.bv_val, 0, 0 );
 320 #endif
 321                 return 0;
 322         }
 323
 324         if( prefix.bv_val == NULL ) {
 325 #ifdef NEW_LOGGING
 326                 LDAP_LOG(INDEX, RESULTS,
 327                         "<= bdb_presence_candidates: (%s) no prefix\n",
 328                         desc->ad_cname.bv_val, 0, 0 );
 329 #else
 330                 Debug( LDAP_DEBUG_TRACE,
 331                         "<= bdb_presence_candidates: (%s) no prefix\n",
 332                         desc->ad_cname.bv_val, 0, 0 );
 333 #endif
 334                 return 0;
 335         }
 336
 337         rc = bdb_key_read( be, db, NULL, &prefix, ids );
 338
 339         if( rc == DB_NOTFOUND ) {
 340                 BDB_IDL_ZERO( ids );
 341                 rc = 0;
 342         } else if( rc != LDAP_SUCCESS ) {
 343 #ifdef NEW_LOGGING
 344                 LDAP_LOG ( INDEX, RESULTS,
 345                         "<= bdb_presence_candidates: (%s) "
 346                         "key read failed (%d)\n",
 347                         desc->ad_cname.bv_val, rc, 0 );
 348 #else
 349                 Debug( LDAP_DEBUG_TRACE,
 350                         "<= bdb_presense_candidates: (%s) "
 351                         "key read failed (%d)\n",
 352                         desc->ad_cname.bv_val, rc, 0 );
 353 #endif
 354                 goto done;
 355         }
 356
 357 #ifdef NEW_LOGGING
 358         LDAP_LOG ( INDEX, RESULTS,
 359                 "<= bdb_presence_candidates: id=%ld first=%ld last=%ld\n",
 360                 (long)ids[0], (long)BDB_IDL_FIRST( ids ), (long)BDB_IDL_LAST( ids ) );
 361 #else
 362         Debug(LDAP_DEBUG_TRACE,
 363                 "<= bdb_presence_candidates: id=%ld first=%ld last=%ld\n",
 364                 (long) ids[0],
 365                 (long) BDB_IDL_FIRST(ids),
 366                 (long) BDB_IDL_LAST(ids) );
 367 #endif
 368
 369 done:
 370         return rc;
 371 }
 372
 373 static int
 374 equality_candidates(
 375         Backend *be,
 376         AttributeAssertion *ava,
 377         ID *ids,
 378         ID *tmp )
 379 {
 380         DB      *db;
 381         int i;
 382         int rc;
 383         slap_mask_t mask;
 384         struct berval prefix = {0, NULL};
 385         struct berval *keys = NULL;
 386         MatchingRule *mr;
 387
 388 #ifdef NEW_LOGGING
 389         LDAP_LOG ( INDEX, ENTRY, "=> bdb_equality_candidates (%s)\n",
 390                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 391 #else
 392         Debug( LDAP_DEBUG_TRACE, "=> bdb_equality_candidates (%s)\n",
 393                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 394 #endif
 395
 396         rc = bdb_index_param( be, ava->aa_desc, LDAP_FILTER_EQUALITY,
 397                 &db, &mask, &prefix );
 398
 399         if( rc != LDAP_SUCCESS ) {
 400 #ifdef NEW_LOGGING
 401                 LDAP_LOG ( INDEX, RESULTS,
 402                         "<= bdb_equality_candidates: (%s) "
 403                         "index_param failed (%d)\n",
 404                         ava->aa_desc->ad_cname.bv_val, rc, 0);
 405 #else
 406                 Debug( LDAP_DEBUG_ANY,
 407                         "<= bdb_equality_candidates: (%s) "
 408                         "index_param failed (%d)\n",
 409                         ava->aa_desc->ad_cname.bv_val, rc, 0 );
 410 #endif
 411                 return rc;
 412         }
 413
 414         if ( db == NULL ) {
 415 #ifdef NEW_LOGGING
 416                 LDAP_LOG(INDEX, RESULTS,
 417                         "<= bdb_equality_candidates: (%s) not indexed\n",
 418                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 419 #else
 420                 Debug( LDAP_DEBUG_ANY,
 421                         "<= bdb_equality_candidates: (%s) not indexed\n",
 422                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 423 #endif
 424                 return -1;
 425         }
 426
 427         mr = ava->aa_desc->ad_type->sat_equality;
 428         if( !mr ) {
 429                 return -1;
 430         }
 431
 432         if( !mr->smr_filter ) {
 433                 return -1;
 434         }
 435
 436         rc = (mr->smr_filter)(
 437                 LDAP_FILTER_EQUALITY,
 438                 mask,
 439                 ava->aa_desc->ad_type->sat_syntax,
 440                 mr,
 441                 &prefix,
 442                 &ava->aa_value,
 443                 &keys );
 444
 445         if( rc != LDAP_SUCCESS ) {
 446 #ifdef NEW_LOGGING
 447                 LDAP_LOG ( INDEX, RESULTS,
 448                         "<= bdb_equality_candidates: (%s, %s) "
 449                         "MR filter failed (%d)\n",
 450                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
 451 #else
 452                 Debug( LDAP_DEBUG_TRACE,
 453                         "<= bdb_equality_candidates: (%s, %s) "
 454                         "MR filter failed (%d)\n",
 455                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
 456 #endif
 457                 return rc;
 458         }
 459
 460         if( keys == NULL ) {
 461 #ifdef NEW_LOGGING
 462                 LDAP_LOG ( INDEX, RESULTS,
 463                         "<= bdb_equality_candidates: (%s) no keys\n",
 464                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 465 #else
 466                 Debug( LDAP_DEBUG_TRACE,
 467                         "<= bdb_equality_candidates: (%s) no keys\n",
 468                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 469 #endif
 470                 return 0;
 471         }
 472
 473         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 474                 rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
 475
 476                 if( rc == DB_NOTFOUND ) {
 477                         BDB_IDL_ZERO( ids );
 478                         rc = 0;
 479                 } else if( rc != LDAP_SUCCESS ) {
 480 #ifdef NEW_LOGGING
 481                         LDAP_LOG ( INDEX, RESULTS,
 482                                 "<= bdb_equality_candidates: (%s) "
 483                                 "key read failed (%d)\n",
 484                                 ava->aa_desc->ad_cname.bv_val, rc, 0 );
 485 #else
 486                         Debug( LDAP_DEBUG_TRACE,
 487                                 "<= bdb_equality_candidates: (%s) "
 488                                 "key read failed (%d)\n",
 489                                 ava->aa_desc->ad_cname.bv_val, rc, 0 );
 490 #endif
 491                         break;
 492                 }
 493
 494                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 495 #ifdef NEW_LOGGING
 496                         LDAP_LOG ( INDEX, RESULTS,
 497                                 "<= bdb_equality_candidates: (%s) NULL\n",
 498                                 ava->aa_desc->ad_cname.bv_val, 0, 0);
 499 #else
 500                         Debug( LDAP_DEBUG_TRACE,
 501                                 "<= bdb_equality_candidates: (%s) NULL\n",
 502                                 ava->aa_desc->ad_cname.bv_val, 0, 0 );
 503 #endif
 504                         BDB_IDL_ZERO( ids );
 505                         break;
 506                 }
 507
 508                 bdb_idl_intersection( ids, tmp );
 509
 510                 if( BDB_IDL_IS_ZERO( ids ) )
 511                         break;
 512         }
 513
 514         ber_bvarray_free( keys );
 515
 516 #ifdef NEW_LOGGING
 517         LDAP_LOG ( INDEX, RESULTS,
 518                 "<= bdb_equality_candidates: id=%ld first=%ld last=%ld\n",
 519                 (long) ids[0], (long) BDB_IDL_FIRST( ids ),
 520                 (long) BDB_IDL_LAST( ids ) );
 521 #else
 522         Debug( LDAP_DEBUG_TRACE,
 523                 "<= bdb_equality_candidates: id=%ld, first=%ld, last=%ld\n",
 524                 (long) ids[0],
 525                 (long) BDB_IDL_FIRST(ids),
 526                 (long) BDB_IDL_LAST(ids) );
 527 #endif
 528         return( rc );
 529 }
 530
 531
 532 static int
 533 approx_candidates(
 534         Backend *be,
 535         AttributeAssertion *ava,
 536         ID *ids,
 537         ID *tmp )
 538 {
 539         DB      *db;
 540         int i;
 541         int rc;
 542         slap_mask_t mask;
 543         struct berval prefix = {0, NULL};
 544         struct berval *keys = NULL;
 545         MatchingRule *mr;
 546
 547 #ifdef NEW_LOGGING
 548         LDAP_LOG ( INDEX, ENTRY, "=> bdb_approx_candidates (%s)\n",
 549                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 550 #else
 551         Debug( LDAP_DEBUG_TRACE, "=> bdb_approx_candidates (%s)\n",
 552                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 553 #endif
 554
 555         rc = bdb_index_param( be, ava->aa_desc, LDAP_FILTER_APPROX,
 556                 &db, &mask, &prefix );
 557
 558         if( rc != LDAP_SUCCESS ) {
 559 #ifdef NEW_LOGGING
 560                 LDAP_LOG ( INDEX, RESULTS,
 561                         "<= bdb_approx_candidates: (%s) "
 562                         "index_param failed (%d)\n",
 563                         ava->aa_desc->ad_cname.bv_val, rc, 0 );
 564 #else
 565                 Debug( LDAP_DEBUG_ANY,
 566                         "<= bdb_approx_candidates: (%s) "
 567                         "index_param failed (%d)\n",
 568                         ava->aa_desc->ad_cname.bv_val, rc, 0 );
 569 #endif
 570                 return rc;
 571         }
 572
 573         if ( db == NULL ) {
 574 #ifdef NEW_LOGGING
 575                 LDAP_LOG(INDEX, RESULTS,
 576                         "<= bdb_approx_candidates: (%s) not indexed\n",
 577                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 578 #else
 579                 Debug( LDAP_DEBUG_ANY,
 580                         "<= bdb_approx_candidates: (%s) not indexed\n",
 581                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 582 #endif
 583                 return -1;
 584         }
 585
 586         mr = ava->aa_desc->ad_type->sat_approx;
 587         if( !mr ) {
 588                 /* no approx matching rule, try equality matching rule */
 589                 mr = ava->aa_desc->ad_type->sat_equality;
 590         }
 591
 592         if( !mr ) {
 593                 return -1;
 594         }
 595
 596         if( !mr->smr_filter ) {
 597                 return -1;
 598         }
 599
 600         rc = (mr->smr_filter)(
 601                 LDAP_FILTER_APPROX,
 602                 mask,
 603                 ava->aa_desc->ad_type->sat_syntax,
 604                 mr,
 605                 &prefix,
 606                 &ava->aa_value,
 607                 &keys );
 608
 609         if( rc != LDAP_SUCCESS ) {
 610 #ifdef NEW_LOGGING
 611                 LDAP_LOG ( INDEX, RESULTS,
 612                         "<= bdb_approx_candidates: (%s, %s) "
 613                         "MR filter failed (%d)\n",
 614                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
 615 #else
 616                 Debug( LDAP_DEBUG_TRACE,
 617                         "<= bdb_approx_candidates: (%s, %s) "
 618                         "MR filter failed (%d)\n",
 619                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
 620 #endif
 621                 return rc;
 622         }
 623
 624         if( keys == NULL ) {
 625 #ifdef NEW_LOGGING
 626                 LDAP_LOG ( INDEX, RESULTS,
 627                         "<= bdb_approx_candidates: (%s) no keys (%s)\n",
 628                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, 0 );
 629 #else
 630                 Debug( LDAP_DEBUG_TRACE,
 631                         "<= bdb_approx_candidates: (%s) no keys (%s)\n",
 632                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, 0 );
 633 #endif
 634                 return 0;
 635         }
 636
 637         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 638                 rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
 639
 640                 if( rc == DB_NOTFOUND ) {
 641                         BDB_IDL_ZERO( ids );
 642                         rc = 0;
 643                         break;
 644                 } else if( rc != LDAP_SUCCESS ) {
 645 #ifdef NEW_LOGGING
 646                         LDAP_LOG ( INDEX, RESULTS,
 647                                 "<= bdb_approx_candidates: (%s) "
 648                                 "key read failed (%d)\n",
 649                                 ava->aa_desc->ad_cname.bv_val, rc, 0);
 650 #else
 651                         Debug( LDAP_DEBUG_TRACE,
 652                                 "<= bdb_approx_candidates: (%s) "
 653                                 "key read failed (%d)\n",
 654                                 ava->aa_desc->ad_cname.bv_val, rc, 0 );
 655 #endif
 656                         break;
 657                 }
 658
 659                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 660 #ifdef NEW_LOGGING
 661                         LDAP_LOG ( INDEX, RESULTS,
 662                                 "<= bdb_approx_candidates: (%s) NULL\n",
 663                                 ava->aa_desc->ad_cname.bv_val, 0, 0 );
 664 #else
 665                         Debug( LDAP_DEBUG_TRACE,
 666                                 "<= bdb_approx_candidates: (%s) NULL\n",
 667                                 ava->aa_desc->ad_cname.bv_val, 0, 0 );
 668 #endif
 669                         BDB_IDL_ZERO( ids );
 670                         break;
 671                 }
 672
 673                 bdb_idl_intersection( ids, tmp );
 674
 675                 if( BDB_IDL_IS_ZERO( ids ) )
 676                         break;
 677         }
 678
 679         ber_bvarray_free( keys );
 680
 681 #ifdef NEW_LOGGING
 682         LDAP_LOG ( INDEX, RESULTS,
 683                 "<= bdb_approx_candidates: id=%ld first=%ld last=%ld\n",
 684                 (long) ids[0], (long) BDB_IDL_FIRST( ids ),
 685                 (long) BDB_IDL_LAST( ids ) );
 686 #else
 687         Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates %ld, first=%ld, last=%ld\n",
 688                 (long) ids[0],
 689                 (long) BDB_IDL_FIRST(ids),
 690                 (long) BDB_IDL_LAST(ids) );
 691 #endif
 692         return( rc );
 693 }
 694
 695 static int
 696 substring_candidates(
 697         Backend *be,
 698         SubstringsAssertion     *sub,
 699         ID *ids,
 700         ID *tmp )
 701 {
 702         DB      *db;
 703         int i;
 704         int rc;
 705         slap_mask_t mask;
 706         struct berval prefix = {0, NULL};
 707         struct berval *keys = NULL;
 708         MatchingRule *mr;
 709
 710 #ifdef NEW_LOGGING
 711         LDAP_LOG ( INDEX, ENTRY, "=> bdb_substring_candidates (%s)\n",
 712                         sub->sa_desc->ad_cname.bv_val, 0, 0 );
 713 #else
 714         Debug( LDAP_DEBUG_TRACE, "=> bdb_substring_candidates (%s)\n",
 715                         sub->sa_desc->ad_cname.bv_val, 0, 0 );
 716 #endif
 717
 718         rc = bdb_index_param( be, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
 719                 &db, &mask, &prefix );
 720
 721         if( rc != LDAP_SUCCESS ) {
 722 #ifdef NEW_LOGGING
 723                 LDAP_LOG ( INDEX, RESULTS,
 724                         "<= bdb_substring_candidates: (%s) "
 725                         "index_param failed (%d)\n",
 726                         sub->sa_desc->ad_cname.bv_val, rc, 0);
 727 #else
 728                 Debug( LDAP_DEBUG_ANY,
 729                         "<= bdb_substring_candidates: (%s) "
 730                         "index_param failed (%d)\n",
 731                         sub->sa_desc->ad_cname.bv_val, rc, 0 );
 732 #endif
 733                 return rc;
 734         }
 735
 736         if ( db == NULL ) {
 737 #ifdef NEW_LOGGING
 738                 LDAP_LOG ( INDEX, RESULTS,
 739                         "<= bdb_substring_candidates: (%s) not indexed\n",
 740                         sub->sa_desc->ad_cname.bv_val, 0, 0 );
 741 #else
 742                 Debug( LDAP_DEBUG_ANY,
 743                         "<= bdb_substring_candidates: (%s) not indexed\n",
 744                         sub->sa_desc->ad_cname.bv_val, 0, 0 );
 745 #endif
 746                 return -1;
 747         }
 748
 749         mr = sub->sa_desc->ad_type->sat_substr;
 750
 751         if( !mr ) {
 752                 return -1;
 753         }
 754
 755         if( !mr->smr_filter ) {
 756                 return -1;
 757         }
 758
 759         rc = (mr->smr_filter)(
 760                 LDAP_FILTER_SUBSTRINGS,
 761                 mask,
 762                 sub->sa_desc->ad_type->sat_syntax,
 763                 mr,
 764                 &prefix,
 765                 sub,
 766                 &keys );
 767
 768         if( rc != LDAP_SUCCESS ) {
 769 #ifdef NEW_LOGGING
 770                 LDAP_LOG ( INDEX, RESULTS,
 771                         "<= bdb_substring_candidates: (%s) "
 772                         "MR filter failed (%d)\n",
 773                         sub->sa_desc->ad_cname.bv_val, rc, 0 );
 774 #else
 775                 Debug( LDAP_DEBUG_TRACE,
 776                         "<= bdb_substring_candidates: (%s) "
 777                         "MR filter failed (%d)\n",
 778                         sub->sa_desc->ad_cname.bv_val, rc, 0 );
 779 #endif
 780                 return rc;
 781         }
 782
 783         if( keys == NULL ) {
 784 #ifdef NEW_LOGGING
 785                 LDAP_LOG ( INDEX, RESULTS,
 786                         "<= bdb_substring_candidates: (0x%04lx) no keys (%s)\n",
 787                         mask, sub->sa_desc->ad_cname.bv_val, 0 );
 788 #else
 789                 Debug( LDAP_DEBUG_TRACE,
 790                         "<= bdb_substring_candidates: (0x%04lx) no keys (%s)\n",
 791                         mask, sub->sa_desc->ad_cname.bv_val, 0 );
 792 #endif
 793                 return 0;
 794         }
 795
 796         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 797                 rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
 798
 799                 if( rc == DB_NOTFOUND ) {
 800                         BDB_IDL_ZERO( ids );
 801                         rc = 0;
 802                         break;
 803                 } else if( rc != LDAP_SUCCESS ) {
 804 #ifdef NEW_LOGGING
 805                         LDAP_LOG ( INDEX, RESULTS,
 806                                 "<= bdb_substring_candidates: (%s) "
 807                                 "key read failed (%d)\n",
 808                                 sub->sa_desc->ad_cname.bv_val, rc, 0 );
 809 #else
 810                         Debug( LDAP_DEBUG_TRACE,
 811                                 "<= bdb_substring_candidates: (%s) "
 812                                 "key read failed (%d)\n",
 813                                 sub->sa_desc->ad_cname.bv_val, rc, 0 );
 814 #endif
 815                         break;
 816                 }
 817
 818                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 819 #ifdef NEW_LOGGING
 820                         LDAP_LOG ( INDEX, RESULTS,
 821                                 "<= bdb_substring_candidates: (%s) NULL\n",
 822                                 sub->sa_desc->ad_cname.bv_val, 0, 0 );
 823 #else
 824                         Debug( LDAP_DEBUG_TRACE,
 825                                 "<= bdb_substring_candidates: (%s) NULL\n",
 826                                 sub->sa_desc->ad_cname.bv_val, 0, 0 );
 827 #endif
 828                         BDB_IDL_ZERO( ids );
 829                         break;
 830                 }
 831
 832                 bdb_idl_intersection( ids, tmp );
 833
 834                 if( BDB_IDL_IS_ZERO( ids ) )
 835                         break;
 836         }
 837
 838         ber_bvarray_free( keys );
 839
 840 #ifdef NEW_LOGGING
 841         LDAP_LOG ( INDEX, RESULTS,
 842                 "<= bdb_substring_candidates: id=%ld first=%ld last=%ld\n",
 843                 (long) ids[0], (long) BDB_IDL_FIRST( ids ),
 844                 (long) BDB_IDL_LAST( ids ) );
 845 #else
 846         Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates: %ld, first=%ld, last=%ld\n",
 847                 (long) ids[0],
 848                 (long) BDB_IDL_FIRST(ids),
 849                 (long) BDB_IDL_LAST(ids) );
 850 #endif
 851         return( 0 );
 852 }
 853