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, *tmp1, *tmp2;
  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                 tmp1 = idl_allids( be );
  82                 tmp2 = filter_candidates( be, f->f_not );
  83                 result = idl_notin( be, tmp1, tmp2 );
  84                 idl_free( tmp2 );
  85                 idl_free( tmp1 );
  86                 break;
  87         }
  88
  89         Debug( LDAP_DEBUG_TRACE, "<= filter_candidates %lu\n",
  90             result ? result->b_nids : 0, 0, 0 );
  91         return( result );
  92 }
  93
  94 static IDList *
  95 ava_candidates(
  96     Backend     *be,
  97     Ava         *ava,
  98     int         type
  99 )
 100 {
 101         IDList  *idl;
 102
 103         Debug( LDAP_DEBUG_TRACE, "=> ava_candidates 0x%x\n", type, 0, 0 );
 104
 105         switch ( type ) {
 106         case LDAP_FILTER_EQUALITY:
 107                 idl = index_read( be, ava->ava_type, INDEX_EQUALITY,
 108                     ava->ava_value.bv_val );
 109                 break;
 110
 111         case LDAP_FILTER_GE:
 112                 idl = idl_allids( be );
 113                 break;
 114
 115         case LDAP_FILTER_LE:
 116                 idl = idl_allids( be );
 117                 break;
 118         }
 119
 120         Debug( LDAP_DEBUG_TRACE, "<= ava_candidates %lu\n",
 121             idl ? idl->b_nids : 0, 0, 0 );
 122         return( idl );
 123 }
 124
 125 static IDList *
 126 presence_candidates(
 127     Backend     *be,
 128     char        *type
 129 )
 130 {
 131         IDList  *idl;
 132
 133         Debug( LDAP_DEBUG_TRACE, "=> presence_candidates\n", 0, 0, 0 );
 134
 135         idl = index_read( be, type, 0, "*" );
 136
 137         Debug( LDAP_DEBUG_TRACE, "<= presence_candidates %lu\n",
 138             idl ? idl->b_nids : 0, 0, 0 );
 139         return( idl );
 140 }
 141
 142 static IDList *
 143 approx_candidates(
 144     Backend     *be,
 145     Ava         *ava
 146 )
 147 {
 148         char    *w, *c;
 149         IDList  *idl, *tmp;
 150
 151         Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 );
 152
 153         idl = NULL;
 154         for ( w = first_word( ava->ava_value.bv_val ); w != NULL;
 155             w = next_word( w ) ) {
 156                 c = phonetic( w );
 157                 if ( (tmp = index_read( be, ava->ava_type, INDEX_APPROX, c ))
 158                     == NULL ) {
 159                         free( c );
 160                         idl_free( idl );
 161                         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n",
 162                             0, 0, 0 );
 163                         return( NULL );
 164                 }
 165                 free( c );
 166
 167                 if ( idl == NULL ) {
 168                         idl = tmp;
 169                 } else {
 170                         idl = idl_intersection( be, idl, tmp );
 171                 }
 172         }
 173
 174         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %lu\n",
 175             idl ? idl->b_nids : 0, 0, 0 );
 176         return( idl );
 177 }
 178
 179 static IDList *
 180 list_candidates(
 181     Backend     *be,
 182     Filter      *flist,
 183     int         ftype
 184 )
 185 {
 186         IDList  *idl, *tmp, *tmp2;
 187         Filter  *f;
 188
 189         Debug( LDAP_DEBUG_TRACE, "=> list_candidates 0x%x\n", ftype, 0, 0 );
 190
 191         idl = NULL;
 192         for ( f = flist; f != NULL; f = f->f_next ) {
 193                 if ( (tmp = filter_candidates( be, f )) == NULL &&
 194                     ftype == LDAP_FILTER_AND ) {
 195                                 Debug( LDAP_DEBUG_TRACE,
 196                                     "<= list_candidates NULL\n", 0, 0, 0 );
 197                                 idl_free( idl );
 198                                 return( NULL );
 199                 }
 200
 201                 tmp2 = idl;
 202                 if ( idl == NULL ) {
 203                         idl = tmp;
 204                 } else if ( ftype == LDAP_FILTER_AND ) {
 205                         idl = idl_intersection( be, idl, tmp );
 206                         idl_free( tmp );
 207                         idl_free( tmp2 );
 208                 } else {
 209                         idl = idl_union( be, idl, tmp );
 210                         idl_free( tmp );
 211                         idl_free( tmp2 );
 212                 }
 213         }
 214
 215         Debug( LDAP_DEBUG_TRACE, "<= list_candidates %lu\n",
 216             idl ? idl->b_nids : 0, 0, 0 );
 217         return( idl );
 218 }
 219
 220 static IDList *
 221 substring_candidates(
 222     Backend     *be,
 223     Filter      *f
 224 )
 225 {
 226         int     i;
 227         IDList  *idl, *tmp, *tmp2;
 228
 229         Debug( LDAP_DEBUG_TRACE, "=> substring_candidates\n", 0, 0, 0 );
 230
 231         idl = NULL;
 232
 233         /* initial */
 234         if ( f->f_sub_initial != NULL ) {
 235                 if ( (int) strlen( f->f_sub_initial ) < SUBLEN - 1 ) {
 236                         idl = idl_allids( be );
 237                 } else if ( (idl = substring_comp_candidates( be, f->f_sub_type,
 238                     f->f_sub_initial, '^' )) == NULL ) {
 239                         return( NULL );
 240                 }
 241         }
 242
 243         /* final */
 244         if ( f->f_sub_final != NULL ) {
 245                 if ( (int) strlen( f->f_sub_final ) < SUBLEN - 1 ) {
 246                         tmp = idl_allids( be );
 247                 } else if ( (tmp = substring_comp_candidates( be, f->f_sub_type,
 248                     f->f_sub_final, '$' )) == NULL ) {
 249                         idl_free( idl );
 250                         return( NULL );
 251                 }
 252
 253                 if ( idl == NULL ) {
 254                         idl = tmp;
 255                 } else {
 256                         tmp2 = idl;
 257                         idl = idl_intersection( be, idl, tmp );
 258                         idl_free( tmp );
 259                         idl_free( tmp2 );
 260                 }
 261         }
 262
 263         for ( i = 0; f->f_sub_any != NULL && f->f_sub_any[i] != NULL; i++ ) {
 264                 if ( (int) strlen( f->f_sub_any[i] ) < SUBLEN ) {
 265                         tmp = idl_allids( be );
 266                 } else if ( (tmp = substring_comp_candidates( be, f->f_sub_type,
 267                     f->f_sub_any[i], 0 )) == NULL ) {
 268                         idl_free( idl );
 269                         return( NULL );
 270                 }
 271
 272                 if ( idl == NULL ) {
 273                         idl = tmp;
 274                 } else {
 275                         tmp2 = idl;
 276                         idl = idl_intersection( be, idl, tmp );
 277                         idl_free( tmp );
 278                         idl_free( tmp2 );
 279                 }
 280         }
 281
 282         Debug( LDAP_DEBUG_TRACE, "<= substring_candidates %lu\n",
 283             idl ? idl->b_nids : 0, 0, 0 );
 284         return( idl );
 285 }
 286
 287 static IDList *
 288 substring_comp_candidates(
 289     Backend     *be,
 290     char        *type,
 291     char        *val,
 292     int         prepost
 293 )
 294 {
 295         int     i, len;
 296         IDList  *idl, *tmp, *tmp2;
 297         char    *p;
 298         char    buf[SUBLEN + 1];
 299
 300         Debug( LDAP_DEBUG_TRACE, "=> substring_comp_candidates\n", 0, 0, 0 );
 301
 302         len = strlen( val );
 303         idl = NULL;
 304
 305         /* prepend ^ for initial substring */
 306         if ( prepost == '^' ) {
 307                 buf[0] = '^';
 308                 for ( i = 0; i < SUBLEN - 1; i++ ) {
 309                         buf[i + 1] = val[i];
 310                 }
 311                 buf[SUBLEN] = '\0';
 312
 313                 if ( (idl = index_read( be, type, INDEX_SUB, buf )) == NULL ) {
 314                         return( NULL );
 315                 }
 316         } else if ( prepost == '$' ) {
 317                 p = val + len - SUBLEN + 1;
 318                 for ( i = 0; i < SUBLEN - 1; i++ ) {
 319                         buf[i] = p[i];
 320                 }
 321                 buf[SUBLEN - 1] = '$';
 322                 buf[SUBLEN] = '\0';
 323
 324                 if ( (idl = index_read( be, type, INDEX_SUB, buf )) == NULL ) {
 325                         return( NULL );
 326                 }
 327         }
 328
 329         for ( p = val; p < (val + len - SUBLEN + 1); p++ ) {
 330                 for ( i = 0; i < SUBLEN; i++ ) {
 331                         buf[i] = p[i];
 332                 }
 333                 buf[SUBLEN] = '\0';
 334
 335                 if ( (tmp = index_read( be, type, INDEX_SUB, buf )) == NULL ) {
 336                         idl_free( idl );
 337                         return( NULL );
 338                 }
 339
 340                 if ( idl == NULL ) {
 341                         idl = tmp;
 342                 } else {
 343                         tmp2 = idl;
 344                         idl = idl_intersection( be, idl, tmp );
 345                         idl_free( tmp );
 346                         idl_free( tmp2 );
 347                 }
 348         }
 349
 350         Debug( LDAP_DEBUG_TRACE, "<= substring_comp_candidates %lu\n",
 351             idl ? idl->b_nids : 0, 0, 0 );
 352         return( idl );
 353 }