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