git.sur5r.net Git - openldap/blob - servers/slapd/back-bdb/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 #include <ac/string.h>
  12
  13 #include "back-bdb.h"
  14 #include "idl.h"
  15
  16 #ifdef BDB_FILTER_INDICES
  17
  18 static int presence_candidates(
  19         Backend *be,
  20         ID *range,
  21         AttributeDescription *desc,
  22         ID *ids );
  23 static int equality_candidates(
  24         Backend *be,
  25         ID *range,
  26         AttributeAssertion *ava,
  27         ID *ids );
  28 static int approx_candidates(
  29         Backend *be,
  30         ID *range,
  31         AttributeAssertion *ava,
  32         ID *ids );
  33 static int substring_candidates(
  34         Backend *be,
  35         ID *range,
  36         SubstringsAssertion *sub,
  37         ID *ids );
  38
  39 static int list_candidates(
  40         Backend *be,
  41         ID *range,
  42         Filter *flist,
  43         int ftype,
  44         ID *ids );
  45
  46
  47 int
  48 bdb_filter_candidates(
  49         Backend *be,
  50         ID *range,
  51         Filter  *f,
  52         ID *ids )
  53 {
  54         int rc = -1;
  55         Debug( LDAP_DEBUG_FILTER, "=> bdb_filter_candidates\n", 0, 0, 0 );
  56
  57         switch ( f->f_choice ) {
  58         case SLAPD_FILTER_DN_ONE:
  59                 Debug( LDAP_DEBUG_FILTER, "\tDN ONE\n", 0, 0, 0 );
  60                 rc = bdb_dn2idl( be, f->f_dn, DN_ONE_PREFIX, ids );
  61                 break;
  62
  63         case SLAPD_FILTER_DN_SUBTREE:
  64                 Debug( LDAP_DEBUG_FILTER, "\tDN SUBTREE\n", 0, 0, 0 );
  65                 rc = bdb_dn2idl( be, f->f_dn, DN_SUBTREE_PREFIX, ids );
  66                 break;
  67
  68         case LDAP_FILTER_PRESENT:
  69                 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
  70                 rc = presence_candidates( be, range, f->f_desc, ids );
  71                 break;
  72
  73 #if 0
  74         case LDAP_FILTER_EQUALITY:
  75                 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
  76                 rc = equality_candidates( be, range, f->f_ava, ids );
  77                 break;
  78
  79         case LDAP_FILTER_APPROX:
  80                 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
  81                 rc = approx_candidates( be, range, f->f_ava, ids );
  82                 break;
  83
  84         case LDAP_FILTER_SUBSTRINGS:
  85                 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
  86                 rc = substring_candidates( be, range, f->f_sub, ids );
  87                 break;
  88 #endif
  89
  90         case LDAP_FILTER_GE:
  91                 Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
  92                 rc = 0;
  93                 break;
  94
  95         case LDAP_FILTER_LE:
  96                 Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
  97                 rc = 0;
  98                 break;
  99
 100         case LDAP_FILTER_NOT: {
 101                         ID tmp[BDB_IDL_UM_SIZE];
 102
 103                         Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
 104                         rc = bdb_filter_candidates( be, range, f->f_not, tmp );
 105                         if( rc == 0 ) {
 106                                 rc = bdb_idl_notin( range, tmp, ids );
 107                         }
 108                 } break;
 109
 110         case LDAP_FILTER_AND:
 111                 Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
 112                 rc = list_candidates( be, range,
 113                         f->f_and, LDAP_FILTER_AND, ids );
 114                 break;
 115
 116         case LDAP_FILTER_OR:
 117                 Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
 118                 rc = list_candidates( be, range,
 119                         f->f_or, LDAP_FILTER_OR, ids );
 120                 break;
 121
 122         default:
 123                 Debug( LDAP_DEBUG_FILTER, "\tUNKNOWN %d\n",
 124                         f->f_choice, 0, 0 );
 125         }
 126
 127         if( rc ) {
 128                 BDB_IDL_CPY( ids, range );
 129         }
 130
 131         Debug( LDAP_DEBUG_FILTER,
 132                 "<= bdb_filter_candidates: id=%ld first=%ld last=%ld\n",
 133                 (long) ids[0],
 134                 (long) BDB_IDL_FIRST( ids ),
 135                 (long) BDB_IDL_LAST( ids ) );
 136
 137         return 0;
 138 }
 139
 140 static int
 141 list_candidates(
 142         Backend *be,
 143         ID *range,
 144         Filter  *flist,
 145         int             ftype,
 146         ID *ids )
 147 {
 148         int rc = 0;
 149         Filter  *f;
 150
 151         Debug( LDAP_DEBUG_FILTER, "=> bdb_list_candidates 0x%x\n", ftype, 0, 0 );
 152
 153         if( ftype == LDAP_FILTER_AND ) {
 154                 BDB_IDL_CPY( ids, range );
 155         } else {
 156                 BDB_IDL_ZERO( ids );
 157         }
 158
 159         for ( f = flist; f != NULL; f = f->f_next ) {
 160                 ID tmp[BDB_IDL_UM_SIZE];
 161                 ID result[BDB_IDL_UM_SIZE];
 162                 rc = bdb_filter_candidates( be, range, f, tmp );
 163
 164                 if ( rc != 0 ) {
 165                         /* Error: treat as undefined */
 166                         if( ftype == LDAP_FILTER_AND ) {
 167                                 continue;
 168                         }
 169                         BDB_IDL_CPY( ids, range );
 170                         break;
 171                 }
 172
 173
 174                 if ( ftype == LDAP_FILTER_AND ) {
 175                         bdb_idl_intersection( tmp, ids, result );
 176                         if( BDB_IDL_IS_ZERO( result ) ) {
 177                                 BDB_IDL_ZERO( ids );
 178                                 break;
 179                         }
 180                 } else {
 181                         bdb_idl_union( tmp, ids, result );
 182                         if( BDB_IDL_IS_ALL( range, result ) ) {
 183                                 BDB_IDL_CPY( ids, range );
 184                                 break;
 185                         }
 186                 }
 187
 188                 BDB_IDL_CPY( ids, result );
 189         }
 190
 191         Debug( LDAP_DEBUG_FILTER,
 192                 "<= bdb_list_candidates: id=%ld first=%ld last=%ld\n",
 193                 (long) ids[0],
 194                 (long) BDB_IDL_FIRST(ids),
 195                 (long) BDB_IDL_LAST(ids) );
 196         return 0;
 197 }
 198
 199 static int
 200 presence_candidates(
 201         Backend *be,
 202         ID *range,
 203         AttributeDescription *desc,
 204         ID *ids )
 205 {
 206         DB *db;
 207         int rc;
 208         slap_mask_t mask;
 209         struct berval *prefix;
 210
 211         Debug( LDAP_DEBUG_TRACE, "=> bdb_presence_candidates\n", 0, 0, 0 );
 212         BDB_IDL_ZERO( ids );
 213
 214         rc = bdb_index_param( be, desc, LDAP_FILTER_PRESENT,
 215                 &db, &mask, &prefix );
 216
 217         if( rc != LDAP_SUCCESS ) {
 218                 Debug( LDAP_DEBUG_TRACE,
 219                         "<= bdb_presence_candidates: index_param returned=%d\n",
 220                         rc, 0, 0 );
 221                 return rc;
 222         }
 223
 224         if( db == NULL ) {
 225                 /* not indexed */
 226                 Debug( LDAP_DEBUG_TRACE,
 227                         "<= bdb_presense_candidates: not indexed\n",
 228                         0, 0, 0 );
 229                 rc = -1;
 230                 goto done;
 231         }
 232
 233         if( prefix == NULL ) {
 234                 Debug( LDAP_DEBUG_TRACE,
 235                         "<= bdb_presense_candidates: no prefix\n",
 236                         0, 0, 0 );
 237                 rc = -1;
 238                 goto done;
 239         }
 240
 241         rc = bdb_key_read( be, db, prefix, ids );
 242
 243         if( rc == DB_NOTFOUND ) {
 244                 rc = 0;
 245
 246         } else if( rc != LDAP_SUCCESS ) {
 247                 Debug( LDAP_DEBUG_TRACE,
 248                         "<= bdb_presense_candidates: key read failed (%d)\n",
 249                         rc, 0, 0 );
 250                 goto done;
 251         }
 252
 253         Debug(LDAP_DEBUG_TRACE,
 254                 "<= bdb_presence_candidates: id=%ld first=%ld last=%ld\n",
 255                 (long) ids[0],
 256                 (long) BDB_IDL_FIRST(ids),
 257                 (long) BDB_IDL_LAST(ids) );
 258
 259 done:
 260         ber_bvfree( prefix );
 261         return rc;
 262 }
 263
 264 static int
 265 equality_candidates(
 266         Backend *be,
 267         ID *range,
 268         AttributeAssertion *ava,
 269         ID *ids )
 270 {
 271         DB      *db;
 272         int i;
 273         int rc;
 274         char *dbname;
 275         slap_mask_t mask;
 276         struct berval *prefix;
 277         struct berval **keys = NULL;
 278         MatchingRule *mr;
 279
 280         Debug( LDAP_DEBUG_TRACE, "=> bdb_equality_candidates\n", 0, 0, 0 );
 281
 282         BDB_IDL_RANGE_CPY( range, ids );
 283
 284         rc = bdb_index_param( be, ava->aa_desc, LDAP_FILTER_EQUALITY,
 285                 &db, &mask, &prefix );
 286
 287         if( rc != LDAP_SUCCESS ) {
 288                 Debug( LDAP_DEBUG_ANY,
 289                         "<= equality_candidates: index_param failed (%d)\n",
 290                         rc, 0, 0 );
 291                 return 0;
 292         }
 293
 294         mr = ava->aa_desc->ad_type->sat_equality;
 295         if( !mr ) {
 296                 ber_bvfree( prefix );
 297                 return 0;
 298         }
 299
 300         if( !mr->smr_filter ) {
 301                 ber_bvfree( prefix );
 302                 return 0;
 303         }
 304
 305         rc = (mr->smr_filter)(
 306                 LDAP_FILTER_EQUALITY,
 307                 mask,
 308                 ava->aa_desc->ad_type->sat_syntax,
 309                 mr,
 310                 prefix,
 311                 ava->aa_value,
 312                 &keys );
 313
 314         ber_bvfree( prefix );
 315
 316         if( rc != LDAP_SUCCESS ) {
 317                 Debug( LDAP_DEBUG_TRACE,
 318                         "<= bdb_equality_candidates: MR filter failed (%d)\n",
 319                         rc, 0, 0 );
 320                 return 0;
 321         }
 322
 323         if( keys == NULL ) {
 324                 Debug( LDAP_DEBUG_TRACE,
 325                         "<= bdb_equality_candidates: no keys\n",
 326                         0, 0, 0 );
 327                 return 0;
 328         }
 329
 330         for ( i= 0; keys[i] != NULL; i++ ) {
 331                 ID save[BDB_IDL_UM_SIZE];
 332                 ID tmp[BDB_IDL_UM_SIZE];
 333
 334                 rc = bdb_key_read( be, db, keys[i], tmp );
 335
 336                 if( rc != LDAP_SUCCESS ) {
 337                         Debug( LDAP_DEBUG_TRACE,
 338                                 "<= bdb_equality_candidates key read failed (%d)\n",
 339                                 rc, 0, 0 );
 340                         break;
 341                 }
 342
 343                 if( tmp == NULL ) {
 344                         Debug( LDAP_DEBUG_TRACE,
 345                                 "<= bdb_equality_candidates NULL\n",
 346                                 0, 0, 0 );
 347                         break;
 348                 }
 349
 350                 save = idl;
 351                 idl = idl_intersection( be, idl, tmp );
 352                 idl_free( save );
 353                 idl_free( tmp );
 354
 355                 if( idl == NULL ) break;
 356         }
 357
 358         ber_bvecfree( keys );
 359
 360         Debug( LDAP_DEBUG_TRACE,
 361                 "<= bdb_equality_candidates id=%ld, first=%ld, last=%ld\n",
 362                 (long) ids[0],
 363                 (long) BDB_IDL_FIRST(ids),
 364                 (long) BDB_IDL_LAST(ids) );
 365         return( idl );
 366 }
 367
 368
 369 static int
 370 approx_candidates(
 371         Backend *be,
 372         ID *range,
 373         AttributeAssertion *ava,
 374         ID *ids )
 375 {
 376         ID_BLOCK *idl;
 377         DBCache *db;
 378         int i;
 379         int rc;
 380         char *dbname;
 381         slap_mask_t mask;
 382         struct berval *prefix;
 383         struct berval **keys = NULL;
 384         MatchingRule *mr;
 385
 386         Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 );
 387
 388         rc = bdb_index_param( be, ava->aa_desc, LDAP_FILTER_APPROX,
 389                 &db, &mask, &prefix );
 390
 391         if( rc != LDAP_SUCCESS ) {
 392                 Debug( LDAP_DEBUG_ANY,
 393                         "<= approx_candidates: index_param failed (%d)\n",
 394                         rc, 0, 0 );
 395                 return idl;
 396         }
 397
 398         mr = ava->aa_desc->ad_type->sat_approx;
 399         if( !mr ) {
 400                 /* no approx matching rule, try equality matching rule */
 401                 mr = ava->aa_desc->ad_type->sat_equality;
 402         }
 403
 404         if( !mr ) {
 405                 ber_bvfree( prefix );
 406                 return idl;
 407         }
 408
 409         if( !mr->smr_filter ) {
 410                 ber_bvfree( prefix );
 411                 return idl;
 412         }
 413
 414         rc = (mr->smr_filter)(
 415                 LDAP_FILTER_APPROX,
 416                 mask,
 417                 ava->aa_desc->ad_type->sat_syntax,
 418                 mr,
 419                 prefix,
 420                 ava->aa_value,
 421                 &keys );
 422
 423         ber_bvfree( prefix );
 424
 425         if( rc != LDAP_SUCCESS ) {
 426                 Debug( LDAP_DEBUG_TRACE,
 427                         "<= approx_candidates: (%s) MR filter failed (%d)\n",
 428                         dbname, rc, 0 );
 429                 return idl;
 430         }
 431
 432         if( keys == NULL ) {
 433                 Debug( LDAP_DEBUG_TRACE,
 434                         "<= approx_candidates: no keys (%s)\n",
 435                         dbname, 0, 0 );
 436                 return idl;
 437         }
 438
 439         if ( db == NULL ) {
 440                 Debug( LDAP_DEBUG_ANY,
 441                         "<= approx_candidates db open failed (%s)\n",
 442                         dbname, 0, 0 );
 443                 return idl;
 444         }
 445
 446         for ( i= 0; keys[i] != NULL; i++ ) {
 447                 ID_BLOCK *save;
 448                 ID_BLOCK *tmp;
 449
 450                 rc = bdb_key_read( be, db, keys[i], tmp );
 451
 452                 if( rc != LDAP_SUCCESS ) {
 453                         idl_free( idl );
 454                         idl = NULL;
 455                         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates key read failed (%d)\n",
 456                                 rc, 0, 0 );
 457                         break;
 458                 }
 459
 460                 if( tmp == NULL ) {
 461                         idl_free( idl );
 462                         idl = NULL;
 463                         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n",
 464                                 0, 0, 0 );
 465                         break;
 466                 }
 467
 468                 save = idl;
 469                 idl = idl_intersection( be, idl, tmp );
 470                 idl_free( save );
 471
 472                 if( idl == NULL ) break;
 473         }
 474
 475         ber_bvecfree( keys );
 476
 477         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %ld, first=%ld, last=%ld\n",
 478                 (long) ids[0],
 479                 (long) BDB_IDL_FIRST(ids),
 480                 (long) BDB_IDL_LAST(ids) );
 481
 482         return( idl );
 483 }
 484
 485 static int
 486 substring_candidates(
 487         Backend *be,
 488         ID *range,
 489         SubstringsAssertion     *sub,
 490         ID *ids )
 491 {
 492         ID_BLOCK *idl;
 493         DBCache *db;
 494         int i;
 495         int rc;
 496         slap_mask_t mask;
 497         struct berval *prefix;
 498         struct berval **keys = NULL;
 499         MatchingRule *mr;
 500
 501         Debug( LDAP_DEBUG_TRACE, "=> substrings_candidates\n", 0, 0, 0 );
 502
 503         idl = idl_allids( be );
 504
 505         rc = bdb_index_param( be, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
 506                 &db, &mask, &prefix );
 507
 508         if( rc != LDAP_SUCCESS ) {
 509                 Debug( LDAP_DEBUG_ANY,
 510                         "<= substrings_candidates: index_param failed (%d)\n",
 511                         rc, 0, 0 );
 512                 return idl;
 513         }
 514
 515         if( dbname == NULL ) {
 516                 /* not indexed */
 517                 Debug( LDAP_DEBUG_ANY,
 518                         "<= substrings_candidates: not indexed\n",
 519                         0, 0, 0 );
 520                 ber_bvfree( prefix );
 521                 return idl;
 522         }
 523
 524         mr = sub->sa_desc->ad_type->sat_substr;
 525
 526         if( !mr ) {
 527                 ber_bvfree( prefix );
 528                 return idl;
 529         }
 530
 531         if( !mr->smr_filter ) {
 532                 ber_bvfree( prefix );
 533                 return idl;
 534         }
 535
 536         rc = (mr->smr_filter)(
 537                 LDAP_FILTER_SUBSTRINGS,
 538                 mask,
 539                 sub->sa_desc->ad_type->sat_syntax,
 540                 mr,
 541                 prefix,
 542                 sub,
 543                 &keys );
 544
 545         ber_bvfree( prefix );
 546
 547         if( rc != LDAP_SUCCESS ) {
 548                 Debug( LDAP_DEBUG_TRACE,
 549                         "<= substrings_candidates: (%s) MR filter failed (%d)\n",
 550                         dbname, rc, 0 );
 551                 return idl;
 552         }
 553
 554         if( keys == NULL ) {
 555                 Debug( LDAP_DEBUG_TRACE,
 556                         "<= substrings_candidates: (0x%04lx) no keys (%s)\n",
 557                         mask, dbname, 0 );
 558                 return idl;
 559         }
 560
 561         rc = bdb_db_cache( be, dbname, &db );
 562
 563         if ( db == NULL ) {
 564                 Debug( LDAP_DEBUG_ANY,
 565                         "<= substrings_candidates db open failed (%s)\n",
 566                         dbname, 0, 0 );
 567                 return idl;
 568         }
 569
 570         for ( i= 0; keys[i] != NULL; i++ ) {
 571                 ID_BLOCK *save;
 572                 ID_BLOCK *tmp;
 573
 574                 rc = bdb_key_read( be, db, keys[i], &tmp );
 575
 576                 if( rc != LDAP_SUCCESS ) {
 577                         idl_free( idl );
 578                         idl = NULL;
 579                         Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates key read failed (%d)\n",
 580                                 rc, 0, 0 );
 581                         break;
 582                 }
 583
 584                 if( tmp == NULL ) {
 585                         idl_free( idl );
 586                         idl = NULL;
 587                         Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates NULL\n",
 588                                 0, 0, 0 );
 589                         break;
 590                 }
 591
 592                 save = idl;
 593                 idl = idl_intersection( be, idl, tmp );
 594                 idl_free( save );
 595
 596                 if( idl == NULL ) break;
 597         }
 598
 599         ber_bvecfree( keys );
 600
 601         Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates %ld, first=%ld, last=%ld\n",
 602                 (long) ids[0],
 603                 (long) BDB_IDL_FIRST(ids),
 604                 (long) BDB_IDL_LAST(ids) );
 605
 606         return( idl );
 607 }
 608
 609 #endif