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