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