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-1999 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 *ava_candidates( Backend *be, Ava *ava, int type );
  19 static ID_BLOCK *presence_candidates( Backend *be, char *type );
  20 static ID_BLOCK *approx_candidates( Backend *be, Ava *ava );
  21 static ID_BLOCK *list_candidates( Backend *be, Filter *flist, int ftype );
  22 static ID_BLOCK *substring_candidates( Backend *be, Filter *f );
  23 static ID_BLOCK *substring_comp_candidates( Backend *be, char *type,
  24         struct berval *val, int prepost );
  25
  26 /*
  27  * test_filter - test a filter against a single entry.
  28  * returns      0       filter matched
  29  *              -1      filter did not match
  30  *              >0      an ldap error code
  31  */
  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_EQUALITY:
  56                 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
  57                 result = ava_candidates( be, &f->f_ava, LDAP_FILTER_EQUALITY );
  58                 break;
  59
  60         case LDAP_FILTER_SUBSTRINGS:
  61                 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
  62                 result = substring_candidates( be, f );
  63                 break;
  64
  65         case LDAP_FILTER_GE:
  66                 Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
  67                 result = ava_candidates( be, &f->f_ava, LDAP_FILTER_GE );
  68                 break;
  69
  70         case LDAP_FILTER_LE:
  71                 Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
  72                 result = ava_candidates( be, &f->f_ava, LDAP_FILTER_LE );
  73                 break;
  74
  75         case LDAP_FILTER_PRESENT:
  76                 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
  77                 result = presence_candidates( be, f->f_type );
  78                 break;
  79
  80         case LDAP_FILTER_APPROX:
  81                 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
  82                 result = approx_candidates( be, &f->f_ava );
  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 ava_candidates(
 112     Backend     *be,
 113     Ava         *ava,
 114     int         type
 115 )
 116 {
 117         ID_BLOCK        *idl;
 118
 119         Debug( LDAP_DEBUG_TRACE, "=> ava_candidates 0x%x\n", type, 0, 0 );
 120
 121         switch ( type ) {
 122         case LDAP_FILTER_EQUALITY:
 123                 idl = index_read( be, ava->ava_type, SLAP_INDEX_EQUALITY,
 124                     ava->ava_value.bv_val );
 125                 break;
 126
 127         case LDAP_FILTER_GE:
 128                 idl = idl_allids( be );
 129                 break;
 130
 131         case LDAP_FILTER_LE:
 132                 idl = idl_allids( be );
 133                 break;
 134         }
 135
 136         Debug( LDAP_DEBUG_TRACE, "<= ava_candidates %ld\n",
 137             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 138         return( idl );
 139 }
 140
 141 static ID_BLOCK *
 142 presence_candidates(
 143     Backend     *be,
 144     char        *type
 145 )
 146 {
 147         ID_BLOCK        *idl;
 148
 149         Debug( LDAP_DEBUG_TRACE, "=> presence_candidates\n", 0, 0, 0 );
 150
 151         idl = index_read( be, type, SLAP_INDEX_PRESENCE, "*" );
 152
 153         Debug( LDAP_DEBUG_TRACE, "<= presence_candidates %ld\n",
 154             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 155         return( idl );
 156 }
 157
 158 static ID_BLOCK *
 159 approx_candidates(
 160     Backend     *be,
 161     Ava         *ava
 162 )
 163 {
 164         char    *w, *c;
 165         ID_BLOCK        *idl, *tmp;
 166
 167         Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 );
 168
 169         idl = NULL;
 170         for ( w = first_word( ava->ava_value.bv_val ); w != NULL;
 171             w = next_word( w ) ) {
 172                 c = phonetic( w );
 173                 if ( (tmp = index_read( be, ava->ava_type, SLAP_INDEX_APPROX, c ))
 174                     == NULL ) {
 175                         free( c );
 176                         idl_free( idl );
 177                         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n",
 178                             0, 0, 0 );
 179                         return( NULL );
 180                 }
 181                 free( c );
 182
 183                 if ( idl == NULL ) {
 184                         idl = tmp;
 185                 } else {
 186                         idl = idl_intersection( be, idl, tmp );
 187                 }
 188         }
 189
 190         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %ld\n",
 191             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 192         return( idl );
 193 }
 194
 195 static ID_BLOCK *
 196 list_candidates(
 197     Backend     *be,
 198     Filter      *flist,
 199     int         ftype
 200 )
 201 {
 202         ID_BLOCK        *idl, *tmp, *tmp2;
 203         Filter  *f;
 204
 205         Debug( LDAP_DEBUG_TRACE, "=> list_candidates 0x%x\n", ftype, 0, 0 );
 206
 207         idl = NULL;
 208         for ( f = flist; f != NULL; f = f->f_next ) {
 209                 if ( (tmp = filter_candidates( be, f )) == NULL &&
 210                     ftype == LDAP_FILTER_AND ) {
 211                                 Debug( LDAP_DEBUG_TRACE,
 212                                     "<= list_candidates NULL\n", 0, 0, 0 );
 213                                 idl_free( idl );
 214                                 return( NULL );
 215                 }
 216
 217                 tmp2 = idl;
 218                 if ( idl == NULL ) {
 219                         idl = tmp;
 220                 } else if ( ftype == LDAP_FILTER_AND ) {
 221                         idl = idl_intersection( be, idl, tmp );
 222                         idl_free( tmp );
 223                         idl_free( tmp2 );
 224                 } else {
 225                         idl = idl_union( be, idl, tmp );
 226                         idl_free( tmp );
 227                         idl_free( tmp2 );
 228                 }
 229         }
 230
 231         Debug( LDAP_DEBUG_TRACE, "<= list_candidates %ld\n",
 232             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 233         return( idl );
 234 }
 235
 236 static ID_BLOCK *
 237 substring_candidates(
 238     Backend     *be,
 239     Filter      *f
 240 )
 241 {
 242         int     i;
 243         ID_BLOCK        *idl, *tmp, *tmp2;
 244
 245         Debug( LDAP_DEBUG_TRACE, "=> substring_candidates\n", 0, 0, 0 );
 246
 247         idl = NULL;
 248
 249         /* initial */
 250         if ( f->f_sub_initial != NULL ) {
 251                 if ( f->f_sub_initial->bv_len < SUBLEN - 1 ) {
 252                         idl = idl_allids( be );
 253                 } else if ( (idl = substring_comp_candidates( be, f->f_sub_type,
 254                     f->f_sub_initial, '^' )) == NULL ) {
 255                         return( NULL );
 256                 }
 257         }
 258
 259         /* final */
 260         if ( f->f_sub_final != NULL ) {
 261                 if ( f->f_sub_final->bv_len < SUBLEN - 1 ) {
 262                         tmp = idl_allids( be );
 263                 } else if ( (tmp = substring_comp_candidates( be, f->f_sub_type,
 264                     f->f_sub_final, '$' )) == NULL ) {
 265                         idl_free( idl );
 266                         return( NULL );
 267                 }
 268
 269                 if ( idl == NULL ) {
 270                         idl = tmp;
 271                 } else {
 272                         tmp2 = idl;
 273                         idl = idl_intersection( be, idl, tmp );
 274                         idl_free( tmp );
 275                         idl_free( tmp2 );
 276                 }
 277         }
 278
 279         if( f->f_sub_any != NULL ) {
 280                 for ( i = 0; f->f_sub_any[i] != NULL; i++ ) {
 281                         if ( f->f_sub_any[i]->bv_len < SUBLEN ) {
 282                                 tmp = idl_allids( be );
 283                         } else if ( (tmp = substring_comp_candidates( be, f->f_sub_type,
 284                                 f->f_sub_any[i], 0 )) == NULL ) {
 285                                 idl_free( idl );
 286                                 return( NULL );
 287                         }
 288
 289                         if ( idl == NULL ) {
 290                                 idl = tmp;
 291                         } else {
 292                                 tmp2 = idl;
 293                                 idl = idl_intersection( be, idl, tmp );
 294                                 idl_free( tmp );
 295                                 idl_free( tmp2 );
 296                         }
 297                 }
 298         }
 299
 300         Debug( LDAP_DEBUG_TRACE, "<= substring_candidates %ld\n",
 301             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 302         return( idl );
 303 }
 304
 305 static ID_BLOCK *
 306 substring_comp_candidates(
 307     Backend     *be,
 308     char        *type,
 309     struct berval       *bv,
 310     int         prepost
 311 )
 312 {
 313         int     i, len;
 314         ID_BLOCK        *idl, *tmp, *tmp2;
 315         char    *p;
 316         char    buf[SUBLEN + 1];
 317         char    *val;
 318
 319         Debug( LDAP_DEBUG_TRACE, "=> substring_comp_candidates\n", 0, 0, 0 );
 320
 321         val = bv->bv_val;
 322         len = bv->bv_len;
 323         idl = NULL;
 324
 325         /* prepend ^ for initial substring */
 326         if ( prepost == '^' ) {
 327                 buf[0] = '^';
 328                 for ( i = 0; i < SUBLEN - 1; i++ ) {
 329                         buf[i + 1] = val[i];
 330                 }
 331                 buf[SUBLEN] = '\0';
 332
 333                 if ( (idl = index_read( be, type, SLAP_INDEX_SUB, buf )) == NULL ) {
 334                         return( NULL );
 335                 }
 336         } else if ( prepost == '$' ) {
 337                 p = val + len - SUBLEN + 1;
 338                 for ( i = 0; i < SUBLEN - 1; i++ ) {
 339                         buf[i] = p[i];
 340                 }
 341                 buf[SUBLEN - 1] = '$';
 342                 buf[SUBLEN] = '\0';
 343
 344                 if ( (idl = index_read( be, type, SLAP_INDEX_SUB, buf )) == NULL ) {
 345                         return( NULL );
 346                 }
 347         }
 348
 349         for ( p = val; p < (val + len - SUBLEN + 1); p++ ) {
 350                 for ( i = 0; i < SUBLEN; i++ ) {
 351                         buf[i] = p[i];
 352                 }
 353                 buf[SUBLEN] = '\0';
 354
 355                 if ( (tmp = index_read( be, type, SLAP_INDEX_SUB, buf )) == NULL ) {
 356                         idl_free( idl );
 357                         return( NULL );
 358                 }
 359
 360                 if ( idl == NULL ) {
 361                         idl = tmp;
 362                 } else {
 363                         tmp2 = idl;
 364                         idl = idl_intersection( be, idl, tmp );
 365                         idl_free( tmp );
 366                         idl_free( tmp2 );
 367                 }
 368
 369                 /* break if no candidates */
 370                 if( idl == NULL ) {
 371                         break;
 372                 }
 373
 374                 /* if we're down to two (or less) matches, stop searching */
 375                 if( ID_BLOCK_NIDS(idl) < 3 ) {
 376                         Debug( LDAP_DEBUG_TRACE, "substring_comp_candiates: "
 377                                 "down to a %ld matches, stopped search\n",
 378                                         (long) ID_BLOCK_NIDS(idl), 0, 0 );
 379                         break;
 380                 }
 381         }
 382
 383         Debug( LDAP_DEBUG_TRACE, "<= substring_comp_candidates %ld\n",
 384             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 385         return( idl );
 386 }