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