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