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_TRACE,
 132                     "<= presence_candidates: index_param returned=%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_TRACE,
 207                     "<= equality_candidates: index_param returned=%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_TRACE,
 333                     "<= approx_candidates: index_param returned=%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                 idl_free( tmp );
 423
 424                 if( idl == NULL ) break;
 425         }
 426
 427         ber_bvecfree( keys );
 428
 429         ldbm_cache_close( be, db );
 430
 431         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %ld\n",
 432             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 433         return( idl );
 434 }
 435
 436 static ID_BLOCK *
 437 list_candidates(
 438     Backend     *be,
 439     Filter      *flist,
 440     int         ftype
 441 )
 442 {
 443         ID_BLOCK        *idl, *tmp, *tmp2;
 444         Filter  *f;
 445
 446         Debug( LDAP_DEBUG_TRACE, "=> list_candidates 0x%x\n", ftype, 0, 0 );
 447
 448         idl = NULL;
 449         for ( f = flist; f != NULL; f = f->f_next ) {
 450                 if ( (tmp = filter_candidates( be, f )) == NULL &&
 451                     ftype == LDAP_FILTER_AND ) {
 452                                 Debug( LDAP_DEBUG_TRACE,
 453                                     "<= list_candidates NULL\n", 0, 0, 0 );
 454                                 idl_free( idl );
 455                                 return( NULL );
 456                 }
 457
 458                 tmp2 = idl;
 459                 if ( idl == NULL ) {
 460                         idl = tmp;
 461                 } else if ( ftype == LDAP_FILTER_AND ) {
 462                         idl = idl_intersection( be, idl, tmp );
 463                         idl_free( tmp );
 464                         idl_free( tmp2 );
 465                 } else {
 466                         idl = idl_union( be, idl, tmp );
 467                         idl_free( tmp );
 468                         idl_free( tmp2 );
 469                 }
 470         }
 471
 472         Debug( LDAP_DEBUG_TRACE, "<= list_candidates %ld\n",
 473             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 474         return( idl );
 475 }
 476
 477 static ID_BLOCK *
 478 substring_candidates(
 479     Backend     *be,
 480     SubstringsAssertion *sub
 481 )
 482 {
 483         ID_BLOCK *idl;
 484         DBCache *db;
 485         int i;
 486         int rc;
 487         char *dbname;
 488         slap_mask_t mask;
 489         struct berval *prefix;
 490         struct berval **keys = NULL;
 491         MatchingRule *mr;
 492
 493         Debug( LDAP_DEBUG_TRACE, "=> substrings_candidates\n", 0, 0, 0 );
 494
 495         idl = idl_allids( be );
 496
 497         rc = index_param( be, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
 498                 &dbname, &mask, &prefix );
 499
 500         if( rc != LDAP_SUCCESS ) {
 501                 Debug( LDAP_DEBUG_TRACE,
 502                     "<= substrings_candidates: index_param returned=%d\n",
 503                         rc, 0, 0 );
 504                 return idl;
 505         }
 506
 507         if( dbname == NULL ) {
 508                 /* not indexed */
 509                 Debug( LDAP_DEBUG_ANY,
 510                     "<= substrings_candidates: not indexed\n",
 511                         0, 0, 0 );
 512                 ber_bvfree( prefix );
 513                 return idl;
 514         }
 515
 516         mr = sub->sa_desc->ad_type->sat_substr;
 517
 518         if( !mr ) {
 519                 ber_bvfree( prefix );
 520                 return idl;
 521         }
 522
 523         if( !mr->smr_filter ) {
 524                 ber_bvfree( prefix );
 525                 return idl;
 526         }
 527
 528         rc = (mr->smr_filter)(
 529                 LDAP_FILTER_SUBSTRINGS,
 530                 mask,
 531                 sub->sa_desc->ad_type->sat_syntax,
 532                 mr,
 533                 prefix,
 534                 sub,
 535                 &keys );
 536
 537         ber_bvfree( prefix );
 538
 539         if( rc != LDAP_SUCCESS ) {
 540                 Debug( LDAP_DEBUG_TRACE,
 541                     "<= substrings_candidates: (%s%s) MR filter failed (%d)\n",
 542                         dbname, LDBM_SUFFIX, rc );
 543                 return idl;
 544         }
 545
 546         if( keys == NULL ) {
 547                 Debug( LDAP_DEBUG_TRACE,
 548                     "<= substrings_candidates: (0x%04lx) no keys (%s%s)\n",
 549                         mask, dbname, LDBM_SUFFIX );
 550                 return idl;
 551         }
 552
 553         db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_READER );
 554
 555         if ( db == NULL ) {
 556                 Debug( LDAP_DEBUG_ANY,
 557                     "<= substrings_candidates db open failed (%s%s)\n",
 558                         dbname, LDBM_SUFFIX, 0 );
 559                 return idl;
 560         }
 561
 562         for ( i= 0; keys[i] != NULL; i++ ) {
 563                 ID_BLOCK *save;
 564                 ID_BLOCK *tmp;
 565
 566                 rc = key_read( be, db, keys[i], &tmp );
 567
 568                 if( rc != LDAP_SUCCESS ) {
 569                         idl_free( idl );
 570                         idl = NULL;
 571                         Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates key read failed (%d)\n",
 572                             rc, 0, 0 );
 573                         break;
 574                 }
 575
 576                 if( tmp == NULL ) {
 577                         idl_free( idl );
 578                         idl = NULL;
 579                         Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates NULL\n",
 580                             0, 0, 0 );
 581                         break;
 582                 }
 583
 584                 save = idl;
 585                 idl = idl_intersection( be, idl, tmp );
 586                 idl_free( save );
 587                 idl_free( tmp );
 588
 589                 if( idl == NULL ) break;
 590         }
 591
 592         ber_bvecfree( keys );
 593
 594         ldbm_cache_close( be, db );
 595
 596         Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates %ld\n",
 597             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 598         return( idl );
 599 }