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