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