idl.c 22.1 KB
Newer Older
Kurt Zeilenga's avatar
Kurt Zeilenga committed
1
/* idl.c - ldap id list handling routines */
2
/* $OpenLDAP$ */
3
4
5
6
7
8
/*
 * Copyright 1998-1999 The OpenLDAP Foundation, All Rights Reserved.
 * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
 */

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

#include <stdio.h>
11
12
13
14

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

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

18
static ID_BLOCK* idl_dup( ID_BLOCK *idl );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
19

20
21
22
/* Allocate an ID_BLOCK with room for nids ids */
ID_BLOCK *
idl_alloc( unsigned int nids )
Kurt Zeilenga's avatar
Kurt Zeilenga committed
23
{
24
	ID_BLOCK	*new;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
25
26

	/* nmax + nids + space for the ids */
27
28
29
	new = (ID_BLOCK *) ch_calloc( (ID_BLOCK_IDS_OFFSET + nids), sizeof(ID) );
	ID_BLOCK_NMAX(new) = nids;
	ID_BLOCK_NIDS(new) = 0;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
30
31
32
33

	return( new );
}

34
35
36

/* Allocate an empty ALLIDS ID_BLOCK */
ID_BLOCK	*
Kurt Zeilenga's avatar
Kurt Zeilenga committed
37
38
idl_allids( Backend *be )
{
39
	ID_BLOCK	*idl;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
40
41

	idl = idl_alloc( 0 );
42
43
	ID_BLOCK_NMAX(idl) = ID_BLOCK_ALLIDS_VALUE;
	ID_BLOCK_NIDS(idl) = next_id_get( be );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
44
45
46
47

	return( idl );
}

48
/* Free an ID_BLOCK */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
49
void
50
idl_free( ID_BLOCK *idl )
Kurt Zeilenga's avatar
Kurt Zeilenga committed
51
52
{
	if ( idl == NULL ) {
53
54
55
		Debug( LDAP_DEBUG_TRACE,
			"idl_free: called with NULL pointer\n",
			0, 0, 0 );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
56
57
58
59
60
61
		return;
	}

	free( (char *) idl );
}

62
63
64

/* Fetch an single ID_BLOCK from the cache */
static ID_BLOCK *
Kurt Zeilenga's avatar
Kurt Zeilenga committed
65
66
idl_fetch_one(
    Backend		*be,
67
    DBCache	*db,
Kurt Zeilenga's avatar
Kurt Zeilenga committed
68
69
70
    Datum		key
)
{
71
72
	Datum	data;
	ID_BLOCK	*idl;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
73
74
75
76
77

	/* Debug( LDAP_DEBUG_TRACE, "=> idl_fetch_one\n", 0, 0, 0 ); */

	data = ldbm_cache_fetch( db, key );

78
79
80
81
	if( data.dptr == NULL ) {
		return NULL;
	}

82
83
	idl = idl_dup((ID_BLOCK *) data.dptr);

84
	ldbm_datum_free( db->dbc_db, data );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
85

86
	return idl;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
87
88
}

89
90
91
92
93
94
95
96
97
98
99

/* Fetch a set of ID_BLOCKs from the cache
 *	if not INDIRECT
 * 		if block return is an ALLIDS block,
 *			return an new ALLIDS block
 * 		otherwise
 *			return block
 *	construct super block from all blocks referenced by INDIRECT block
 *	return super block
 */
ID_BLOCK *
Kurt Zeilenga's avatar
Kurt Zeilenga committed
100
101
idl_fetch(
    Backend		*be,
102
    DBCache	*db,
Kurt Zeilenga's avatar
Kurt Zeilenga committed
103
104
105
    Datum		key
)
{
106
107
108
	Datum	data;
	ID_BLOCK	*idl;
	ID_BLOCK	**tmp;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
109
110
111
	char	*kstr;
	int	i, nids;

112
	idl = idl_fetch_one( be, db, key );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
113

114
115
	if ( idl == NULL ) {
		return NULL;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
116
117
	}

118
119
	if ( ID_BLOCK_ALLIDS(idl) ) {
		/* all ids block */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
120
		/* make sure we have the current value of highest id */
121
122
123
124
125
126
127
128
		idl_free( idl );
		idl = idl_allids( be );

		return( idl );
	}

	if ( ! ID_BLOCK_INDIRECT( idl ) ) {
		/* regular block */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
129
130
131
132
133
134
135
136
137
138
		return( idl );
	}

	/*
	 * this is an indirect block which points to other blocks.
	 * we need to read in all the blocks it points to and construct
	 * a big id list containing all the ids, which we will return.
	 */

	/* count the number of blocks & allocate space for pointers to them */
139
	for ( i = 0; !ID_BLOCK_NOID(idl, i); i++ )
Kurt Zeilenga's avatar
Kurt Zeilenga committed
140
		;	/* NULL */
141
	tmp = (ID_BLOCK **) ch_malloc( (i + 1) * sizeof(ID_BLOCK *) );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
142
143

	/* read in all the blocks */
144
	kstr = (char *) ch_malloc( key.dsize + CONT_SIZE );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
145
	nids = 0;
146
147
	for ( i = 0; !ID_BLOCK_NOID(idl, i); i++ ) {
		ldbm_datum_init( data );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
148

149
150
151
152
153
154
155
		sprintf( kstr, "%c%ld%s", CONT_PREFIX,
			ID_BLOCK_ID(idl, i), key.dptr );

		data.dptr = kstr;
		data.dsize = strlen( kstr ) + 1;

		if ( (tmp[i] = idl_fetch_one( be, db, data )) == NULL ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
156
			Debug( LDAP_DEBUG_ANY,
157
			    "idl_fetch of (%s) returns NULL\n", data.dptr, 0, 0 );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
158
159
160
			continue;
		}

161
		nids += ID_BLOCK_NIDS(tmp[i]);
Kurt Zeilenga's avatar
Kurt Zeilenga committed
162
163
	}
	tmp[i] = NULL;
164
	free( kstr );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
165
166
167
168
	idl_free( idl );

	/* allocate space for the big block */
	idl = idl_alloc( nids );
169
	ID_BLOCK_NIDS(idl) = nids;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
170
171
172
173
174
175
176
177
	nids = 0;

	/* copy in all the ids from the component blocks */
	for ( i = 0; tmp[i] != NULL; i++ ) {
		if ( tmp[i] == NULL ) {
			continue;
		}

178
179
180
181
182
		SAFEMEMCPY(
			(char *) &ID_BLOCK_ID(idl, nids),
			(char *) &ID_BLOCK_ID(tmp[i], 0),
			ID_BLOCK_NIDS(tmp[i]) * sizeof(ID) );
		nids += ID_BLOCK_NIDS(tmp[i]);
Kurt Zeilenga's avatar
Kurt Zeilenga committed
183
184
185
186
187

		idl_free( tmp[i] );
	}
	free( (char *) tmp );

188
189
	Debug( LDAP_DEBUG_TRACE, "<= idl_fetch %ld ids (%ld max)\n",
	       ID_BLOCK_NIDS(idl), ID_BLOCK_NMAX(idl), 0 );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
190
191
192
	return( idl );
}

193
194

/* store a single block */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
195
196
197
static int
idl_store(
    Backend		*be,
198
    DBCache	*db,
Kurt Zeilenga's avatar
Kurt Zeilenga committed
199
    Datum		key, 
200
    ID_BLOCK		*idl
Kurt Zeilenga's avatar
Kurt Zeilenga committed
201
202
)
{
203
	int	rc, flags;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
204
	Datum	data;
205
206
207
	struct ldbminfo *li = (struct ldbminfo *) be->be_private;

	ldbm_datum_init( data );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
208
209
210
211

	/* Debug( LDAP_DEBUG_TRACE, "=> idl_store\n", 0, 0, 0 ); */

	data.dptr = (char *) idl;
212
213
214
215
216
217
	data.dsize = (ID_BLOCK_IDS_OFFSET + ID_BLOCK_NMAX(idl)) * sizeof(ID);
	
#ifdef LDBM_DEBUG
	Statslog( LDAP_DEBUG_STATS, "<= idl_store(): rc=%d\n",
		rc, 0, 0, 0, 0 );
#endif
Kurt Zeilenga's avatar
Kurt Zeilenga committed
218

219
220
221
	flags = LDBM_REPLACE;
	if( li->li_dbcachewsync ) flags |= LDBM_SYNC;
	rc = ldbm_cache_store( db, key, data, flags );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
222
223
224
225
226

	/* Debug( LDAP_DEBUG_TRACE, "<= idl_store %d\n", rc, 0, 0 ); */
	return( rc );
}

227
228
229
/* split the block at id 
 *	locate ID greater than or equal to id.
 */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
230
231
static void
idl_split_block(
232
    ID_BLOCK	*b,
Kurt Zeilenga's avatar
Kurt Zeilenga committed
233
    ID		id,
234
235
    ID_BLOCK	**right,
    ID_BLOCK	**left
Kurt Zeilenga's avatar
Kurt Zeilenga committed
236
237
)
{
238
	unsigned int	nr, nl;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
239

240
241
	/* find where to split the block *//* XXX linear search XXX */
	for ( nr = 0; nr < ID_BLOCK_NIDS(b) && id > ID_BLOCK_ID(b, nr); nr++ )
Kurt Zeilenga's avatar
Kurt Zeilenga committed
242
243
		;	/* NULL */

244
245
246
247
	nl = ID_BLOCK_NIDS(b) - nr;

	*right = idl_alloc( nr == 0 ? 1 : nr );
	*left = idl_alloc( nl + (nr == 0 ? 0 : 1));
Kurt Zeilenga's avatar
Kurt Zeilenga committed
248
249
250
251
252
253

	/*
	 * everything before the id being inserted in the first block
	 * unless there is nothing, in which case the id being inserted
	 * goes there.
	 */
254
255
256
	if ( nr == 0 ) {
		ID_BLOCK_NIDS(*right) = 1;
		ID_BLOCK_ID(*right, 0) = id;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
257
	} else {
258
259
260
261
262
263
		SAFEMEMCPY(
			(char *) &ID_BLOCK_ID(*right, 0),
			(char *) &ID_BLOCK_ID(b, 0),
			nr * sizeof(ID) );
		ID_BLOCK_NIDS(*right) = nr;
		ID_BLOCK_ID(*left, 0) = id;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
264
265
266
	}

	/* the id being inserted & everything after in the second block */
267
268
269
270
271
	SAFEMEMCPY(
		(char *) &ID_BLOCK_ID(*left, (nr == 0 ? 0 : 1)),
	    (char *) &ID_BLOCK_ID(b, nr),
		nl * sizeof(ID) );
	ID_BLOCK_NIDS(*left) = nl + (nr == 0 ? 0 : 1);
Kurt Zeilenga's avatar
Kurt Zeilenga committed
272
273
}

274

Kurt Zeilenga's avatar
Kurt Zeilenga committed
275
276
277
278
279
280
281
282
/*
 * idl_change_first - called when an indirect block's first key has
 * changed, meaning it needs to be stored under a new key, and the
 * header block pointing to it needs updating.
 */
static int
idl_change_first(
    Backend		*be,
283
    DBCache	*db,
Kurt Zeilenga's avatar
Kurt Zeilenga committed
284
    Datum		hkey,		/* header block key	*/
285
    ID_BLOCK		*h,		/* header block 	*/
Kurt Zeilenga's avatar
Kurt Zeilenga committed
286
287
    int			pos,		/* pos in h to update	*/
    Datum		bkey,		/* data block key	*/
288
    ID_BLOCK		*b		/* data block 		*/
Kurt Zeilenga's avatar
Kurt Zeilenga committed
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
)
{
	int	rc;

	/* Debug( LDAP_DEBUG_TRACE, "=> idl_change_first\n", 0, 0, 0 ); */

	/* delete old key block */
	if ( (rc = ldbm_cache_delete( db, bkey )) != 0 ) {
		Debug( LDAP_DEBUG_ANY,
		    "ldbm_delete of (%s) returns %d\n", bkey.dptr, rc,
		    0 );
		return( rc );
	}

	/* write block with new key */
304
305
306
	sprintf( bkey.dptr, "%c%ld%s", CONT_PREFIX,
		ID_BLOCK_ID(b, 0), hkey.dptr );

Kurt Zeilenga's avatar
Kurt Zeilenga committed
307
308
309
310
311
312
313
314
	bkey.dsize = strlen( bkey.dptr ) + 1;
	if ( (rc = idl_store( be, db, bkey, b )) != 0 ) {
		Debug( LDAP_DEBUG_ANY,
		    "idl_store of (%s) returns %d\n", bkey.dptr, rc, 0 );
		return( rc );
	}

	/* update + write indirect header block */
315
	ID_BLOCK_ID(h, pos) = ID_BLOCK_ID(b, 0);
Kurt Zeilenga's avatar
Kurt Zeilenga committed
316
317
318
319
320
321
322
323
324
	if ( (rc = idl_store( be, db, hkey, h )) != 0 ) {
		Debug( LDAP_DEBUG_ANY,
		    "idl_store of (%s) returns %d\n", hkey.dptr, rc, 0 );
		return( rc );
	}

	return( 0 );
}

325

Kurt Zeilenga's avatar
Kurt Zeilenga committed
326
327
328
int
idl_insert_key(
    Backend		*be,
329
    DBCache	*db,
Kurt Zeilenga's avatar
Kurt Zeilenga committed
330
331
332
333
334
    Datum		key,
    ID			id
)
{
	int	i, j, first, rc;
335
	ID_BLOCK	*idl, *tmp, *tmp2, *tmp3;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
336
337
338
	char	*kstr;
	Datum	k2;

339
340
	ldbm_datum_init( k2 );

Kurt Zeilenga's avatar
Kurt Zeilenga committed
341
	if ( (idl = idl_fetch_one( be, db, key )) == NULL ) {
342
343
344
345
346
#ifdef LDBM_DEBUG
		Statslog( LDAP_DEBUG_STATS, "=> idl_insert_key(): no key yet\n",
			0, 0, 0, 0, 0 );
#endif

Kurt Zeilenga's avatar
Kurt Zeilenga committed
347
		idl = idl_alloc( 1 );
348
		ID_BLOCK_ID(idl, ID_BLOCK_NIDS(idl)++) = id;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
349
350
351
352
353
354
		rc = idl_store( be, db, key, idl );

		idl_free( idl );
		return( rc );
	}

355
356
357
358
359
360
361
362
	if ( ID_BLOCK_ALLIDS( idl ) ) {
		/* ALLIDS */
		idl_free( idl );
		return 0;
	}

	if ( ! ID_BLOCK_INDIRECT( idl ) ) {
		/* regular block */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
		switch ( idl_insert( &idl, id, db->dbc_maxids ) ) {
		case 0:		/* id inserted - store the updated block */
		case 1:
			rc = idl_store( be, db, key, idl );
			break;

		case 2:		/* id already there - nothing to do */
			rc = 0;
			break;

		case 3:		/* id not inserted - block must be split */
			/* check threshold for marking this an all-id block */
			if ( db->dbc_maxindirect < 2 ) {
				idl_free( idl );
				idl = idl_allids( be );
				rc = idl_store( be, db, key, idl );
379
				break;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
380
381
382
383
384
385
386
			}

			idl_split_block( idl, id, &tmp, &tmp2 );
			idl_free( idl );

			/* create the header indirect block */
			idl = idl_alloc( 3 );
387
388
389
390
391
			ID_BLOCK_NMAX(idl) = 3;
			ID_BLOCK_NIDS(idl) = ID_BLOCK_INDIRECT_VALUE;
			ID_BLOCK_ID(idl, 0) = ID_BLOCK_ID(tmp, 0);
			ID_BLOCK_ID(idl, 1) = ID_BLOCK_ID(tmp2, 0);
			ID_BLOCK_ID(idl, 2) = NOID;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
392
393
394
395
396

			/* store it */
			rc = idl_store( be, db, key, idl );

			/* store the first id block */
397
398
399
400
			kstr = (char *) ch_malloc( key.dsize + CONT_SIZE );
			sprintf( kstr, "%c%ld%s", CONT_PREFIX,
				ID_BLOCK_ID(tmp, 0), key.dptr );

Kurt Zeilenga's avatar
Kurt Zeilenga committed
401
402
403
404
405
			k2.dptr = kstr;
			k2.dsize = strlen( kstr ) + 1;
			rc = idl_store( be, db, k2, tmp );

			/* store the second id block */
406
407
			sprintf( kstr, "%c%ld%s", CONT_PREFIX,
				ID_BLOCK_ID(tmp2, 0), key.dptr );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
			k2.dptr = kstr;
			k2.dsize = strlen( kstr ) + 1;
			rc = idl_store( be, db, k2, tmp2 );

			free( kstr );
			idl_free( tmp );
			idl_free( tmp2 );
			break;
		}

		idl_free( idl );
		return( rc );
	}

	/*
	 * this is an indirect block which points to other blocks.
	 * we need to read in the block into which the id should be
	 * inserted, then insert the id and store the block.  we might
	 * have to split the block if it is full, which means we also
	 * need to write a new "header" block.
	 */

430
431
	/* select the block to try inserting into *//* XXX linear search XXX */
	for ( i = 0; !ID_BLOCK_NOID(idl, i) && id > ID_BLOCK_ID(idl, i); i++ )
Kurt Zeilenga's avatar
Kurt Zeilenga committed
432
433
434
435
436
437
438
439
440
		;	/* NULL */
	if ( i != 0 ) {
		i--;
		first = 0;
	} else {
		first = 1;
	}

	/* get the block */
441
442
443
	kstr = (char *) ch_malloc( key.dsize + CONT_SIZE );
	sprintf( kstr, "%c%ld%s", CONT_PREFIX,
		ID_BLOCK_ID(idl, i), key.dptr );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
444
445
446
447
448
	k2.dptr = kstr;
	k2.dsize = strlen( kstr ) + 1;
	if ( (tmp = idl_fetch_one( be, db, k2 )) == NULL ) {
		Debug( LDAP_DEBUG_ANY, "nonexistent continuation block (%s)\n",
		    k2.dptr, 0, 0 );
449
450
		free( kstr );
		idl_free( idl );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
		return( -1 );
	}

	/* insert the id */
	switch ( idl_insert( &tmp, id, db->dbc_maxids ) ) {
	case 0:		/* id inserted ok */
		if ( (rc = idl_store( be, db, k2, tmp )) != 0 ) {
			Debug( LDAP_DEBUG_ANY,
			    "idl_store of (%s) returns %d\n", k2.dptr, rc, 0 );
		}
		break;

	case 1:		/* id inserted - first id in block has changed */
		/*
		 * key for this block has changed, so we have to
		 * write the block under the new key, delete the
		 * old key block + update and write the indirect
		 * header block.
		 */

		rc = idl_change_first( be, db, key, idl, i, k2, tmp );
		break;

474
475
	case 2:		/* id not inserted - already there, do nothing */
		rc = 0;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
476
477
478
479
480
481
482
483
484
485
		break;

	case 3:		/* id not inserted - block is full */
		/*
		 * first, see if it will fit in the next block,
		 * without splitting, unless we're trying to insert
		 * into the beginning of the first block.
		 */

		/* is there a next block? */
486
		if ( !first && !ID_BLOCK_NOID(idl, i + 1) ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
487
			/* read it in */
488
489
			sprintf( kstr, "%c%ld%s", CONT_PREFIX,
				ID_BLOCK_ID(idl, i + 1), key.dptr );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
490
491
492
493
494
495
			k2.dptr = kstr;
			k2.dsize = strlen( kstr ) + 1;
			if ( (tmp2 = idl_fetch_one( be, db, k2 )) == NULL ) {
				Debug( LDAP_DEBUG_ANY,
				    "idl_fetch_one (%s) returns NULL\n",
				    k2.dptr, 0, 0 );
496
497
				/* split the original block */
				goto split;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
498
499
500
501
502
503
504
505
506
507
508
509
510
			}

			switch ( (rc = idl_insert( &tmp2, id,
			    db->dbc_maxids )) ) {
			case 1:		/* id inserted first in block */
				rc = idl_change_first( be, db, key, idl,
				    i + 1, k2, tmp2 );
				/* FALL */

			case 2:		/* id already there - how? */
			case 0:		/* id inserted */
				if ( rc == 2 ) {
					Debug( LDAP_DEBUG_ANY,
511
					    "id %ld already in next block\n",
Kurt Zeilenga's avatar
Kurt Zeilenga committed
512
513
514
515
516
517
518
519
520
521
522
					    id, 0, 0 );
				}
				free( kstr );
				idl_free( tmp );
				idl_free( tmp2 );
				idl_free( idl );
				return( 0 );

			case 3:		/* split the original block */
				break;
			}
523

524
			idl_free( tmp2 );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
525
526
		}

527
split:
Kurt Zeilenga's avatar
Kurt Zeilenga committed
528
529
530
531
532
		/*
		 * must split the block, write both new blocks + update
		 * and write the indirect header block.
		 */

533
534
535
		rc = 0;	/* optimistic */


536
537
		/* count how many indirect blocks *//* XXX linear count XXX */
		for ( j = 0; !ID_BLOCK_NOID(idl, j); j++ )
Kurt Zeilenga's avatar
Kurt Zeilenga committed
538
539
540
541
542
543
544
545
546
547
548
549
550
			;	/* NULL */

		/* check it against all-id thresholed */
		if ( j + 1 > db->dbc_maxindirect ) {
			/*
			 * we've passed the all-id threshold, meaning
			 * that this set of blocks should be replaced
			 * by a single "all-id" block.  our job: delete
			 * all the indirect blocks, and replace the header
			 * block by an all-id block.
			 */

			/* delete all indirect blocks */
551
552
553
			for ( j = 0; !ID_BLOCK_NOID(idl, j); j++ ) {
				sprintf( kstr, "%c%ld%s", CONT_PREFIX,
					ID_BLOCK_ID(idl, j), key.dptr );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
				k2.dptr = kstr;
				k2.dsize = strlen( kstr ) + 1;

				rc = ldbm_cache_delete( db, k2 );
			}

			/* store allid block in place of header block */
			idl_free( idl );
			idl = idl_allids( be );
			rc = idl_store( be, db, key, idl );

			free( kstr );
			idl_free( idl );
			idl_free( tmp );
			return( rc );
		}

		idl_split_block( tmp, id, &tmp2, &tmp3 );
		idl_free( tmp );

		/* create a new updated indirect header block */
575
576
		tmp = idl_alloc( ID_BLOCK_NMAX(idl) + 1 );
		ID_BLOCK_NIDS(tmp) = ID_BLOCK_INDIRECT_VALUE;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
577
		/* everything up to the split block */
578
579
580
		SAFEMEMCPY(
			(char *) &ID_BLOCK_ID(tmp, 0),
			(char *) &ID_BLOCK_ID(idl, 0),
Kurt Zeilenga's avatar
Kurt Zeilenga committed
581
582
		    i * sizeof(ID) );
		/* the two new blocks */
583
584
		ID_BLOCK_ID(tmp, i) = ID_BLOCK_ID(tmp2, 0);
		ID_BLOCK_ID(tmp, i + 1) = ID_BLOCK_ID(tmp3, 0);
Kurt Zeilenga's avatar
Kurt Zeilenga committed
585
		/* everything after the split block */
586
587
588
589
		SAFEMEMCPY(
			(char *) &ID_BLOCK_ID(tmp, i + 2),
			(char *) &ID_BLOCK_ID(idl, i + 1),
			(ID_BLOCK_NMAX(idl) - i - 1) * sizeof(ID) );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
590
591
592
593
594

		/* store the header block */
		rc = idl_store( be, db, key, tmp );

		/* store the first id block */
595
596
		sprintf( kstr, "%c%ld%s", CONT_PREFIX,
			ID_BLOCK_ID(tmp2, 0), key.dptr );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
597
598
599
600
601
		k2.dptr = kstr;
		k2.dsize = strlen( kstr ) + 1;
		rc = idl_store( be, db, k2, tmp2 );

		/* store the second id block */
602
603
		sprintf( kstr, "%c%ld%s", CONT_PREFIX,
			ID_BLOCK_ID(tmp3, 0), key.dptr );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
		k2.dptr = kstr;
		k2.dsize = strlen( kstr ) + 1;
		rc = idl_store( be, db, k2, tmp3 );

		idl_free( tmp2 );
		idl_free( tmp3 );
		break;
	}

	free( kstr );
	idl_free( tmp );
	idl_free( idl );
	return( rc );
}

619

Kurt Zeilenga's avatar
Kurt Zeilenga committed
620
621
/*
 * idl_insert - insert an id into an id list.
622
623
624
 *
 *	returns
 * 		0	id inserted
Kurt Zeilenga's avatar
Kurt Zeilenga committed
625
626
627
628
629
 *		1	id inserted, first id in block has changed
 *		2	id not inserted, already there
 *		3	id not inserted, block must be split
 */
int
630
idl_insert( ID_BLOCK **idl, ID id, unsigned int maxids )
Kurt Zeilenga's avatar
Kurt Zeilenga committed
631
{
632
	unsigned int	i;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
633

634
	if ( ID_BLOCK_ALLIDS( *idl ) ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
635
636
637
		return( 2 );	/* already there */
	}

638
639
	/* is it already there? *//* XXX linear search XXX */
	for ( i = 0; i < ID_BLOCK_NIDS(*idl) && id > ID_BLOCK_ID(*idl, i); i++ ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
640
641
		;	/* NULL */
	}
642
	if ( i < ID_BLOCK_NIDS(*idl) && ID_BLOCK_ID(*idl, i) == id ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
643
644
645
646
		return( 2 );	/* already there */
	}

	/* do we need to make room for it? */
647
	if ( ID_BLOCK_NIDS(*idl) == ID_BLOCK_NMAX(*idl) ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
648
		/* make room or indicate block needs splitting */
649
		if ( ID_BLOCK_NMAX(*idl) >= maxids ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
650
651
652
			return( 3 );	/* block needs splitting */
		}

653
654
655
		ID_BLOCK_NMAX(*idl) *= 2;
		if ( ID_BLOCK_NMAX(*idl) > maxids ) {
			ID_BLOCK_NMAX(*idl) = maxids;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
656
		}
657
658
		*idl = (ID_BLOCK *) ch_realloc( (char *) *idl,
		    (ID_BLOCK_NMAX(*idl) + ID_BLOCK_IDS_OFFSET) * sizeof(ID) );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
659
660
661
	}

	/* make a slot for the new id */
662
663
	SAFEMEMCPY( &ID_BLOCK_ID(*idl, i+1), &ID_BLOCK_ID(*idl, i),
	            (ID_BLOCK_NIDS(*idl) - i) * sizeof(ID) );
664
665
666
667
668
669
670

	ID_BLOCK_ID(*idl, i) = id;
	ID_BLOCK_NIDS(*idl)++;
	(void) memset(
		(char *) &ID_BLOCK_ID((*idl), ID_BLOCK_NIDS(*idl)),
		'\0',
	    (ID_BLOCK_NMAX(*idl) - ID_BLOCK_NIDS(*idl)) * sizeof(ID) );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
671
672
673
674

	return( i == 0 ? 1 : 0 );	/* inserted - first id changed or not */
}

675
676
677
678
679
680
681
682
683
684

int
idl_delete_key (
	Backend         *be,
	DBCache  *db,
	Datum           key,
	ID              id
)
{
	Datum  data;
685
	ID_BLOCK *idl;
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
	unsigned i;
	int j, nids;
	char	*kstr;

	if ( (idl = idl_fetch_one( be, db, key ) ) == NULL )
	{
		/* It wasn't found.  Hmm... */
		return -1;
	}

	if ( ID_BLOCK_ALLIDS( idl ) ) {
		idl_free( idl );
		return 0;
	}

	if ( ! ID_BLOCK_INDIRECT( idl ) ) {
		for ( i=0; i < ID_BLOCK_NIDS(idl); i++ ) {
			if ( ID_BLOCK_ID(idl, i) == id ) {
				if( --ID_BLOCK_NIDS(idl) == 0 ) {
					ldbm_cache_delete( db, key );

				} else {
					SAFEMEMCPY (
						&ID_BLOCK_ID(idl, i),
						&ID_BLOCK_ID(idl, i+1),
						(ID_BLOCK_NIDS(idl)-i) * sizeof(ID) );

					ID_BLOCK_ID(idl, ID_BLOCK_NIDS(idl)) = NOID;

					idl_store( be, db, key, idl );
				}

				idl_free( idl );
				return 0;
			}
			/*  We didn't find the ID.  Hmmm... */
		}
		idl_free( idl );
		return -1;
	}
	
	/* We have to go through an indirect block and find the ID
	   in the list of IDL's
	   */
	for ( nids = 0; !ID_BLOCK_NOID(idl, nids); nids++ )
		;	/* NULL */
	kstr = (char *) ch_malloc( key.dsize + CONT_SIZE );

	for ( j = 0; !ID_BLOCK_NOID(idl, j); j++ ) 
	{
736
		ID_BLOCK *tmp;
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
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
785
786
787
788
789
790
791
792
793
794
		ldbm_datum_init( data );
		sprintf( kstr, "%c%ld%s", CONT_PREFIX,
			ID_BLOCK_ID(idl, j), key.dptr );
		data.dptr = kstr;
		data.dsize = strlen( kstr ) + 1;

		if ( (tmp = idl_fetch_one( be, db, data )) == NULL ) {
			Debug( LDAP_DEBUG_ANY,
			    "idl_fetch of (%s) returns NULL\n", data.dptr, 0, 0 );
			continue;
		}
		/*
		   Now try to find the ID in tmp
		*/
		for ( i=0; i < ID_BLOCK_NIDS(tmp); i++ )
		{
			if ( ID_BLOCK_ID(tmp, i) == id )
			{
				SAFEMEMCPY(
					&ID_BLOCK_ID(tmp, i),
					&ID_BLOCK_ID(tmp, i+1),
					(ID_BLOCK_NIDS(tmp)-(i+1)) * sizeof(ID));
				ID_BLOCK_ID(tmp, ID_BLOCK_NIDS(tmp)-1 ) = NOID;
				ID_BLOCK_NIDS(tmp)--;

				if ( ID_BLOCK_NIDS(tmp) ) {
					idl_store ( be, db, data, tmp );

				} else {
					ldbm_cache_delete( db, data );
					SAFEMEMCPY(
						&ID_BLOCK_ID(idl, j),
						&ID_BLOCK_ID(idl, j+1),
						(nids-(j+1)) * sizeof(ID));
					ID_BLOCK_ID(idl, nids-1) = NOID;
					nids--;
					if ( ! nids )
						ldbm_cache_delete( db, key );
					else
						idl_store( be, db, key, idl );
				}
				idl_free( tmp );
				free( kstr );
				idl_free( idl );
				return 0;
			}
		}
		idl_free( tmp );
	}
	free( kstr );
	idl_free( idl );
	return -1;
}


/* return a duplicate of a single ID_BLOCK */
static ID_BLOCK *
idl_dup( ID_BLOCK *idl )
Kurt Zeilenga's avatar
Kurt Zeilenga committed
795
{
796
	ID_BLOCK	*new;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
797
798
799
800
801

	if ( idl == NULL ) {
		return( NULL );
	}

802
803
804
805
806
807
	new = idl_alloc( ID_BLOCK_NMAX(idl) );

	SAFEMEMCPY(
		(char *) new,
		(char *) idl,
		(ID_BLOCK_NMAX(idl) + ID_BLOCK_IDS_OFFSET) * sizeof(ID) );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
808
809
810
811

	return( new );
}

812
813
814
815

/* return the smaller ID_BLOCK */
static ID_BLOCK *
idl_min( ID_BLOCK *a, ID_BLOCK *b )
Kurt Zeilenga's avatar
Kurt Zeilenga committed
816
{
817
	return( ID_BLOCK_NIDS(a) > ID_BLOCK_NIDS(b) ? b : a );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
818
819
}

820

Kurt Zeilenga's avatar
Kurt Zeilenga committed
821
822
823
/*
 * idl_intersection - return a intersection b
 */
824
ID_BLOCK *
Kurt Zeilenga's avatar
Kurt Zeilenga committed
825
826
idl_intersection(
    Backend	*be,
827
828
    ID_BLOCK	*a,
    ID_BLOCK	*b
Kurt Zeilenga's avatar
Kurt Zeilenga committed
829
830
)
{
831
832
	unsigned int	ai, bi, ni;
	ID_BLOCK		*n;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
833
834
835
836

	if ( a == NULL || b == NULL ) {
		return( NULL );
	}
837
	if ( ID_BLOCK_ALLIDS( a ) ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
838
839
		return( idl_dup( b ) );
	}
840
	if ( ID_BLOCK_ALLIDS( b ) ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
841
842
843
844
845
		return( idl_dup( a ) );
	}

	n = idl_dup( idl_min( a, b ) );

846
847
848
849
850
	for ( ni = 0, ai = 0, bi = 0; ai < ID_BLOCK_NIDS(a); ai++ ) {
		for ( ;
			bi < ID_BLOCK_NIDS(b) && ID_BLOCK_ID(b, bi) < ID_BLOCK_ID(a, ai);
			bi++ )
		{
Kurt Zeilenga's avatar
Kurt Zeilenga committed
851
			;	/* NULL */
852
		}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
853

854
		if ( bi == ID_BLOCK_NIDS(b) ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
855
856
857
			break;
		}

858
859
		if ( ID_BLOCK_ID(b, bi) == ID_BLOCK_ID(a, ai) ) {
			ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
Kurt Zeilenga's avatar
Kurt Zeilenga committed
860
861
862
863
864
865
866
		}
	}

	if ( ni == 0 ) {
		idl_free( n );
		return( NULL );
	}
867
	ID_BLOCK_NIDS(n) = ni;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
868
869
870
871

	return( n );
}

872

Kurt Zeilenga's avatar
Kurt Zeilenga committed
873
874
875
/*
 * idl_union - return a union b
 */
876
ID_BLOCK *
Kurt Zeilenga's avatar
Kurt Zeilenga committed
877
878
idl_union(
    Backend	*be,
879
880
    ID_BLOCK	*a,
    ID_BLOCK	*b
Kurt Zeilenga's avatar
Kurt Zeilenga committed
881
882
)
{
883
884
	unsigned int	ai, bi, ni;
	ID_BLOCK		*n;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
885
886
887
888
889
890
891

	if ( a == NULL ) {
		return( idl_dup( b ) );
	}
	if ( b == NULL ) {
		return( idl_dup( a ) );
	}
892
	if ( ID_BLOCK_ALLIDS( a ) || ID_BLOCK_ALLIDS( b ) ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
893
894
895
		return( idl_allids( be ) );
	}

896
	if ( ID_BLOCK_NIDS(b) < ID_BLOCK_NIDS(a) ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
897
898
899
900
901
		n = a;
		a = b;
		b = n;
	}

902
903
904
905
906
907
908
909
910
911
912
	n = idl_alloc( ID_BLOCK_NIDS(a) + ID_BLOCK_NIDS(b) );

	for ( ni = 0, ai = 0, bi = 0;
		ai < ID_BLOCK_NIDS(a) && bi < ID_BLOCK_NIDS(b);
		)
	{
		if ( ID_BLOCK_ID(a, ai) < ID_BLOCK_ID(b, bi) ) {
			ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai++);

		} else if ( ID_BLOCK_ID(b, bi) < ID_BLOCK_ID(a, ai) ) {
			ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(b, bi++);
Kurt Zeilenga's avatar
Kurt Zeilenga committed
913
914

		} else {
915
			ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
Kurt Zeilenga's avatar
Kurt Zeilenga committed
916
917
918
919
			ai++, bi++;
		}
	}

920
921
	for ( ; ai < ID_BLOCK_NIDS(a); ai++ ) {
		ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
Kurt Zeilenga's avatar
Kurt Zeilenga committed
922
	}
923
924
	for ( ; bi < ID_BLOCK_NIDS(b); bi++ ) {
		ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(b, bi);
Kurt Zeilenga's avatar
Kurt Zeilenga committed
925
	}
926
	ID_BLOCK_NIDS(n) = ni;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
927
928
929
930

	return( n );
}

931

Kurt Zeilenga's avatar
Kurt Zeilenga committed
932
933
934
/*
 * idl_notin - return a intersection ~b (or a minus b)
 */
935
ID_BLOCK *
Kurt Zeilenga's avatar
Kurt Zeilenga committed
936
937
idl_notin(
    Backend	*be,
938
939
    ID_BLOCK 	*a,
    ID_BLOCK 	*b
Kurt Zeilenga's avatar
Kurt Zeilenga committed
940
941
)
{
942
943
	unsigned int	ni, ai, bi;
	ID_BLOCK		*n;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
944
945
946
947

	if ( a == NULL ) {
		return( NULL );
	}
948
	if ( b == NULL || ID_BLOCK_ALLIDS( b )) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
949
950
951
		return( idl_dup( a ) );
	}

952
	if ( ID_BLOCK_ALLIDS( a ) ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
953
954
955
		n = idl_alloc( SLAPD_LDBM_MIN_MAXIDS );
		ni = 0;

956
957
958
959
960
		for ( ai = 1, bi = 0;
			ai < ID_BLOCK_NIDS(a) && ni < ID_BLOCK_NMAX(n) && bi < ID_BLOCK_NMAX(b);
			ai++ )
		{
			if ( ID_BLOCK_ID(b, bi) == ai ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
961
962
				bi++;
			} else {
963
				ID_BLOCK_ID(n, ni++) = ai;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
964
965
966
			}
		}

967
968
		for ( ; ai < ID_BLOCK_NIDS(a) && ni < ID_BLOCK_NMAX(n); ai++ ) {
			ID_BLOCK_ID(n, ni++) = ai;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
969
970
		}

971
		if ( ni == ID_BLOCK_NMAX(n) ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
972
973
974
			idl_free( n );
			return( idl_allids( be ) );
		} else {
975
			ID_BLOCK_NIDS(n) = ni;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
976
977
978
979
980
981
982
			return( n );
		}
	}

	n = idl_dup( a );

	ni = 0;
983
984
985
986
987
	for ( ai = 0, bi = 0; ai < ID_BLOCK_NIDS(a); ai++ ) {
		for ( ;
			bi < ID_BLOCK_NIDS(b) && ID_BLOCK_ID(b, bi) < ID_BLOCK_ID(a, ai);
		    bi++ )
		{
Kurt Zeilenga's avatar
Kurt Zeilenga committed
988
989
990
			;	/* NULL */
		}

991
		if ( bi == ID_BLOCK_NIDS(b) ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
992
993
994
			break;
		}

995
996
		if ( ID_BLOCK_ID(b, bi) != ID_BLOCK_ID(a, ai) ) {
			ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
Kurt Zeilenga's avatar
Kurt Zeilenga committed
997
998
999
		}
	}

1000
	for ( ; ai < ID_BLOCK_NIDS(a); ai++ ) {
For faster browsing, not all history is shown. View entire blame