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, *tmp1, *tmp2;
  40
  41         Debug( LDAP_DEBUG_TRACE, "=> filter_candidates\n", 0, 0, 0 );
  42
  43         result = NULL;
  44         switch ( f->f_choice ) {
  45         case SLAPD_FILTER_DN_ONE:
  46                 Debug( LDAP_DEBUG_FILTER, "\tDN ONE\n", 0, 0, 0 );
  47                 result = dn2idl( be, f->f_dn, DN_ONE_PREFIX );
  48                 break;
  49
  50         case SLAPD_FILTER_DN_SUBTREE:
  51                 Debug( LDAP_DEBUG_FILTER, "\tDN SUBTREE\n", 0, 0, 0 );
  52                 result = dn2idl( be, f->f_dn, DN_SUBTREE_PREFIX );
  53                 break;
  54
  55         case LDAP_FILTER_PRESENT:
  56                 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
  57                 result = presence_candidates( be, f->f_desc );
  58                 break;
  59
  60         case LDAP_FILTER_EQUALITY:
  61                 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
  62                 result = equality_candidates( be, f->f_ava );
  63                 break;
  64
  65         case LDAP_FILTER_APPROX:
  66                 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
  67                 result = approx_candidates( be, f->f_ava );
  68                 break;
  69
  70         case LDAP_FILTER_SUBSTRINGS:
  71                 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
  72                 result = substring_candidates( be, f->f_sub );
  73                 break;
  74
  75         case LDAP_FILTER_GE:
  76                 Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
  77                 result = idl_allids( be );
  78                 break;
  79
  80         case LDAP_FILTER_LE:
  81                 Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
  82                 result = idl_allids( be );
  83                 break;
  84
  85         case LDAP_FILTER_AND:
  86                 Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
  87                 result = list_candidates( be, f->f_and, LDAP_FILTER_AND );
  88                 break;
  89
  90         case LDAP_FILTER_OR:
  91                 Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
  92                 result = list_candidates( be, f->f_or, LDAP_FILTER_OR );
  93                 break;
  94
  95         case LDAP_FILTER_NOT:
  96                 Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
  97                 tmp1 = idl_allids( be );
  98                 tmp2 = filter_candidates( be, f->f_not );
  99                 result = idl_notin( be, tmp1, tmp2 );
 100                 idl_free( tmp2 );
 101                 idl_free( tmp1 );
 102                 break;
 103         }
 104
 105         Debug( LDAP_DEBUG_TRACE, "<= filter_candidates %ld\n",
 106             result ? ID_BLOCK_NIDS(result) : 0, 0, 0 );
 107         return( result );
 108 }
 109
 110 static ID_BLOCK *
 111 presence_candidates(
 112     Backend     *be,
 113         AttributeDescription *desc
 114 )
 115 {
 116         ID_BLOCK        *idl;
 117         DBCache *db;
 118         int rc;
 119         char *dbname;
 120         slap_mask_t mask;
 121         struct berval *prefix;
 122
 123         Debug( LDAP_DEBUG_TRACE, "=> presence_candidates\n", 0, 0, 0 );
 124
 125         idl = idl_allids( be );
 126
 127         rc = index_param( be, desc, LDAP_FILTER_PRESENT,
 128                 &dbname, &mask, &prefix );
 129
 130         if( rc != LDAP_SUCCESS ) {
 131                 Debug( LDAP_DEBUG_ANY,
 132                     "<= presence_candidates: index_param failed (%d)\n",
 133                         rc, 0, 0 );
 134                 return idl;
 135         }
 136
 137         if( dbname == NULL ) {
 138                 /* not indexed */
 139                 Debug( LDAP_DEBUG_TRACE,
 140                     "<= presense_candidates: not indexed\n",
 141                         0, 0, 0 );
 142                 ber_bvfree( prefix );
 143                 return idl;
 144         }
 145
 146         db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_READER );
 147
 148         if ( db == NULL ) {
 149                 Debug( LDAP_DEBUG_ANY,
 150                     "<= presense_candidates db open failed (%s%s)\n",
 151                         dbname, LDBM_SUFFIX, 0 );
 152                 ber_bvfree( prefix );
 153                 return idl;
 154         }
 155
 156         if( prefix != NULL ) {
 157                 idl_free( idl );
 158                 idl = NULL;
 159
 160                 rc = key_read( be, db, prefix, &idl );
 161
 162                 if( rc != LDAP_SUCCESS ) {
 163                         Debug( LDAP_DEBUG_TRACE,
 164                                 "<= presense_candidates key read failed (%d)\n",
 165                             rc, 0, 0 );
 166
 167                 } else if( idl == NULL ) {
 168                         Debug( LDAP_DEBUG_TRACE,
 169                                 "<= presense_candidates NULL\n",
 170                             0, 0, 0 );
 171                 }
 172         }
 173
 174         ldbm_cache_close( be, db );
 175         ber_bvfree( prefix );
 176
 177         Debug( LDAP_DEBUG_TRACE, "<= presence_candidates %ld\n",
 178             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 179         return( idl );
 180 }
 181
 182 static ID_BLOCK *
 183 equality_candidates(
 184     Backend     *be,
 185         AttributeAssertion *ava
 186 )
 187 {
 188         ID_BLOCK        *idl;
 189         DBCache *db;
 190         int i;
 191         int rc;
 192         char *dbname;
 193         slap_mask_t mask;
 194         struct berval *prefix;
 195         struct berval **keys = NULL;
 196         MatchingRule *mr;
 197
 198         Debug( LDAP_DEBUG_TRACE, "=> equality_candidates\n", 0, 0, 0 );
 199
 200         idl = idl_allids( be );
 201
 202         rc = index_param( be, ava->aa_desc, LDAP_FILTER_EQUALITY,
 203                 &dbname, &mask, &prefix );
 204
 205         if( rc != LDAP_SUCCESS ) {
 206                 Debug( LDAP_DEBUG_ANY,
 207                     "<= equality_candidates: index_param failed (%d)\n",
 208                         rc, 0, 0 );
 209                 return idl;
 210         }
 211
 212         if( dbname == NULL ) {
 213                 /* not indexed */
 214                 Debug( LDAP_DEBUG_TRACE,
 215                     "<= equality_candidates: not indexed\n",
 216                         0, 0, 0 );
 217                 ber_bvfree( prefix );
 218                 return idl;
 219         }
 220
 221         mr = ava->aa_desc->ad_type->sat_equality;
 222         if( !mr ) {
 223                 ber_bvfree( prefix );
 224                 return idl;
 225         }
 226
 227         if( !mr->smr_filter ) {
 228                 ber_bvfree( prefix );
 229                 return idl;
 230         }
 231
 232         rc = (mr->smr_filter)(
 233                 LDAP_FILTER_EQUALITY,
 234                 mask,
 235                 ava->aa_desc->ad_type->sat_syntax,
 236                 mr,
 237                 prefix,
 238                 ava->aa_value,
 239                 &keys );
 240
 241         ber_bvfree( prefix );
 242
 243         if( rc != LDAP_SUCCESS ) {
 244                 Debug( LDAP_DEBUG_TRACE,
 245                     "<= equality_candidates: (%s%s) MR filter failed (%d)\n",
 246                         dbname, LDBM_SUFFIX, rc );
 247                 return idl;
 248         }
 249
 250         if( keys == NULL ) {
 251                 Debug( LDAP_DEBUG_TRACE,
 252                     "<= equality_candidates: no keys (%s%s)\n",
 253                         dbname, LDBM_SUFFIX, 0 );
 254                 return idl;
 255         }
 256
 257         db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_READER );
 258
 259         if ( db == NULL ) {
 260                 Debug( LDAP_DEBUG_ANY,
 261                     "<= equality_candidates db open failed (%s%s)\n",
 262                         dbname, LDBM_SUFFIX, 0 );
 263                 return idl;
 264         }
 265
 266         for ( i= 0; keys[i] != NULL; i++ ) {
 267                 ID_BLOCK *save;
 268                 ID_BLOCK *tmp;
 269
 270                 rc = key_read( be, db, keys[i], &tmp );
 271
 272                 if( rc != LDAP_SUCCESS ) {
 273                         idl_free( idl );
 274                         idl = NULL;
 275                         Debug( LDAP_DEBUG_TRACE,
 276                                 "<= equality_candidates key read failed (%d)\n",
 277                             rc, 0, 0 );
 278                         break;
 279                 }
 280
 281                 if( tmp == NULL ) {
 282                         idl_free( idl );
 283                         idl = NULL;
 284                         Debug( LDAP_DEBUG_TRACE,
 285                                 "<= equality_candidates NULL\n",
 286                             0, 0, 0 );
 287                         break;
 288                 }
 289
 290                 save = idl;
 291                 idl = idl_intersection( be, idl, tmp );
 292                 idl_free( save );
 293                 idl_free( tmp );
 294
 295                 if( idl == NULL ) break;
 296         }
 297
 298         ber_bvecfree( keys );
 299
 300         ldbm_cache_close( be, db );
 301
 302
 303         Debug( LDAP_DEBUG_TRACE, "<= equality_candidates %ld\n",
 304             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 305         return( idl );
 306 }
 307
 308 static ID_BLOCK *
 309 approx_candidates(
 310     Backend     *be,
 311         AttributeAssertion *ava
 312 )
 313 {
 314         ID_BLOCK *idl;
 315         DBCache *db;
 316         int i;
 317         int rc;
 318         char *dbname;
 319         slap_mask_t mask;
 320         struct berval *prefix;
 321         struct berval **keys = NULL;
 322         MatchingRule *mr;
 323
 324         Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 );
 325
 326         idl = idl_allids( be );
 327
 328         rc = index_param( be, ava->aa_desc, LDAP_FILTER_APPROX,
 329                 &dbname, &mask, &prefix );
 330
 331         if( rc != LDAP_SUCCESS ) {
 332                 Debug( LDAP_DEBUG_ANY,
 333                     "<= approx_candidates: index_param failed (%d)\n",
 334                         rc, 0, 0 );
 335                 return idl;
 336         }
 337
 338         if( dbname == NULL ) {
 339                 /* not indexed */
 340                 Debug( LDAP_DEBUG_ANY,
 341                     "<= approx_candidates: not indexed\n",
 342                         0, 0, 0 );
 343                 ber_bvfree( prefix );
 344                 return idl;
 345         }
 346
 347         mr = ava->aa_desc->ad_type->sat_approx;
 348         if( !mr ) {
 349                 /* no approx matching rule, try equality matching rule */
 350                 mr = ava->aa_desc->ad_type->sat_equality;
 351         }
 352
 353         if( !mr ) {
 354                 ber_bvfree( prefix );
 355                 return idl;
 356         }
 357
 358         if( !mr->smr_filter ) {
 359                 ber_bvfree( prefix );
 360                 return idl;
 361         }
 362
 363         rc = (mr->smr_filter)(
 364                 LDAP_FILTER_APPROX,
 365                 mask,
 366                 ava->aa_desc->ad_type->sat_syntax,
 367                 mr,
 368                 prefix,
 369                 ava->aa_value,
 370                 &keys );
 371
 372         ber_bvfree( prefix );
 373
 374         if( rc != LDAP_SUCCESS ) {
 375                 Debug( LDAP_DEBUG_TRACE,
 376                     "<= approx_candidates: (%s%s) MR filter failed (%d)\n",
 377                         dbname, LDBM_SUFFIX, rc );
 378                 return idl;
 379         }
 380
 381         if( keys == NULL ) {
 382                 Debug( LDAP_DEBUG_TRACE,
 383                     "<= approx_candidates: no keys (%s%s)\n",
 384                         dbname, LDBM_SUFFIX, 0 );
 385                 return idl;
 386         }
 387
 388         db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_READER );
 389
 390         if ( db == NULL ) {
 391                 Debug( LDAP_DEBUG_ANY,
 392                     "<= approx_candidates db open failed (%s%s)\n",
 393                         dbname, LDBM_SUFFIX, 0 );
 394                 return idl;
 395         }
 396
 397         for ( i= 0; keys[i] != NULL; i++ ) {
 398                 ID_BLOCK *save;
 399                 ID_BLOCK *tmp;
 400
 401                 rc = key_read( be, db, keys[i], &tmp );
 402
 403                 if( rc != LDAP_SUCCESS ) {
 404                         idl_free( idl );
 405                         idl = NULL;
 406                         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates key read failed (%d)\n",
 407                             rc, 0, 0 );
 408                         break;
 409                 }
 410
 411                 if( tmp == NULL ) {
 412                         idl_free( idl );
 413                         idl = NULL;
 414                         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n",
 415                             0, 0, 0 );
 416                         break;
 417                 }
 418
 419                 save = idl;
 420                 idl = idl_intersection( be, idl, tmp );
 421                 idl_free( save );
 422
 423                 if( idl == NULL ) break;
 424         }
 425
 426         ber_bvecfree( keys );
 427
 428         ldbm_cache_close( be, db );
 429
 430         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %ld\n",
 431             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 432         return( idl );
 433 }
 434
 435 static ID_BLOCK *
 436 list_candidates(
 437     Backend     *be,
 438     Filter      *flist,
 439     int         ftype
 440 )
 441 {
 442         ID_BLOCK        *idl, *tmp, *tmp2;
 443         Filter  *f;
 444
 445         Debug( LDAP_DEBUG_TRACE, "=> list_candidates 0x%x\n", ftype, 0, 0 );
 446
 447         idl = NULL;
 448         for ( f = flist; f != NULL; f = f->f_next ) {
 449                 if ( (tmp = filter_candidates( be, f )) == NULL &&
 450                     ftype == LDAP_FILTER_AND ) {
 451                                 Debug( LDAP_DEBUG_TRACE,
 452                                     "<= list_candidates NULL\n", 0, 0, 0 );
 453                                 idl_free( idl );
 454                                 return( NULL );
 455                 }
 456
 457                 tmp2 = idl;
 458                 if ( idl == NULL ) {
 459                         idl = tmp;
 460                 } else if ( ftype == LDAP_FILTER_AND ) {
 461                         idl = idl_intersection( be, idl, tmp );
 462                         idl_free( tmp );
 463                         idl_free( tmp2 );
 464                 } else {
 465                         idl = idl_union( be, idl, tmp );
 466                         idl_free( tmp );
 467                         idl_free( tmp2 );
 468                 }
 469         }
 470
 471         Debug( LDAP_DEBUG_TRACE, "<= list_candidates %ld\n",
 472             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 473         return( idl );
 474 }
 475
 476 static ID_BLOCK *
 477 substring_candidates(
 478     Backend     *be,
 479     SubstringsAssertion *sub
 480 )
 481 {
 482         ID_BLOCK *idl;
 483         DBCache *db;
 484         int i;
 485         int rc;
 486         char *dbname;
 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 = index_param( be, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
 497                 &dbname, &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 = 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         ldbm_cache_close( be, db );
 593
 594         Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates %ld\n",
 595             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 596         return( idl );
 597 }