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