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