git.sur5r.net Git - openldap/blob - servers/slapd/back-ldbm/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
  12 #include <ac/socket.h>
  13 #include <ac/string.h>
  14
  15 #include "slap.h"
  16 #include "back-ldbm.h"
  17
  18 static ID_BLOCK *presence_candidates(
  19         Backend *be,
  20         AttributeDescription *desc );
  21 static ID_BLOCK *equality_candidates(
  22         Backend *be, AttributeAssertion *ava );
  23 static ID_BLOCK *approx_candidates(
  24         Backend *be, AttributeAssertion *ava );
  25 static ID_BLOCK *substring_candidates(
  26         Backend *be,
  27         Filter *f );
  28 static ID_BLOCK *list_candidates(
  29         Backend *be,
  30         Filter *flist,
  31         int ftype );
  32
  33 ID_BLOCK *
  34 filter_candidates(
  35     Backend     *be,
  36     Filter      *f
  37 )
  38 {
  39         ID_BLOCK        *result, *tmp1, *tmp2;
  40
  41         Debug( LDAP_DEBUG_TRACE, "=> filter_candidates\n", 0, 0, 0 );
  42
  43         result = NULL;
  44         switch ( f->f_choice ) {
  45         case SLAPD_FILTER_DN_ONE:
  46                 Debug( LDAP_DEBUG_FILTER, "\tDN ONE\n", 0, 0, 0 );
  47                 result = dn2idl( be, f->f_dn, DN_ONE_PREFIX );
  48                 break;
  49
  50         case SLAPD_FILTER_DN_SUBTREE:
  51                 Debug( LDAP_DEBUG_FILTER, "\tDN SUBTREE\n", 0, 0, 0 );
  52                 result = dn2idl( be, f->f_dn, DN_SUBTREE_PREFIX );
  53                 break;
  54
  55         case LDAP_FILTER_PRESENT:
  56                 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
  57                 result = presence_candidates( be, f->f_desc );
  58                 break;
  59
  60         case LDAP_FILTER_EQUALITY:
  61                 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
  62                 result = equality_candidates( be, f->f_ava );
  63                 break;
  64
  65         case LDAP_FILTER_APPROX:
  66                 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
  67                 result = approx_candidates( be, f->f_ava );
  68                 break;
  69
  70         case LDAP_FILTER_SUBSTRINGS:
  71                 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
  72                 result = substring_candidates( be, f );
  73                 break;
  74
  75         case LDAP_FILTER_GE:
  76                 Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
  77                 result = idl_allids( be );
  78                 break;
  79
  80         case LDAP_FILTER_LE:
  81                 Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
  82                 result = idl_allids( be );
  83                 break;
  84
  85         case LDAP_FILTER_AND:
  86                 Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
  87                 result = list_candidates( be, f->f_and, LDAP_FILTER_AND );
  88                 break;
  89
  90         case LDAP_FILTER_OR:
  91                 Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
  92                 result = list_candidates( be, f->f_or, LDAP_FILTER_OR );
  93                 break;
  94
  95         case LDAP_FILTER_NOT:
  96                 Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
  97                 tmp1 = idl_allids( be );
  98                 tmp2 = filter_candidates( be, f->f_not );
  99                 result = idl_notin( be, tmp1, tmp2 );
 100                 idl_free( tmp2 );
 101                 idl_free( tmp1 );
 102                 break;
 103         }
 104
 105         Debug( LDAP_DEBUG_TRACE, "<= filter_candidates %ld\n",
 106             result ? ID_BLOCK_NIDS(result) : 0, 0, 0 );
 107         return( result );
 108 }
 109
 110 static ID_BLOCK *
 111 presence_candidates(
 112     Backend     *be,
 113         AttributeDescription *desc
 114 )
 115 {
 116         ID_BLOCK        *idl;
 117         DBCache *db;
 118         int rc;
 119         char *dbname;
 120         slap_index mask;
 121         struct berval *prefix;
 122
 123         Debug( LDAP_DEBUG_TRACE, "=> presence_candidates\n", 0, 0, 0 );
 124
 125         idl = idl_allids( be );
 126
 127         rc = index_param( be, desc, LDAP_FILTER_PRESENT,
 128                 &dbname, &mask, &prefix );
 129
 130         if( rc != LDAP_SUCCESS ) {
 131                 return idl;
 132         }
 133
 134         if( dbname == NULL ) {
 135                 /* not indexed */
 136                 return idl;
 137         }
 138
 139         db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_READER );
 140
 141         if ( db == NULL ) {
 142                 Debug( LDAP_DEBUG_ANY,
 143                     "<= presense_candidates db open failed (%s%s)\n",
 144                         dbname, LDBM_SUFFIX, 0 );
 145                 return idl;
 146         }
 147
 148         if( prefix != NULL ) {
 149                 idl_free( idl );
 150                 idl = NULL;
 151
 152                 rc = key_read( be, db, prefix, &idl );
 153
 154                 if( rc != LDAP_SUCCESS ) {
 155                         Debug( LDAP_DEBUG_TRACE, "<= presense_candidates key read failed (%d)\n",
 156                             rc, 0, 0 );
 157
 158                 } else if( idl == NULL ) {
 159                         Debug( LDAP_DEBUG_TRACE, "<= presense_candidates NULL\n",
 160                             0, 0, 0 );
 161                 }
 162         }
 163
 164         ldbm_cache_close( be, db );
 165
 166
 167         Debug( LDAP_DEBUG_TRACE, "<= presence_candidates %ld\n",
 168             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 169         return( idl );
 170 }
 171
 172 static ID_BLOCK *
 173 equality_candidates(
 174     Backend     *be,
 175         AttributeAssertion *ava
 176 )
 177 {
 178         ID_BLOCK        *idl;
 179         DBCache *db;
 180         int i;
 181         int rc;
 182         char *dbname;
 183         slap_index mask;
 184         struct berval *prefix;
 185         struct berval **keys = NULL;
 186         MatchingRule *mr;
 187
 188         Debug( LDAP_DEBUG_TRACE, "=> equality_candidates\n", 0, 0, 0 );
 189
 190         idl = idl_allids( be );
 191
 192         rc = index_param( be, ava->aa_desc, LDAP_FILTER_EQUALITY,
 193                 &dbname, &mask, &prefix );
 194
 195         if( rc != LDAP_SUCCESS ) {
 196                 return idl;
 197         }
 198
 199         if( dbname == NULL ) {
 200                 /* not indexed */
 201                 return idl;
 202         }
 203
 204         mr = ava->aa_desc->ad_type->sat_equality;
 205         if( !mr ) {
 206                 /* return LDAP_INAPPROPRIATE_MATCHING; */
 207                 return idl;
 208         }
 209
 210         if( !mr->smr_filter ) {
 211                 return idl;
 212         }
 213
 214         rc = (mr->smr_filter)(
 215                 LDAP_FILTER_EQUALITY,
 216                 ava->aa_desc->ad_type->sat_syntax,
 217                 mr,
 218                 prefix,
 219                 ava->aa_value,
 220                 &keys );
 221
 222         if( rc != LDAP_SUCCESS ) {
 223                 return idl;
 224         }
 225
 226         db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_READER );
 227
 228         if ( db == NULL ) {
 229                 Debug( LDAP_DEBUG_ANY,
 230                     "<= equality_candidates db open failed (%s%s)\n",
 231                         dbname, LDBM_SUFFIX, 0 );
 232                 return idl;
 233         }
 234
 235         for ( i= 0; keys[i] != NULL; i++ ) {
 236                 ID_BLOCK *save;
 237                 ID_BLOCK *tmp;
 238
 239                 rc = key_read( be, db, keys[i], &tmp );
 240
 241                 if( rc != LDAP_SUCCESS ) {
 242                         idl_free( idl );
 243                         idl = NULL;
 244                         Debug( LDAP_DEBUG_TRACE, "<= equality_candidates key read failed (%d)\n",
 245                             rc, 0, 0 );
 246                         break;
 247                 }
 248
 249                 if( tmp == NULL ) {
 250                         idl_free( idl );
 251                         idl = NULL;
 252                         Debug( LDAP_DEBUG_TRACE, "<= equality_candidates NULL\n",
 253                             0, 0, 0 );
 254                         break;
 255                 }
 256
 257                 save = idl;
 258                 idl = idl_intersection( be, idl, tmp );
 259                 idl_free( save );
 260
 261                 if( idl == NULL ) break;
 262         }
 263
 264         ber_bvecfree( keys );
 265
 266         ldbm_cache_close( be, db );
 267
 268
 269         Debug( LDAP_DEBUG_TRACE, "<= equality_candidates %ld\n",
 270             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 271         return( idl );
 272 }
 273
 274 static ID_BLOCK *
 275 approx_candidates(
 276     Backend     *be,
 277         AttributeAssertion *ava
 278 )
 279 {
 280         ID_BLOCK *idl;
 281         DBCache *db;
 282         int i;
 283         int rc;
 284         char *dbname;
 285         slap_index mask;
 286         struct berval *prefix;
 287         struct berval **keys = NULL;
 288         MatchingRule *mr;
 289
 290         Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 );
 291
 292         idl = idl_allids( be );
 293
 294         rc = index_param( be, ava->aa_desc, LDAP_FILTER_EQUALITY,
 295                 &dbname, &mask, &prefix );
 296
 297         if( rc != LDAP_SUCCESS ) {
 298                 return idl;
 299         }
 300
 301         if( dbname == NULL ) {
 302                 /* not indexed */
 303                 return idl;
 304         }
 305
 306         mr = ava->aa_desc->ad_type->sat_approx;
 307         if( mr == NULL ) {
 308                 /* no approx matching rule, try equality matching rule */
 309                 mr = ava->aa_desc->ad_type->sat_equality;
 310         }
 311
 312         if( !mr ) {
 313                 /* return LDAP_INAPPROPRIATE_MATCHING; */
 314                 return idl;
 315         }
 316
 317         if( !mr->smr_filter ) {
 318                 return idl;
 319         }
 320
 321         rc = (mr->smr_filter)(
 322                 LDAP_FILTER_EQUALITY,
 323                 ava->aa_desc->ad_type->sat_syntax,
 324                 mr,
 325                 prefix,
 326                 ava->aa_value,
 327                 &keys );
 328
 329         if( rc != LDAP_SUCCESS ) {
 330                 return idl;
 331         }
 332
 333         db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_READER );
 334
 335         if ( db == NULL ) {
 336                 Debug( LDAP_DEBUG_ANY,
 337                     "<= approx_candidates db open failed (%s%s)\n",
 338                         dbname, LDBM_SUFFIX, 0 );
 339                 return idl;
 340         }
 341
 342         for ( i= 0; keys[i] != NULL; i++ ) {
 343                 ID_BLOCK *save;
 344                 ID_BLOCK *tmp;
 345
 346                 rc = key_read( be, db, keys[i], &tmp );
 347
 348                 if( rc != LDAP_SUCCESS ) {
 349                         idl_free( idl );
 350                         idl = NULL;
 351                         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates key read failed (%d)\n",
 352                             rc, 0, 0 );
 353                         break;
 354                 }
 355
 356                 if( tmp == NULL ) {
 357                         idl_free( idl );
 358                         idl = NULL;
 359                         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n",
 360                             0, 0, 0 );
 361                         break;
 362                 }
 363
 364                 save = idl;
 365                 idl = idl_intersection( be, idl, tmp );
 366                 idl_free( save );
 367
 368                 if( idl == NULL ) break;
 369         }
 370
 371         ber_bvecfree( keys );
 372
 373         ldbm_cache_close( be, db );
 374
 375         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %ld\n",
 376             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 377         return( idl );
 378 }
 379
 380 static ID_BLOCK *
 381 list_candidates(
 382     Backend     *be,
 383     Filter      *flist,
 384     int         ftype
 385 )
 386 {
 387         ID_BLOCK        *idl, *tmp, *tmp2;
 388         Filter  *f;
 389
 390         Debug( LDAP_DEBUG_TRACE, "=> list_candidates 0x%x\n", ftype, 0, 0 );
 391
 392         idl = NULL;
 393         for ( f = flist; f != NULL; f = f->f_next ) {
 394                 if ( (tmp = filter_candidates( be, f )) == NULL &&
 395                     ftype == LDAP_FILTER_AND ) {
 396                                 Debug( LDAP_DEBUG_TRACE,
 397                                     "<= list_candidates NULL\n", 0, 0, 0 );
 398                                 idl_free( idl );
 399                                 return( NULL );
 400                 }
 401
 402                 tmp2 = idl;
 403                 if ( idl == NULL ) {
 404                         idl = tmp;
 405                 } else if ( ftype == LDAP_FILTER_AND ) {
 406                         idl = idl_intersection( be, idl, tmp );
 407                         idl_free( tmp );
 408                         idl_free( tmp2 );
 409                 } else {
 410                         idl = idl_union( be, idl, tmp );
 411                         idl_free( tmp );
 412                         idl_free( tmp2 );
 413                 }
 414         }
 415
 416         Debug( LDAP_DEBUG_TRACE, "<= list_candidates %ld\n",
 417             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 418         return( idl );
 419 }
 420
 421 static ID_BLOCK *
 422 substring_candidates(
 423     Backend     *be,
 424     Filter      *f
 425 )
 426 {
 427         ID_BLOCK *idl;
 428
 429         Debug( LDAP_DEBUG_TRACE, "=> substring_candidates\n", 0, 0, 0 );
 430
 431         idl = idl_allids( be );
 432         Debug( LDAP_DEBUG_TRACE, "<= substring_candidates %ld\n",
 433             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 434         return( idl );
 435 }
 436