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                         if ( ftype == LDAP_FILTER_AND ) {
 162                                 rc = 0;
 163                                 continue;
 164                         }
 165                         break;
 166                 }
 167
 168                 if ( ftype == LDAP_FILTER_AND ) {
 169                         bdb_idl_intersection( ids, save );
 170                         if( BDB_IDL_IS_ZERO( ids ) )
 171                                 break;
 172                 } else {
 173                         bdb_idl_union( ids, save );
 174                         BDB_IDL_ALL( bdb, save );
 175                 }
 176         }
 177
 178 #if !defined(LDAP_PVT_THREAD_STACK_SIZE) || (LDAP_PVT_THREAD_STACK_SIZE == 0)
 179         free(save);
 180 #endif
 181
 182         if( rc ) {
 183                 Debug( LDAP_DEBUG_FILTER,
 184                         "<= bdb_list_candidates: id=%ld first=%ld last=%ld\n",
 185                         (long) ids[0],
 186                         (long) BDB_IDL_FIRST(ids),
 187                         (long) BDB_IDL_LAST(ids) );
 188
 189         } else {
 190                 Debug( LDAP_DEBUG_FILTER,
 191                         "<= bdb_list_candidates: undefined rc=%d\n",
 192                         rc, 0, 0 );
 193         }
 194
 195         return rc;
 196 }
 197
 198 static int
 199 presence_candidates(
 200         Backend *be,
 201         AttributeDescription *desc,
 202         ID *ids )
 203 {
 204         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 205         DB *db;
 206         int rc;
 207         slap_mask_t mask;
 208         struct berval prefix = {0};
 209
 210         Debug( LDAP_DEBUG_TRACE, "=> bdb_presence_candidates\n", 0, 0, 0 );
 211
 212         if( desc == slap_schema.si_ad_objectClass ) {
 213                 BDB_IDL_ALL( bdb, ids );
 214                 return 0;
 215         }
 216
 217         rc = bdb_index_param( be, desc, LDAP_FILTER_PRESENT,
 218                 &db, &mask, &prefix );
 219
 220         if( rc != LDAP_SUCCESS ) {
 221                 Debug( LDAP_DEBUG_TRACE,
 222                         "<= bdb_presence_candidates: index_param returned=%d\n",
 223                         rc, 0, 0 );
 224                 return 0;
 225         }
 226
 227         if( db == NULL ) {
 228                 /* not indexed */
 229                 Debug( LDAP_DEBUG_TRACE,
 230                         "<= bdb_presence_candidates: not indexed\n",
 231                         0, 0, 0 );
 232                 return 0;
 233         }
 234
 235         if( prefix.bv_val == NULL ) {
 236                 Debug( LDAP_DEBUG_TRACE,
 237                         "<= bdb_presence_candidates: no prefix\n",
 238                         0, 0, 0 );
 239                 return 0;
 240         }
 241
 242         rc = bdb_key_read( be, db, NULL, &prefix, ids );
 243
 244         if( rc == DB_NOTFOUND ) {
 245                 BDB_IDL_ZERO( ids );
 246                 rc = 0;
 247         } else if( rc != LDAP_SUCCESS ) {
 248                 Debug( LDAP_DEBUG_TRACE,
 249                         "<= bdb_presense_candidates: key read failed (%d)\n",
 250                         rc, 0, 0 );
 251                 goto done;
 252         }
 253
 254         Debug(LDAP_DEBUG_TRACE,
 255                 "<= bdb_presence_candidates: id=%ld first=%ld last=%ld\n",
 256                 (long) ids[0],
 257                 (long) BDB_IDL_FIRST(ids),
 258                 (long) BDB_IDL_LAST(ids) );
 259
 260 done:
 261         return rc;
 262 }
 263
 264 static int
 265 equality_candidates(
 266         Backend *be,
 267         AttributeAssertion *ava,
 268         ID *ids,
 269         ID *tmp )
 270 {
 271         DB      *db;
 272         int i;
 273         int rc;
 274         slap_mask_t mask;
 275         struct berval prefix = {0};
 276         struct berval *keys = NULL;
 277         MatchingRule *mr;
 278
 279         Debug( LDAP_DEBUG_TRACE, "=> bdb_equality_candidates\n", 0, 0, 0 );
 280
 281         rc = bdb_index_param( be, ava->aa_desc, LDAP_FILTER_EQUALITY,
 282                 &db, &mask, &prefix );
 283
 284         if( rc != LDAP_SUCCESS ) {
 285                 Debug( LDAP_DEBUG_ANY,
 286                         "<= bdb_equality_candidates: index_param failed (%d)\n",
 287                         rc, 0, 0 );
 288                 return rc;
 289         }
 290
 291         if ( db == NULL ) {
 292                 Debug( LDAP_DEBUG_ANY,
 293                         "<= bdb_equality_candidates: not indexed\n", 0, 0, 0 );
 294                 return -1;
 295         }
 296
 297         mr = ava->aa_desc->ad_type->sat_equality;
 298         if( !mr ) {
 299                 return -1;
 300         }
 301
 302         if( !mr->smr_filter ) {
 303                 return -1;
 304         }
 305
 306         rc = (mr->smr_filter)(
 307                 LDAP_FILTER_EQUALITY,
 308                 mask,
 309                 ava->aa_desc->ad_type->sat_syntax,
 310                 mr,
 311                 &prefix,
 312                 &ava->aa_value,
 313                 &keys );
 314
 315         if( rc != LDAP_SUCCESS ) {
 316                 Debug( LDAP_DEBUG_TRACE,
 317                         "<= bdb_equality_candidates: MR filter failed (%d)\n",
 318                         rc, 0, 0 );
 319                 return rc;
 320         }
 321
 322         if( keys == NULL ) {
 323                 Debug( LDAP_DEBUG_TRACE,
 324                         "<= bdb_equality_candidates: no keys\n",
 325                         0, 0, 0 );
 326                 return 0;
 327         }
 328
 329         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 330                 rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
 331
 332                 if( rc == DB_NOTFOUND ) {
 333                         BDB_IDL_ZERO( ids );
 334                         rc = 0;
 335                 } else if( rc != LDAP_SUCCESS ) {
 336                         Debug( LDAP_DEBUG_TRACE,
 337                                 "<= bdb_equality_candidates key read failed (%d)\n",
 338                                 rc, 0, 0 );
 339                         break;
 340                 }
 341
 342                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 343                         Debug( LDAP_DEBUG_TRACE,
 344                                 "<= bdb_equality_candidates NULL\n",
 345                                 0, 0, 0 );
 346                         BDB_IDL_ZERO( ids );
 347                         break;
 348                 }
 349
 350                 bdb_idl_intersection( ids, tmp );
 351
 352                 if( BDB_IDL_IS_ZERO( ids ) )
 353                         break;
 354         }
 355
 356         ber_bvarray_free( keys );
 357
 358         Debug( LDAP_DEBUG_TRACE,
 359                 "<= bdb_equality_candidates id=%ld, first=%ld, last=%ld\n",
 360                 (long) ids[0],
 361                 (long) BDB_IDL_FIRST(ids),
 362                 (long) BDB_IDL_LAST(ids) );
 363         return( rc );
 364 }
 365
 366
 367 static int
 368 approx_candidates(
 369         Backend *be,
 370         AttributeAssertion *ava,
 371         ID *ids,
 372         ID *tmp )
 373 {
 374         DB      *db;
 375         int i;
 376         int rc;
 377         slap_mask_t mask;
 378         struct berval prefix = {0};
 379         struct berval *keys = NULL;
 380         MatchingRule *mr;
 381
 382         Debug( LDAP_DEBUG_TRACE, "=> bdb_approx_candidates\n", 0, 0, 0 );
 383
 384         rc = bdb_index_param( be, ava->aa_desc, LDAP_FILTER_APPROX,
 385                 &db, &mask, &prefix );
 386
 387         if( rc != LDAP_SUCCESS ) {
 388                 Debug( LDAP_DEBUG_ANY,
 389                         "<= bdb_approx_candidates: index_param failed (%d)\n",
 390                         rc, 0, 0 );
 391                 return rc;
 392         }
 393
 394         if ( db == NULL ) {
 395                 Debug( LDAP_DEBUG_ANY,
 396                         "<= bdb_approx_candidates: not indexed\n", 0, 0, 0 );
 397                 return -1;
 398         }
 399
 400         mr = ava->aa_desc->ad_type->sat_approx;
 401         if( !mr ) {
 402                 /* no approx matching rule, try equality matching rule */
 403                 mr = ava->aa_desc->ad_type->sat_equality;
 404         }
 405
 406         if( !mr ) {
 407                 return -1;
 408         }
 409
 410         if( !mr->smr_filter ) {
 411                 return -1;
 412         }
 413
 414         rc = (mr->smr_filter)(
 415                 LDAP_FILTER_APPROX,
 416                 mask,
 417                 ava->aa_desc->ad_type->sat_syntax,
 418                 mr,
 419                 &prefix,
 420                 &ava->aa_value,
 421                 &keys );
 422
 423         if( rc != LDAP_SUCCESS ) {
 424                 Debug( LDAP_DEBUG_TRACE,
 425                         "<= bdb_approx_candidates: (%s) MR filter failed (%d)\n",
 426                         prefix.bv_val, rc, 0 );
 427                 return rc;
 428         }
 429
 430         if( keys == NULL ) {
 431                 Debug( LDAP_DEBUG_TRACE,
 432                         "<= bdb_approx_candidates: no keys (%s)\n",
 433                         prefix.bv_val, 0, 0 );
 434                 return 0;
 435         }
 436
 437         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 438                 rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
 439
 440                 if( rc == DB_NOTFOUND ) {
 441                         BDB_IDL_ZERO( ids );
 442                         rc = 0;
 443                         break;
 444                 } else if( rc != LDAP_SUCCESS ) {
 445                         Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates key read failed (%d)\n",
 446                                 rc, 0, 0 );
 447                         break;
 448                 }
 449
 450                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 451                         Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates NULL\n",
 452                                 0, 0, 0 );
 453                         BDB_IDL_ZERO( ids );
 454                         break;
 455                 }
 456
 457                 bdb_idl_intersection( ids, tmp );
 458
 459                 if( BDB_IDL_IS_ZERO( ids ) )
 460                         break;
 461         }
 462
 463         ber_bvarray_free( keys );
 464
 465         Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates %ld, first=%ld, last=%ld\n",
 466                 (long) ids[0],
 467                 (long) BDB_IDL_FIRST(ids),
 468                 (long) BDB_IDL_LAST(ids) );
 469
 470         return( rc );
 471 }
 472
 473 static int
 474 substring_candidates(
 475         Backend *be,
 476         SubstringsAssertion     *sub,
 477         ID *ids,
 478         ID *tmp )
 479 {
 480         DB      *db;
 481         int i;
 482         int rc;
 483         slap_mask_t mask;
 484         struct berval prefix = {0};
 485         struct berval *keys = NULL;
 486         MatchingRule *mr;
 487
 488         Debug( LDAP_DEBUG_TRACE, "=> bdb_substring_candidates\n", 0, 0, 0 );
 489
 490         rc = bdb_index_param( be, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
 491                 &db, &mask, &prefix );
 492
 493         if( rc != LDAP_SUCCESS ) {
 494                 Debug( LDAP_DEBUG_ANY,
 495                         "<= bdb_substring_candidates: index_param failed (%d)\n",
 496                         rc, 0, 0 );
 497                 return rc;
 498         }
 499
 500         if ( db == NULL ) {
 501                 Debug( LDAP_DEBUG_ANY,
 502                         "<= bdb_substring_candidates not indexed\n",
 503                         0, 0, 0 );
 504                 return -1;
 505         }
 506
 507         mr = sub->sa_desc->ad_type->sat_substr;
 508
 509         if( !mr ) {
 510                 return -1;
 511         }
 512
 513         if( !mr->smr_filter ) {
 514                 return -1;
 515         }
 516
 517         rc = (mr->smr_filter)(
 518                 LDAP_FILTER_SUBSTRINGS,
 519                 mask,
 520                 sub->sa_desc->ad_type->sat_syntax,
 521                 mr,
 522                 &prefix,
 523                 sub,
 524                 &keys );
 525
 526         if( rc != LDAP_SUCCESS ) {
 527                 Debug( LDAP_DEBUG_TRACE,
 528                         "<= bdb_substring_candidates: (%s) MR filter failed (%d)\n",
 529                         sub->sa_desc->ad_cname.bv_val, rc, 0 );
 530                 return rc;
 531         }
 532
 533         if( keys == NULL ) {
 534                 Debug( LDAP_DEBUG_TRACE,
 535                         "<= bdb_substring_candidates: (0x%04lx) no keys (%s)\n",
 536                         mask, sub->sa_desc->ad_cname.bv_val, 0 );
 537                 return 0;
 538         }
 539
 540         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 541                 rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
 542
 543                 if( rc == DB_NOTFOUND ) {
 544                         BDB_IDL_ZERO( ids );
 545                         rc = 0;
 546                         break;
 547                 } else if( rc != LDAP_SUCCESS ) {
 548                         Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates key read failed (%d)\n",
 549                                 rc, 0, 0 );
 550                         break;
 551                 }
 552
 553                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 554                         Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates NULL\n",
 555                                 0, 0, 0 );
 556                         BDB_IDL_ZERO( ids );
 557                         break;
 558                 }
 559
 560                 bdb_idl_intersection( ids, tmp );
 561
 562                 if( BDB_IDL_IS_ZERO( ids ) )
 563                         break;
 564         }
 565
 566         ber_bvarray_free( keys );
 567
 568         Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates %ld, first=%ld, last=%ld\n",
 569                 (long) ids[0],
 570                 (long) BDB_IDL_FIRST(ids),
 571                 (long) BDB_IDL_LAST(ids) );
 572
 573         return( 0 );
 574 }
 575