idl.c 25.6 KB
Newer Older
Kurt Zeilenga's avatar
Kurt Zeilenga committed
1
2
/* idl.c - ldap id list handling routines */
/* $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-2005 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>.
Kurt Zeilenga's avatar
Kurt Zeilenga committed
15
16
17
18
19
20
21
22
 */

#include "portable.h"

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

#include "back-bdb.h"
23
24
25
26
#include "idl.h"

#define IDL_MAX(x,y)	( x > y ? x : y )
#define IDL_MIN(x,y)	( x < y ? x : y )
Kurt Zeilenga's avatar
Kurt Zeilenga committed
27

28
29
#define IDL_CMP(x,y)	( x < y ? -1 : ( x > y ? 1 : 0 ) )

30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#define IDL_LRU_DELETE( bdb, e ) do { 					\
	if ( e->idl_lru_prev != NULL ) {				\
		e->idl_lru_prev->idl_lru_next = e->idl_lru_next; 	\
	} else {							\
		bdb->bi_idl_lru_head = e->idl_lru_next;			\
	}								\
	if ( e->idl_lru_next != NULL ) {				\
		e->idl_lru_next->idl_lru_prev = e->idl_lru_prev;	\
	} else {							\
		bdb->bi_idl_lru_tail = e->idl_lru_prev;			\
	}								\
} while ( 0 )

#define IDL_LRU_ADD( bdb, e ) do {					\
	e->idl_lru_next = bdb->bi_idl_lru_head;				\
	if ( e->idl_lru_next != NULL ) {				\
		e->idl_lru_next->idl_lru_prev = (e);			\
	}								\
	(bdb)->bi_idl_lru_head = (e);					\
	e->idl_lru_prev = NULL;						\
	if ( (bdb)->bi_idl_lru_tail == NULL ) {				\
		(bdb)->bi_idl_lru_tail = (e);				\
	}								\
} while ( 0 )

55
static int
56
bdb_idl_entry_cmp( const void *v_idl1, const void *v_idl2 )
57
{
58
	const bdb_idl_cache_entry_t *idl1 = v_idl1, *idl2 = v_idl2;
59
60
	int rc;

Howard Chu's avatar
Howard Chu committed
61
	if ((rc = SLAP_PTRCMP( idl1->db, idl2->db ))) return rc;
62
63
64
65
	if ((rc = idl1->kstr.bv_len - idl2->kstr.bv_len )) return rc;
	return ( memcmp ( idl1->kstr.bv_val, idl2->kstr.bv_val , idl1->kstr.bv_len ) );
}

Kurt Zeilenga's avatar
Kurt Zeilenga committed
66
67
68
69
#if IDL_DEBUG > 0
static void idl_check( ID *ids )
{
	if( BDB_IDL_IS_RANGE( ids ) ) {
70
		assert( BDB_IDL_RANGE_FIRST(ids) <= BDB_IDL_RANGE_LAST(ids) );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
71
72
73
74
75
76
77
78
79
80
	} else {
		ID i;
		for( i=1; i < ids[0]; i++ ) {
			assert( ids[i+1] > ids[i] );
		}
	}
}

#if IDL_DEBUG > 1
static void idl_dump( ID *ids )
81
82
{
	if( BDB_IDL_IS_RANGE( ids ) ) {
83
		Debug( LDAP_DEBUG_ANY,
84
85
86
			"IDL: range ( %ld - %ld )\n",
			(long) BDB_IDL_RANGE_FIRST( ids ),
			(long) BDB_IDL_RANGE_LAST( ids ) );
87

88
89
	} else {
		ID i;
90
		Debug( LDAP_DEBUG_ANY, "IDL: size %ld", (long) ids[0], 0, 0 );
91
92

		for( i=1; i<=ids[0]; i++ ) {
93
94
95
			if( i % 16 == 1 ) {
				Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
			}
96
			Debug( LDAP_DEBUG_ANY, "  %02lx", (long) ids[i], 0, 0 );
97
98
		}

99
		Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
100
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
101
102

	idl_check( ids );
103
}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
104
105
#endif /* IDL_DEBUG > 1 */
#endif /* IDL_DEBUG > 0 */
106

Kurt Zeilenga's avatar
Kurt Zeilenga committed
107
unsigned bdb_idl_search( ID *ids, ID id )
Kurt Zeilenga's avatar
Kurt Zeilenga committed
108
{
Kurt Zeilenga's avatar
Kurt Zeilenga committed
109
#define IDL_BINARY_SEARCH 1
110
#ifdef IDL_BINARY_SEARCH
111
112
113
114
115
	/*
	 * binary search of id in ids
	 * if found, returns position of id
	 * if not found, returns first postion greater than id
	 */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
116
117
	unsigned base = 0;
	unsigned cursor = 0;
118
	int val = 0;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
119
	unsigned n = ids[0];
120

Kurt Zeilenga's avatar
Kurt Zeilenga committed
121
122
123
124
#if IDL_DEBUG > 0
	idl_check( ids );
#endif

125
126
127
128
129
130
131
132
133
134
135
136
137
138
	while( 0 < n ) {
		int pivot = n >> 1;
		cursor = base + pivot;
		val = IDL_CMP( id, ids[cursor + 1] );

		if( val < 0 ) {
			n = pivot;

		} else if ( val > 0 ) {
			base = cursor + 1;
			n -= pivot + 1;

		} else {
			return cursor + 1;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
139
140
		}
	}
141
	
Kurt Zeilenga's avatar
Kurt Zeilenga committed
142
	if( val > 0 ) {
143
		return cursor + 2;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
144
145
	} else {
		return cursor + 1;
146
	}
147

148
#else
149
	/* (reverse) linear search */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
150
	int i;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
151

Kurt Zeilenga's avatar
Kurt Zeilenga committed
152
153
154
#if IDL_DEBUG > 0
	idl_check( ids );
#endif
Kurt Zeilenga's avatar
Kurt Zeilenga committed
155

Kurt Zeilenga's avatar
Kurt Zeilenga committed
156
157
158
159
	for( i=ids[0]; i; i-- ) {
		if( id > ids[i] ) {
			break;
		}
160
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
161
162

	return i+1;
163
#endif
Kurt Zeilenga's avatar
Kurt Zeilenga committed
164
165
}

166
int bdb_idl_insert( ID *ids, ID id )
Kurt Zeilenga's avatar
Kurt Zeilenga committed
167
{
168
	unsigned x;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
169

Kurt Zeilenga's avatar
Kurt Zeilenga committed
170
#if IDL_DEBUG > 1
171
	Debug( LDAP_DEBUG_ANY, "insert: %04lx at %d\n", (long) id, x, 0 );
172
	idl_dump( ids );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
173
174
#elif IDL_DEBUG > 0
	idl_check( ids );
175
176
#endif

177
	if (BDB_IDL_IS_RANGE( ids )) {
178
179
180
		/* if already in range, treat as a dup */
		if (id >= BDB_IDL_FIRST(ids) && id <= BDB_IDL_LAST(ids))
			return -1;
181
182
183
184
185
186
187
188
		if (id < BDB_IDL_FIRST(ids))
			ids[1] = id;
		else if (id > BDB_IDL_LAST(ids))
			ids[2] = id;
		return 0;
	}

	x = bdb_idl_search( ids, id );
189
190
	assert( x > 0 );

Kurt Zeilenga's avatar
Kurt Zeilenga committed
191
	if( x < 1 ) {
192
		/* internal error */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
193
		return -2;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
194
195
	}

Kurt Zeilenga's avatar
Kurt Zeilenga committed
196
	if ( x <= ids[0] && ids[x] == id ) {
197
198
199
		/* duplicate */
		return -1;
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
200

201
	if ( ++ids[0] >= BDB_IDL_DB_MAX ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
202
203
204
205
206
207
208
209
		if( id < ids[1] ) {
			ids[1] = id;
			ids[2] = ids[ids[0]-1];
		} else if ( ids[ids[0]-1] < id ) {
			ids[2] = id;
		} else {
			ids[2] = ids[ids[0]-1];
		}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
210
211
212
213
		ids[0] = NOID;
	
	} else {
		/* insert id */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
214
		AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
215
216
217
		ids[x] = id;
	}

Kurt Zeilenga's avatar
Kurt Zeilenga committed
218
#if IDL_DEBUG > 1
219
	idl_dump( ids );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
220
221
#elif IDL_DEBUG > 0
	idl_check( ids );
222
223
#endif

Kurt Zeilenga's avatar
Kurt Zeilenga committed
224
225
226
	return 0;
}

Howard Chu's avatar
Howard Chu committed
227
228
#if 0	/* unused */
static int idl_delete( ID *ids, ID id )
Kurt Zeilenga's avatar
Kurt Zeilenga committed
229
{
Howard Chu's avatar
Howard Chu committed
230
	unsigned x = bdb_idl_search( ids, id );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
231

Kurt Zeilenga's avatar
Kurt Zeilenga committed
232
#if IDL_DEBUG > 1
233
	Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x, 0 );
234
	idl_dump( ids );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
235
236
#elif IDL_DEBUG > 0
	idl_check( ids );
237
238
#endif

239
240
241
242
	assert( x > 0 );

	if( x <= 0 ) {
		/* internal error */
243
		return -2;
244
245
246
	}

	if( x > ids[0] || ids[x] != id ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
247
248
249
250
		/* not found */
		return -1;

	} else if ( --ids[0] == 0 ) {
251
		if( x != 1 ) {
252
			return -3;
253
		}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
254
255
256
257
258

	} else {
		AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
	}

Kurt Zeilenga's avatar
Kurt Zeilenga committed
259
#if IDL_DEBUG > 1
260
	idl_dump( ids );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
261
262
#elif IDL_DEBUG > 0
	idl_check( ids );
263
264
#endif

Kurt Zeilenga's avatar
Kurt Zeilenga committed
265
266
	return 0;
}
Howard Chu's avatar
Howard Chu committed
267
#endif	/* unused */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
268

269
270
271
272
273
274
275
276
277
278
279
280
281
282
static char *
bdb_show_key(
	DBT		*key,
	char		*buf )
{
	if ( key->size == sizeof( ID ) ) {
		unsigned char *c = key->data;
		sprintf( buf, "[%02x%02x%02x%02x]", c[0], c[1], c[2], c[3] );
		return buf;
	} else {
		return key->data;
	}
}

283
284
285
286
287
288
289
290
291
292
293
294
/* Find a db/key pair in the IDL cache. If ids is non-NULL,
 * copy the cached IDL into it, otherwise just return the status.
 */
int
bdb_idl_cache_get(
	struct bdb_info	*bdb,
	DB			*db,
	DBT			*key,
	ID			*ids )
{
	bdb_idl_cache_entry_t idl_tmp;
	bdb_idl_cache_entry_t *matched_idl_entry;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
295
	int rc = LDAP_NO_SUCH_OBJECT;
296
297
298
299
300
301
302
303
304
305
306
307
308
309

	DBT2bv( key, &idl_tmp.kstr );
	idl_tmp.db = db;
	ldap_pvt_thread_rdwr_rlock( &bdb->bi_idl_tree_rwlock );
	matched_idl_entry = avl_find( bdb->bi_idl_tree, &idl_tmp,
				      bdb_idl_entry_cmp );
	if ( matched_idl_entry != NULL ) {
		if ( matched_idl_entry->idl && ids )
			BDB_IDL_CPY( ids, matched_idl_entry->idl );
		ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock );
		IDL_LRU_DELETE( bdb, matched_idl_entry );
		IDL_LRU_ADD( bdb, matched_idl_entry );
		ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock );
		if ( matched_idl_entry->idl )
Kurt Zeilenga's avatar
Kurt Zeilenga committed
310
			rc = LDAP_SUCCESS;
311
		else
Kurt Zeilenga's avatar
Kurt Zeilenga committed
312
			rc = DB_NOTFOUND;
313
314
315
	}
	ldap_pvt_thread_rdwr_runlock( &bdb->bi_idl_tree_rwlock );

Kurt Zeilenga's avatar
Kurt Zeilenga committed
316
	return rc;
317
318
319
320
321
322
323
324
325
326
327
328
329
}

void
bdb_idl_cache_put(
	struct bdb_info	*bdb,
	DB			*db,
	DBT			*key,
	ID			*ids,
	int			rc )
{
	bdb_idl_cache_entry_t idl_tmp;
	bdb_idl_cache_entry_t *ee;

330
331
	DBT2bv( key, &idl_tmp.kstr );

332
333
334
335
336
337
338
339
340
341
342
343
344
345
	ee = (bdb_idl_cache_entry_t *) ch_malloc(
		sizeof( bdb_idl_cache_entry_t ) );
	ee->db = db;
	if ( rc == DB_NOTFOUND) {
		ee->idl = NULL;
	} else {
		ee->idl = (ID*) ch_malloc( BDB_IDL_SIZEOF ( ids ) );
		BDB_IDL_CPY( ee->idl, ids );
	}
	ee->idl_lru_prev = NULL;
	ee->idl_lru_next = NULL;
	ber_dupbv( &ee->kstr, &idl_tmp.kstr );
	ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock );
	if ( avl_insert( &bdb->bi_idl_tree, (caddr_t) ee,
Howard Chu's avatar
Howard Chu committed
346
		bdb_idl_entry_cmp, avl_dup_error ))
347
348
	{
		ch_free( ee->kstr.bv_val );
Howard Chu's avatar
Howard Chu committed
349
		ch_free( ee->idl );
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
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
		ch_free( ee );
		ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
		return;
	}
	ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock );
	IDL_LRU_ADD( bdb, ee );
	if ( ++bdb->bi_idl_cache_size > bdb->bi_idl_cache_max_size ) {
		int i = 0;
		while ( bdb->bi_idl_lru_tail != NULL && i < 10 ) {
			ee = bdb->bi_idl_lru_tail;
			if ( avl_delete( &bdb->bi_idl_tree, (caddr_t) ee,
				    bdb_idl_entry_cmp ) == NULL ) {
				Debug( LDAP_DEBUG_ANY, "=> bdb_idl_cache_put: "
					"AVL delete failed\n",
					0, 0, 0 );
			}
			IDL_LRU_DELETE( bdb, ee );
			i++;
			--bdb->bi_idl_cache_size;
			ch_free( ee->kstr.bv_val );
			ch_free( ee->idl );
			ch_free( ee );
		}
	}

	ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock );
	ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
}

void
bdb_idl_cache_del(
	struct bdb_info	*bdb,
	DB			*db,
	DBT			*key )
{
	bdb_idl_cache_entry_t *matched_idl_entry, idl_tmp;
	DBT2bv( key, &idl_tmp.kstr );
	idl_tmp.db = db;
	ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock );
	matched_idl_entry = avl_find( bdb->bi_idl_tree, &idl_tmp,
				      bdb_idl_entry_cmp );
	if ( matched_idl_entry != NULL ) {
		if ( avl_delete( &bdb->bi_idl_tree, (caddr_t) matched_idl_entry,
				    bdb_idl_entry_cmp ) == NULL ) {
			Debug( LDAP_DEBUG_ANY, "=> bdb_idl_cache_del: "
				"AVL delete failed\n",
				0, 0, 0 );
		}
		--bdb->bi_idl_cache_size;
		ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock );
		IDL_LRU_DELETE( bdb, matched_idl_entry );
		ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock );
		free( matched_idl_entry->kstr.bv_val );
		if ( matched_idl_entry->idl )
			free( matched_idl_entry->idl );
		free( matched_idl_entry );
	}
	ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
}

410
411
412
413
414
415
int
bdb_idl_fetch_key(
	BackendDB	*be,
	DB			*db,
	DB_TXN		*tid,
	DBT			*key,
416
417
418
	ID			*ids,
	DBC                     **saved_cursor,
	int                     get_flag )
419
{
420
	struct bdb_info *bdb = (struct bdb_info *) be->be_private;
421
	int rc;
422
	DBT data, key2, *kptr;
423
	DBC *cursor;
Howard Chu's avatar
Howard Chu committed
424
425
426
427
428
	ID *i;
	void *ptr;
	size_t len;
	int rc2;
	int flags = bdb->bi_db_opflags | DB_MULTIPLE;
429
	int opflag;
Howard Chu's avatar
Howard Chu committed
430

431
432
433
434
435
436
437
438
439
	/* If using BerkeleyDB 4.0, the buf must be large enough to
	 * grab the entire IDL in one get(), otherwise BDB will leak
	 * resources on subsequent get's.  We can safely call get()
	 * twice - once for the data, and once to get the DB_NOTFOUND
	 * result meaning there's no more data. See ITS#2040 for details.
	 * This bug is fixed in BDB 4.1 so a smaller buffer will work if
	 * stack space is too limited.
	 *
	 * configure now requires Berkeley DB 4.1.
Howard Chu's avatar
Howard Chu committed
440
	 */
441
#if DB_VERSION_FULL < 0x04010000
442
443
#	define BDB_ENOUGH 5
#else
Kurt Zeilenga's avatar
Kurt Zeilenga committed
444
445
446
447
448
449
	/* We sometimes test with tiny IDLs, and BDB always wants buffers
	 * that are at least one page in size.
	 */
# if BDB_IDL_DB_SIZE < 4096
#   define BDB_ENOUGH 2048
# else
450
#	define BDB_ENOUGH 1
Kurt Zeilenga's avatar
Kurt Zeilenga committed
451
# endif
452
#endif
453
	ID buf[BDB_IDL_DB_SIZE*BDB_ENOUGH];
454

Kurt Zeilenga's avatar
Kurt Zeilenga committed
455
456
457
458
459
460
	char keybuf[16];

	Debug( LDAP_DEBUG_ARGS,
		"bdb_idl_fetch_key: %s\n", 
		bdb_show_key( key, keybuf ), 0, 0 );

461
462
	assert( ids != NULL );

463
464
465
466
467
468
469
470
471
472
473
474
	if ( saved_cursor && *saved_cursor ) {
		opflag = DB_NEXT;
	} else if ( get_flag == LDAP_FILTER_GE ) {
		opflag = DB_SET_RANGE;
	} else if ( get_flag == LDAP_FILTER_LE ) {
		opflag = DB_FIRST;
	} else {
		opflag = DB_SET;
	}

	/* only non-range lookups can use the IDL cache */
	if ( bdb->bi_idl_cache_size && opflag == DB_SET ) {
475
476
		rc = bdb_idl_cache_get( bdb, db, key, ids );
		if ( rc != LDAP_NO_SUCH_OBJECT ) return rc;
477
478
	}

479
	DBTzero( &data );
480

481
482
483
484
	data.data = buf;
	data.ulen = sizeof(buf);
	data.flags = DB_DBT_USERMEM;

485
	/* If we're not reusing an existing cursor, get a new one */
Howard Chu's avatar
Howard Chu committed
486
	if( opflag != DB_NEXT ) {
487
		rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
Howard Chu's avatar
Howard Chu committed
488
489
490
491
492
493
		if( rc != 0 ) {
			Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
				"cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
			return rc;
		}
	} else {
494
		cursor = *saved_cursor;
495
	}
496
497
	
	/* If this is a LE lookup, save original key so we can determine
498
499
	 * when to stop. If this is a GE lookup, save the key since it
	 * will be overwritten.
500
	 */
501
	if ( get_flag == LDAP_FILTER_LE || get_flag == LDAP_FILTER_GE ) {
502
503
504
505
		DBTzero( &key2 );
		key2.flags = DB_DBT_USERMEM;
		key2.ulen = sizeof(keybuf);
		key2.data = keybuf;
506
		key2.size = key->size;
507
508
509
510
511
512
513
		AC_MEMCPY( keybuf, key->data, key->size );
		kptr = &key2;
	} else {
		kptr = key;
	}
	len = key->size;
	rc = cursor->c_get( cursor, kptr, &data, flags | opflag );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
514

515
516
517
518
519
520
521
522
523
524
525
	/* skip presence key on range inequality lookups */
	while (rc == 0 && kptr->size != len) {
		rc = cursor->c_get( cursor, kptr, &data, flags | DB_NEXT_NODUP );
	}
	/* If we're doing a LE compare and the new key is greater than
	 * our search key, we're done
	 */
	if (rc == 0 && get_flag == LDAP_FILTER_LE && memcmp( kptr->data,
		key->data, key->size ) > 0 ) {
		rc = DB_NOTFOUND;
	}
526
527
528
529
530
531
532
533
534
	if (rc == 0) {
		i = ids;
		while (rc == 0) {
			u_int8_t *j;

			DB_MULTIPLE_INIT( ptr, &data );
			while (ptr) {
				DB_MULTIPLE_NEXT(ptr, &data, j, len);
				if (j) {
Howard Chu's avatar
Howard Chu committed
535
					++i;
536
					BDB_DISK2ID( j, i );
537
538
				}
			}
539
540
541
542
543
544
545
546
547
548
549
550
			rc = cursor->c_get( cursor, key, &data, flags | DB_NEXT_DUP );
		}
		if ( rc == DB_NOTFOUND ) rc = 0;
		ids[0] = i - ids;
		/* On disk, a range is denoted by 0 in the first element */
		if (ids[1] == 0) {
			if (ids[0] != BDB_IDL_RANGE_SIZE) {
				Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
					"range size mismatch: expected %d, got %ld\n",
					BDB_IDL_RANGE_SIZE, ids[0], 0 );
				cursor->c_close( cursor );
				return -1;
551
			}
552
			BDB_IDL_RANGE( ids, ids[2], ids[3] );
553
		}
554
555
		data.size = BDB_IDL_SIZEOF(ids);
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
556

557
558
559
560
561
562
563
	if ( saved_cursor && rc == 0 ) {
		if ( !*saved_cursor )
			*saved_cursor = cursor;
		rc2 = 0;
	}
	else
		rc2 = cursor->c_close( cursor );
564
565
566
567
	if (rc2) {
		Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
			"close failed: %s (%d)\n", db_strerror(rc2), rc2, 0 );
		return rc2;
568
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
569

Howard Chu's avatar
Howard Chu committed
570
571
572
	if( rc == DB_NOTFOUND ) {
		return rc;

573
	} else if( rc != 0 ) {
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
		Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
			"get failed: %s (%d)\n",
			db_strerror(rc), rc, 0 );
		return rc;

	} else if ( data.size == 0 || data.size % sizeof( ID ) ) {
		/* size not multiple of ID size */
		Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
			"odd size: expected %ld multiple, got %ld\n",
			(long) sizeof( ID ), (long) data.size, 0 );
		return -1;

	} else if ( data.size != BDB_IDL_SIZEOF(ids) ) {
		/* size mismatch */
		Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
			"get size mismatch: expected %ld, got %ld\n",
			(long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
		return -1;
	}

594
	if ( bdb->bi_idl_cache_max_size ) {
595
		bdb_idl_cache_put( bdb, db, key, ids, rc );
596
597
	}

598
599
600
	return rc;
}

601

Kurt Zeilenga's avatar
Kurt Zeilenga committed
602
603
int
bdb_idl_insert_key(
604
605
	BackendDB	*be,
	DB			*db,
Kurt Zeilenga's avatar
Kurt Zeilenga committed
606
	DB_TXN		*tid,
607
608
	DBT			*key,
	ID			id )
Kurt Zeilenga's avatar
Kurt Zeilenga committed
609
{
610
	struct bdb_info *bdb = (struct bdb_info *) be->be_private;
Howard Chu's avatar
Howard Chu committed
611
	int	rc;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
612
	DBT data;
Howard Chu's avatar
Howard Chu committed
613
	DBC *cursor;
614
	ID lo, hi, tmp, nlo, nhi, nid;
Howard Chu's avatar
Howard Chu committed
615
	char *err;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
616

617
618
619
620
621
622
	{
		char buf[16];
		Debug( LDAP_DEBUG_ARGS,
			"bdb_idl_insert_key: %lx %s\n", 
			(long) id, bdb_show_key( key, buf ), 0 );
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
623

Kurt Zeilenga's avatar
Kurt Zeilenga committed
624
625
	assert( id != NOID );

Howard Chu's avatar
Howard Chu committed
626
627
	if ( bdb->bi_idl_cache_size ) {
		bdb_idl_cache_del( bdb, db, key );
628
629
	}

630
	DBTzero( &data );
631
632
633
	data.size = sizeof( ID );
	data.ulen = data.size;
	data.flags = DB_DBT_USERMEM;
634

635
636
	BDB_ID2DISK( id, &nid );

Howard Chu's avatar
Howard Chu committed
637
638
639
640
641
642
	rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
	if ( rc != 0 ) {
		Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
			"cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
		return rc;
	}
643
	data.data = &nlo;
Howard Chu's avatar
Howard Chu committed
644
645
646
	/* Fetch the first data item for this key, to see if it
	 * exists and if it's a range.
	 */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
647
	rc = cursor->c_get( cursor, key, &data, DB_SET );
Howard Chu's avatar
Howard Chu committed
648
649
	err = "c_get";
	if ( rc == 0 ) {
650
		if ( nlo != 0 ) {
Howard Chu's avatar
Howard Chu committed
651
652
653
			/* not a range, count the number of items */
			db_recno_t count;
			rc = cursor->c_count( cursor, &count, 0 );
654
			if ( rc != 0 ) {
Howard Chu's avatar
Howard Chu committed
655
656
				err = "c_count";
				goto fail;
657
			}
Howard Chu's avatar
Howard Chu committed
658
659
660
			if ( count >= BDB_IDL_DB_MAX ) {
			/* No room, convert to a range */
				DBT key2 = *key;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
661
				db_recno_t i;
Howard Chu's avatar
Howard Chu committed
662
663
664
665

				key2.dlen = key2.ulen;
				key2.flags |= DB_DBT_PARTIAL;

666
667
668
				BDB_DISK2ID( &nlo, &lo );
				data.data = &nhi;

Howard Chu's avatar
Howard Chu committed
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
				rc = cursor->c_get( cursor, &key2, &data, DB_NEXT_NODUP );
				if ( rc != 0 && rc != DB_NOTFOUND ) {
					err = "c_get next_nodup";
					goto fail;
				}
				if ( rc == DB_NOTFOUND ) {
					rc = cursor->c_get( cursor, key, &data, DB_LAST );
					if ( rc != 0 ) {
						err = "c_get last";
						goto fail;
					}
				} else {
					rc = cursor->c_get( cursor, key, &data, DB_PREV );
					if ( rc != 0 ) {
						err = "c_get prev";
						goto fail;
					}
				}
687
				BDB_DISK2ID( &nhi, &hi );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
688
689
690
				/* Update hi/lo if needed, then delete all the items
				 * between lo and hi
				 */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
691
692
693
694
695
696
				if ( id < lo ) {
					lo = id;
					nlo = nid;
				} else if ( id > hi ) {
					hi = id;
					nhi = nid;
697
				}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
698
				data.data = &nid;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
699
700
701
				/* Don't fetch anything, just position cursor */
				data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
				data.dlen = data.ulen = 0;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
702
				rc = cursor->c_get( cursor, key, &data, DB_SET );
Howard Chu's avatar
Howard Chu committed
703
				if ( rc != 0 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
704
					err = "c_get 2";
Howard Chu's avatar
Howard Chu committed
705
706
					goto fail;
				}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
707
708
709
710
				rc = cursor->c_del( cursor, 0 );
				if ( rc != 0 ) {
					err = "c_del range1";
					goto fail;
Howard Chu's avatar
Howard Chu committed
711
				}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
712
713
714
				/* Delete all the records */
				for ( i=1; i<count; i++ ) {
					rc = cursor->c_get( cursor, &key2, &data, DB_NEXT_DUP );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
715
716
717
718
719
720
721
722
723
					if ( rc != 0 ) {
						err = "c_get next_dup";
						goto fail;
					}
					rc = cursor->c_del( cursor, 0 );
					if ( rc != 0 ) {
						err = "c_del range";
						goto fail;
					}
Howard Chu's avatar
Howard Chu committed
724
				}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
725
726
727
728
729
				/* Store the range marker */
				data.size = data.ulen = sizeof(ID);
				data.flags = DB_DBT_USERMEM;
				nid = 0;
				rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
Howard Chu's avatar
Howard Chu committed
730
				if ( rc != 0 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
731
					err = "c_put range";
Howard Chu's avatar
Howard Chu committed
732
733
					goto fail;
				}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
734
735
736
737
738
739
740
741
742
743
744
745
				nid = nlo;
				rc = cursor->c_put( cursor, key, &data, DB_KEYLAST );
				if ( rc != 0 ) {
					err = "c_put lo";
					goto fail;
				}
				nid = nhi;
				rc = cursor->c_put( cursor, key, &data, DB_KEYLAST );
				if ( rc != 0 ) {
					err = "c_put hi";
					goto fail;
				}
Howard Chu's avatar
Howard Chu committed
746
747
748
			} else {
			/* There's room, just store it */
				goto put1;
749
			}
Howard Chu's avatar
Howard Chu committed
750
751
752
753
754
		} else {
			/* It's a range, see if we need to rewrite
			 * the boundaries
			 */
			hi = id;
755
			data.data = &nlo;
Howard Chu's avatar
Howard Chu committed
756
			rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
757
			if ( rc != 0 ) {
Howard Chu's avatar
Howard Chu committed
758
759
				err = "c_get lo";
				goto fail;
760
			}
761
			BDB_DISK2ID( &nlo, &lo );
Howard Chu's avatar
Howard Chu committed
762
			if ( id > lo ) {
763
				data.data = &nhi;
Howard Chu's avatar
Howard Chu committed
764
765
766
767
768
				rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
				if ( rc != 0 ) {
					err = "c_get hi";
					goto fail;
				}
769
				BDB_DISK2ID( &nhi, &hi );
770
			}
Howard Chu's avatar
Howard Chu committed
771
			if ( id < lo || id > hi ) {
772
773
774
775
776
777
				/* Delete the current lo/hi */
				rc = cursor->c_del( cursor, 0 );
				if ( rc != 0 ) {
					err = "c_del";
					goto fail;
				}
778
				data.data = &nid;
779
				rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
Howard Chu's avatar
Howard Chu committed
780
781
782
783
				if ( rc != 0 ) {
					err = "c_put lo/hi";
					goto fail;
				}
784
785
			}
		}
Howard Chu's avatar
Howard Chu committed
786
	} else if ( rc == DB_NOTFOUND ) {
787
put1:		data.data = &nid;
Howard Chu's avatar
Howard Chu committed
788
789
790
791
792
		rc = cursor->c_put( cursor, key, &data, DB_NODUPDATA );
		/* Don't worry if it's already there */
		if ( rc != 0 && rc != DB_KEYEXIST ) {
			err = "c_put id";
			goto fail;
793
794
		}
	} else {
Howard Chu's avatar
Howard Chu committed
795
796
		/* initial c_get failed, nothing was done */
fail:
797
798
		Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
			"%s failed: %s (%d)\n", err, db_strerror(rc), rc );
Howard Chu's avatar
Howard Chu committed
799
		cursor->c_close( cursor );
800
		return rc;
801
	}
Howard Chu's avatar
Howard Chu committed
802
803
804
805
806
	rc = cursor->c_close( cursor );
	if( rc != 0 ) {
		Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
			"c_close failed: %s (%d)\n",
			db_strerror(rc), rc, 0 );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
807
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
808
809
	return rc;
}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
810
811
812

int
bdb_idl_delete_key(
813
814
	BackendDB	*be,
	DB			*db,
Kurt Zeilenga's avatar
Kurt Zeilenga committed
815
	DB_TXN		*tid,
816
817
	DBT			*key,
	ID			id )
Kurt Zeilenga's avatar
Kurt Zeilenga committed
818
{
819
	struct bdb_info *bdb = (struct bdb_info *) be->be_private;
Howard Chu's avatar
Howard Chu committed
820
	int	rc;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
821
	DBT data;
822
	DBC *cursor;
823
	ID lo, hi, tmp, nid, nlo, nhi;
Howard Chu's avatar
Howard Chu committed
824
	char *err;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
825

826
827
828
829
830
831
	{
		char buf[16];
		Debug( LDAP_DEBUG_ARGS,
			"bdb_idl_delete_key: %lx %s\n", 
			(long) id, bdb_show_key( key, buf ), 0 );
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
832
833
	assert( id != NOID );

Howard Chu's avatar
Howard Chu committed
834
835
	if ( bdb->bi_idl_cache_max_size ) {
		bdb_idl_cache_del( bdb, db, key );
836
837
	}

838
839
	BDB_ID2DISK( id, &nid );

840
	DBTzero( &data );
Howard Chu's avatar
Howard Chu committed
841
	data.data = &tmp;
842
843
844
	data.size = sizeof( id );
	data.ulen = data.size;
	data.flags = DB_DBT_USERMEM;
845

846
847
848
849
850
851
	rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
	if ( rc != 0 ) {
		Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
			"cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
		return rc;
	}
Howard Chu's avatar
Howard Chu committed
852
853
854
	/* Fetch the first data item for this key, to see if it
	 * exists and if it's a range.
	 */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
855
	rc = cursor->c_get( cursor, key, &data, DB_SET );
Howard Chu's avatar
Howard Chu committed
856
857
858
859
	err = "c_get";
	if ( rc == 0 ) {
		if ( tmp != 0 ) {
			/* Not a range, just delete it */
860
			if (tmp != nid) {
Howard Chu's avatar
Howard Chu committed
861
				/* position to correct item */
862
				tmp = nid;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
863
				rc = cursor->c_get( cursor, key, &data, DB_GET_BOTH );
Howard Chu's avatar
Howard Chu committed
864
865
866
867
				if ( rc != 0 ) {
					err = "c_get id";
					goto fail;
				}
868
			}
Howard Chu's avatar
Howard Chu committed
869
			rc = cursor->c_del( cursor, 0 );
870
			if ( rc != 0 ) {
Howard Chu's avatar
Howard Chu committed
871
872
				err = "c_del id";
				goto fail;
873
			}
874
		} else {
Howard Chu's avatar
Howard Chu committed
875
876
877
			/* It's a range, see if we need to rewrite
			 * the boundaries
			 */
878
			data.data = &nlo;
Howard Chu's avatar
Howard Chu committed
879
			rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
880
			if ( rc != 0 ) {
Howard Chu's avatar
Howard Chu committed
881
882
883
				err = "c_get lo";
				goto fail;
			}
884
885
			BDB_DISK2ID( &nlo, &lo );
			data.data = &nhi;
Howard Chu's avatar
Howard Chu committed
886
887
888
889
890
			rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
			if ( rc != 0 ) {
				err = "c_get hi";
				goto fail;
			}
891
			BDB_DISK2ID( &nhi, &hi );
Howard Chu's avatar
Howard Chu committed
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
			if ( id == lo || id == hi ) {
				if ( id == lo ) {
					id++;
					lo = id;
				} else if ( id == hi ) {
					id--;
					hi = id;
				}
				if ( lo >= hi ) {
				/* The range has collapsed... */
					rc = db->del( db, tid, key, 0 );
					if ( rc != 0 ) {
						err = "del";
						goto fail;
					}
				} else {
					if ( id == lo ) {
						/* reposition on lo slot */
910
						data.data = &nlo;
Howard Chu's avatar
Howard Chu committed
911
912
913
914
915
916
917
918
919
						cursor->c_get( cursor, key, &data, DB_PREV );
					}
					rc = cursor->c_del( cursor, 0 );
					if ( rc != 0 ) {
						err = "c_del";
						goto fail;
					}
				}
				if ( lo <= hi ) {
920
921
					BDB_ID2DISK( id, &nid );
					data.data = &nid;
Howard Chu's avatar
Howard Chu committed
922
923
924
925
926
927
					rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
					if ( rc != 0 ) {
						err = "c_put lo/hi";
						goto fail;
					}
				}
928
			}
929
		}
Howard Chu's avatar
Howard Chu committed
930
931
932
933
	} else {
		/* initial c_get failed, nothing was done */
fail:
		if ( rc != DB_NOTFOUND ) {
934
935
		Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
			"%s failed: %s (%d)\n", err, db_strerror(rc), rc );
Howard Chu's avatar
Howard Chu committed
936
		}
937
938
		cursor->c_close( cursor );
		return rc;
939
	}
940
	rc = cursor->c_close( cursor );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
941
942
	if( rc != 0 ) {
		Debug( LDAP_DEBUG_ANY,
Howard Chu's avatar
Howard Chu committed
943
			"=> bdb_idl_delete_key: c_close failed: %s (%d)\n",
Kurt Zeilenga's avatar
Kurt Zeilenga committed
944
945
946
			db_strerror(rc), rc, 0 );
	}

Kurt Zeilenga's avatar
Kurt Zeilenga committed
947
948
	return rc;
}
949
950
951


/*
952
 * idl_intersection - return a = a intersection b
953
954
955
956
 */
int
bdb_idl_intersection(
	ID *a,
957
	ID *b )
958
959
{
	ID ida, idb;
960
961
962
	ID idmax, idmin;
	ID cursora = 0, cursorb = 0, cursorc;
	int swap = 0;
963
964

	if ( BDB_IDL_IS_ZERO( a ) || BDB_IDL_IS_ZERO( b ) ) {
965
		a[0] = 0;
966
967
968
		return 0;
	}

969
970
971
972
973
974
975
976
977
978
	idmin = IDL_MAX( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
	idmax = IDL_MIN( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
	if ( idmin > idmax ) {
		a[0] = 0;
		return 0;
	} else if ( idmin == idmax ) {
		a[0] = 1;
		a[1] = idmin;
		return 0;
	}
979

980
	if ( BDB_IDL_IS_RANGE( a ) ) {
981
982
983
984
985
986
987
988
989
990
991
992
		if ( BDB_IDL_IS_RANGE(b) ) {
		/* If both are ranges, just shrink the boundaries */
			a[1] = idmin;
			a[2] = idmax;
			return 0;
		} else {
		/* Else swap so that b is the range, a is a list */
			ID *tmp = a;
			a = b;
			b = tmp;
			swap = 1;
		}
993
994
	}

995
996
997
998
999
1000
1001
	/* If a range completely covers the list, the result is
	 * just the list. If idmin to idmax is contiguous, just
	 * turn it into a range.
	 */
	if ( BDB_IDL_IS_RANGE( b )
		&& BDB_IDL_FIRST( b ) <= BDB_IDL_FIRST( a )
		&& BDB_IDL_LAST( b ) >= BDB_IDL_LAST( a ) ) {
1002
1003
1004
1005
1006
1007
1008
1009
1010
		if (idmax - idmin + 1 == a[0])
		{
			a[0] = NOID;
			a[1] = idmin;
			a[2] = idmax;
		}
		goto done;
	}

1011
1012
1013
1014
	/* Fine, do the intersection one element at a time.
	 * First advance to idmin in both IDLs.
	 */
	cursora = cursorb = idmin;
1015
	ida = bdb_idl_first( a, &cursora );
1016
	idb = bdb_idl_first( b, &cursorb );
1017
	cursorc = 0;
1018

1019
	while( ida <= idmax || idb <= idmax ) {
1020
		if( ida == idb ) {
1021
			a[++cursorc] = ida;
1022
1023
1024
1025
1026
1027
1028
1029
			ida = bdb_idl_next( a, &cursora );
			idb = bdb_idl_next( b, &cursorb );
		} else if ( ida < idb ) {
			ida = bdb_idl_next( a, &cursora );
		} else {
			idb = bdb_idl_next( b, &cursorb );
		}
	}
1030
1031
1032
1033
	a[0] = cursorc;
done:
	if (swap)
		BDB_IDL_CPY( b, a );
1034
1035
1036
1037
1038
1039

	return 0;
}


/*
1040
 * idl_union - return a = a union b
1041
1042
1043
1044
 */
int
bdb_idl_union(
	ID	*a,
1045
	ID	*b )
1046
1047
{
	ID ida, idb;
1048
	ID cursora = 0, cursorb = 0, cursorc;
1049

1050
	if ( BDB_IDL_IS_ZERO( b ) ) {
1051
1052
1053
		return 0;
	}

1054
1055
	if ( BDB_IDL_IS_ZERO( a ) ) {
		BDB_IDL_CPY( a, b );
1056
1057
1058
1059
		return 0;
	}

	if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ) {
1060
1061
1062
1063
1064
over:		ida = IDL_MIN( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
		idb = IDL_MAX( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
		a[0] = NOID;
		a[1] = ida;
		a[2] = idb;
1065
1066
1067
		return 0;
	}

Howard Chu's avatar
Howard Chu committed
1068
	ida = bdb_idl_first( a, &cursora );
1069
1070
	idb = bdb_idl_first( b, &cursorb );

1071
	cursorc = b[0];
1072

1073
	/* The distinct elements of a are cat'd to b */
1074
	while( ida != NOID || idb != NOID ) {
1075
		if ( ida < idb ) {
1076
1077
1078
1079
			if( ++cursorc > BDB_IDL_UM_MAX ) {
				goto over;
			}
			b[cursorc] = ida;
1080
1081
1082
			ida = bdb_idl_next( a, &cursora );

		} else {
1083
1084
			if ( ida == idb )
				ida = bdb_idl_next( a, &cursora );
1085
1086
1087
1088
			idb = bdb_idl_next( b, &cursorb );
		}
	}

1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
	/* b is copied back to a in sorted order */
	a[0] = cursorc;
	cursora = 1;
	cursorb = 1;
	cursorc = b[0]+1;
	while (cursorb <= b[0] || cursorc <= a[0]) {
		if (cursorc > a[0])
			idb = NOID;
		else
			idb = b[cursorc];
1099
		if (cursorb <= b[0] && b[cursorb] < idb)
1100
1101
1102
1103
1104
1105
1106
			a[cursora++] = b[cursorb++];
		else {
			a[cursora++] = idb;
			cursorc++;
		}
	}

1107
1108
1109
1110
	return 0;
}


1111
#if 0
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
/*
 * bdb_idl_notin - return a intersection ~b (or a minus b)
 */
int
bdb_idl_notin(
	ID	*a,
	ID	*b,
	ID *ids )
{
	ID ida, idb;
Howard Chu's avatar
Howard Chu committed
1122
	ID cursora = 0, cursorb = 0;
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162

	if( BDB_IDL_IS_ZERO( a ) ||
		BDB_IDL_IS_ZERO( b ) ||
		BDB_IDL_IS_RANGE( b ) )
	{
		BDB_IDL_CPY( ids, a );
		return 0;
	}

	if( BDB_IDL_IS_RANGE( a ) ) {
		BDB_IDL_CPY( ids, a );
		return 0;
	}

	ida = bdb_idl_first( a, &cursora ),
	idb = bdb_idl_first( b, &cursorb );

	ids[0] = 0;

	while( ida != NOID ) {
		if ( idb == NOID ) {
			/* we could shortcut this */
			ids[++ids[0]] = ida;
			ida = bdb_idl_next( a, &cursora );

		} else if ( ida < idb ) {
			ids[++ids[0]] = ida;
			ida = bdb_idl_next( a, &cursora );

		} else if ( ida > idb ) {
			idb = bdb_idl_next( b, &cursorb );

		} else {
			ida = bdb_idl_next( a, &cursora );
			idb = bdb_idl_next( b, &cursorb );