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