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