filterindex.c 22.8 KB
Newer Older
1
2
/* filterindex.c - generate the list of candidate entries from a filter */
/* $OpenLDAP$ */
Kurt Zeilenga's avatar
Notices    
Kurt Zeilenga committed
3
4
/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
 *
Kurt Zeilenga's avatar
Kurt Zeilenga committed
5
 * Copyright 2000-2004 The OpenLDAP Foundation.
Kurt Zeilenga's avatar
Notices    
Kurt Zeilenga committed
6
7
8
9
10
11
12
13
14
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted only as authorized by the OpenLDAP
 * Public License.
 *
 * A copy of this license is available in the file LICENSE in the
 * top-level directory of the distribution or, alternatively, at
 * <http://www.OpenLDAP.org/license.html>.
15
16
17
18
19
20
21
22
23
24
25
 */

#include "portable.h"

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

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

static int presence_candidates(
Howard Chu's avatar
Howard Chu committed
26
	Operation *op,
27
28
	AttributeDescription *desc,
	ID *ids );
29

30
static int equality_candidates(
Howard Chu's avatar
Howard Chu committed
31
	Operation *op,
32
	AttributeAssertion *ava,
33
34
	ID *ids,
	ID *tmp );
35
36
37
38
39
40
static int inequality_candidates(
	Operation *op,
	AttributeAssertion *ava,
	ID *ids,
	ID *tmp,
	int gtorlt );
41
static int approx_candidates(
Howard Chu's avatar
Howard Chu committed
42
	Operation *op,
43
	AttributeAssertion *ava,
44
45
	ID *ids,
	ID *tmp );
46
static int substring_candidates(
Howard Chu's avatar
Howard Chu committed
47
	Operation *op,
48
	SubstringsAssertion *sub,
49
50
	ID *ids,
	ID *tmp );
51
52

static int list_candidates(
Howard Chu's avatar
Howard Chu committed
53
	Operation *op,
54
55
	Filter *flist,
	int ftype,
56
	ID *ids,
57
58
	ID *tmp,
	ID *stack );
59

60
#ifdef LDAP_COMP_MATCH
61
static int
62
63
64
65
66
67
ext_candidates(
        Operation *op,
        MatchingRuleAssertion *mra,
        ID *ids,
        ID *tmp,
        ID *stack);
Jong Hyuk Choi's avatar
Jong Hyuk Choi committed
68
69
70
71
72
73
74
75
76

static int
comp_candidates (
	Operation *op,
	MatchingRuleAssertion *mra,
	ComponentFilter *f,
	ID *ids,
	ID *tmp,
	ID *stack);
77
78
#endif

79
80
int
bdb_filter_candidates(
Howard Chu's avatar
Howard Chu committed
81
	Operation *op,
82
	Filter	*f,
83
	ID *ids,
84
85
	ID *tmp,
	ID *stack )
86
{
Howard Chu's avatar
Howard Chu committed
87
	int rc = 0;
88
89
90
	Debug( LDAP_DEBUG_FILTER, "=> bdb_filter_candidates\n", 0, 0, 0 );

	switch ( f->f_choice ) {
91
	case SLAPD_FILTER_COMPUTED:
92
		switch( f->f_result ) {
93
94
95
96
		case SLAPD_COMPARE_UNDEFINED:
		/* This technically is not the same as FALSE, but it
		 * certainly will produce no matches.
		 */
97
		/* FALL THRU */
98
99
100
101
102
103
104
		case LDAP_COMPARE_FALSE:
			BDB_IDL_ZERO( ids );
			break;
		case LDAP_COMPARE_TRUE: {
			struct bdb_info *bdb = (struct bdb_info *)op->o_bd->be_private;
			BDB_IDL_ALL( bdb, ids );
			} break;
105
		case LDAP_SUCCESS:
106
			/* this is a pre-computed scope, leave it alone */
107
108
			break;
		}
109
		break;
110
111
	case LDAP_FILTER_PRESENT:
		Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
Howard Chu's avatar
Howard Chu committed
112
		rc = presence_candidates( op, f->f_desc, ids );
113
114
115
116
		break;

	case LDAP_FILTER_EQUALITY:
		Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
Howard Chu's avatar
Howard Chu committed
117
		rc = equality_candidates( op, f->f_ava, ids, tmp );
118
119
120
121
		break;

	case LDAP_FILTER_APPROX:
		Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
Howard Chu's avatar
Howard Chu committed
122
		rc = approx_candidates( op, f->f_ava, ids, tmp );
123
124
125
126
		break;

	case LDAP_FILTER_SUBSTRINGS:
		Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
Howard Chu's avatar
Howard Chu committed
127
		rc = substring_candidates( op, f->f_sub, ids, tmp );
128
129
130
		break;

	case LDAP_FILTER_GE:
131
		/* if no GE index, use pres */
132
		Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
133
134
135
136
137
		if( f->f_ava->aa_desc->ad_type->sat_ordering &&
			( f->f_ava->aa_desc->ad_type->sat_ordering->smr_usage && SLAP_MR_ORDERED_INDEX ) )
			rc = inequality_candidates( op, f->f_ava, ids, tmp, LDAP_FILTER_GE );
		else
			rc = presence_candidates( op, f->f_ava->aa_desc, ids );
138
139
140
		break;

	case LDAP_FILTER_LE:
141
		/* if no LE index, use pres */
142
		Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
143
144
145
146
147
		if( f->f_ava->aa_desc->ad_type->sat_ordering &&
			( f->f_ava->aa_desc->ad_type->sat_ordering->smr_usage && SLAP_MR_ORDERED_INDEX ) )
			rc = inequality_candidates( op, f->f_ava, ids, tmp, LDAP_FILTER_LE );
		else
			rc = presence_candidates( op, f->f_ava->aa_desc, ids );
148
149
		break;

150
151
152
	case LDAP_FILTER_NOT:
		/* no indexing to support NOT filters */
		Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
Howard Chu's avatar
Howard Chu committed
153
154
155
		{ struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
		BDB_IDL_ALL( bdb, ids );
		}
156
		break;
157
158
159

	case LDAP_FILTER_AND:
		Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
Howard Chu's avatar
Howard Chu committed
160
		rc = list_candidates( op, 
161
			f->f_and, LDAP_FILTER_AND, ids, tmp, stack );
162
163
164
165
		break;

	case LDAP_FILTER_OR:
		Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
Howard Chu's avatar
Howard Chu committed
166
		rc = list_candidates( op, 
167
			f->f_or, LDAP_FILTER_OR, ids, tmp, stack );
168
		break;
169
170
171
172
173
174
#ifdef LDAP_COMP_MATCH
	case LDAP_FILTER_EXT:
                Debug( LDAP_DEBUG_FILTER, "\tEXT\n", 0, 0, 0 );
                rc = ext_candidates( op, f->f_mra, ids, tmp, stack );
                break;
#endif
175
	default:
176
177
		Debug( LDAP_DEBUG_FILTER, "\tUNKNOWN %lu\n",
			(unsigned long) f->f_choice, 0, 0 );
178
179
180
181
		/* Must not return NULL, otherwise extended filters break */
		{ struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
		BDB_IDL_ALL( bdb, ids );
		}
182
183
184
185
	}

	Debug( LDAP_DEBUG_FILTER,
		"<= bdb_filter_candidates: id=%ld first=%ld last=%ld\n",
186
187
188
		(long) ids[0],
		(long) BDB_IDL_FIRST( ids ),
		(long) BDB_IDL_LAST( ids ) );
189

190
	return rc;
191
192
}

193
194
195
196
197
198
199
200
201
202
203
204
205
206
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
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
#ifdef LDAP_COMP_MATCH
static int
comp_list_candidates(
	Operation *op,
	MatchingRuleAssertion* mra,
	ComponentFilter	*flist,
	int	ftype,
	ID *ids,
	ID *tmp,
	ID *save )
{
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
	int rc = 0;
	ComponentFilter	*f;

	Debug( LDAP_DEBUG_FILTER, "=> comp_list_candidates 0x%x\n", ftype, 0, 0 );
	for ( f = flist; f != NULL; f = f->cf_next ) {
		/* ignore precomputed scopes */
		if ( f->cf_choice == SLAPD_FILTER_COMPUTED &&
		     f->cf_result == LDAP_SUCCESS ) {
			continue;
		}
		BDB_IDL_ZERO( save );
		rc = comp_candidates( op, mra, f, save, tmp, save+BDB_IDL_UM_SIZE );

		if ( rc != 0 ) {
			if ( ftype == LDAP_COMP_FILTER_AND ) {
				rc = 0;
				continue;
			}
			break;
		}
		
		if ( ftype == LDAP_COMP_FILTER_AND ) {
			if ( f == flist ) {
				BDB_IDL_CPY( ids, save );
			} else {
				bdb_idl_intersection( ids, save );
			}
			if( BDB_IDL_IS_ZERO( ids ) )
				break;
		} else {
			if ( f == flist ) {
				BDB_IDL_CPY( ids, save );
			} else {
				bdb_idl_union( ids, save );
			}
		}
	}

	if( rc == LDAP_SUCCESS ) {
		Debug( LDAP_DEBUG_FILTER,
			"<= comp_list_candidates: id=%ld first=%ld last=%ld\n",
			(long) ids[0],
			(long) BDB_IDL_FIRST(ids),
			(long) BDB_IDL_LAST(ids) );

	} else {
		Debug( LDAP_DEBUG_FILTER,
			"<= comp_list_candidates: undefined rc=%d\n",
			rc, 0, 0 );
	}

	return rc;
}

259
static int
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
comp_equality_candidates (
        Operation *op,
        MatchingRuleAssertion *mra,
	ComponentAssertion *ca,
        ID *ids,
        ID *tmp,
        ID *stack)
{
       struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
        DB      *db;
        int i;
        int rc;
        slap_mask_t mask;
        struct berval prefix = {0, NULL};
        struct berval *keys = NULL;
        MatchingRule *mr = mra->ma_rule;
        Syntax *sat_syntax;
	ComponentReference* cr_list, *cr;

        BDB_IDL_ALL( bdb, ids );

	bdb_attr_comp_ref ( op->o_bd->be_private, mra->ma_desc, &cr_list );
	if( !cr_list || !ca->ca_comp_ref )
		return 0;
	/* find a component reference to be indexed */
	sat_syntax = ca->ca_ma_rule->smr_syntax;
	for ( cr = cr_list ; cr ; cr = cr->cr_next ) {
		if ( cr->cr_string.bv_len == ca->ca_comp_ref->cr_string.bv_len &&
			strncmp( cr->cr_string.bv_val, ca->ca_comp_ref->cr_string.bv_val,cr->cr_string.bv_len ) == 0 )
			break;
	}
	
	if ( !cr )
		return 0;

        rc = bdb_index_param( op->o_bd, mra->ma_desc, LDAP_FILTER_EQUALITY,
                &db, &mask, &prefix );

        if( rc != LDAP_SUCCESS ) {
                return 0;
        }
        if ( db == NULL ) {
                return 0;
        }

        if( !mr ) {
                return 0;
        }

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

	rc = (ca->ca_ma_rule->smr_filter)(
                LDAP_FILTER_EQUALITY,
                cr->cr_indexmask,
                sat_syntax,
                ca->ca_ma_rule,
                &prefix,
                &ca->ca_ma_value,
                &keys, op->o_tmpmemctx );

        if( rc != LDAP_SUCCESS ) {
                return 0;
        }

        if( keys == NULL ) {
                return 0;
        }
        for ( i= 0; keys[i].bv_val != NULL; i++ ) {
                rc = bdb_key_read( op->o_bd, db, NULL, &keys[i], tmp, NULL, 0 );

                if( rc == DB_NOTFOUND ) {
                        BDB_IDL_ZERO( ids );
                        rc = 0;
                        break;
                } else if( rc != LDAP_SUCCESS ) {
                        break;
                }

                if( BDB_IDL_IS_ZERO( tmp ) ) {
                        BDB_IDL_ZERO( ids );
                        break;
                }

                if ( i == 0 ) {
                        BDB_IDL_CPY( ids, tmp );
                } else {
                        bdb_idl_intersection( ids, tmp );
                }

                if( BDB_IDL_IS_ZERO( ids ) )
                        break;
        }
        ber_bvarray_free_x( keys, op->o_tmpmemctx );

        Debug( LDAP_DEBUG_TRACE,
                "<= comp_equality_candidates: id=%ld, first=%ld, last=%ld\n",
                (long) ids[0],
                (long) BDB_IDL_FIRST(ids),
                (long) BDB_IDL_LAST(ids) );
        return( rc );
}

364
static int
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
comp_candidates (
	Operation *op,
	MatchingRuleAssertion *mra,
	ComponentFilter *f,
	ID *ids,
	ID *tmp,
	ID *stack)
{
	int	rc;

	if ( !f ) return LDAP_PROTOCOL_ERROR;

	Debug( LDAP_DEBUG_FILTER, "comp_candidates\n", 0, 0, 0 );
	switch ( f->cf_choice ) {
	case SLAPD_FILTER_COMPUTED:
		rc = f->cf_result;
		break;
	case LDAP_COMP_FILTER_AND:
		rc = comp_list_candidates( op, mra, f->cf_and, LDAP_COMP_FILTER_AND, ids, tmp, stack );
		break;
	case LDAP_COMP_FILTER_OR:
		rc = comp_list_candidates( op, mra, f->cf_or, LDAP_COMP_FILTER_OR, ids, tmp, stack );
		break;
	case LDAP_COMP_FILTER_NOT:
		/* No component indexing supported for NOT filter */
		Debug( LDAP_DEBUG_FILTER, "\tComponent NOT\n", 0, 0, 0 );
		{
			struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
			BDB_IDL_ALL( bdb, ids );
		}
		rc = LDAP_PROTOCOL_ERROR;
		break;
	case LDAP_COMP_FILTER_ITEM:
		rc = comp_equality_candidates( op, mra, f->cf_ca, ids, tmp, stack );
		break;
	default:
		{
			struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
			BDB_IDL_ALL( bdb, ids );
		}
		rc = LDAP_PROTOCOL_ERROR;
	}

	return( rc );
}

411
static int
412
413
414
415
416
417
418
419
420
421
422
ext_candidates(
        Operation *op,
        MatchingRuleAssertion *mra,
        ID *ids,
        ID *tmp,
        ID *stack)
{
	/*
	 * Currently Only Component Indexing for componentFilterMatch is supported
	 * Indexing for an extensible filter is not supported yet
	 */
423
424
425
	if ( !mra->ma_cf ) {
		struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
		BDB_IDL_ALL( bdb, ids );
426
		return 0;
427
428
	}

429
430
431
432
	return comp_candidates ( op, mra, mra->ma_cf, ids, tmp, stack);
}
#endif

433
434
static int
list_candidates(
Howard Chu's avatar
Howard Chu committed
435
	Operation *op,
436
437
	Filter	*flist,
	int		ftype,
438
	ID *ids,
439
440
	ID *tmp,
	ID *save )
441
{
Howard Chu's avatar
Howard Chu committed
442
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
443
444
	int rc = 0;
	Filter	*f;
445

446
447
	Debug( LDAP_DEBUG_FILTER, "=> bdb_list_candidates 0x%x\n", ftype, 0, 0 );
	for ( f = flist; f != NULL; f = f->f_next ) {
448
449
450
451
452
		/* ignore precomputed scopes */
		if ( f->f_choice == SLAPD_FILTER_COMPUTED &&
		     f->f_result == LDAP_SUCCESS ) {
			continue;
		}
Howard Chu's avatar
Howard Chu committed
453
		BDB_IDL_ZERO( save );
Howard Chu's avatar
Howard Chu committed
454
		rc = bdb_filter_candidates( op, f, save, tmp,
455
			save+BDB_IDL_UM_SIZE );
456
457

		if ( rc != 0 ) {
458
459
460
461
462
			if ( ftype == LDAP_FILTER_AND ) {
				rc = 0;
				continue;
			}
			break;
463
		}
464

465
		
466
		if ( ftype == LDAP_FILTER_AND ) {
467
468
469
470
471
			if ( f == flist ) {
				BDB_IDL_CPY( ids, save );
			} else {
				bdb_idl_intersection( ids, save );
			}
472
			if( BDB_IDL_IS_ZERO( ids ) )
473
474
				break;
		} else {
475
476
477
478
479
			if ( f == flist ) {
				BDB_IDL_CPY( ids, save );
			} else {
				bdb_idl_union( ids, save );
			}
480
481
		}
	}
482

Howard Chu's avatar
Howard Chu committed
483
	if( rc == LDAP_SUCCESS ) {
484
485
486
487
488
489
490
491
492
493
494
495
496
		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) );

	} else {
		Debug( LDAP_DEBUG_FILTER,
			"<= bdb_list_candidates: undefined rc=%d\n",
			rc, 0, 0 );
	}

	return rc;
497
498
499
500
}

static int
presence_candidates(
Howard Chu's avatar
Howard Chu committed
501
	Operation *op,
502
503
504
	AttributeDescription *desc,
	ID *ids )
{
Howard Chu's avatar
Howard Chu committed
505
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
506
507
508
	DB *db;
	int rc;
	slap_mask_t mask;
509
	struct berval prefix = {0, NULL};
510

511
512
	Debug( LDAP_DEBUG_TRACE, "=> bdb_presence_candidates (%s)\n",
			desc->ad_cname.bv_val, 0, 0 );
513

514
515
	BDB_IDL_ALL( bdb, ids );

516
517
518
519
	if( desc == slap_schema.si_ad_objectClass ) {
		return 0;
	}

Howard Chu's avatar
Howard Chu committed
520
	rc = bdb_index_param( op->o_bd, desc, LDAP_FILTER_PRESENT,
521
522
523
524
		&db, &mask, &prefix );

	if( rc != LDAP_SUCCESS ) {
		Debug( LDAP_DEBUG_TRACE,
525
526
527
			"<= bdb_presence_candidates: (%s) index_param "
			"returned=%d\n",
			desc->ad_cname.bv_val, rc, 0 );
528
		return 0;
529
530
531
532
533
	}

	if( db == NULL ) {
		/* not indexed */
		Debug( LDAP_DEBUG_TRACE,
534
535
			"<= bdb_presence_candidates: (%s) not indexed\n",
			desc->ad_cname.bv_val, 0, 0 );
536
		return 0;
537
538
	}

539
	if( prefix.bv_val == NULL ) {
540
		Debug( LDAP_DEBUG_TRACE,
541
542
			"<= bdb_presence_candidates: (%s) no prefix\n",
			desc->ad_cname.bv_val, 0, 0 );
543
		return -1;
544
545
	}

546
	rc = bdb_key_read( op->o_bd, db, NULL, &prefix, ids, NULL, 0 );
547
548

	if( rc == DB_NOTFOUND ) {
549
		BDB_IDL_ZERO( ids );
550
551
552
		rc = 0;
	} else if( rc != LDAP_SUCCESS ) {
		Debug( LDAP_DEBUG_TRACE,
553
554
555
			"<= bdb_presense_candidates: (%s) "
			"key read failed (%d)\n",
			desc->ad_cname.bv_val, rc, 0 );
556
557
558
559
560
		goto done;
	}

	Debug(LDAP_DEBUG_TRACE,
		"<= bdb_presence_candidates: id=%ld first=%ld last=%ld\n",
561
562
563
		(long) ids[0],
		(long) BDB_IDL_FIRST(ids),
		(long) BDB_IDL_LAST(ids) );
564
565
566
567
568
569
570

done:
	return rc;
}

static int
equality_candidates(
Howard Chu's avatar
Howard Chu committed
571
	Operation *op,
572
	AttributeAssertion *ava,
573
574
	ID *ids,
	ID *tmp )
575
{
576
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
577
578
579
580
	DB	*db;
	int i;
	int rc;
	slap_mask_t mask;
581
	struct berval prefix = {0, NULL};
582
	struct berval *keys = NULL;
583
584
	MatchingRule *mr;

585
586
	Debug( LDAP_DEBUG_TRACE, "=> bdb_equality_candidates (%s)\n",
			ava->aa_desc->ad_cname.bv_val, 0, 0 );
587

588
589
	BDB_IDL_ALL( bdb, ids );

Howard Chu's avatar
Howard Chu committed
590
	rc = bdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_EQUALITY,
591
592
593
594
		&db, &mask, &prefix );

	if( rc != LDAP_SUCCESS ) {
		Debug( LDAP_DEBUG_ANY,
595
596
597
			"<= bdb_equality_candidates: (%s) "
			"index_param failed (%d)\n",
			ava->aa_desc->ad_cname.bv_val, rc, 0 );
598
		return 0;
599
600
601
602
	}

	if ( db == NULL ) {
		Debug( LDAP_DEBUG_ANY,
603
604
			"<= bdb_equality_candidates: (%s) not indexed\n", 
			ava->aa_desc->ad_cname.bv_val, 0, 0 );
605
		return 0;
606
607
608
609
	}

	mr = ava->aa_desc->ad_type->sat_equality;
	if( !mr ) {
610
		return 0;
611
612
613
	}

	if( !mr->smr_filter ) {
614
		return 0;
615
616
617
618
619
620
621
	}

	rc = (mr->smr_filter)(
		LDAP_FILTER_EQUALITY,
		mask,
		ava->aa_desc->ad_type->sat_syntax,
		mr,
622
		&prefix,
623
		&ava->aa_value,
Howard Chu's avatar
Howard Chu committed
624
		&keys, op->o_tmpmemctx );
625
626
627

	if( rc != LDAP_SUCCESS ) {
		Debug( LDAP_DEBUG_TRACE,
628
629
630
			"<= bdb_equality_candidates: (%s, %s) "
			"MR filter failed (%d)\n",
			prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
631
		return 0;
632
633
634
635
	}

	if( keys == NULL ) {
		Debug( LDAP_DEBUG_TRACE,
636
637
			"<= bdb_equality_candidates: (%s) no keys\n",
			ava->aa_desc->ad_cname.bv_val, 0, 0 );
638
		return 0;
639
640
	}

641
	for ( i= 0; keys[i].bv_val != NULL; i++ ) {
642
		rc = bdb_key_read( op->o_bd, db, NULL, &keys[i], tmp, NULL, 0 );
643

644
645
646
		if( rc == DB_NOTFOUND ) {
			BDB_IDL_ZERO( ids );
			rc = 0;
Howard Chu's avatar
Howard Chu committed
647
			break;
648
		} else if( rc != LDAP_SUCCESS ) {
649
			Debug( LDAP_DEBUG_TRACE,
650
651
652
				"<= bdb_equality_candidates: (%s) "
				"key read failed (%d)\n",
				ava->aa_desc->ad_cname.bv_val, rc, 0 );
653
654
655
			break;
		}

656
		if( BDB_IDL_IS_ZERO( tmp ) ) {
657
			Debug( LDAP_DEBUG_TRACE,
658
659
				"<= bdb_equality_candidates: (%s) NULL\n", 
				ava->aa_desc->ad_cname.bv_val, 0, 0 );
660
			BDB_IDL_ZERO( ids );
661
662
663
			break;
		}

664
665
666
667
668
		if ( i == 0 ) {
			BDB_IDL_CPY( ids, tmp );
		} else {
			bdb_idl_intersection( ids, tmp );
		}
669

670
		if( BDB_IDL_IS_ZERO( ids ) )
671
			break;
672
673
	}

Howard Chu's avatar
Howard Chu committed
674
	ber_bvarray_free_x( keys, op->o_tmpmemctx );
675
676

	Debug( LDAP_DEBUG_TRACE,
Howard Chu's avatar
Howard Chu committed
677
		"<= bdb_equality_candidates: id=%ld, first=%ld, last=%ld\n",
678
679
680
		(long) ids[0],
		(long) BDB_IDL_FIRST(ids),
		(long) BDB_IDL_LAST(ids) );
681
	return( rc );
682
683
684
685
686
}


static int
approx_candidates(
Howard Chu's avatar
Howard Chu committed
687
	Operation *op,
688
	AttributeAssertion *ava,
689
690
	ID *ids,
	ID *tmp )
691
{
692
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
693
	DB	*db;
694
695
696
	int i;
	int rc;
	slap_mask_t mask;
697
	struct berval prefix = {0, NULL};
698
	struct berval *keys = NULL;
699
700
	MatchingRule *mr;

701
702
	Debug( LDAP_DEBUG_TRACE, "=> bdb_approx_candidates (%s)\n",
			ava->aa_desc->ad_cname.bv_val, 0, 0 );
703

704
705
	BDB_IDL_ALL( bdb, ids );

Howard Chu's avatar
Howard Chu committed
706
	rc = bdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_APPROX,
707
708
709
710
		&db, &mask, &prefix );

	if( rc != LDAP_SUCCESS ) {
		Debug( LDAP_DEBUG_ANY,
711
712
713
			"<= bdb_approx_candidates: (%s) "
			"index_param failed (%d)\n",
			ava->aa_desc->ad_cname.bv_val, rc, 0 );
714
		return 0;
715
716
717
718
	}

	if ( db == NULL ) {
		Debug( LDAP_DEBUG_ANY,
719
720
			"<= bdb_approx_candidates: (%s) not indexed\n",
			ava->aa_desc->ad_cname.bv_val, 0, 0 );
721
		return 0;
722
723
724
725
726
727
728
729
730
	}

	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 ) {
731
		return 0;
732
733
734
	}

	if( !mr->smr_filter ) {
735
		return 0;
736
737
738
739
740
741
742
	}

	rc = (mr->smr_filter)(
		LDAP_FILTER_APPROX,
		mask,
		ava->aa_desc->ad_type->sat_syntax,
		mr,
743
		&prefix,
744
		&ava->aa_value,
Howard Chu's avatar
Howard Chu committed
745
		&keys, op->o_tmpmemctx );
746
747
748

	if( rc != LDAP_SUCCESS ) {
		Debug( LDAP_DEBUG_TRACE,
749
750
751
			"<= bdb_approx_candidates: (%s, %s) "
			"MR filter failed (%d)\n",
			prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
752
		return 0;
753
754
755
756
	}

	if( keys == NULL ) {
		Debug( LDAP_DEBUG_TRACE,
757
758
			"<= bdb_approx_candidates: (%s) no keys (%s)\n",
			prefix.bv_val, ava->aa_desc->ad_cname.bv_val, 0 );
759
		return 0;
760
761
	}

762
	for ( i= 0; keys[i].bv_val != NULL; i++ ) {
763
		rc = bdb_key_read( op->o_bd, db, NULL, &keys[i], tmp, NULL, 0 );
764

765
766
767
768
769
		if( rc == DB_NOTFOUND ) {
			BDB_IDL_ZERO( ids );
			rc = 0;
			break;
		} else if( rc != LDAP_SUCCESS ) {
770
771
772
773
			Debug( LDAP_DEBUG_TRACE,
				"<= bdb_approx_candidates: (%s) "
				"key read failed (%d)\n",
				ava->aa_desc->ad_cname.bv_val, rc, 0 );
774
775
776
			break;
		}

777
		if( BDB_IDL_IS_ZERO( tmp ) ) {
778
779
780
			Debug( LDAP_DEBUG_TRACE,
				"<= bdb_approx_candidates: (%s) NULL\n",
				ava->aa_desc->ad_cname.bv_val, 0, 0 );
781
			BDB_IDL_ZERO( ids );
782
783
784
			break;
		}

785
786
787
788
789
		if ( i == 0 ) {
			BDB_IDL_CPY( ids, tmp );
		} else {
			bdb_idl_intersection( ids, tmp );
		}
790

791
		if( BDB_IDL_IS_ZERO( ids ) )
792
			break;
793
794
	}

Howard Chu's avatar
Howard Chu committed
795
	ber_bvarray_free_x( keys, op->o_tmpmemctx );
796

797
	Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates %ld, first=%ld, last=%ld\n",
798
799
800
		(long) ids[0],
		(long) BDB_IDL_FIRST(ids),
		(long) BDB_IDL_LAST(ids) );
801
	return( rc );
802
803
804
805
}

static int
substring_candidates(
Howard Chu's avatar
Howard Chu committed
806
	Operation *op,
807
	SubstringsAssertion	*sub,
808
809
	ID *ids,
	ID *tmp )
810
{
811
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
812
	DB	*db;
813
814
815
	int i;
	int rc;
	slap_mask_t mask;
816
	struct berval prefix = {0, NULL};
817
	struct berval *keys = NULL;
818
819
	MatchingRule *mr;

820
821
	Debug( LDAP_DEBUG_TRACE, "=> bdb_substring_candidates (%s)\n",
			sub->sa_desc->ad_cname.bv_val, 0, 0 );
822

823
824
	BDB_IDL_ALL( bdb, ids );

Howard Chu's avatar
Howard Chu committed
825
	rc = bdb_index_param( op->o_bd, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
826
827
828
829
		&db, &mask, &prefix );

	if( rc != LDAP_SUCCESS ) {
		Debug( LDAP_DEBUG_ANY,
830
831
832
			"<= bdb_substring_candidates: (%s) "
			"index_param failed (%d)\n",
			sub->sa_desc->ad_cname.bv_val, rc, 0 );
833
		return 0;
834
835
	}

836
	if ( db == NULL ) {
837
		Debug( LDAP_DEBUG_ANY,
838
839
			"<= bdb_substring_candidates: (%s) not indexed\n",
			sub->sa_desc->ad_cname.bv_val, 0, 0 );
840
		return 0;
841
842
843
844
845
	}

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

	if( !mr ) {
846
		return 0;
847
848
849
	}

	if( !mr->smr_filter ) {
850
		return 0;
851
852
853
854
855
856
857
	}

	rc = (mr->smr_filter)(
		LDAP_FILTER_SUBSTRINGS,
		mask,
		sub->sa_desc->ad_type->sat_syntax,
		mr,
858
		&prefix,
859
		sub,
Howard Chu's avatar
Howard Chu committed
860
		&keys, op->o_tmpmemctx );
861
862
863

	if( rc != LDAP_SUCCESS ) {
		Debug( LDAP_DEBUG_TRACE,
864
865
			"<= bdb_substring_candidates: (%s) "
			"MR filter failed (%d)\n",
866
			sub->sa_desc->ad_cname.bv_val, rc, 0 );
867
		return 0;
868
869
870
871
	}

	if( keys == NULL ) {
		Debug( LDAP_DEBUG_TRACE,
872
873
			"<= bdb_substring_candidates: (0x%04lx) no keys (%s)\n",
			mask, sub->sa_desc->ad_cname.bv_val, 0 );
874
		return 0;
875
876
	}

877
	for ( i= 0; keys[i].bv_val != NULL; i++ ) {
878
		rc = bdb_key_read( op->o_bd, db, NULL, &keys[i], tmp, NULL, 0 );
879

880
881
882
883
884
		if( rc == DB_NOTFOUND ) {
			BDB_IDL_ZERO( ids );
			rc = 0;
			break;
		} else if( rc != LDAP_SUCCESS ) {
885
886
887
888
			Debug( LDAP_DEBUG_TRACE,
				"<= bdb_substring_candidates: (%s) "
				"key read failed (%d)\n",
				sub->sa_desc->ad_cname.bv_val, rc, 0 );
889
890
891
			break;
		}

892
		if( BDB_IDL_IS_ZERO( tmp ) ) {
893
894
895
			Debug( LDAP_DEBUG_TRACE,
				"<= bdb_substring_candidates: (%s) NULL\n",
				sub->sa_desc->ad_cname.bv_val, 0, 0 );
896
			BDB_IDL_ZERO( ids );
897
898
899
			break;
		}

900
901
902
903
904
		if ( i == 0 ) {
			BDB_IDL_CPY( ids, tmp );
		} else {
			bdb_idl_intersection( ids, tmp );
		}
905

906
		if( BDB_IDL_IS_ZERO( ids ) )
907
			break;
908
909
	}

Howard Chu's avatar
Howard Chu committed
910
	ber_bvarray_free_x( keys, op->o_tmpmemctx );
911

Howard Chu's avatar
Howard Chu committed
912
	Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates: %ld, first=%ld, last=%ld\n",
913
914
915
		(long) ids[0],
		(long) BDB_IDL_FIRST(ids),
		(long) BDB_IDL_LAST(ids) );
916
	return( rc );
917
918
}

919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
static int
inequality_candidates(
	Operation *op,
	AttributeAssertion *ava,
	ID *ids,
	ID *tmp,
	int gtorlt )
{
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
	DB	*db;
	int i;
	int rc;
	slap_mask_t mask;
	struct berval prefix = {0, NULL};
	struct berval *keys = NULL;
	MatchingRule *mr;
	DBC * cursor = NULL;

	Debug( LDAP_DEBUG_TRACE, "=> bdb_inequality_candidates (%s)\n",
			ava->aa_desc->ad_cname.bv_val, 0, 0 );

	BDB_IDL_ALL( bdb, ids );

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

	if( rc != LDAP_SUCCESS ) {
		Debug( LDAP_DEBUG_ANY,
			"<= bdb_inequality_candidates: (%s) "
			"index_param failed (%d)\n",
			ava->aa_desc->ad_cname.bv_val, rc, 0 );
		return 0;
	}

	if ( db == NULL ) {
		Debug( LDAP_DEBUG_ANY,
			"<= bdb_inequality_candidates: (%s) not indexed\n", 
			ava->aa_desc->ad_cname.bv_val, 0, 0 );
		return 0;
	}

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

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

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

	if( rc != LDAP_SUCCESS ) {
		Debug( LDAP_DEBUG_TRACE,
			"<= bdb_inequality_candidates: (%s, %s) "
			"MR filter failed (%d)\n",
			prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
		return 0;
	}

	if( keys == NULL ) {
		Debug( LDAP_DEBUG_TRACE,
			"<= bdb_inequality_candidates: (%s) no keys\n",
			ava->aa_desc->ad_cname.bv_val, 0, 0 );
		return 0;
	}

	BDB_IDL_ZERO( ids );
	while(1) {
		rc = bdb_key_read( op->o_bd, db, NULL, &keys[0], tmp, &cursor, gtorlt );

		if( rc == DB_NOTFOUND ) {
			rc = 0;
			break;
		} else if( rc != LDAP_SUCCESS ) {
For faster browsing, not all history is shown. View entire blame