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