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