1 /* filterindex.c - generate the list of candidate entries from a filter */
11 #include "back-bdb2.h"
13 static ID_BLOCK *ava_candidates( BackendDB *be, Ava *ava, int type );
14 static ID_BLOCK *presence_candidates( BackendDB *be, char *type );
15 static ID_BLOCK *approx_candidates( BackendDB *be, Ava *ava );
16 static ID_BLOCK *list_candidates( BackendDB *be, Filter *flist, int ftype );
17 static ID_BLOCK *substring_candidates( BackendDB *be, Filter *f );
18 static ID_BLOCK *substring_comp_candidates( BackendDB *be, char *type, char *val, int prepost );
21 * test_filter - test a filter against a single entry.
22 * returns 0 filter matched
23 * -1 filter did not match
24 * >0 an ldap error code
28 bdb2i_filter_candidates(
33 ID_BLOCK *result, *tmp1, *tmp2;
35 Debug( LDAP_DEBUG_TRACE, "=> bdb2i_filter_candidates\n", 0, 0, 0 );
38 switch ( f->f_choice ) {
39 case LDAP_FILTER_EQUALITY:
40 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
41 result = ava_candidates( be, &f->f_ava, LDAP_FILTER_EQUALITY );
44 case LDAP_FILTER_SUBSTRINGS:
45 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
46 result = substring_candidates( be, f );
50 Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
51 result = ava_candidates( be, &f->f_ava, LDAP_FILTER_GE );
55 Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
56 result = ava_candidates( be, &f->f_ava, LDAP_FILTER_LE );
59 case LDAP_FILTER_PRESENT:
60 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
61 result = presence_candidates( be, f->f_type );
64 case LDAP_FILTER_APPROX:
65 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
66 result = approx_candidates( be, &f->f_ava );
70 Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
71 result = list_candidates( be, f->f_and, LDAP_FILTER_AND );
75 Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
76 result = list_candidates( be, f->f_or, LDAP_FILTER_OR );
80 Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
81 tmp1 = bdb2i_idl_allids( be );
82 tmp2 = bdb2i_filter_candidates( be, f->f_not );
83 result = bdb2i_idl_notin( be, tmp1, tmp2 );
84 bdb2i_idl_free( tmp2 );
85 bdb2i_idl_free( tmp1 );
89 Debug( LDAP_DEBUG_TRACE, "<= bdb2i_filter_candidates %lu\n",
90 result ? ID_BLOCK_NIDS(result) : 0, 0, 0 );
103 Debug( LDAP_DEBUG_TRACE, "=> ava_candidates 0x%x\n", type, 0, 0 );
106 case LDAP_FILTER_EQUALITY:
107 idl = bdb2i_index_read( be, ava->ava_type, INDEX_EQUALITY,
108 ava->ava_value.bv_val );
112 idl = bdb2i_idl_allids( be );
116 idl = bdb2i_idl_allids( be );
120 Debug( LDAP_DEBUG_TRACE, "<= ava_candidates %lu\n",
121 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
133 Debug( LDAP_DEBUG_TRACE, "=> presence_candidates\n", 0, 0, 0 );
135 idl = bdb2i_index_read( be, type, 0, "*" );
137 Debug( LDAP_DEBUG_TRACE, "<= presence_candidates %lu\n",
138 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
151 Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 );
154 for ( w = first_word( ava->ava_value.bv_val ); w != NULL;
155 w = next_word( w ) ) {
157 if ( (tmp = bdb2i_index_read( be, ava->ava_type, INDEX_APPROX, c ))
160 bdb2i_idl_free( idl );
161 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n",
170 idl = bdb2i_idl_intersection( be, idl, tmp );
174 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %lu\n",
175 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
186 ID_BLOCK *idl, *tmp, *tmp2;
189 Debug( LDAP_DEBUG_TRACE, "=> list_candidates 0x%x\n", ftype, 0, 0 );
192 for ( f = flist; f != NULL; f = f->f_next ) {
193 if ( (tmp = bdb2i_filter_candidates( be, f )) == NULL &&
194 ftype == LDAP_FILTER_AND ) {
195 Debug( LDAP_DEBUG_TRACE,
196 "<= list_candidates NULL\n", 0, 0, 0 );
197 bdb2i_idl_free( idl );
204 } else if ( ftype == LDAP_FILTER_AND ) {
205 idl = bdb2i_idl_intersection( be, idl, tmp );
206 bdb2i_idl_free( tmp );
207 bdb2i_idl_free( tmp2 );
209 idl = bdb2i_idl_union( be, idl, tmp );
210 bdb2i_idl_free( tmp );
211 bdb2i_idl_free( tmp2 );
215 Debug( LDAP_DEBUG_TRACE, "<= list_candidates %lu\n",
216 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
221 substring_candidates(
227 ID_BLOCK *idl, *tmp, *tmp2;
229 Debug( LDAP_DEBUG_TRACE, "=> substring_candidates\n", 0, 0, 0 );
234 if ( f->f_sub_initial != NULL ) {
235 if ( (int) strlen( f->f_sub_initial ) < SUBLEN - 1 ) {
236 idl = bdb2i_idl_allids( be );
237 } else if ( (idl = substring_comp_candidates( be, f->f_sub_type,
238 f->f_sub_initial, '^' )) == NULL ) {
244 if ( f->f_sub_final != NULL ) {
245 if ( (int) strlen( f->f_sub_final ) < SUBLEN - 1 ) {
246 tmp = bdb2i_idl_allids( be );
247 } else if ( (tmp = substring_comp_candidates( be, f->f_sub_type,
248 f->f_sub_final, '$' )) == NULL ) {
249 bdb2i_idl_free( idl );
257 idl = bdb2i_idl_intersection( be, idl, tmp );
258 bdb2i_idl_free( tmp );
259 bdb2i_idl_free( tmp2 );
263 for ( i = 0; f->f_sub_any != NULL && f->f_sub_any[i] != NULL; i++ ) {
264 if ( (int) strlen( f->f_sub_any[i] ) < SUBLEN ) {
265 tmp = bdb2i_idl_allids( be );
266 } else if ( (tmp = substring_comp_candidates( be, f->f_sub_type,
267 f->f_sub_any[i], 0 )) == NULL ) {
268 bdb2i_idl_free( idl );
276 idl = bdb2i_idl_intersection( be, idl, tmp );
277 bdb2i_idl_free( tmp );
278 bdb2i_idl_free( tmp2 );
282 Debug( LDAP_DEBUG_TRACE, "<= substring_candidates %lu\n",
283 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
288 substring_comp_candidates(
296 ID_BLOCK *idl, *tmp, *tmp2;
298 char buf[SUBLEN + 1];
300 Debug( LDAP_DEBUG_TRACE, "=> substring_comp_candidates\n", 0, 0, 0 );
305 /* prepend ^ for initial substring */
306 if ( prepost == '^' ) {
308 for ( i = 0; i < SUBLEN - 1; i++ ) {
313 if ( (idl = bdb2i_index_read( be, type, INDEX_SUB, buf )) == NULL ) {
316 } else if ( prepost == '$' ) {
317 p = val + len - SUBLEN + 1;
318 for ( i = 0; i < SUBLEN - 1; i++ ) {
321 buf[SUBLEN - 1] = '$';
324 if ( (idl = bdb2i_index_read( be, type, INDEX_SUB, buf )) == NULL ) {
329 for ( p = val; p < (val + len - SUBLEN + 1); p++ ) {
330 for ( i = 0; i < SUBLEN; i++ ) {
335 if ( (tmp = bdb2i_index_read( be, type, INDEX_SUB, buf )) == NULL ) {
336 bdb2i_idl_free( idl );
344 idl = bdb2i_idl_intersection( be, idl, tmp );
345 bdb2i_idl_free( tmp );
346 bdb2i_idl_free( tmp2 );
350 Debug( LDAP_DEBUG_TRACE, "<= substring_comp_candidates %lu\n",
351 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );