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