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