git.sur5r.net Git - openldap/blob - servers/slapd/back-ldbm/filterindex.c

   1 /* filterindex.c - generate the list of candidate entries from a filter */
   2 /* $OpenLDAP$ */
   3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
   4  *
   5  * Copyright 1998-2004 The OpenLDAP Foundation.
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted only as authorized by the OpenLDAP
  10  * Public License.
  11  *
  12  * A copy of this license is available in the file LICENSE in the
  13  * top-level directory of the distribution or, alternatively, at
  14  * <http://www.OpenLDAP.org/license.html>.
  15  */
  16
  17 #include "portable.h"
  18
  19 #include <stdio.h>
  20
  21 #include <ac/socket.h>
  22 #include <ac/string.h>
  23
  24 #include "slap.h"
  25 #include "back-ldbm.h"
  26
  27 static ID_BLOCK *presence_candidates(
  28         Operation *op,
  29         AttributeDescription *desc );
  30 static ID_BLOCK *equality_candidates(
  31         Operation *op, AttributeAssertion *ava );
  32 static ID_BLOCK *approx_candidates(
  33         Operation *op, AttributeAssertion *ava );
  34 static ID_BLOCK *substring_candidates(
  35         Operation *op,
  36         SubstringsAssertion *sub );
  37 static ID_BLOCK *list_candidates(
  38         Operation *op,
  39         Filter *flist,
  40         int ftype );
  41
  42 ID_BLOCK *
  43 filter_candidates(
  44     Operation   *op,
  45     Filter      *f
  46 )
  47 {
  48         char *sub = "SUBTREE";
  49         ID_BLOCK        *result;
  50
  51 #ifdef NEW_LOGGING
  52         LDAP_LOG( FILTER, ENTRY, "filter_candidates: enter\n", 0, 0, 0 );
  53 #else
  54         Debug( LDAP_DEBUG_TRACE, "=> filter_candidates\n", 0, 0, 0 );
  55 #endif
  56
  57
  58         result = NULL;
  59         switch ( f->f_choice ) {
  60         case SLAPD_FILTER_COMPUTED:
  61                 switch( f->f_result ) {
  62                 case SLAPD_COMPARE_UNDEFINED:
  63                 /* This technically is not the same as FALSE, but it
  64                  * certainly will produce no matches.
  65                  */
  66                 /* FALLTHRU */
  67                 case LDAP_COMPARE_FALSE:
  68                         result = NULL;
  69                         break;
  70                 case LDAP_COMPARE_TRUE:
  71                         result = idl_allids( op->o_bd );
  72                         break;
  73                 }
  74                 break;
  75
  76         case SLAPD_FILTER_DN_ONE:
  77 #ifdef NEW_LOGGING
  78                 LDAP_LOG( FILTER, DETAIL1,
  79                            "filter_candidates:  DN ONE (%s)\n", f->f_dn, 0, 0 );
  80 #else
  81                 Debug( LDAP_DEBUG_FILTER, "\tDN ONE\n", 0, 0, 0 );
  82 #endif
  83
  84                 /* an error is treated as an empty list */
  85                 if ( dn2idl( op->o_bd, f->f_dn, DN_ONE_PREFIX, &result ) != 0
  86                                 && result != NULL ) {
  87                         idl_free( result );
  88                         result = NULL;
  89                 }
  90                 break;
  91
  92 #ifdef SLAPD_FILTER_DN_CHILDREN
  93         case SLAPD_FILTER_DN_CHILDREN:
  94                 sub = "CHILDREN";
  95 #endif
  96         case SLAPD_FILTER_DN_SUBTREE:
  97 #ifdef NEW_LOGGING
  98                 LDAP_LOG( FILTER, DETAIL1,
  99                    "filter_candidates:  DN %s (%s)\n", sub, f->f_dn, 0 );
 100 #else
 101                 Debug( LDAP_DEBUG_FILTER,
 102                         "\tDN %s\n", sub, 0, 0 );
 103 #endif
 104
 105                 /* an error is treated as an empty list */
 106                 if ( dn2idl( op->o_bd, f->f_dn, DN_SUBTREE_PREFIX, &result ) != 0
 107                                 && result != NULL ) {
 108                         idl_free( result );
 109                         result = NULL;
 110                 }
 111                 break;
 112
 113         case LDAP_FILTER_PRESENT:
 114 #ifdef NEW_LOGGING
 115                 LDAP_LOG( FILTER, DETAIL1,
 116                         "filter_candidates:  Present (%s)\n",
 117                         f->f_desc->ad_cname.bv_val, 0, 0 );
 118 #else
 119                 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
 120 #endif
 121
 122                 result = presence_candidates( op, f->f_desc );
 123                 break;
 124
 125         case LDAP_FILTER_EQUALITY:
 126 #ifdef NEW_LOGGING
 127                 LDAP_LOG( FILTER, DETAIL1,
 128                            "filter_candidates:  EQUALITY (%s),(%s)\n",
 129                            f->f_ava->aa_desc->ad_cname.bv_val,
 130                            f->f_ava->aa_value.bv_val, 0 );
 131 #else
 132                 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
 133 #endif
 134
 135                 result = equality_candidates( op, f->f_ava );
 136                 break;
 137
 138         case LDAP_FILTER_APPROX:
 139 #ifdef NEW_LOGGING
 140                 LDAP_LOG( FILTER, DETAIL1,
 141                            "filter_candidates:  APPROX (%s), (%s)\n",
 142                            f->f_ava->aa_desc->ad_cname.bv_val,
 143                            f->f_ava->aa_value.bv_val, 0 );
 144 #else
 145                 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
 146 #endif
 147
 148                 result = approx_candidates( op, f->f_ava );
 149                 break;
 150
 151         case LDAP_FILTER_SUBSTRINGS:
 152 #ifdef NEW_LOGGING
 153                 LDAP_LOG( FILTER, DETAIL1,
 154                            "filter_candidates:  SUBSTRINGS\n", 0, 0, 0 );
 155 #else
 156                 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
 157 #endif
 158
 159                 result = substring_candidates( op, f->f_sub );
 160                 break;
 161
 162         case LDAP_FILTER_GE:
 163 #ifdef NEW_LOGGING
 164                 LDAP_LOG( FILTER, DETAIL1, "filter_candidates:  GE\n", 0, 0, 0 );
 165 #else
 166                 Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
 167 #endif
 168
 169                 result = presence_candidates( op, f->f_ava->aa_desc );
 170                 break;
 171
 172         case LDAP_FILTER_LE:
 173 #ifdef NEW_LOGGING
 174                 LDAP_LOG( FILTER, DETAIL1, "filter_candidates:  LE\n", 0, 0, 0 );
 175 #else
 176                 Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
 177 #endif
 178
 179                 result = presence_candidates( op, f->f_ava->aa_desc );
 180                 break;
 181
 182         case LDAP_FILTER_AND:
 183 #ifdef NEW_LOGGING
 184                 LDAP_LOG( FILTER, DETAIL1, "filter_candidates:  AND\n", 0, 0, 0 );
 185 #else
 186                 Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
 187 #endif
 188
 189                 result = list_candidates( op, f->f_and, LDAP_FILTER_AND );
 190                 break;
 191
 192         case LDAP_FILTER_OR:
 193 #ifdef NEW_LOGGING
 194                 LDAP_LOG( FILTER, DETAIL1, "filter_candidates:  OR\n", 0, 0, 0 );
 195 #else
 196                 Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
 197 #endif
 198
 199                 result = list_candidates( op, f->f_or, LDAP_FILTER_OR );
 200                 break;
 201
 202         case LDAP_FILTER_NOT:
 203 #ifdef NEW_LOGGING
 204                 LDAP_LOG( FILTER, DETAIL1, "filter_candidates:  NOT\n", 0, 0, 0 );
 205 #else
 206                 Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
 207 #endif
 208
 209                 /*
 210                  * As candidates lists may contain entries which do
 211                  * not match the assertion, negation of the inner candidate
 212                  * list could result in matching entries be excluded from
 213                  * the returned candidate list.
 214                  */
 215                 result = idl_allids( op->o_bd );
 216                 break;
 217         default:
 218 #ifdef NEW_LOGGING
 219                 LDAP_LOG( FILTER, DETAIL1, "filter_candidates:  UNKNOWN\n", 0, 0, 0 );
 220 #else
 221                 Debug( LDAP_DEBUG_FILTER, "\tUNKNOWN\n", 0, 0, 0 );
 222 #endif
 223                 /* unknown filters must not return NULL, to allow
 224                  * extended filter processing to be done later.
 225                  */
 226                 result = idl_allids( op->o_bd );
 227                 break;
 228         }
 229
 230 #ifdef NEW_LOGGING
 231         LDAP_LOG( FILTER, ENTRY,
 232                 "filter_candidates: return %ld\n",
 233                 result ? ID_BLOCK_NIDS(result) : 0, 0, 0 );
 234 #else
 235         Debug( LDAP_DEBUG_TRACE, "<= filter_candidates %ld\n",
 236             result ? ID_BLOCK_NIDS(result) : 0, 0, 0 );
 237 #endif
 238
 239         return( result );
 240 }
 241
 242 static ID_BLOCK *
 243 presence_candidates(
 244     Operation *op,
 245         AttributeDescription *desc
 246 )
 247 {
 248         ID_BLOCK        *idl;
 249         DBCache *db;
 250         int rc;
 251         char *dbname;
 252         slap_mask_t mask;
 253         struct berval prefix = {0, NULL};
 254
 255 #ifdef NEW_LOGGING
 256         LDAP_LOG( FILTER, ENTRY, "presence_candidates: enter\n", 0, 0, 0 );
 257 #else
 258         Debug( LDAP_DEBUG_TRACE, "=> presence_candidates\n", 0, 0, 0 );
 259 #endif
 260
 261         idl = idl_allids( op->o_bd );
 262
 263         if( desc == slap_schema.si_ad_objectClass ) {
 264                 return idl;
 265         }
 266
 267         rc = index_param( op->o_bd, desc, LDAP_FILTER_PRESENT,
 268                 &dbname, &mask, &prefix );
 269
 270         if( rc != LDAP_SUCCESS ) {
 271 #ifdef NEW_LOGGING
 272                 LDAP_LOG( FILTER, INFO,
 273                            "presence_candidates: index_param returned %d\n", rc, 0, 0 );
 274 #else
 275                 Debug( LDAP_DEBUG_TRACE,
 276                     "<= presence_candidates: index_param returned=%d\n",
 277                         rc, 0, 0 );
 278 #endif
 279
 280                 return idl;
 281         }
 282
 283         if( dbname == NULL ) {
 284                 /* not indexed */
 285 #ifdef NEW_LOGGING
 286                 LDAP_LOG( FILTER, INFO, "presence_candidates: not indexed\n", 0, 0, 0 );
 287 #else
 288                 Debug( LDAP_DEBUG_TRACE,
 289                     "<= presense_candidates: not indexed\n",
 290                         0, 0, 0 );
 291 #endif
 292
 293                 return idl;
 294         }
 295
 296         db = ldbm_cache_open( op->o_bd, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
 297
 298         if ( db == NULL ) {
 299 #ifdef NEW_LOGGING
 300                 LDAP_LOG( FILTER, INFO,
 301                            "presence_candidates: db open failed (%s%s)\n",
 302                            dbname, LDBM_SUFFIX, 0 );
 303 #else
 304                 Debug( LDAP_DEBUG_ANY,
 305                     "<= presense_candidates db open failed (%s%s)\n",
 306                         dbname, LDBM_SUFFIX, 0 );
 307 #endif
 308
 309                 return idl;
 310         }
 311
 312         if( prefix.bv_val != NULL ) {
 313                 idl_free( idl );
 314                 idl = NULL;
 315
 316                 rc = key_read( op->o_bd, db, &prefix, &idl );
 317
 318                 if( rc != LDAP_SUCCESS ) {
 319 #ifdef NEW_LOGGING
 320                         LDAP_LOG( FILTER, ERR,
 321                                    "presence_candidates: key read failed (%d)\n", rc, 0, 0 );
 322 #else
 323                         Debug( LDAP_DEBUG_TRACE,
 324                                 "<= presense_candidates key read failed (%d)\n",
 325                             rc, 0, 0 );
 326 #endif
 327
 328
 329                 } else if( idl == NULL ) {
 330 #ifdef NEW_LOGGING
 331                         LDAP_LOG( FILTER, DETAIL1, "presence_candidates: NULL\n", 0, 0, 0 );
 332 #else
 333                         Debug( LDAP_DEBUG_TRACE,
 334                                 "<= presense_candidates NULL\n",
 335                             0, 0, 0 );
 336 #endif
 337
 338                 }
 339         }
 340
 341         ldbm_cache_close( op->o_bd, db );
 342
 343 #ifdef NEW_LOGGING
 344         LDAP_LOG( FILTER, ENTRY,
 345                 "presence_candidates:  return %ld\n",
 346                 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 347 #else
 348         Debug( LDAP_DEBUG_TRACE, "<= presence_candidates %ld\n",
 349             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 350 #endif
 351
 352         return( idl );
 353 }
 354
 355 static ID_BLOCK *
 356 equality_candidates(
 357     Operation *op,
 358         AttributeAssertion *ava
 359 )
 360 {
 361         ID_BLOCK        *idl;
 362         DBCache *db;
 363         int i;
 364         int rc;
 365         char *dbname;
 366         slap_mask_t mask;
 367         struct berval prefix = {0, NULL};
 368         struct berval *keys = NULL;
 369         MatchingRule *mr;
 370
 371 #ifdef NEW_LOGGING
 372         LDAP_LOG( FILTER, ENTRY, "equality_candidates: enter\n", 0, 0, 0 );
 373 #else
 374         Debug( LDAP_DEBUG_TRACE, "=> equality_candidates\n", 0, 0, 0 );
 375 #endif
 376
 377
 378         idl = idl_allids( op->o_bd );
 379
 380         rc = index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_EQUALITY,
 381                 &dbname, &mask, &prefix );
 382
 383         if( rc != LDAP_SUCCESS ) {
 384 #ifdef NEW_LOGGING
 385                 LDAP_LOG( FILTER, ERR,
 386                            "equality_candidates:  index_param returned %d\n", rc, 0, 0 );
 387 #else
 388                 Debug( LDAP_DEBUG_TRACE,
 389                     "<= equality_candidates: index_param returned=%d\n",
 390                         rc, 0, 0 );
 391 #endif
 392
 393                 return idl;
 394         }
 395
 396         if( dbname == NULL ) {
 397                 /* not indexed */
 398 #ifdef NEW_LOGGING
 399                 LDAP_LOG( FILTER, ERR, "equality_candidates: not indexed\n", 0, 0, 0 );
 400 #else
 401                 Debug( LDAP_DEBUG_TRACE,
 402                     "<= equality_candidates: not indexed\n",
 403                         0, 0, 0 );
 404 #endif
 405
 406                 return idl;
 407         }
 408
 409         mr = ava->aa_desc->ad_type->sat_equality;
 410         if( !mr ) {
 411                 return idl;
 412         }
 413
 414         if( !mr->smr_filter ) {
 415                 return idl;
 416         }
 417
 418         rc = (mr->smr_filter)(
 419                 LDAP_FILTER_EQUALITY,
 420                 mask,
 421                 ava->aa_desc->ad_type->sat_syntax,
 422                 mr,
 423                 &prefix,
 424                 &ava->aa_value,
 425                 &keys, op->o_tmpmemctx );
 426
 427         if( rc != LDAP_SUCCESS ) {
 428 #ifdef NEW_LOGGING
 429                 LDAP_LOG( FILTER, ERR,
 430                            "equality_candidates: (%s%s) MR filter failed (%d\n",
 431                            dbname, LDBM_SUFFIX, rc );
 432 #else
 433                 Debug( LDAP_DEBUG_TRACE,
 434                     "<= equality_candidates: (%s%s) MR filter failed (%d)\n",
 435                         dbname, LDBM_SUFFIX, rc );
 436 #endif
 437
 438                 return idl;
 439         }
 440
 441         if( keys == NULL ) {
 442 #ifdef NEW_LOGGING
 443                 LDAP_LOG( FILTER, ERR,
 444                    "equality_candidates: no keys (%s%s)\n", dbname, LDBM_SUFFIX, 0 );
 445 #else
 446                 Debug( LDAP_DEBUG_TRACE,
 447                     "<= equality_candidates: no keys (%s%s)\n",
 448                         dbname, LDBM_SUFFIX, 0 );
 449 #endif
 450
 451                 return idl;
 452         }
 453
 454         db = ldbm_cache_open( op->o_bd, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
 455
 456         if ( db == NULL ) {
 457 #ifdef NEW_LOGGING
 458                 LDAP_LOG( FILTER, ERR, "equality_candidates: db open failed (%s%s)\n",
 459                         dbname, LDBM_SUFFIX, 0 );
 460 #else
 461                 Debug( LDAP_DEBUG_ANY,
 462                     "<= equality_candidates db open failed (%s%s)\n",
 463                         dbname, LDBM_SUFFIX, 0 );
 464 #endif
 465
 466                 return idl;
 467         }
 468
 469         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 470                 ID_BLOCK *save;
 471                 ID_BLOCK *tmp;
 472
 473                 rc = key_read( op->o_bd, db, &keys[i], &tmp );
 474
 475                 if( rc != LDAP_SUCCESS ) {
 476                         idl_free( idl );
 477                         idl = NULL;
 478 #ifdef NEW_LOGGING
 479                         LDAP_LOG( FILTER, ERR,
 480                                    "equality_candidates: key read failed (%d)\n", rc, 0, 0 );
 481 #else
 482                         Debug( LDAP_DEBUG_TRACE,
 483                                 "<= equality_candidates key read failed (%d)\n",
 484                             rc, 0, 0 );
 485 #endif
 486
 487                         break;
 488                 }
 489
 490                 if( tmp == NULL ) {
 491                         idl_free( idl );
 492                         idl = NULL;
 493 #ifdef NEW_LOGGING
 494                         LDAP_LOG( FILTER, INFO, "equality_candidates NULL\n", 0, 0, 0 );
 495 #else
 496                         Debug( LDAP_DEBUG_TRACE,
 497                                 "<= equality_candidates NULL\n",
 498                             0, 0, 0 );
 499 #endif
 500
 501                         break;
 502                 }
 503
 504                 save = idl;
 505                 idl = idl_intersection( op->o_bd, idl, tmp );
 506                 idl_free( save );
 507                 idl_free( tmp );
 508
 509                 if( idl == NULL ) break;
 510         }
 511
 512         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 513
 514         ldbm_cache_close( op->o_bd, db );
 515
 516
 517 #ifdef NEW_LOGGING
 518         LDAP_LOG( FILTER, ENTRY,
 519                    "equality_candidates: return %ld\n",
 520                    idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 521 #else
 522         Debug( LDAP_DEBUG_TRACE, "<= equality_candidates %ld\n",
 523             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 524 #endif
 525
 526         return( idl );
 527 }
 528
 529 static ID_BLOCK *
 530 approx_candidates(
 531     Operation *op,
 532         AttributeAssertion *ava
 533 )
 534 {
 535         ID_BLOCK *idl;
 536         DBCache *db;
 537         int i;
 538         int rc;
 539         char *dbname;
 540         slap_mask_t mask;
 541         struct berval prefix = {0, NULL};
 542         struct berval *keys = NULL;
 543         MatchingRule *mr;
 544
 545 #ifdef NEW_LOGGING
 546         LDAP_LOG( FILTER, ENTRY, "approx_candidates: enter\n", 0, 0, 0 );
 547 #else
 548         Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 );
 549 #endif
 550
 551
 552         idl = idl_allids( op->o_bd );
 553
 554         rc = index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_APPROX,
 555                 &dbname, &mask, &prefix );
 556
 557         if( rc != LDAP_SUCCESS ) {
 558 #ifdef NEW_LOGGING
 559                 LDAP_LOG( FILTER, ERR,
 560                            "approx_candidates: index_param returned %d\n", rc, 0, 0 );
 561 #else
 562                 Debug( LDAP_DEBUG_TRACE,
 563                     "<= approx_candidates: index_param returned=%d\n",
 564                         rc, 0, 0 );
 565 #endif
 566
 567                 return idl;
 568         }
 569
 570         if( dbname == NULL ) {
 571                 /* not indexed */
 572 #ifdef NEW_LOGGING
 573                 LDAP_LOG( FILTER, ERR, "approx_candidates: not indexed\n", 0, 0, 0 );
 574 #else
 575                 Debug( LDAP_DEBUG_ANY,
 576                     "<= approx_candidates: not indexed\n",
 577                         0, 0, 0 );
 578 #endif
 579
 580                 return idl;
 581         }
 582
 583         mr = ava->aa_desc->ad_type->sat_approx;
 584         if( !mr ) {
 585                 /* no approx matching rule, try equality matching rule */
 586                 mr = ava->aa_desc->ad_type->sat_equality;
 587         }
 588
 589         if( !mr ) {
 590                 return idl;
 591         }
 592
 593         if( !mr->smr_filter ) {
 594                 return idl;
 595         }
 596
 597         rc = (mr->smr_filter)(
 598                 LDAP_FILTER_APPROX,
 599                 mask,
 600                 ava->aa_desc->ad_type->sat_syntax,
 601                 mr,
 602                 &prefix,
 603                 &ava->aa_value,
 604                 &keys, op->o_tmpmemctx );
 605
 606         if( rc != LDAP_SUCCESS ) {
 607 #ifdef NEW_LOGGING
 608                 LDAP_LOG( FILTER, ERR,
 609                            "approx_candidates: (%s%s) MR filter failed (%d)\n",
 610                            dbname, LDBM_SUFFIX, rc );
 611 #else
 612                 Debug( LDAP_DEBUG_TRACE,
 613                     "<= approx_candidates: (%s%s) MR filter failed (%d)\n",
 614                         dbname, LDBM_SUFFIX, rc );
 615 #endif
 616
 617                 return idl;
 618         }
 619
 620         if( keys == NULL ) {
 621 #ifdef NEW_LOGGING
 622                 LDAP_LOG( FILTER, INFO,
 623                            "approx_candidates: no keys (%s%s)\n",
 624                            dbname, LDBM_SUFFIX, 0 );
 625 #else
 626                 Debug( LDAP_DEBUG_TRACE,
 627                     "<= approx_candidates: no keys (%s%s)\n",
 628                         dbname, LDBM_SUFFIX, 0 );
 629 #endif
 630
 631                 return idl;
 632         }
 633
 634         db = ldbm_cache_open( op->o_bd, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
 635
 636         if ( db == NULL ) {
 637 #ifdef NEW_LOGGING
 638                 LDAP_LOG( FILTER, ERR,
 639                         "approx_candidates db open failed (%s%s)\n",
 640                         dbname, LDBM_SUFFIX, 0 );
 641 #else
 642                 Debug( LDAP_DEBUG_ANY,
 643                     "<= approx_candidates db open failed (%s%s)\n",
 644                         dbname, LDBM_SUFFIX, 0 );
 645 #endif
 646
 647                 return idl;
 648         }
 649
 650         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 651                 ID_BLOCK *save;
 652                 ID_BLOCK *tmp;
 653
 654                 rc = key_read( op->o_bd, db, &keys[i], &tmp );
 655
 656                 if( rc != LDAP_SUCCESS ) {
 657                         idl_free( idl );
 658                         idl = NULL;
 659 #ifdef NEW_LOGGING
 660                         LDAP_LOG( FILTER, ERR,
 661                                    "approx_candidates: key read failed (%d)\n", rc, 0, 0 );
 662 #else
 663                         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates key read failed (%d)\n",
 664                             rc, 0, 0 );
 665 #endif
 666
 667                         break;
 668                 }
 669
 670                 if( tmp == NULL ) {
 671                         idl_free( idl );
 672                         idl = NULL;
 673 #ifdef NEW_LOGGING
 674                         LDAP_LOG( FILTER, INFO, "approx_candidates: NULL\n", 0, 0, 0 );
 675 #else
 676                         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n",
 677                             0, 0, 0 );
 678 #endif
 679
 680                         break;
 681                 }
 682
 683                 save = idl;
 684                 idl = idl_intersection( op->o_bd, idl, tmp );
 685                 idl_free( save );
 686                 idl_free( tmp );
 687
 688                 if( idl == NULL ) break;
 689         }
 690
 691         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 692
 693         ldbm_cache_close( op->o_bd, db );
 694
 695 #ifdef NEW_LOGGING
 696         LDAP_LOG( FILTER, ENTRY,
 697                 "approx_candidates: return %ld\n",
 698                 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 699 #else
 700         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %ld\n",
 701             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 702 #endif
 703
 704         return( idl );
 705 }
 706
 707 static ID_BLOCK *
 708 list_candidates(
 709     Operation *op,
 710     Filter      *flist,
 711     int         ftype
 712 )
 713 {
 714         ID_BLOCK        *idl, *tmp, *tmp2;
 715         Filter  *f;
 716
 717 #ifdef NEW_LOGGING
 718         LDAP_LOG( FILTER, ENTRY, "list_candidates: 0x%x\n", ftype, 0, 0 );
 719 #else
 720         Debug( LDAP_DEBUG_TRACE, "=> list_candidates 0x%x\n", ftype, 0, 0 );
 721 #endif
 722
 723
 724         idl = NULL;
 725         for ( f = flist; f != NULL; f = f->f_next ) {
 726                 if ( (tmp = filter_candidates( op, f )) == NULL &&
 727                     ftype == LDAP_FILTER_AND ) {
 728 #ifdef NEW_LOGGING
 729                         LDAP_LOG( FILTER, INFO, "list_candidates: NULL\n", 0, 0, 0 );
 730 #else
 731                         Debug( LDAP_DEBUG_TRACE,
 732                                "<= list_candidates NULL\n", 0, 0, 0 );
 733 #endif
 734
 735                         idl_free( idl );
 736                         return( NULL );
 737                 }
 738
 739                 tmp2 = idl;
 740                 if ( idl == NULL ) {
 741                         idl = tmp;
 742                 } else if ( ftype == LDAP_FILTER_AND ) {
 743                         idl = idl_intersection( op->o_bd, idl, tmp );
 744                         idl_free( tmp );
 745                         idl_free( tmp2 );
 746                 } else {
 747                         idl = idl_union( op->o_bd, idl, tmp );
 748                         idl_free( tmp );
 749                         idl_free( tmp2 );
 750                 }
 751         }
 752
 753 #ifdef NEW_LOGGING
 754         LDAP_LOG( FILTER, ENTRY, "list_candidates: return %ld\n",
 755                    idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 756 #else
 757         Debug( LDAP_DEBUG_TRACE, "<= list_candidates %ld\n",
 758             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 759 #endif
 760
 761         return( idl );
 762 }
 763
 764 static ID_BLOCK *
 765 substring_candidates(
 766     Operation *op,
 767     SubstringsAssertion *sub
 768 )
 769 {
 770         ID_BLOCK *idl;
 771         DBCache *db;
 772         int i;
 773         int rc;
 774         char *dbname;
 775         slap_mask_t mask;
 776         struct berval prefix = {0, NULL};
 777         struct berval *keys = NULL;
 778         MatchingRule *mr;
 779
 780 #ifdef NEW_LOGGING
 781         LDAP_LOG( FILTER, ENTRY, "substrings_candidates: enter\n", 0, 0, 0 );
 782 #else
 783         Debug( LDAP_DEBUG_TRACE, "=> substrings_candidates\n", 0, 0, 0 );
 784 #endif
 785
 786
 787         idl = idl_allids( op->o_bd );
 788
 789         rc = index_param( op->o_bd, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
 790                 &dbname, &mask, &prefix );
 791
 792         if( rc != LDAP_SUCCESS ) {
 793 #ifdef NEW_LOGGING
 794                 LDAP_LOG( FILTER, ERR,
 795                            "substrings_candidates: index_param returned %d\n", rc, 0, 0 );
 796 #else
 797                 Debug( LDAP_DEBUG_TRACE,
 798                     "<= substrings_candidates: index_param returned=%d\n",
 799                         rc, 0, 0 );
 800 #endif
 801
 802                 return idl;
 803         }
 804
 805         if( dbname == NULL ) {
 806                 /* not indexed */
 807 #ifdef NEW_LOGGING
 808                 LDAP_LOG( FILTER, ERR, "substrings_candidates: not indexed\n", 0, 0, 0);
 809 #else
 810                 Debug( LDAP_DEBUG_ANY,
 811                     "<= substrings_candidates: not indexed\n",
 812                         0, 0, 0 );
 813 #endif
 814
 815                 return idl;
 816         }
 817
 818         mr = sub->sa_desc->ad_type->sat_substr;
 819
 820         if( !mr ) {
 821                 return idl;
 822         }
 823
 824         if( !mr->smr_filter ) {
 825                 return idl;
 826         }
 827
 828         rc = (mr->smr_filter)(
 829                 LDAP_FILTER_SUBSTRINGS,
 830                 mask,
 831                 sub->sa_desc->ad_type->sat_syntax,
 832                 mr,
 833                 &prefix,
 834                 sub,
 835                 &keys, op->o_tmpmemctx );
 836
 837         if( rc != LDAP_SUCCESS ) {
 838 #ifdef NEW_LOGGING
 839                 LDAP_LOG( FILTER, ERR,
 840                            "substrings_candidates: (%s%s) MR filter failed (%d)\n",
 841                            dbname, LDBM_SUFFIX, rc );
 842 #else
 843                 Debug( LDAP_DEBUG_TRACE,
 844                     "<= substrings_candidates: (%s%s) MR filter failed (%d)\n",
 845                         dbname, LDBM_SUFFIX, rc );
 846 #endif
 847
 848                 return idl;
 849         }
 850
 851         if( keys == NULL ) {
 852 #ifdef NEW_LOGGING
 853                 LDAP_LOG( FILTER, ERR,
 854                            "substrings_candidates: (0x%04lx) no keys (%s%s)\n",
 855                            mask, dbname, LDBM_SUFFIX );
 856 #else
 857                 Debug( LDAP_DEBUG_TRACE,
 858                     "<= substrings_candidates: (0x%04lx) no keys (%s%s)\n",
 859                         mask, dbname, LDBM_SUFFIX );
 860 #endif
 861
 862                 return idl;
 863         }
 864
 865         db = ldbm_cache_open( op->o_bd, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
 866
 867         if ( db == NULL ) {
 868 #ifdef NEW_LOGGING
 869                 LDAP_LOG( FILTER, ERR,
 870                            "substrings_candidates: db open failed (%s%s)\n",
 871                            dbname, LDBM_SUFFIX, 0 );
 872 #else
 873                 Debug( LDAP_DEBUG_ANY,
 874                     "<= substrings_candidates db open failed (%s%s)\n",
 875                         dbname, LDBM_SUFFIX, 0 );
 876 #endif
 877
 878                 return idl;
 879         }
 880
 881         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 882                 ID_BLOCK *save;
 883                 ID_BLOCK *tmp;
 884
 885                 rc = key_read( op->o_bd, db, &keys[i], &tmp );
 886
 887                 if( rc != LDAP_SUCCESS ) {
 888                         idl_free( idl );
 889                         idl = NULL;
 890 #ifdef NEW_LOGGING
 891                         LDAP_LOG( FILTER, ERR,
 892                                    "substrings_candidates: key read failed (%d)\n", rc, 0, 0 );
 893 #else
 894                         Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates key read failed (%d)\n",
 895                             rc, 0, 0 );
 896 #endif
 897
 898                         break;
 899                 }
 900
 901                 if( tmp == NULL ) {
 902                         idl_free( idl );
 903                         idl = NULL;
 904 #ifdef NEW_LOGGING
 905                         LDAP_LOG( FILTER, INFO, "substrings_candidates: NULL\n", 0, 0, 0 );
 906 #else
 907                         Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates NULL\n",
 908                             0, 0, 0 );
 909 #endif
 910
 911                         break;
 912                 }
 913
 914                 save = idl;
 915                 idl = idl_intersection( op->o_bd, idl, tmp );
 916                 idl_free( save );
 917                 idl_free( tmp );
 918
 919                 if( idl == NULL ) break;
 920         }
 921
 922         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 923
 924         ldbm_cache_close( op->o_bd, db );
 925
 926 #ifdef NEW_LOGGING
 927         LDAP_LOG( FILTER, ENTRY,
 928                    "substrings_candidates: return %ld\n",
 929                    idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 930 #else
 931         Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates %ld\n",
 932             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 933 #endif
 934
 935         return( idl );
 936 }