git.sur5r.net Git - openldap/blob - servers/slapd/back-bdb2/filterindex.c

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