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