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