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