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