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_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                 ids[0], ids[1],
 134                 BDB_IDL_IS_RANGE( ids ) ? ids[2] : ids[ids[0]] );
 135
 136         return 0;
 137 }
 138
 139 static int
 140 list_candidates(
 141         Backend *be,
 142         ID *range,
 143         Filter  *flist,
 144         int             ftype,
 145         ID *ids )
 146 {
 147         int rc = 0;
 148         Filter  *f;
 149
 150         Debug( LDAP_DEBUG_FILTER, "=> bdb_list_candidates 0x%x\n", ftype, 0, 0 );
 151
 152         if( ftype == LDAP_FILTER_AND ) {
 153                 BDB_IDL_CPY( ids, range );
 154         } else {
 155                 BDB_IDL_ZERO( ids );
 156         }
 157
 158         for ( f = flist; f != NULL; f = f->f_next ) {
 159                 ID tmp[BDB_IDL_SIZE];
 160                 ID result[BDB_IDL_SIZE];
 161                 rc = bdb_filter_candidates( be, range, f, tmp );
 162
 163                 if ( rc != 0 ) {
 164                         /* Error: treat as undefined */
 165                         if( ftype == LDAP_FILTER_AND ) {
 166                                 continue;
 167                         }
 168                         BDB_IDL_CPY( ids, range );
 169                         break;
 170                 }
 171
 172
 173                 if ( ftype == LDAP_FILTER_AND ) {
 174                         bdb_idl_intersection( tmp, ids, result );
 175                         if( BDB_IDL_IS_ZERO( result ) ) {
 176                                 BDB_IDL_ZERO( ids );
 177                                 break;
 178                         }
 179                 } else {
 180                         bdb_idl_union( tmp, ids, result );
 181                         if( BDB_IDL_IS_ALL( range, result ) ) {
 182                                 BDB_IDL_CPY( ids, range );
 183                                 break;
 184                         }
 185                 }
 186
 187                 BDB_IDL_CPY( ids, result );
 188         }
 189
 190         Debug( LDAP_DEBUG_FILTER,
 191                 "<= bdb_list_candidates: id=%ld first=%ld last=%ld\n",
 192                 ids[0], BDB_IDL_FIRST(ids), 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                 ids[0], BDB_IDL_FIRST(ids), BDB_IDL_LAST(ids) );
 253
 254 done:
 255         ber_bvfree( prefix );
 256         return rc;
 257 }
 258
 259 static int
 260 equality_candidates(
 261         Backend *be,
 262         ID *range,
 263         AttributeAssertion *ava,
 264         ID *ids )
 265 {
 266         DB      *db;
 267         int i;
 268         int rc;
 269         char *dbname;
 270         slap_mask_t mask;
 271         struct berval *prefix;
 272         struct berval **keys = NULL;
 273         MatchingRule *mr;
 274
 275         Debug( LDAP_DEBUG_TRACE, "=> bdb_equality_candidates\n", 0, 0, 0 );
 276
 277         BDB_IDL_RANGE_CPY( range, ids );
 278
 279         rc = bdb_index_param( be, ava->aa_desc, LDAP_FILTER_EQUALITY,
 280                 &db, &mask, &prefix );
 281
 282         if( rc != LDAP_SUCCESS ) {
 283                 Debug( LDAP_DEBUG_ANY,
 284                         "<= equality_candidates: index_param failed (%d)\n",
 285                         rc, 0, 0 );
 286                 return 0;
 287         }
 288
 289         mr = ava->aa_desc->ad_type->sat_equality;
 290         if( !mr ) {
 291                 ber_bvfree( prefix );
 292                 return 0;
 293         }
 294
 295         if( !mr->smr_filter ) {
 296                 ber_bvfree( prefix );
 297                 return 0;
 298         }
 299
 300         rc = (mr->smr_filter)(
 301                 LDAP_FILTER_EQUALITY,
 302                 mask,
 303                 ava->aa_desc->ad_type->sat_syntax,
 304                 mr,
 305                 prefix,
 306                 ava->aa_value,
 307                 &keys );
 308
 309         ber_bvfree( prefix );
 310
 311         if( rc != LDAP_SUCCESS ) {
 312                 Debug( LDAP_DEBUG_TRACE,
 313                         "<= bdb_equality_candidates: (%s%s) MR filter failed (%d)\n",
 314                         "", "", rc );
 315                 return 0;
 316         }
 317
 318         if( keys == NULL ) {
 319                 Debug( LDAP_DEBUG_TRACE,
 320                         "<= bdb_equality_candidates: no keys (%s%s)\n",
 321                         "", "", 0 );
 322                 return 0;
 323         }
 324
 325         for ( i= 0; keys[i] != NULL; i++ ) {
 326                 ID save[BDB_IDL_SIZE];
 327                 ID tmp[BDB_IDL_SIZE];
 328
 329                 rc = bdb_key_read( be, db, keys[i], tmp );
 330
 331                 if( rc != LDAP_SUCCESS ) {
 332                         Debug( LDAP_DEBUG_TRACE,
 333                                 "<= bdb_equality_candidates key read failed (%d)\n",
 334                                 rc, 0, 0 );
 335                         break;
 336                 }
 337
 338                 if( tmp == NULL ) {
 339                         Debug( LDAP_DEBUG_TRACE,
 340                                 "<= bdb_equality_candidates NULL\n",
 341                                 0, 0, 0 );
 342                         break;
 343                 }
 344
 345                 save = idl;
 346                 idl = idl_intersection( be, idl, tmp );
 347                 idl_free( save );
 348                 idl_free( tmp );
 349
 350                 if( idl == NULL ) break;
 351         }
 352
 353         ber_bvecfree( keys );
 354
 355         Debug( LDAP_DEBUG_TRACE,
 356                 "<= bdb_equality_candidates %ld\n",
 357                 ids[0], BDB_IDL_FIRST(ids), BDB_IDL_LAST(ids) );
 358         return( idl );
 359 }
 360
 361
 362 static int
 363 approx_candidates(
 364         Backend *be,
 365         ID *range,
 366         AttributeAssertion *ava,
 367         ID *ids )
 368 {
 369         ID_BLOCK *idl;
 370         DBCache *db;
 371         int i;
 372         int rc;
 373         char *dbname;
 374         slap_mask_t mask;
 375         struct berval *prefix;
 376         struct berval **keys = NULL;
 377         MatchingRule *mr;
 378
 379         Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 );
 380
 381         rc = bdb_index_param( be, ava->aa_desc, LDAP_FILTER_APPROX,
 382                 &db, &mask, &prefix );
 383
 384         if( rc != LDAP_SUCCESS ) {
 385                 Debug( LDAP_DEBUG_ANY,
 386                         "<= approx_candidates: index_param failed (%d)\n",
 387                         rc, 0, 0 );
 388                 return idl;
 389         }
 390
 391         mr = ava->aa_desc->ad_type->sat_approx;
 392         if( !mr ) {
 393                 /* no approx matching rule, try equality matching rule */
 394                 mr = ava->aa_desc->ad_type->sat_equality;
 395         }
 396
 397         if( !mr ) {
 398                 ber_bvfree( prefix );
 399                 return idl;
 400         }
 401
 402         if( !mr->smr_filter ) {
 403                 ber_bvfree( prefix );
 404                 return idl;
 405         }
 406
 407         rc = (mr->smr_filter)(
 408                 LDAP_FILTER_APPROX,
 409                 mask,
 410                 ava->aa_desc->ad_type->sat_syntax,
 411                 mr,
 412                 prefix,
 413                 ava->aa_value,
 414                 &keys );
 415
 416         ber_bvfree( prefix );
 417
 418         if( rc != LDAP_SUCCESS ) {
 419                 Debug( LDAP_DEBUG_TRACE,
 420                         "<= approx_candidates: (%s%s) MR filter failed (%d)\n",
 421                         dbname, LDBM_SUFFIX, rc );
 422                 return idl;
 423         }
 424
 425         if( keys == NULL ) {
 426                 Debug( LDAP_DEBUG_TRACE,
 427                         "<= approx_candidates: no keys (%s%s)\n",
 428                         dbname, LDBM_SUFFIX, 0 );
 429                 return idl;
 430         }
 431
 432         if ( db == NULL ) {
 433                 Debug( LDAP_DEBUG_ANY,
 434                         "<= approx_candidates db open failed (%s%s)\n",
 435                         dbname, LDBM_SUFFIX, 0 );
 436                 return idl;
 437         }
 438
 439         for ( i= 0; keys[i] != NULL; i++ ) {
 440                 ID_BLOCK *save;
 441                 ID_BLOCK *tmp;
 442
 443                 rc = bdb_key_read( be, db, keys[i], tmp );
 444
 445                 if( rc != LDAP_SUCCESS ) {
 446                         idl_free( idl );
 447                         idl = NULL;
 448                         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates key read failed (%d)\n",
 449                                 rc, 0, 0 );
 450                         break;
 451                 }
 452
 453                 if( tmp == NULL ) {
 454                         idl_free( idl );
 455                         idl = NULL;
 456                         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n",
 457                                 0, 0, 0 );
 458                         break;
 459                 }
 460
 461                 save = idl;
 462                 idl = idl_intersection( be, idl, tmp );
 463                 idl_free( save );
 464
 465                 if( idl == NULL ) break;
 466         }
 467
 468         ber_bvecfree( keys );
 469
 470         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %ld\n",
 471                 ids[0], BDB_IDL_FIRST(ids), BDB_IDL_LAST(ids) );
 472
 473         return( idl );
 474 }
 475
 476 static int
 477 substring_candidates(
 478         Backend *be,
 479         ID *range,
 480         SubstringsAssertion     *sub,
 481         ID *ids )
 482 {
 483         ID_BLOCK *idl;
 484         DBCache *db;
 485         int i;
 486         int rc;
 487         slap_mask_t mask;
 488         struct berval *prefix;
 489         struct berval **keys = NULL;
 490         MatchingRule *mr;
 491
 492         Debug( LDAP_DEBUG_TRACE, "=> substrings_candidates\n", 0, 0, 0 );
 493
 494         idl = idl_allids( be );
 495
 496         rc = bdb_index_param( be, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
 497                 &db, &mask, &prefix );
 498
 499         if( rc != LDAP_SUCCESS ) {
 500                 Debug( LDAP_DEBUG_ANY,
 501                         "<= substrings_candidates: index_param failed (%d)\n",
 502                         rc, 0, 0 );
 503                 return idl;
 504         }
 505
 506         if( dbname == NULL ) {
 507                 /* not indexed */
 508                 Debug( LDAP_DEBUG_ANY,
 509                         "<= substrings_candidates: not indexed\n",
 510                         0, 0, 0 );
 511                 ber_bvfree( prefix );
 512                 return idl;
 513         }
 514
 515         mr = sub->sa_desc->ad_type->sat_substr;
 516
 517         if( !mr ) {
 518                 ber_bvfree( prefix );
 519                 return idl;
 520         }
 521
 522         if( !mr->smr_filter ) {
 523                 ber_bvfree( prefix );
 524                 return idl;
 525         }
 526
 527         rc = (mr->smr_filter)(
 528                 LDAP_FILTER_SUBSTRINGS,
 529                 mask,
 530                 sub->sa_desc->ad_type->sat_syntax,
 531                 mr,
 532                 prefix,
 533                 sub,
 534                 &keys );
 535
 536         ber_bvfree( prefix );
 537
 538         if( rc != LDAP_SUCCESS ) {
 539                 Debug( LDAP_DEBUG_TRACE,
 540                         "<= substrings_candidates: (%s%s) MR filter failed (%d)\n",
 541                         dbname, LDBM_SUFFIX, rc );
 542                 return idl;
 543         }
 544
 545         if( keys == NULL ) {
 546                 Debug( LDAP_DEBUG_TRACE,
 547                         "<= substrings_candidates: (0x%04lx) no keys (%s%s)\n",
 548                         mask, dbname, LDBM_SUFFIX );
 549                 return idl;
 550         }
 551
 552         db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_READER );
 553
 554         if ( db == NULL ) {
 555                 Debug( LDAP_DEBUG_ANY,
 556                         "<= substrings_candidates db open failed (%s%s)\n",
 557                         dbname, LDBM_SUFFIX, 0 );
 558                 return idl;
 559         }
 560
 561         for ( i= 0; keys[i] != NULL; i++ ) {
 562                 ID_BLOCK *save;
 563                 ID_BLOCK *tmp;
 564
 565                 rc = bdb_key_read( be, db, keys[i], &tmp );
 566
 567                 if( rc != LDAP_SUCCESS ) {
 568                         idl_free( idl );
 569                         idl = NULL;
 570                         Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates key read failed (%d)\n",
 571                                 rc, 0, 0 );
 572                         break;
 573                 }
 574
 575                 if( tmp == NULL ) {
 576                         idl_free( idl );
 577                         idl = NULL;
 578                         Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates NULL\n",
 579                                 0, 0, 0 );
 580                         break;
 581                 }
 582
 583                 save = idl;
 584                 idl = idl_intersection( be, idl, tmp );
 585                 idl_free( save );
 586
 587                 if( idl == NULL ) break;
 588         }
 589
 590         ber_bvecfree( keys );
 591
 592         Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates %ld\n",
 593                 ids[0], BDB_IDL_FIRST(ids), BDB_IDL_LAST(ids) );
 594
 595         return( idl );
 596 }
 597
 598 #endif