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