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
   3 #include "portable.h"
   4
   5 #include <stdio.h>
   6
   7 #include <ac/socket.h>
   8 #include <ac/string.h>
   9
  10 #include "slap.h"
  11 #include "back-ldbm.h"
  12
  13 static IDList   *ava_candidates( Backend *be, Ava *ava, int type );
  14 static IDList   *presence_candidates( Backend *be, char *type );
  15 static IDList   *approx_candidates( Backend *be, Ava *ava );
  16 static IDList   *list_candidates( Backend *be, Filter *flist, int ftype );
  17 static IDList   *substring_candidates( Backend *be, Filter *f );
  18 static IDList   *substring_comp_candidates( Backend *be, char *type, char *val, int prepost );
  19
  20 /*
  21  * test_filter - test a filter against a single entry.
  22  * returns      0       filter matched
  23  *              -1      filter did not match
  24  *              >0      an ldap error code
  25  */
  26
  27 IDList *
  28 filter_candidates(
  29     Backend     *be,
  30     Filter      *f
  31 )
  32 {
  33         IDList  *result;
  34
  35         Debug( LDAP_DEBUG_TRACE, "=> filter_candidates\n", 0, 0, 0 );
  36
  37         result = NULL;
  38         switch ( f->f_choice ) {
  39         case LDAP_FILTER_EQUALITY:
  40                 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
  41                 result = ava_candidates( be, &f->f_ava, LDAP_FILTER_EQUALITY );
  42                 break;
  43
  44         case LDAP_FILTER_SUBSTRINGS:
  45                 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
  46                 result = substring_candidates( be, f );
  47                 break;
  48
  49         case LDAP_FILTER_GE:
  50                 Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
  51                 result = ava_candidates( be, &f->f_ava, LDAP_FILTER_GE );
  52                 break;
  53
  54         case LDAP_FILTER_LE:
  55                 Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
  56                 result = ava_candidates( be, &f->f_ava, LDAP_FILTER_LE );
  57                 break;
  58
  59         case LDAP_FILTER_PRESENT:
  60                 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
  61                 result = presence_candidates( be, f->f_type );
  62                 break;
  63
  64         case LDAP_FILTER_APPROX:
  65                 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
  66                 result = approx_candidates( be, &f->f_ava );
  67                 break;
  68
  69         case LDAP_FILTER_AND:
  70                 Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
  71                 result = list_candidates( be, f->f_and, LDAP_FILTER_AND );
  72                 break;
  73
  74         case LDAP_FILTER_OR:
  75                 Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
  76                 result = list_candidates( be, f->f_or, LDAP_FILTER_OR );
  77                 break;
  78
  79         case LDAP_FILTER_NOT:
  80                 Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
  81                 result = idl_notin( be, idl_allids( be ), filter_candidates( be,
  82                     f->f_not ) );
  83                 break;
  84         }
  85
  86         Debug( LDAP_DEBUG_TRACE, "<= filter_candidates %lu\n",
  87             result ? result->b_nids : 0, 0, 0 );
  88         return( result );
  89 }
  90
  91 static IDList *
  92 ava_candidates(
  93     Backend     *be,
  94     Ava         *ava,
  95     int         type
  96 )
  97 {
  98         IDList  *idl;
  99
 100         Debug( LDAP_DEBUG_TRACE, "=> ava_candidates 0x%x\n", type, 0, 0 );
 101
 102         switch ( type ) {
 103         case LDAP_FILTER_EQUALITY:
 104                 idl = index_read( be, ava->ava_type, INDEX_EQUALITY,
 105                     ava->ava_value.bv_val );
 106                 break;
 107
 108         case LDAP_FILTER_GE:
 109                 idl = idl_allids( be );
 110                 break;
 111
 112         case LDAP_FILTER_LE:
 113                 idl = idl_allids( be );
 114                 break;
 115         }
 116
 117         Debug( LDAP_DEBUG_TRACE, "<= ava_candidates %lu\n",
 118             idl ? idl->b_nids : 0, 0, 0 );
 119         return( idl );
 120 }
 121
 122 static IDList *
 123 presence_candidates(
 124     Backend     *be,
 125     char        *type
 126 )
 127 {
 128         IDList  *idl;
 129
 130         Debug( LDAP_DEBUG_TRACE, "=> presence_candidates\n", 0, 0, 0 );
 131
 132         idl = index_read( be, type, 0, "*" );
 133
 134         Debug( LDAP_DEBUG_TRACE, "<= presence_candidates %lu\n",
 135             idl ? idl->b_nids : 0, 0, 0 );
 136         return( idl );
 137 }
 138
 139 static IDList *
 140 approx_candidates(
 141     Backend     *be,
 142     Ava         *ava
 143 )
 144 {
 145         char    *w, *c;
 146         IDList  *idl, *tmp;
 147
 148         Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 );
 149
 150         idl = NULL;
 151         for ( w = first_word( ava->ava_value.bv_val ); w != NULL;
 152             w = next_word( w ) ) {
 153                 c = phonetic( w );
 154                 if ( (tmp = index_read( be, ava->ava_type, INDEX_APPROX, c ))
 155                     == NULL ) {
 156                         free( c );
 157                         idl_free( idl );
 158                         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n",
 159                             0, 0, 0 );
 160                         return( NULL );
 161                 }
 162                 free( c );
 163
 164                 if ( idl == NULL ) {
 165                         idl = tmp;
 166                 } else {
 167                         idl = idl_intersection( be, idl, tmp );
 168                 }
 169         }
 170
 171         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %lu\n",
 172             idl ? idl->b_nids : 0, 0, 0 );
 173         return( idl );
 174 }
 175
 176 static IDList *
 177 list_candidates(
 178     Backend     *be,
 179     Filter      *flist,
 180     int         ftype
 181 )
 182 {
 183         IDList  *idl, *tmp, *tmp2;
 184         Filter  *f;
 185
 186         Debug( LDAP_DEBUG_TRACE, "=> list_candidates 0x%x\n", ftype, 0, 0 );
 187
 188         idl = NULL;
 189         for ( f = flist; f != NULL; f = f->f_next ) {
 190                 if ( (tmp = filter_candidates( be, f )) == NULL &&
 191                     ftype == LDAP_FILTER_AND ) {
 192                                 Debug( LDAP_DEBUG_TRACE,
 193                                     "<= list_candidates NULL\n", 0, 0, 0 );
 194                                 idl_free( idl );
 195                                 return( NULL );
 196                 }
 197
 198                 tmp2 = idl;
 199                 if ( idl == NULL ) {
 200                         idl = tmp;
 201                 } else if ( ftype == LDAP_FILTER_AND ) {
 202                         idl = idl_intersection( be, idl, tmp );
 203                         idl_free( tmp );
 204                         idl_free( tmp2 );
 205                 } else {
 206                         idl = idl_union( be, idl, tmp );
 207                         idl_free( tmp );
 208                         idl_free( tmp2 );
 209                 }
 210         }
 211
 212         Debug( LDAP_DEBUG_TRACE, "<= list_candidates %lu\n",
 213             idl ? idl->b_nids : 0, 0, 0 );
 214         return( idl );
 215 }
 216
 217 static IDList *
 218 substring_candidates(
 219     Backend     *be,
 220     Filter      *f
 221 )
 222 {
 223         int     i;
 224         IDList  *idl, *tmp, *tmp2;
 225
 226         Debug( LDAP_DEBUG_TRACE, "=> substring_candidates\n", 0, 0, 0 );
 227
 228         idl = NULL;
 229
 230         /* initial */
 231         if ( f->f_sub_initial != NULL ) {
 232                 if ( (int) strlen( f->f_sub_initial ) < SUBLEN - 1 ) {
 233                         idl = idl_allids( be );
 234                 } else if ( (idl = substring_comp_candidates( be, f->f_sub_type,
 235                     f->f_sub_initial, '^' )) == NULL ) {
 236                         return( NULL );
 237                 }
 238         }
 239
 240         /* final */
 241         if ( f->f_sub_final != NULL ) {
 242                 if ( (int) strlen( f->f_sub_final ) < SUBLEN - 1 ) {
 243                         tmp = idl_allids( be );
 244                 } else if ( (tmp = substring_comp_candidates( be, f->f_sub_type,
 245                     f->f_sub_final, '$' )) == NULL ) {
 246                         idl_free( idl );
 247                         return( NULL );
 248                 }
 249
 250                 if ( idl == NULL ) {
 251                         idl = tmp;
 252                 } else {
 253                         tmp2 = idl;
 254                         idl = idl_intersection( be, idl, tmp );
 255                         idl_free( tmp );
 256                         idl_free( tmp2 );
 257                 }
 258         }
 259
 260         for ( i = 0; f->f_sub_any != NULL && f->f_sub_any[i] != NULL; i++ ) {
 261                 if ( (int) strlen( f->f_sub_any[i] ) < SUBLEN ) {
 262                         tmp = idl_allids( be );
 263                 } else if ( (tmp = substring_comp_candidates( be, f->f_sub_type,
 264                     f->f_sub_any[i], 0 )) == 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         Debug( LDAP_DEBUG_TRACE, "<= substring_candidates %lu\n",
 280             idl ? idl->b_nids : 0, 0, 0 );
 281         return( idl );
 282 }
 283
 284 static IDList *
 285 substring_comp_candidates(
 286     Backend     *be,
 287     char        *type,
 288     char        *val,
 289     int         prepost
 290 )
 291 {
 292         int     i, len;
 293         IDList  *idl, *tmp, *tmp2;
 294         char    *p;
 295         char    buf[SUBLEN + 1];
 296
 297         Debug( LDAP_DEBUG_TRACE, "=> substring_comp_candidates\n", 0, 0, 0 );
 298
 299         len = strlen( val );
 300         idl = NULL;
 301
 302         /* prepend ^ for initial substring */
 303         if ( prepost == '^' ) {
 304                 buf[0] = '^';
 305                 for ( i = 0; i < SUBLEN - 1; i++ ) {
 306                         buf[i + 1] = val[i];
 307                 }
 308                 buf[SUBLEN] = '\0';
 309
 310                 if ( (idl = index_read( be, type, INDEX_SUB, buf )) == NULL ) {
 311                         return( NULL );
 312                 }
 313         } else if ( prepost == '$' ) {
 314                 p = val + len - SUBLEN + 1;
 315                 for ( i = 0; i < SUBLEN - 1; i++ ) {
 316                         buf[i] = p[i];
 317                 }
 318                 buf[SUBLEN - 1] = '$';
 319                 buf[SUBLEN] = '\0';
 320
 321                 if ( (idl = index_read( be, type, INDEX_SUB, buf )) == NULL ) {
 322                         return( NULL );
 323                 }
 324         }
 325
 326         for ( p = val; p < (val + len - SUBLEN + 1); p++ ) {
 327                 for ( i = 0; i < SUBLEN; i++ ) {
 328                         buf[i] = p[i];
 329                 }
 330                 buf[SUBLEN] = '\0';
 331
 332                 if ( (tmp = index_read( be, type, INDEX_SUB, buf )) == NULL ) {
 333                         idl_free( idl );
 334                         return( NULL );
 335                 }
 336
 337                 if ( idl == NULL ) {
 338                         idl = tmp;
 339                 } else {
 340                         tmp2 = idl;
 341                         idl = idl_intersection( be, idl, tmp );
 342                         idl_free( tmp );
 343                         idl_free( tmp2 );
 344                 }
 345         }
 346
 347         Debug( LDAP_DEBUG_TRACE, "<= substring_comp_candidates %lu\n",
 348             idl ? idl->b_nids : 0, 0, 0 );
 349         return( idl );
 350 }