filterindex.c 8.43 KB
Newer Older
Kurt Zeilenga's avatar
Kurt Zeilenga committed
1
/* filterindex.c - generate the list of candidate entries from a filter */
2
/* $OpenLDAP$ */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
3
/*
Kurt Zeilenga's avatar
Kurt Zeilenga committed
4
 * Copyright 1998-2000 The OpenLDAP Foundation, All Rights Reserved.
Kurt Zeilenga's avatar
Kurt Zeilenga committed
5
6
 * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
 */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
7

Kurt Zeilenga's avatar
Kurt Zeilenga committed
8
9
#include "portable.h"

Kurt Zeilenga's avatar
Kurt Zeilenga committed
10
#include <stdio.h>
Kurt Zeilenga's avatar
Kurt Zeilenga committed
11
12
13
14

#include <ac/socket.h>
#include <ac/string.h>

Kurt Zeilenga's avatar
Kurt Zeilenga committed
15
16
17
#include "slap.h"
#include "back-ldbm.h"

18
19
20
21
22
23
#ifdef SLAPD_SCHEMA_NOT_COMPAT
ID_BLOCK *
filter_candidates(
    Backend	*be,
    Filter	*f )
{
24
	return idl_allids( be );
25
}
26

27
28
#else

29
30
31
32
33
static ID_BLOCK	*ava_candidates( Backend *be, Ava *ava, int type );
static ID_BLOCK	*presence_candidates( Backend *be, char *type );
static ID_BLOCK	*approx_candidates( Backend *be, Ava *ava );
static ID_BLOCK	*list_candidates( Backend *be, Filter *flist, int ftype );
static ID_BLOCK	*substring_candidates( Backend *be, Filter *f );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
34
35
static ID_BLOCK	*substring_comp_candidates( Backend *be, char *type,
	struct berval *val, int prepost );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
36

37
ID_BLOCK *
Kurt Zeilenga's avatar
Kurt Zeilenga committed
38
39
40
41
42
filter_candidates(
    Backend	*be,
    Filter	*f
)
{
43
	ID_BLOCK	*result, *tmp1, *tmp2;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
44
45
46
47
48

	Debug( LDAP_DEBUG_TRACE, "=> filter_candidates\n", 0, 0, 0 );

	result = NULL;
	switch ( f->f_choice ) {
49
50
51
52
53
54
55
56
57
	case SLAPD_FILTER_DN_ONE:
		Debug( LDAP_DEBUG_FILTER, "\tDN ONE\n", 0, 0, 0 );
		result = dn2idl( be, f->f_dn, DN_ONE_PREFIX );
		break;

	case SLAPD_FILTER_DN_SUBTREE:
		Debug( LDAP_DEBUG_FILTER, "\tDN SUBTREE\n", 0, 0, 0 );
		result = dn2idl( be, f->f_dn, DN_SUBTREE_PREFIX );
		break;
58

Kurt Zeilenga's avatar
Kurt Zeilenga committed
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
	case LDAP_FILTER_EQUALITY:
		Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
		result = ava_candidates( be, &f->f_ava, LDAP_FILTER_EQUALITY );
		break;

	case LDAP_FILTER_SUBSTRINGS:
		Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
		result = substring_candidates( be, f );
		break;

	case LDAP_FILTER_GE:
		Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
		result = ava_candidates( be, &f->f_ava, LDAP_FILTER_GE );
		break;

	case LDAP_FILTER_LE:
		Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
		result = ava_candidates( be, &f->f_ava, LDAP_FILTER_LE );
		break;

	case LDAP_FILTER_PRESENT:
		Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
		result = presence_candidates( be, f->f_type );
		break;

	case LDAP_FILTER_APPROX:
		Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
		result = approx_candidates( be, &f->f_ava );
		break;

	case LDAP_FILTER_AND:
		Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
		result = list_candidates( be, f->f_and, LDAP_FILTER_AND );
		break;

	case LDAP_FILTER_OR:
		Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
		result = list_candidates( be, f->f_or, LDAP_FILTER_OR );
		break;

	case LDAP_FILTER_NOT:
		Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
Hallvard Furuseth's avatar
Hallvard Furuseth committed
101
102
103
104
105
		tmp1 = idl_allids( be );
		tmp2 = filter_candidates( be, f->f_not );
		result = idl_notin( be, tmp1, tmp2 );
		idl_free( tmp2 );
		idl_free( tmp1 );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
106
107
108
		break;
	}

109
	Debug( LDAP_DEBUG_TRACE, "<= filter_candidates %ld\n",
110
	    result ? ID_BLOCK_NIDS(result) : 0, 0, 0 );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
111
112
113
	return( result );
}

114
static ID_BLOCK *
Kurt Zeilenga's avatar
Kurt Zeilenga committed
115
116
117
118
119
120
ava_candidates(
    Backend	*be,
    Ava		*ava,
    int		type
)
{
121
	ID_BLOCK	*idl;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
122
123
124
125
126

	Debug( LDAP_DEBUG_TRACE, "=> ava_candidates 0x%x\n", type, 0, 0 );

	switch ( type ) {
	case LDAP_FILTER_EQUALITY:
127
		idl = index_read( be, ava->ava_type, SLAP_INDEX_EQUALITY,
Kurt Zeilenga's avatar
Kurt Zeilenga committed
128
129
130
131
132
133
134
135
136
137
138
139
		    ava->ava_value.bv_val );
		break;

	case LDAP_FILTER_GE:
		idl = idl_allids( be );
		break;

	case LDAP_FILTER_LE:
		idl = idl_allids( be );
		break;
	}

140
	Debug( LDAP_DEBUG_TRACE, "<= ava_candidates %ld\n",
141
	    idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
142
143
144
	return( idl );
}

145
static ID_BLOCK *
Kurt Zeilenga's avatar
Kurt Zeilenga committed
146
147
148
149
150
presence_candidates(
    Backend	*be,
    char	*type
)
{
151
	ID_BLOCK	*idl;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
152
153
154

	Debug( LDAP_DEBUG_TRACE, "=> presence_candidates\n", 0, 0, 0 );

155
	idl = index_read( be, type, SLAP_INDEX_PRESENCE, "*" );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
156

157
	Debug( LDAP_DEBUG_TRACE, "<= presence_candidates %ld\n",
158
	    idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
159
160
161
	return( idl );
}

162
static ID_BLOCK *
Kurt Zeilenga's avatar
Kurt Zeilenga committed
163
164
165
166
167
168
approx_candidates(
    Backend	*be,
    Ava		*ava
)
{
	char	*w, *c;
169
	ID_BLOCK	*idl, *tmp;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
170
171
172
173
174
175
176

	Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 );

	idl = NULL;
	for ( w = first_word( ava->ava_value.bv_val ); w != NULL;
	    w = next_word( w ) ) {
		c = phonetic( w );
177
		if ( (tmp = index_read( be, ava->ava_type, SLAP_INDEX_APPROX, c ))
Kurt Zeilenga's avatar
Kurt Zeilenga committed
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
		    == NULL ) {
			free( c );
			idl_free( idl );
			Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n",
			    0, 0, 0 );
			return( NULL );
		}
		free( c );

		if ( idl == NULL ) {
			idl = tmp;
		} else {
			idl = idl_intersection( be, idl, tmp );
		}
	}

194
	Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %ld\n",
195
	    idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
196
197
198
	return( idl );
}

199
static ID_BLOCK *
Kurt Zeilenga's avatar
Kurt Zeilenga committed
200
201
202
203
204
205
list_candidates(
    Backend	*be,
    Filter	*flist,
    int		ftype
)
{
206
	ID_BLOCK	*idl, *tmp, *tmp2;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
	Filter	*f;

	Debug( LDAP_DEBUG_TRACE, "=> list_candidates 0x%x\n", ftype, 0, 0 );

	idl = NULL;
	for ( f = flist; f != NULL; f = f->f_next ) {
		if ( (tmp = filter_candidates( be, f )) == NULL &&
		    ftype == LDAP_FILTER_AND ) {
				Debug( LDAP_DEBUG_TRACE,
				    "<= list_candidates NULL\n", 0, 0, 0 );
				idl_free( idl );
				return( NULL );
		}

		tmp2 = idl;
		if ( idl == NULL ) {
			idl = tmp;
		} else if ( ftype == LDAP_FILTER_AND ) {
			idl = idl_intersection( be, idl, tmp );
			idl_free( tmp );
			idl_free( tmp2 );
		} else {
			idl = idl_union( be, idl, tmp );
			idl_free( tmp );
			idl_free( tmp2 );
		}
	}

235
	Debug( LDAP_DEBUG_TRACE, "<= list_candidates %ld\n",
236
	    idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
237
238
239
	return( idl );
}

240
static ID_BLOCK *
Kurt Zeilenga's avatar
Kurt Zeilenga committed
241
242
243
244
245
246
substring_candidates(
    Backend	*be,
    Filter	*f
)
{
	int	i;
247
	ID_BLOCK	*idl, *tmp, *tmp2;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
248
249
250
251
252
253
254

	Debug( LDAP_DEBUG_TRACE, "=> substring_candidates\n", 0, 0, 0 );

	idl = NULL;

	/* initial */
	if ( f->f_sub_initial != NULL ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
255
		if ( f->f_sub_initial->bv_len < SUBLEN - 1 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
256
257
258
259
260
261
262
263
264
			idl = idl_allids( be );
		} else if ( (idl = substring_comp_candidates( be, f->f_sub_type,
		    f->f_sub_initial, '^' )) == NULL ) {
			return( NULL );
		}
	}

	/* final */
	if ( f->f_sub_final != NULL ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
265
		if ( f->f_sub_final->bv_len < SUBLEN - 1 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
			tmp = idl_allids( be );
		} else if ( (tmp = substring_comp_candidates( be, f->f_sub_type,
		    f->f_sub_final, '$' )) == NULL ) {
			idl_free( idl );
			return( NULL );
		}

		if ( idl == NULL ) {
			idl = tmp;
		} else {
			tmp2 = idl;
			idl = idl_intersection( be, idl, tmp );
			idl_free( tmp );
			idl_free( tmp2 );
		}
	}

Kurt Zeilenga's avatar
Kurt Zeilenga committed
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
	if( f->f_sub_any != NULL ) {
		for ( i = 0; f->f_sub_any[i] != NULL; i++ ) {
			if ( f->f_sub_any[i]->bv_len < SUBLEN ) {
				tmp = idl_allids( be );
			} else if ( (tmp = substring_comp_candidates( be, f->f_sub_type,
				f->f_sub_any[i], 0 )) == NULL ) {
				idl_free( idl );
				return( NULL );
			}

			if ( idl == NULL ) {
				idl = tmp;
			} else {
				tmp2 = idl;
				idl = idl_intersection( be, idl, tmp );
				idl_free( tmp );
				idl_free( tmp2 );
			}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
301
302
303
		}
	}

304
	Debug( LDAP_DEBUG_TRACE, "<= substring_candidates %ld\n",
305
	    idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
306
307
308
	return( idl );
}

309
static ID_BLOCK *
Kurt Zeilenga's avatar
Kurt Zeilenga committed
310
311
312
substring_comp_candidates(
    Backend	*be,
    char	*type,
Kurt Zeilenga's avatar
Kurt Zeilenga committed
313
    struct berval	*bv,
Kurt Zeilenga's avatar
Kurt Zeilenga committed
314
315
316
317
    int		prepost
)
{
	int	i, len;
318
	ID_BLOCK	*idl, *tmp, *tmp2;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
319
320
	char	*p;
	char	buf[SUBLEN + 1];
Kurt Zeilenga's avatar
Kurt Zeilenga committed
321
	char	*val;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
322
323
324

	Debug( LDAP_DEBUG_TRACE, "=> substring_comp_candidates\n", 0, 0, 0 );

Kurt Zeilenga's avatar
Kurt Zeilenga committed
325
326
	val = bv->bv_val;
	len = bv->bv_len;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
327
328
329
330
331
332
333
334
335
336
	idl = NULL;

	/* prepend ^ for initial substring */
	if ( prepost == '^' ) {
		buf[0] = '^';
		for ( i = 0; i < SUBLEN - 1; i++ ) {
			buf[i + 1] = val[i];
		}
		buf[SUBLEN] = '\0';

337
		if ( (idl = index_read( be, type, SLAP_INDEX_SUBSTR, buf )) == NULL ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
338
339
340
341
342
343
344
345
346
347
			return( NULL );
		}
	} else if ( prepost == '$' ) {
		p = val + len - SUBLEN + 1;
		for ( i = 0; i < SUBLEN - 1; i++ ) {
			buf[i] = p[i];
		}
		buf[SUBLEN - 1] = '$';
		buf[SUBLEN] = '\0';

348
		if ( (idl = index_read( be, type, SLAP_INDEX_SUBSTR, buf )) == NULL ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
349
350
351
352
353
354
355
356
357
358
			return( NULL );
		}
	}

	for ( p = val; p < (val + len - SUBLEN + 1); p++ ) {
		for ( i = 0; i < SUBLEN; i++ ) {
			buf[i] = p[i];
		}
		buf[SUBLEN] = '\0';

359
		if ( (tmp = index_read( be, type, SLAP_INDEX_SUBSTR, buf )) == NULL ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
360
361
362
363
364
365
366
367
368
369
370
371
			idl_free( idl );
			return( NULL );
		}

		if ( idl == NULL ) {
			idl = tmp;
		} else {
			tmp2 = idl;
			idl = idl_intersection( be, idl, tmp );
			idl_free( tmp );
			idl_free( tmp2 );
		}
372
373
374
375
376

		/* break if no candidates */
		if( idl == NULL ) {
			break;
		}
377
378
379
380
381
382
383
384

		/* if we're down to two (or less) matches, stop searching */
		if( ID_BLOCK_NIDS(idl) < 3 ) {
			Debug( LDAP_DEBUG_TRACE, "substring_comp_candiates: "
				"down to a %ld matches, stopped search\n",
					(long) ID_BLOCK_NIDS(idl), 0, 0 );
			break;
		}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
385
386
	}

387
	Debug( LDAP_DEBUG_TRACE, "<= substring_comp_candidates %ld\n",
388
	    idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
389
390
	return( idl );
}
391
#endif