filterindex.c 19.3 KB
Newer Older
1
2
3
/* filterindex.c - generate the list of candidate entries from a filter */
/* $OpenLDAP$ */
/*
4
 * Copyright 1998-2003 The OpenLDAP Foundation, All Rights Reserved.
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
 */

#include "portable.h"

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

#include "back-bdb.h"
#include "idl.h"

static int presence_candidates(
	Backend *be,
	AttributeDescription *desc,
	ID *ids );

static int equality_candidates(
	Backend *be,
	AttributeAssertion *ava,
	ID *ids,
	ID *tmp );
static int approx_candidates(
	Backend *be,
	AttributeAssertion *ava,
	ID *ids,
	ID *tmp );
static int substring_candidates(
	Backend *be,
	SubstringsAssertion *sub,
	ID *ids,
	ID *tmp );

static int list_candidates(
	Backend *be,
	Filter *flist,
	int ftype,
	ID *ids,
	ID *tmp,
	ID *stack );

int
bdb_filter_candidates(
	Backend	*be,
	Filter	*f,
	ID *ids,
	ID *tmp,
	ID *stack )
{
Howard Chu's avatar
Howard Chu committed
53
	int rc = 0;
54
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
55
	LDAP_LOG ( INDEX, ENTRY, "=> bdb_filter_candidates\n", 0, 0, 0 );
56
57
58
59
60
61
62
#else
	Debug( LDAP_DEBUG_FILTER, "=> bdb_filter_candidates\n", 0, 0, 0 );
#endif

	switch ( f->f_choice ) {
	case SLAPD_FILTER_DN_ONE:
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
63
		LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tDN ONE\n", 0, 0, 0 );
64
65
66
67
#else
		Debug( LDAP_DEBUG_FILTER, "\tDN ONE\n", 0, 0, 0 );
#endif
		rc = bdb_dn2idl( be, f->f_dn, DN_ONE_PREFIX, ids );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
68
69
70
71
		if( rc == DB_NOTFOUND ) {
			BDB_IDL_ZERO( ids );
			rc = 0;
		}
72
73
74
75
		break;

	case SLAPD_FILTER_DN_SUBTREE:
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
76
		LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tDN SUBTREE\n", 0, 0, 0 );
77
78
79
80
81
82
83
84
#else
		Debug( LDAP_DEBUG_FILTER, "\tDN SUBTREE\n", 0, 0, 0 );
#endif
		rc = bdb_dn2idl( be, f->f_dn, DN_SUBTREE_PREFIX, ids );
		break;

	case LDAP_FILTER_PRESENT:
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
85
		LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tPRESENT\n", 0, 0, 0 );
86
87
88
89
90
91
92
93
#else
		Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
#endif
		rc = presence_candidates( be, f->f_desc, ids );
		break;

	case LDAP_FILTER_EQUALITY:
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
94
		LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tEQUALITY\n", 0, 0, 0 );
95
96
97
98
99
100
101
102
#else
		Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
#endif
		rc = equality_candidates( be, f->f_ava, ids, tmp );
		break;

	case LDAP_FILTER_APPROX:
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
103
		LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tAPPROX\n", 0, 0, 0 );
104
105
106
107
108
109
110
111
#else
		Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
#endif
		rc = approx_candidates( be, f->f_ava, ids, tmp );
		break;

	case LDAP_FILTER_SUBSTRINGS:
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
112
		LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tSUBSTRINGS\n", 0, 0, 0 );
113
114
115
116
117
118
119
120
121
#else
		Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
#endif
		rc = substring_candidates( be, f->f_sub, ids, tmp );
		break;

	case LDAP_FILTER_GE:
		/* no GE index, use pres */
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
122
		LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tGE\n", 0, 0, 0 );
123
124
125
126
127
128
129
130
131
#else
		Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
#endif
		rc = presence_candidates( be, f->f_ava->aa_desc, ids );
		break;

	case LDAP_FILTER_LE:
		/* no LE index, use pres */
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
132
		LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tLE\n", 0, 0, 0 );
133
134
135
136
137
138
139
140
141
#else
		Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
#endif
		rc = presence_candidates( be, f->f_ava->aa_desc, ids );
		break;

	case LDAP_FILTER_NOT:
		/* no indexing to support NOT filters */
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
142
		LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tNOT\n",0, 0, 0 );
143
144
145
#else
		Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
#endif
Howard Chu's avatar
Howard Chu committed
146
147
148
                { struct bdb_info *bdb = (struct bdb_info *) be->be_private;
		BDB_IDL_ALL( bdb, ids );
		}
149
150
151
152
		break;

	case LDAP_FILTER_AND:
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
153
		LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tAND\n", 0, 0, 0 );
154
155
156
157
158
159
160
161
162
#else
		Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
#endif
		rc = list_candidates( be, 
			f->f_and, LDAP_FILTER_AND, ids, tmp, stack );
		break;

	case LDAP_FILTER_OR:
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
163
		LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tOR\n", 0, 0, 0 );
164
165
166
167
168
169
170
171
172
#else
		Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
#endif
		rc = list_candidates( be, 
			f->f_or, LDAP_FILTER_OR, ids, tmp, stack );
		break;

	default:
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
173
		LDAP_LOG ( INDEX, ARGS, "=> bdb_filter_candidates: \tUNKNOWN\n", 0, 0, 0 );
174
175
176
177
#else
		Debug( LDAP_DEBUG_FILTER, "\tUNKNOWN %lu\n",
			(unsigned long) f->f_choice, 0, 0 );
#endif
178
179
180
181
		/* Must not return NULL, otherwise extended filters break */
                { struct bdb_info *bdb = (struct bdb_info *) be->be_private;
		BDB_IDL_ALL( bdb, ids );
		}
182
183
184
	}

#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
185
	LDAP_LOG ( INDEX, RESULTS, 
Kurt Zeilenga's avatar
Kurt Zeilenga committed
186
		"<= bdb_filter_candidates: id=%ld first=%ld last=%ld\n", 
Kurt Zeilenga's avatar
Kurt Zeilenga committed
187
		(long)ids[0], (long)BDB_IDL_FIRST( ids ), (long) BDB_IDL_LAST( ids ));
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
#else
	Debug( LDAP_DEBUG_FILTER,
		"<= bdb_filter_candidates: id=%ld first=%ld last=%ld\n",
		(long) ids[0],
		(long) BDB_IDL_FIRST( ids ),
		(long) BDB_IDL_LAST( ids ) );
#endif

	return rc;
}

static int
list_candidates(
	Backend	*be,
	Filter	*flist,
	int		ftype,
	ID *ids,
	ID *tmp,
	ID *save )
{
	struct bdb_info *bdb = (struct bdb_info *) be->be_private;
	int rc = 0;
	Filter	*f;

#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
213
	LDAP_LOG ( INDEX, ARGS, "=> bdb_list_candidates: 0x%x\n", ftype, 0 , 0 );
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
#else
	Debug( LDAP_DEBUG_FILTER, "=> bdb_list_candidates 0x%x\n", ftype, 0, 0 );
#endif

	for ( f = flist; f != NULL; f = f->f_next ) {
		rc = bdb_filter_candidates( be, f, save, tmp,
			save+BDB_IDL_UM_SIZE );

		if ( rc != 0 ) {
			if ( ftype == LDAP_FILTER_AND ) {
				rc = 0;
				continue;
			}
			break;
		}
		
		if ( ftype == LDAP_FILTER_AND ) {
Howard Chu's avatar
Howard Chu committed
231
232
233
234
235
			if ( f == flist ) {
				BDB_IDL_CPY( ids, save );
			} else {
				bdb_idl_intersection( ids, save );
			}
236
237
238
			if( BDB_IDL_IS_ZERO( ids ) )
				break;
		} else {
Howard Chu's avatar
Howard Chu committed
239
240
241
242
243
			if ( f == flist ) {
				BDB_IDL_CPY( ids, save );
			} else {
				bdb_idl_union( ids, save );
			}
244
245
246
		}
	}

Kurt Zeilenga's avatar
Kurt Zeilenga committed
247
	if( rc == LDAP_SUCCESS ) {
248
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
249
250
251
252
		LDAP_LOG ( INDEX, RESULTS, 
			"<= bdb_list_candidates: id=%ld first=%ld last=%ld\n",
			(long) ids[0], (long) BDB_IDL_FIRST( ids ), 
			(long) BDB_IDL_LAST( ids ) );
253
254
255
256
257
258
259
260
261
262
#else
		Debug( LDAP_DEBUG_FILTER,
			"<= bdb_list_candidates: id=%ld first=%ld last=%ld\n",
			(long) ids[0],
			(long) BDB_IDL_FIRST(ids),
			(long) BDB_IDL_LAST(ids) );
#endif

	} else {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
263
		LDAP_LOG ( INDEX, ARGS, "<= bdb_list_candidates: rc=%d\n", rc, 0, 0 );
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
#else
		Debug( LDAP_DEBUG_FILTER,
			"<= bdb_list_candidates: undefined rc=%d\n",
			rc, 0, 0 );
#endif
	}

	return rc;
}

static int
presence_candidates(
	Backend	*be,
	AttributeDescription *desc,
	ID *ids )
{
	struct bdb_info *bdb = (struct bdb_info *) be->be_private;
	DB *db;
	int rc;
	slap_mask_t mask;
284
	struct berval prefix = {0, NULL};
285
286

#ifdef NEW_LOGGING
287
288
	LDAP_LOG ( INDEX, ENTRY, "=> bdb_presence_candidates (%s)\n", 
			desc->ad_cname.bv_val, 0, 0 );
289
#else
290
291
	Debug( LDAP_DEBUG_TRACE, "=> bdb_presence_candidates (%s)\n",
			desc->ad_cname.bv_val, 0, 0 );
292
293
294
295
296
297
298
299
300
301
302
303
#endif

	if( desc == slap_schema.si_ad_objectClass ) {
		BDB_IDL_ALL( bdb, ids );
		return 0;
	}

	rc = bdb_index_param( be, desc, LDAP_FILTER_PRESENT,
		&db, &mask, &prefix );

	if( rc != LDAP_SUCCESS ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
304
		LDAP_LOG ( INDEX, RESULTS, 
305
306
307
			"<= bdb_presence_candidates: (%s) index_param "
			"returned=%d\n",
			desc->ad_cname.bv_val, rc, 0 );
308
309
#else
		Debug( LDAP_DEBUG_TRACE,
310
311
312
			"<= bdb_presence_candidates: (%s) index_param "
			"returned=%d\n",
			desc->ad_cname.bv_val, rc, 0 );
313
314
315
316
317
318
319
#endif
		return 0;
	}

	if( db == NULL ) {
		/* not indexed */
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
320
		LDAP_LOG(INDEX, RESULTS, 
321
322
			"<= bdb_presence_candidates: (%s) not indexed\n",
			desc->ad_cname.bv_val, 0, 0 );
323
324
#else
		Debug( LDAP_DEBUG_TRACE,
325
326
			"<= bdb_presence_candidates: (%s) not indexed\n",
			desc->ad_cname.bv_val, 0, 0 );
327
328
329
330
331
332
#endif
		return 0;
	}

	if( prefix.bv_val == NULL ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
333
		LDAP_LOG(INDEX, RESULTS, 
334
335
			"<= bdb_presence_candidates: (%s) no prefix\n",
			desc->ad_cname.bv_val, 0, 0 );
336
337
#else
		Debug( LDAP_DEBUG_TRACE,
338
339
			"<= bdb_presence_candidates: (%s) no prefix\n",
			desc->ad_cname.bv_val, 0, 0 );
340
341
342
343
344
345
346
347
348
349
350
#endif
		return 0;
	}

	rc = bdb_key_read( be, db, NULL, &prefix, ids );

	if( rc == DB_NOTFOUND ) {
		BDB_IDL_ZERO( ids );
		rc = 0;
	} else if( rc != LDAP_SUCCESS ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
351
		LDAP_LOG ( INDEX, RESULTS, 
352
353
354
			"<= bdb_presence_candidates: (%s) "
			"key read failed (%d)\n",
			desc->ad_cname.bv_val, rc, 0 );
355
356
#else
		Debug( LDAP_DEBUG_TRACE,
357
358
359
			"<= bdb_presense_candidates: (%s) "
			"key read failed (%d)\n",
			desc->ad_cname.bv_val, rc, 0 );
360
361
362
363
364
#endif
		goto done;
	}

#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
365
366
367
	LDAP_LOG ( INDEX, RESULTS, 
		"<= bdb_presence_candidates: id=%ld first=%ld last=%ld\n",
		(long)ids[0], (long)BDB_IDL_FIRST( ids ), (long)BDB_IDL_LAST( ids ) );
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
#else
	Debug(LDAP_DEBUG_TRACE,
		"<= bdb_presence_candidates: id=%ld first=%ld last=%ld\n",
		(long) ids[0],
		(long) BDB_IDL_FIRST(ids),
		(long) BDB_IDL_LAST(ids) );
#endif

done:
	return rc;
}

static int
equality_candidates(
	Backend	*be,
	AttributeAssertion *ava,
	ID *ids,
	ID *tmp )
{
	DB	*db;
	int i;
	int rc;
	slap_mask_t mask;
391
	struct berval prefix = {0, NULL};
392
393
394
395
	struct berval *keys = NULL;
	MatchingRule *mr;

#ifdef NEW_LOGGING
396
397
	LDAP_LOG ( INDEX, ENTRY, "=> bdb_equality_candidates (%s)\n",
			ava->aa_desc->ad_cname.bv_val, 0, 0 );
398
#else
399
400
	Debug( LDAP_DEBUG_TRACE, "=> bdb_equality_candidates (%s)\n",
			ava->aa_desc->ad_cname.bv_val, 0, 0 );
401
402
403
404
405
406
407
#endif

	rc = bdb_index_param( be, ava->aa_desc, LDAP_FILTER_EQUALITY,
		&db, &mask, &prefix );

	if( rc != LDAP_SUCCESS ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
408
		LDAP_LOG ( INDEX, RESULTS, 
409
410
411
			"<= bdb_equality_candidates: (%s) "
			"index_param failed (%d)\n", 
			ava->aa_desc->ad_cname.bv_val, rc, 0);
412
413
#else
		Debug( LDAP_DEBUG_ANY,
414
415
416
			"<= bdb_equality_candidates: (%s) "
			"index_param failed (%d)\n",
			ava->aa_desc->ad_cname.bv_val, rc, 0 );
417
418
419
420
421
422
#endif
		return rc;
	}

	if ( db == NULL ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
423
		LDAP_LOG(INDEX, RESULTS, 
424
425
			"<= bdb_equality_candidates: (%s) not indexed\n", 
			ava->aa_desc->ad_cname.bv_val, 0, 0 );
426
427
#else
		Debug( LDAP_DEBUG_ANY,
428
429
			"<= bdb_equality_candidates: (%s) not indexed\n", 
			ava->aa_desc->ad_cname.bv_val, 0, 0 );
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
#endif
		return -1;
	}

	mr = ava->aa_desc->ad_type->sat_equality;
	if( !mr ) {
		return -1;
	}

	if( !mr->smr_filter ) {
		return -1;
	}

	rc = (mr->smr_filter)(
		LDAP_FILTER_EQUALITY,
		mask,
		ava->aa_desc->ad_type->sat_syntax,
		mr,
		&prefix,
		&ava->aa_value,
		&keys );

	if( rc != LDAP_SUCCESS ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
454
		LDAP_LOG ( INDEX, RESULTS, 
455
456
457
			"<= bdb_equality_candidates: (%s, %s) "
			"MR filter failed (%d)\n",
			prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
458
459
#else
		Debug( LDAP_DEBUG_TRACE,
460
461
462
			"<= bdb_equality_candidates: (%s, %s) "
			"MR filter failed (%d)\n",
			prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
463
464
465
466
467
468
#endif
		return rc;
	}

	if( keys == NULL ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
469
		LDAP_LOG ( INDEX, RESULTS, 
470
471
			"<= bdb_equality_candidates: (%s) no keys\n", 
			ava->aa_desc->ad_cname.bv_val, 0, 0 );
472
473
#else
		Debug( LDAP_DEBUG_TRACE,
474
475
			"<= bdb_equality_candidates: (%s) no keys\n",
			ava->aa_desc->ad_cname.bv_val, 0, 0 );
476
477
478
479
480
481
482
483
484
485
486
487
#endif
		return 0;
	}

	for ( i= 0; keys[i].bv_val != NULL; i++ ) {
		rc = bdb_key_read( be, db, NULL, &keys[i], tmp );

		if( rc == DB_NOTFOUND ) {
			BDB_IDL_ZERO( ids );
			rc = 0;
		} else if( rc != LDAP_SUCCESS ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
488
			LDAP_LOG ( INDEX, RESULTS, 
489
490
491
				"<= bdb_equality_candidates: (%s) "
				"key read failed (%d)\n",
				ava->aa_desc->ad_cname.bv_val, rc, 0 );
492
493
#else
			Debug( LDAP_DEBUG_TRACE,
494
495
496
				"<= bdb_equality_candidates: (%s) "
				"key read failed (%d)\n",
				ava->aa_desc->ad_cname.bv_val, rc, 0 );
497
498
499
500
501
502
#endif
			break;
		}

		if( BDB_IDL_IS_ZERO( tmp ) ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
503
			LDAP_LOG ( INDEX, RESULTS,
504
505
				"<= bdb_equality_candidates: (%s) NULL\n",
				ava->aa_desc->ad_cname.bv_val, 0, 0);
506
507
#else
			Debug( LDAP_DEBUG_TRACE,
508
509
				"<= bdb_equality_candidates: (%s) NULL\n", 
				ava->aa_desc->ad_cname.bv_val, 0, 0 );
510
511
512
513
514
#endif
			BDB_IDL_ZERO( ids );
			break;
		}

Howard Chu's avatar
Howard Chu committed
515
516
517
518
519
		if ( i == 0 ) {
			BDB_IDL_CPY( ids, tmp );
		} else {
			bdb_idl_intersection( ids, tmp );
		}
520
521
522
523
524
525
526
527

		if( BDB_IDL_IS_ZERO( ids ) )
			break;
	}

	ber_bvarray_free( keys );

#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
528
529
530
531
	LDAP_LOG ( INDEX, RESULTS, 
		"<= bdb_equality_candidates: id=%ld first=%ld last=%ld\n", 
		(long) ids[0], (long) BDB_IDL_FIRST( ids ), 
		(long) BDB_IDL_LAST( ids ) );
532
533
#else
	Debug( LDAP_DEBUG_TRACE,
Kurt Zeilenga's avatar
Kurt Zeilenga committed
534
		"<= bdb_equality_candidates: id=%ld, first=%ld, last=%ld\n",
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
		(long) ids[0],
		(long) BDB_IDL_FIRST(ids),
		(long) BDB_IDL_LAST(ids) );
#endif
	return( rc );
}


static int
approx_candidates(
	Backend	*be,
	AttributeAssertion *ava,
	ID *ids,
	ID *tmp )
{
	DB	*db;
	int i;
	int rc;
	slap_mask_t mask;
554
	struct berval prefix = {0, NULL};
555
556
557
558
	struct berval *keys = NULL;
	MatchingRule *mr;

#ifdef NEW_LOGGING
559
560
	LDAP_LOG ( INDEX, ENTRY, "=> bdb_approx_candidates (%s)\n",
			ava->aa_desc->ad_cname.bv_val, 0, 0 );
561
#else
562
563
	Debug( LDAP_DEBUG_TRACE, "=> bdb_approx_candidates (%s)\n",
			ava->aa_desc->ad_cname.bv_val, 0, 0 );
564
565
566
567
568
569
570
#endif

	rc = bdb_index_param( be, ava->aa_desc, LDAP_FILTER_APPROX,
		&db, &mask, &prefix );

	if( rc != LDAP_SUCCESS ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
571
		LDAP_LOG ( INDEX, RESULTS, 
572
573
574
			"<= bdb_approx_candidates: (%s) "
			"index_param failed (%d)\n",
			ava->aa_desc->ad_cname.bv_val, rc, 0 );
575
576
#else
		Debug( LDAP_DEBUG_ANY,
577
578
579
			"<= bdb_approx_candidates: (%s) "
			"index_param failed (%d)\n",
			ava->aa_desc->ad_cname.bv_val, rc, 0 );
580
581
582
583
584
585
#endif
		return rc;
	}

	if ( db == NULL ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
586
		LDAP_LOG(INDEX, RESULTS, 
587
588
			"<= bdb_approx_candidates: (%s) not indexed\n",
			ava->aa_desc->ad_cname.bv_val, 0, 0 );
589
590
#else
		Debug( LDAP_DEBUG_ANY,
591
592
			"<= bdb_approx_candidates: (%s) not indexed\n",
			ava->aa_desc->ad_cname.bv_val, 0, 0 );
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
#endif
		return -1;
	}

	mr = ava->aa_desc->ad_type->sat_approx;
	if( !mr ) {
		/* no approx matching rule, try equality matching rule */
		mr = ava->aa_desc->ad_type->sat_equality;
	}

	if( !mr ) {
		return -1;
	}

	if( !mr->smr_filter ) {
		return -1;
	}

	rc = (mr->smr_filter)(
		LDAP_FILTER_APPROX,
		mask,
		ava->aa_desc->ad_type->sat_syntax,
		mr,
		&prefix,
		&ava->aa_value,
		&keys );

	if( rc != LDAP_SUCCESS ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
622
		LDAP_LOG ( INDEX, RESULTS, 
623
624
625
			"<= bdb_approx_candidates: (%s, %s) "
			"MR filter failed (%d)\n",
			prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
626
627
#else
		Debug( LDAP_DEBUG_TRACE,
628
629
630
			"<= bdb_approx_candidates: (%s, %s) "
			"MR filter failed (%d)\n",
			prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
631
632
633
634
635
636
#endif
		return rc;
	}

	if( keys == NULL ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
637
		LDAP_LOG ( INDEX, RESULTS, 
638
639
			"<= bdb_approx_candidates: (%s) no keys (%s)\n",
			prefix.bv_val, ava->aa_desc->ad_cname.bv_val, 0 );
640
641
#else
		Debug( LDAP_DEBUG_TRACE,
642
643
			"<= bdb_approx_candidates: (%s) no keys (%s)\n",
			prefix.bv_val, ava->aa_desc->ad_cname.bv_val, 0 );
644
645
646
647
648
649
650
651
652
653
654
655
656
#endif
		return 0;
	}

	for ( i= 0; keys[i].bv_val != NULL; i++ ) {
		rc = bdb_key_read( be, db, NULL, &keys[i], tmp );

		if( rc == DB_NOTFOUND ) {
			BDB_IDL_ZERO( ids );
			rc = 0;
			break;
		} else if( rc != LDAP_SUCCESS ) {
#ifdef NEW_LOGGING
657
658
659
660
			LDAP_LOG ( INDEX, RESULTS, 
				"<= bdb_approx_candidates: (%s) "
				"key read failed (%d)\n",
				ava->aa_desc->ad_cname.bv_val, rc, 0);
661
#else
662
663
664
665
			Debug( LDAP_DEBUG_TRACE,
				"<= bdb_approx_candidates: (%s) "
				"key read failed (%d)\n",
				ava->aa_desc->ad_cname.bv_val, rc, 0 );
666
667
668
669
670
671
#endif
			break;
		}

		if( BDB_IDL_IS_ZERO( tmp ) ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
672
			LDAP_LOG ( INDEX, RESULTS, 
673
674
				"<= bdb_approx_candidates: (%s) NULL\n",
				ava->aa_desc->ad_cname.bv_val, 0, 0 );
675
#else
676
677
678
			Debug( LDAP_DEBUG_TRACE,
				"<= bdb_approx_candidates: (%s) NULL\n",
				ava->aa_desc->ad_cname.bv_val, 0, 0 );
679
680
681
682
683
#endif
			BDB_IDL_ZERO( ids );
			break;
		}

Howard Chu's avatar
Howard Chu committed
684
685
686
687
688
		if ( i == 0 ) {
			BDB_IDL_CPY( ids, tmp );
		} else {
			bdb_idl_intersection( ids, tmp );
		}
689
690
691
692
693
694
695
696

		if( BDB_IDL_IS_ZERO( ids ) )
			break;
	}

	ber_bvarray_free( keys );

#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
697
698
699
700
	LDAP_LOG ( INDEX, RESULTS, 
		"<= bdb_approx_candidates: id=%ld first=%ld last=%ld\n", 
		(long) ids[0], (long) BDB_IDL_FIRST( ids ), 
		(long) BDB_IDL_LAST( ids ) );
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
#else
	Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates %ld, first=%ld, last=%ld\n",
		(long) ids[0],
		(long) BDB_IDL_FIRST(ids),
		(long) BDB_IDL_LAST(ids) );
#endif
	return( rc );
}

static int
substring_candidates(
	Backend	*be,
	SubstringsAssertion	*sub,
	ID *ids,
	ID *tmp )
{
	DB	*db;
	int i;
	int rc;
	slap_mask_t mask;
721
	struct berval prefix = {0, NULL};
722
723
724
725
	struct berval *keys = NULL;
	MatchingRule *mr;

#ifdef NEW_LOGGING
726
727
	LDAP_LOG ( INDEX, ENTRY, "=> bdb_substring_candidates (%s)\n",
			sub->sa_desc->ad_cname.bv_val, 0, 0 );
728
#else
729
730
	Debug( LDAP_DEBUG_TRACE, "=> bdb_substring_candidates (%s)\n",
			sub->sa_desc->ad_cname.bv_val, 0, 0 );
731
732
733
734
735
736
737
#endif

	rc = bdb_index_param( be, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
		&db, &mask, &prefix );

	if( rc != LDAP_SUCCESS ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
738
		LDAP_LOG ( INDEX, RESULTS, 
739
740
741
			"<= bdb_substring_candidates: (%s) "
			"index_param failed (%d)\n",
			sub->sa_desc->ad_cname.bv_val, rc, 0);
742
743
#else
		Debug( LDAP_DEBUG_ANY,
744
745
746
			"<= bdb_substring_candidates: (%s) "
			"index_param failed (%d)\n",
			sub->sa_desc->ad_cname.bv_val, rc, 0 );
747
748
749
750
751
752
#endif
		return rc;
	}

	if ( db == NULL ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
753
		LDAP_LOG ( INDEX, RESULTS, 
754
755
			"<= bdb_substring_candidates: (%s) not indexed\n",
			sub->sa_desc->ad_cname.bv_val, 0, 0 );
756
757
#else
		Debug( LDAP_DEBUG_ANY,
758
759
			"<= bdb_substring_candidates: (%s) not indexed\n",
			sub->sa_desc->ad_cname.bv_val, 0, 0 );
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
#endif
		return -1;
	}

	mr = sub->sa_desc->ad_type->sat_substr;

	if( !mr ) {
		return -1;
	}

	if( !mr->smr_filter ) {
		return -1;
	}

	rc = (mr->smr_filter)(
		LDAP_FILTER_SUBSTRINGS,
		mask,
		sub->sa_desc->ad_type->sat_syntax,
		mr,
		&prefix,
		sub,
		&keys );

	if( rc != LDAP_SUCCESS ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
785
		LDAP_LOG ( INDEX, RESULTS, 
786
787
			"<= bdb_substring_candidates: (%s) "
			"MR filter failed (%d)\n", 
Kurt Zeilenga's avatar
Kurt Zeilenga committed
788
			sub->sa_desc->ad_cname.bv_val, rc, 0 );
789
790
#else
		Debug( LDAP_DEBUG_TRACE,
791
792
			"<= bdb_substring_candidates: (%s) "
			"MR filter failed (%d)\n",
793
794
795
796
797
798
799
			sub->sa_desc->ad_cname.bv_val, rc, 0 );
#endif
		return rc;
	}

	if( keys == NULL ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
800
		LDAP_LOG ( INDEX, RESULTS, 
Kurt Zeilenga's avatar
Kurt Zeilenga committed
801
			"<= bdb_substring_candidates: (0x%04lx) no keys (%s)\n",
Kurt Zeilenga's avatar
Kurt Zeilenga committed
802
			mask, sub->sa_desc->ad_cname.bv_val, 0 );
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
#else
		Debug( LDAP_DEBUG_TRACE,
			"<= bdb_substring_candidates: (0x%04lx) no keys (%s)\n",
			mask, sub->sa_desc->ad_cname.bv_val, 0 );
#endif
		return 0;
	}

	for ( i= 0; keys[i].bv_val != NULL; i++ ) {
		rc = bdb_key_read( be, db, NULL, &keys[i], tmp );

		if( rc == DB_NOTFOUND ) {
			BDB_IDL_ZERO( ids );
			rc = 0;
			break;
		} else if( rc != LDAP_SUCCESS ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
820
			LDAP_LOG ( INDEX, RESULTS, 
821
822
823
				"<= bdb_substring_candidates: (%s) "
				"key read failed (%d)\n",
				sub->sa_desc->ad_cname.bv_val, rc, 0 );
824
#else
825
826
827
828
			Debug( LDAP_DEBUG_TRACE,
				"<= bdb_substring_candidates: (%s) "
				"key read failed (%d)\n",
				sub->sa_desc->ad_cname.bv_val, rc, 0 );
829
830
831
832
833
834
#endif
			break;
		}

		if( BDB_IDL_IS_ZERO( tmp ) ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
835
			LDAP_LOG ( INDEX, RESULTS, 
836
837
				"<= bdb_substring_candidates: (%s) NULL\n",
				sub->sa_desc->ad_cname.bv_val, 0, 0 );
838
#else
839
840
841
			Debug( LDAP_DEBUG_TRACE,
				"<= bdb_substring_candidates: (%s) NULL\n",
				sub->sa_desc->ad_cname.bv_val, 0, 0 );
842
843
844
845
846
#endif
			BDB_IDL_ZERO( ids );
			break;
		}

Howard Chu's avatar
Howard Chu committed
847
848
849
850
851
		if ( i == 0 ) {
			BDB_IDL_CPY( ids, tmp );
		} else {
			bdb_idl_intersection( ids, tmp );
		}
852
853
854
855
856
857
858
859

		if( BDB_IDL_IS_ZERO( ids ) )
			break;
	}

	ber_bvarray_free( keys );

#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
860
861
862
863
	LDAP_LOG ( INDEX, RESULTS, 
		"<= bdb_substring_candidates: id=%ld first=%ld last=%ld\n",
		(long) ids[0], (long) BDB_IDL_FIRST( ids ), 
		(long) BDB_IDL_LAST( ids ) );
864
#else
Kurt Zeilenga's avatar
Kurt Zeilenga committed
865
	Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates: %ld, first=%ld, last=%ld\n",
866
867
868
869
870
871
872
		(long) ids[0],
		(long) BDB_IDL_FIRST(ids),
		(long) BDB_IDL_LAST(ids) );
#endif
	return( 0 );
}