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                 rc = 0;
 236
 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 != LDAP_SUCCESS ) {
 323                         Debug( LDAP_DEBUG_TRACE,
 324                                 "<= bdb_equality_candidates key read failed (%d)\n",
 325                                 rc, 0, 0 );
 326                         break;
 327                 }
 328
 329                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 330                         Debug( LDAP_DEBUG_TRACE,
 331                                 "<= bdb_equality_candidates NULL\n",
 332                                 0, 0, 0 );
 333                         BDB_IDL_ZERO( ids );
 334                         break;
 335                 }
 336
 337                 bdb_idl_intersection( ids, tmp );
 338
 339                 if( BDB_IDL_IS_ZERO( ids ) )
 340                         break;
 341         }
 342
 343         bvarray_free( keys );
 344
 345         Debug( LDAP_DEBUG_TRACE,
 346                 "<= bdb_equality_candidates id=%ld, first=%ld, last=%ld\n",
 347                 (long) ids[0],
 348                 (long) BDB_IDL_FIRST(ids),
 349                 (long) BDB_IDL_LAST(ids) );
 350         return( rc );
 351 }
 352
 353
 354 static int
 355 approx_candidates(
 356         Backend *be,
 357         AttributeAssertion *ava,
 358         ID *ids,
 359         ID *tmp )
 360 {
 361         DB      *db;
 362         int i;
 363         int rc;
 364         slap_mask_t mask;
 365         struct berval prefix = {0};
 366         struct berval *keys = NULL;
 367         MatchingRule *mr;
 368
 369         Debug( LDAP_DEBUG_TRACE, "=> bdb_approx_candidates\n", 0, 0, 0 );
 370
 371         rc = bdb_index_param( be, ava->aa_desc, LDAP_FILTER_APPROX,
 372                 &db, &mask, &prefix );
 373
 374         if( rc != LDAP_SUCCESS ) {
 375                 Debug( LDAP_DEBUG_ANY,
 376                         "<= bdb_approx_candidates: index_param failed (%d)\n",
 377                         rc, 0, 0 );
 378                 return rc;
 379         }
 380
 381         if ( db == NULL ) {
 382                 Debug( LDAP_DEBUG_ANY,
 383                         "<= bdb_approx_candidates: not indexed\n", 0, 0, 0 );
 384                 return -1;
 385         }
 386
 387         mr = ava->aa_desc->ad_type->sat_approx;
 388         if( !mr ) {
 389                 /* no approx matching rule, try equality matching rule */
 390                 mr = ava->aa_desc->ad_type->sat_equality;
 391         }
 392
 393         if( !mr ) {
 394                 return -1;
 395         }
 396
 397         if( !mr->smr_filter ) {
 398                 return -1;
 399         }
 400
 401         rc = (mr->smr_filter)(
 402                 LDAP_FILTER_APPROX,
 403                 mask,
 404                 ava->aa_desc->ad_type->sat_syntax,
 405                 mr,
 406                 &prefix,
 407                 &ava->aa_value,
 408                 &keys );
 409
 410         if( rc != LDAP_SUCCESS ) {
 411                 Debug( LDAP_DEBUG_TRACE,
 412                         "<= bdb_approx_candidates: (%s) MR filter failed (%d)\n",
 413                         prefix.bv_val, rc, 0 );
 414                 return rc;
 415         }
 416
 417         if( keys == NULL ) {
 418                 Debug( LDAP_DEBUG_TRACE,
 419                         "<= bdb_approx_candidates: no keys (%s)\n",
 420                         prefix.bv_val, 0, 0 );
 421                 return 0;
 422         }
 423
 424         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 425                 rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
 426
 427                 if( rc != LDAP_SUCCESS ) {
 428                         Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates key read failed (%d)\n",
 429                                 rc, 0, 0 );
 430                         break;
 431                 }
 432
 433                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 434                         Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates NULL\n",
 435                                 0, 0, 0 );
 436                         BDB_IDL_ZERO( ids );
 437                         break;
 438                 }
 439
 440                 bdb_idl_intersection( ids, tmp );
 441
 442                 if( BDB_IDL_IS_ZERO( ids ) )
 443                         break;
 444         }
 445
 446         bvarray_free( keys );
 447
 448         Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates %ld, first=%ld, last=%ld\n",
 449                 (long) ids[0],
 450                 (long) BDB_IDL_FIRST(ids),
 451                 (long) BDB_IDL_LAST(ids) );
 452
 453         return( rc );
 454 }
 455
 456 static int
 457 substring_candidates(
 458         Backend *be,
 459         SubstringsAssertion     *sub,
 460         ID *ids,
 461         ID *tmp )
 462 {
 463         DB      *db;
 464         int i;
 465         int rc;
 466         slap_mask_t mask;
 467         struct berval prefix = {0};
 468         struct berval *keys = NULL;
 469         MatchingRule *mr;
 470
 471         Debug( LDAP_DEBUG_TRACE, "=> bdb_substring_candidates\n", 0, 0, 0 );
 472
 473         rc = bdb_index_param( be, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
 474                 &db, &mask, &prefix );
 475
 476         if( rc != LDAP_SUCCESS ) {
 477                 Debug( LDAP_DEBUG_ANY,
 478                         "<= bdb_substring_candidates: index_param failed (%d)\n",
 479                         rc, 0, 0 );
 480                 return 0;
 481         }
 482
 483         if ( db == NULL ) {
 484                 Debug( LDAP_DEBUG_ANY,
 485                         "<= bdb_substring_candidates not indexed\n",
 486                         0, 0, 0 );
 487                 return 0;
 488         }
 489
 490         mr = sub->sa_desc->ad_type->sat_substr;
 491
 492         if( !mr ) {
 493                 return 0;
 494         }
 495
 496         if( !mr->smr_filter ) {
 497                 return 0;
 498         }
 499
 500         rc = (mr->smr_filter)(
 501                 LDAP_FILTER_SUBSTRINGS,
 502                 mask,
 503                 sub->sa_desc->ad_type->sat_syntax,
 504                 mr,
 505                 &prefix,
 506                 sub,
 507                 &keys );
 508
 509         if( rc != LDAP_SUCCESS ) {
 510                 Debug( LDAP_DEBUG_TRACE,
 511                         "<= bdb_substring_candidates: (%s) MR filter failed (%d)\n",
 512                         sub->sa_desc->ad_cname.bv_val, rc, 0 );
 513                 return 0;
 514         }
 515
 516         if( keys == NULL ) {
 517                 Debug( LDAP_DEBUG_TRACE,
 518                         "<= bdb_substring_candidates: (0x%04lx) no keys (%s)\n",
 519                         mask, sub->sa_desc->ad_cname.bv_val, 0 );
 520                 return 0;
 521         }
 522
 523         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 524                 rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
 525
 526                 if( rc != LDAP_SUCCESS ) {
 527                         Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates key read failed (%d)\n",
 528                                 rc, 0, 0 );
 529                         break;
 530                 }
 531
 532                 if( BDB_IDL_IS_ZERO( tmp ) ) {
 533                         Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates NULL\n",
 534                                 0, 0, 0 );
 535                         BDB_IDL_ZERO( ids );
 536                         break;
 537                 }
 538
 539                 bdb_idl_intersection( ids, tmp );
 540
 541                 if( BDB_IDL_IS_ZERO( ids ) )
 542                         break;
 543         }
 544
 545         bvarray_free( keys );
 546
 547         Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates %ld, first=%ld, last=%ld\n",
 548                 (long) ids[0],
 549                 (long) BDB_IDL_FIRST(ids),
 550                 (long) BDB_IDL_LAST(ids) );
 551
 552         return( 0 );
 553 }
 554
 555 #endif