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