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