xref: /netbsd-src/external/bsd/openldap/dist/servers/slapd/back-mdb/idl.c (revision 549b59ed3ccf0d36d3097190a0db27b770f3a839)
1 /*	$NetBSD: idl.c,v 1.3 2021/08/14 16:15:00 christos Exp $	*/
2 
3 /* idl.c - ldap id list handling routines */
4 /* $OpenLDAP$ */
5 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
6  *
7  * Copyright 2000-2021 The OpenLDAP Foundation.
8  * All rights reserved.
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted only as authorized by the OpenLDAP
12  * Public License.
13  *
14  * A copy of this license is available in the file LICENSE in the
15  * top-level directory of the distribution or, alternatively, at
16  * <http://www.OpenLDAP.org/license.html>.
17  */
18 
19 #include <sys/cdefs.h>
20 __RCSID("$NetBSD: idl.c,v 1.3 2021/08/14 16:15:00 christos Exp $");
21 
22 #include "portable.h"
23 
24 #include <stdio.h>
25 #include <ac/string.h>
26 
27 #include "back-mdb.h"
28 #include "idl.h"
29 
30 unsigned int MDB_idl_logn = MDB_IDL_LOGN;
31 unsigned int MDB_idl_db_size = 1 << MDB_IDL_LOGN;
32 unsigned int MDB_idl_um_size = 1 << (MDB_IDL_LOGN+1);
33 unsigned int MDB_idl_db_max = (1 << MDB_IDL_LOGN) - 1;
34 unsigned int MDB_idl_um_max = (1 << (MDB_IDL_LOGN+1)) - 1;
35 
36 #define IDL_MAX(x,y)	( (x) > (y) ? (x) : (y) )
37 #define IDL_MIN(x,y)	( (x) < (y) ? (x) : (y) )
38 #define IDL_CMP(x,y)	( (x) < (y) ? -1 : (x) > (y) )
39 
40 #if IDL_DEBUG > 0
idl_check(ID * ids)41 static void idl_check( ID *ids )
42 {
43 	if( MDB_IDL_IS_RANGE( ids ) ) {
44 		assert( MDB_IDL_RANGE_FIRST(ids) <= MDB_IDL_RANGE_LAST(ids) );
45 	} else {
46 		ID i;
47 		for( i=1; i < ids[0]; i++ ) {
48 			assert( ids[i+1] > ids[i] );
49 		}
50 	}
51 }
52 
53 #if IDL_DEBUG > 1
idl_dump(ID * ids)54 static void idl_dump( ID *ids )
55 {
56 	if( MDB_IDL_IS_RANGE( ids ) ) {
57 		Debug( LDAP_DEBUG_ANY,
58 			"IDL: range ( %ld - %ld )\n",
59 			(long) MDB_IDL_RANGE_FIRST( ids ),
60 			(long) MDB_IDL_RANGE_LAST( ids ) );
61 
62 	} else {
63 		ID i;
64 		Debug( LDAP_DEBUG_ANY, "IDL: size %ld", (long) ids[0] );
65 
66 		for( i=1; i<=ids[0]; i++ ) {
67 			if( i % 16 == 1 ) {
68 				Debug( LDAP_DEBUG_ANY, "\n" );
69 			}
70 			Debug( LDAP_DEBUG_ANY, "  %02lx", (long) ids[i] );
71 		}
72 
73 		Debug( LDAP_DEBUG_ANY, "\n" );
74 	}
75 
76 	idl_check( ids );
77 }
78 #endif /* IDL_DEBUG > 1 */
79 #endif /* IDL_DEBUG > 0 */
80 
mdb_idl_reset()81 void mdb_idl_reset()
82 {
83 	if ( !MDB_idl_logn )
84 		MDB_idl_logn = MDB_IDL_LOGN;
85 
86 	MDB_idl_db_size = 1 << MDB_idl_logn;
87 	MDB_idl_um_size = 1 << (MDB_idl_logn+1);
88 	MDB_idl_db_max = MDB_idl_db_size - 1;
89 	MDB_idl_um_max = MDB_idl_um_size - 1;
90 }
91 
mdb_idl_search(ID * ids,ID id)92 unsigned mdb_idl_search( ID *ids, ID id )
93 {
94 #define IDL_BINARY_SEARCH 1
95 #ifdef IDL_BINARY_SEARCH
96 	/*
97 	 * binary search of id in ids
98 	 * if found, returns position of id
99 	 * if not found, returns first position greater than id
100 	 */
101 	unsigned base = 0;
102 	unsigned cursor = 1;
103 	int val = 0;
104 	unsigned n = ids[0];
105 
106 #if IDL_DEBUG > 0
107 	idl_check( ids );
108 #endif
109 
110 	while( 0 < n ) {
111 		unsigned pivot = n >> 1;
112 		cursor = base + pivot + 1;
113 		val = IDL_CMP( id, ids[cursor] );
114 
115 		if( val < 0 ) {
116 			n = pivot;
117 
118 		} else if ( val > 0 ) {
119 			base = cursor;
120 			n -= pivot + 1;
121 
122 		} else {
123 			return cursor;
124 		}
125 	}
126 
127 	if( val > 0 ) {
128 		++cursor;
129 	}
130 	return cursor;
131 
132 #else
133 	/* (reverse) linear search */
134 	int i;
135 
136 #if IDL_DEBUG > 0
137 	idl_check( ids );
138 #endif
139 
140 	for( i=ids[0]; i; i-- ) {
141 		if( id > ids[i] ) {
142 			break;
143 		}
144 	}
145 
146 	return i+1;
147 #endif
148 }
149 
mdb_idl_insert(ID * ids,ID id)150 int mdb_idl_insert( ID *ids, ID id )
151 {
152 	unsigned x;
153 
154 #if IDL_DEBUG > 1
155 	Debug( LDAP_DEBUG_ANY, "insert: %04lx at %d\n", (long) id, x );
156 	idl_dump( ids );
157 #elif IDL_DEBUG > 0
158 	idl_check( ids );
159 #endif
160 
161 	if (MDB_IDL_IS_RANGE( ids )) {
162 		/* if already in range, treat as a dup */
163 		if (id >= MDB_IDL_RANGE_FIRST(ids) && id <= MDB_IDL_RANGE_LAST(ids))
164 			return -1;
165 		if (id < MDB_IDL_RANGE_FIRST(ids))
166 			ids[1] = id;
167 		else if (id > MDB_IDL_RANGE_LAST(ids))
168 			ids[2] = id;
169 		return 0;
170 	}
171 
172 	x = mdb_idl_search( ids, id );
173 	assert( x > 0 );
174 
175 	if( x < 1 ) {
176 		/* internal error */
177 		return -2;
178 	}
179 
180 	if ( x <= ids[0] && ids[x] == id ) {
181 		/* duplicate */
182 		return -1;
183 	}
184 
185 	if ( ++ids[0] >= MDB_idl_db_max ) {
186 		if( id < ids[1] ) {
187 			ids[1] = id;
188 			ids[2] = ids[ids[0]-1];
189 		} else if ( ids[ids[0]-1] < id ) {
190 			ids[2] = id;
191 		} else {
192 			ids[2] = ids[ids[0]-1];
193 		}
194 		ids[0] = NOID;
195 
196 	} else {
197 		/* insert id */
198 		AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
199 		ids[x] = id;
200 	}
201 
202 #if IDL_DEBUG > 1
203 	idl_dump( ids );
204 #elif IDL_DEBUG > 0
205 	idl_check( ids );
206 #endif
207 
208 	return 0;
209 }
210 
mdb_idl_delete(ID * ids,ID id)211 static int mdb_idl_delete( ID *ids, ID id )
212 {
213 	unsigned x;
214 
215 #if IDL_DEBUG > 1
216 	Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x );
217 	idl_dump( ids );
218 #elif IDL_DEBUG > 0
219 	idl_check( ids );
220 #endif
221 
222 	if (MDB_IDL_IS_RANGE( ids )) {
223 		/* If deleting a range boundary, adjust */
224 		if ( ids[1] == id )
225 			ids[1]++;
226 		else if ( ids[2] == id )
227 			ids[2]--;
228 		/* deleting from inside a range is a no-op */
229 
230 		/* If the range has collapsed, re-adjust */
231 		if ( ids[1] > ids[2] )
232 			ids[0] = 0;
233 		else if ( ids[1] == ids[2] )
234 			ids[1] = 1;
235 		return 0;
236 	}
237 
238 	x = mdb_idl_search( ids, id );
239 	assert( x > 0 );
240 
241 	if( x <= 0 ) {
242 		/* internal error */
243 		return -2;
244 	}
245 
246 	if( x > ids[0] || ids[x] != id ) {
247 		/* not found */
248 		return -1;
249 
250 	} else if ( --ids[0] == 0 ) {
251 		if( x != 1 ) {
252 			return -3;
253 		}
254 
255 	} else {
256 		AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
257 	}
258 
259 #if IDL_DEBUG > 1
260 	idl_dump( ids );
261 #elif IDL_DEBUG > 0
262 	idl_check( ids );
263 #endif
264 
265 	return 0;
266 }
267 
268 static char *
mdb_show_key(char * buf,void * val,size_t len)269 mdb_show_key(
270 	char		*buf,
271 	void		*val,
272 	size_t		len )
273 {
274 	if ( len == 4 /* LUTIL_HASH_BYTES */ ) {
275 		unsigned char *c = val;
276 		sprintf( buf, "[%02x%02x%02x%02x]", c[0], c[1], c[2], c[3] );
277 		return buf;
278 	} else {
279 		return val;
280 	}
281 }
282 
283 int
mdb_idl_fetch_key(BackendDB * be,MDB_txn * txn,MDB_dbi dbi,MDB_val * key,ID * ids,MDB_cursor ** saved_cursor,int get_flag)284 mdb_idl_fetch_key(
285 	BackendDB	*be,
286 	MDB_txn		*txn,
287 	MDB_dbi		dbi,
288 	MDB_val		*key,
289 	ID			*ids,
290 	MDB_cursor	**saved_cursor,
291 	int			get_flag )
292 {
293 	MDB_val data, key2, *kptr;
294 	MDB_cursor *cursor;
295 	ID *i;
296 	size_t len;
297 	int rc;
298 	MDB_cursor_op opflag;
299 
300 	char keybuf[16];
301 
302 	Debug( LDAP_DEBUG_ARGS,
303 		"mdb_idl_fetch_key: %s\n",
304 		mdb_show_key( keybuf, key->mv_data, key->mv_size ) );
305 
306 	assert( ids != NULL );
307 
308 	if ( saved_cursor && *saved_cursor ) {
309 		opflag = MDB_NEXT;
310 	} else if ( get_flag == LDAP_FILTER_GE ) {
311 		opflag = MDB_SET_RANGE;
312 	} else if ( get_flag == LDAP_FILTER_LE ) {
313 		opflag = MDB_FIRST;
314 	} else {
315 		opflag = MDB_SET;
316 	}
317 
318 	/* If we're not reusing an existing cursor, get a new one */
319 	if( opflag != MDB_NEXT ) {
320 		rc = mdb_cursor_open( txn, dbi, &cursor );
321 		if( rc != 0 ) {
322 			Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
323 				"cursor failed: %s (%d)\n", mdb_strerror(rc), rc );
324 			return rc;
325 		}
326 	} else {
327 		cursor = *saved_cursor;
328 	}
329 
330 	/* If this is a LE lookup, save original key so we can determine
331 	 * when to stop. If this is a GE lookup, save the key since it
332 	 * will be overwritten.
333 	 */
334 	if ( get_flag == LDAP_FILTER_LE || get_flag == LDAP_FILTER_GE ) {
335 		key2.mv_data = keybuf;
336 		key2.mv_size = key->mv_size;
337 		AC_MEMCPY( keybuf, key->mv_data, key->mv_size );
338 		kptr = &key2;
339 	} else {
340 		kptr = key;
341 	}
342 	len = key->mv_size;
343 	rc = mdb_cursor_get( cursor, kptr, &data, opflag );
344 
345 	/* skip presence key on range inequality lookups */
346 	while (rc == 0 && kptr->mv_size != len) {
347 		rc = mdb_cursor_get( cursor, kptr, &data, MDB_NEXT_NODUP );
348 	}
349 	/* If we're doing a LE compare and the new key is greater than
350 	 * our search key, we're done
351 	 */
352 	if (rc == 0 && get_flag == LDAP_FILTER_LE && memcmp( kptr->mv_data,
353 		key->mv_data, key->mv_size ) > 0 ) {
354 		rc = MDB_NOTFOUND;
355 	}
356 	if (rc == 0) {
357 		i = ids+1;
358 		rc = mdb_cursor_get( cursor, key, &data, MDB_GET_MULTIPLE );
359 		while (rc == 0) {
360 			memcpy( i, data.mv_data, data.mv_size );
361 			i += data.mv_size / sizeof(ID);
362 			rc = mdb_cursor_get( cursor, key, &data, MDB_NEXT_MULTIPLE );
363 		}
364 		if ( rc == MDB_NOTFOUND ) rc = 0;
365 		ids[0] = i - &ids[1];
366 		/* On disk, a range is denoted by 0 in the first element */
367 		if (ids[1] == 0) {
368 			if (ids[0] != MDB_IDL_RANGE_SIZE) {
369 				Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
370 					"range size mismatch: expected %d, got %ld\n",
371 					MDB_IDL_RANGE_SIZE, ids[0] );
372 				mdb_cursor_close( cursor );
373 				return -1;
374 			}
375 			MDB_IDL_RANGE( ids, ids[2], ids[3] );
376 		}
377 		data.mv_size = MDB_IDL_SIZEOF(ids);
378 	}
379 
380 	if ( saved_cursor && rc == 0 ) {
381 		if ( !*saved_cursor )
382 			*saved_cursor = cursor;
383 	}
384 	else
385 		mdb_cursor_close( cursor );
386 
387 	if( rc == MDB_NOTFOUND ) {
388 		return rc;
389 
390 	} else if( rc != 0 ) {
391 		Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
392 			"get failed: %s (%d)\n",
393 			mdb_strerror(rc), rc );
394 		return rc;
395 
396 	} else if ( data.mv_size == 0 || data.mv_size % sizeof( ID ) ) {
397 		/* size not multiple of ID size */
398 		Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
399 			"odd size: expected %ld multiple, got %ld\n",
400 			(long) sizeof( ID ), (long) data.mv_size );
401 		return -1;
402 
403 	} else if ( data.mv_size != MDB_IDL_SIZEOF(ids) ) {
404 		/* size mismatch */
405 		Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
406 			"get size mismatch: expected %ld, got %ld\n",
407 			(long) ((1 + ids[0]) * sizeof( ID )), (long) data.mv_size );
408 		return -1;
409 	}
410 
411 	return rc;
412 }
413 
414 int
mdb_idl_insert_keys(BackendDB * be,MDB_cursor * cursor,struct berval * keys,ID id)415 mdb_idl_insert_keys(
416 	BackendDB	*be,
417 	MDB_cursor	*cursor,
418 	struct berval *keys,
419 	ID			id )
420 {
421 	struct mdb_info *mdb = be->be_private;
422 	MDB_val key, data;
423 	ID lo, hi, *i;
424 	char *err;
425 	int	rc = 0, k;
426 	unsigned int flag = MDB_NODUPDATA;
427 #ifndef	MISALIGNED_OK
428 	int kbuf[2];
429 #endif
430 
431 	{
432 		char buf[16];
433 		Debug( LDAP_DEBUG_ARGS,
434 			"mdb_idl_insert_keys: %lx %s\n",
435 			(long) id, mdb_show_key( buf, keys->bv_val, keys->bv_len ) );
436 	}
437 
438 	assert( id != NOID );
439 
440 #ifndef MISALIGNED_OK
441 	if (keys[0].bv_len & ALIGNER)
442 		kbuf[1] = 0;
443 #endif
444 	for ( k=0; keys[k].bv_val; k++ ) {
445 	/* Fetch the first data item for this key, to see if it
446 	 * exists and if it's a range.
447 	 */
448 #ifndef MISALIGNED_OK
449 	if (keys[k].bv_len & ALIGNER) {
450 		key.mv_size = sizeof(kbuf);
451 		key.mv_data = kbuf;
452 		memcpy(key.mv_data, keys[k].bv_val, keys[k].bv_len);
453 	} else
454 #endif
455 	{
456 		key.mv_size = keys[k].bv_len;
457 		key.mv_data = keys[k].bv_val;
458 	}
459 	rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
460 	err = "c_get";
461 	if ( rc == 0 ) {
462 		i = data.mv_data;
463 		memcpy(&lo, data.mv_data, sizeof(ID));
464 		if ( lo != 0 ) {
465 			/* not a range, count the number of items */
466 			size_t count;
467 			rc = mdb_cursor_count( cursor, &count );
468 			if ( rc != 0 ) {
469 				err = "c_count";
470 				goto fail;
471 			}
472 			if ( count >= MDB_idl_db_max ) {
473 			/* No room, convert to a range */
474 				lo = *i;
475 				rc = mdb_cursor_get( cursor, &key, &data, MDB_LAST_DUP );
476 				if ( rc != 0 && rc != MDB_NOTFOUND ) {
477 					err = "c_get last_dup";
478 					goto fail;
479 				}
480 				i = data.mv_data;
481 				hi = *i;
482 				/* Update hi/lo if needed */
483 				if ( id < lo ) {
484 					lo = id;
485 				} else if ( id > hi ) {
486 					hi = id;
487 				}
488 				/* delete the old key */
489 				rc = mdb_cursor_del( cursor, MDB_NODUPDATA );
490 				if ( rc != 0 ) {
491 					err = "c_del dups";
492 					goto fail;
493 				}
494 				/* Store the range */
495 				data.mv_size = sizeof(ID);
496 				data.mv_data = &id;
497 				id = 0;
498 				rc = mdb_cursor_put( cursor, &key, &data, 0 );
499 				if ( rc != 0 ) {
500 					err = "c_put range";
501 					goto fail;
502 				}
503 				id = lo;
504 				rc = mdb_cursor_put( cursor, &key, &data, 0 );
505 				if ( rc != 0 ) {
506 					err = "c_put lo";
507 					goto fail;
508 				}
509 				id = hi;
510 				rc = mdb_cursor_put( cursor, &key, &data, 0 );
511 				if ( rc != 0 ) {
512 					err = "c_put hi";
513 					goto fail;
514 				}
515 			} else {
516 			/* There's room, just store it */
517 				if (id == mdb->mi_nextid)
518 					flag |= MDB_APPENDDUP;
519 				goto put1;
520 			}
521 		} else {
522 			/* It's a range, see if we need to rewrite
523 			 * the boundaries
524 			 */
525 			lo = i[1];
526 			hi = i[2];
527 			if ( id < lo || id > hi ) {
528 				/* position on lo */
529 				rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
530 				if ( rc != 0 ) {
531 					err = "c_get lo";
532 					goto fail;
533 				}
534 				if ( id > hi ) {
535 					/* position on hi */
536 					rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
537 					if ( rc != 0 ) {
538 						err = "c_get hi";
539 						goto fail;
540 					}
541 				}
542 				data.mv_size = sizeof(ID);
543 				data.mv_data = &id;
544 				/* Replace the current lo/hi */
545 				rc = mdb_cursor_put( cursor, &key, &data, MDB_CURRENT );
546 				if ( rc != 0 ) {
547 					err = "c_put lo/hi";
548 					goto fail;
549 				}
550 			}
551 		}
552 	} else if ( rc == MDB_NOTFOUND ) {
553 		flag &= ~MDB_APPENDDUP;
554 put1:	data.mv_data = &id;
555 		data.mv_size = sizeof(ID);
556 		rc = mdb_cursor_put( cursor, &key, &data, flag );
557 		/* Don't worry if it's already there */
558 		if ( rc == MDB_KEYEXIST )
559 			rc = 0;
560 		if ( rc ) {
561 			err = "c_put id";
562 			goto fail;
563 		}
564 	} else {
565 		/* initial c_get failed, nothing was done */
566 fail:
567 		Debug( LDAP_DEBUG_ANY, "=> mdb_idl_insert_keys: "
568 			"%s failed: %s (%d)\n", err, mdb_strerror(rc), rc );
569 		break;
570 	}
571 	}
572 	return rc;
573 }
574 
575 int
mdb_idl_delete_keys(BackendDB * be,MDB_cursor * cursor,struct berval * keys,ID id)576 mdb_idl_delete_keys(
577 	BackendDB	*be,
578 	MDB_cursor	*cursor,
579 	struct berval *keys,
580 	ID			id )
581 {
582 	int	rc = 0, k;
583 	MDB_val key, data;
584 	ID lo, hi, tmp, *i;
585 	char *err;
586 #ifndef	MISALIGNED_OK
587 	int kbuf[2];
588 #endif
589 
590 	{
591 		char buf[16];
592 		Debug( LDAP_DEBUG_ARGS,
593 			"mdb_idl_delete_keys: %lx %s\n",
594 			(long) id, mdb_show_key( buf, keys->bv_val, keys->bv_len ) );
595 	}
596 	assert( id != NOID );
597 
598 #ifndef MISALIGNED_OK
599 	if (keys[0].bv_len & ALIGNER)
600 		kbuf[1] = 0;
601 #endif
602 	for ( k=0; keys[k].bv_val; k++) {
603 	/* Fetch the first data item for this key, to see if it
604 	 * exists and if it's a range.
605 	 */
606 #ifndef MISALIGNED_OK
607 	if (keys[k].bv_len & ALIGNER) {
608 		key.mv_size = sizeof(kbuf);
609 		key.mv_data = kbuf;
610 		memcpy(key.mv_data, keys[k].bv_val, keys[k].bv_len);
611 	} else
612 #endif
613 	{
614 		key.mv_size = keys[k].bv_len;
615 		key.mv_data = keys[k].bv_val;
616 	}
617 	rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
618 	err = "c_get";
619 	if ( rc == 0 ) {
620 		memcpy( &tmp, data.mv_data, sizeof(ID) );
621 		i = data.mv_data;
622 		if ( tmp != 0 ) {
623 			/* Not a range, just delete it */
624 			data.mv_data = &id;
625 			rc = mdb_cursor_get( cursor, &key, &data, MDB_GET_BOTH );
626 			if ( rc != 0 ) {
627 				err = "c_get id";
628 				goto fail;
629 			}
630 			rc = mdb_cursor_del( cursor, 0 );
631 			if ( rc != 0 ) {
632 				err = "c_del id";
633 				goto fail;
634 			}
635 		} else {
636 			/* It's a range, see if we need to rewrite
637 			 * the boundaries
638 			 */
639 			lo = i[1];
640 			hi = i[2];
641 			if ( id == lo || id == hi ) {
642 				ID lo2 = lo, hi2 = hi;
643 				if ( id == lo ) {
644 					lo2++;
645 				} else if ( id == hi ) {
646 					hi2--;
647 				}
648 				if ( lo2 >= hi2 ) {
649 				/* The range has collapsed... */
650 					/* delete the range marker */
651 					rc = mdb_cursor_del( cursor, 0 );
652 					if ( rc != 0 ) {
653 						err = "c_del dup1";
654 						goto fail;
655 					}
656 					/* skip past deleted marker */
657 					rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
658 					if ( rc != 0 ) {
659 						err = "c_get dup1";
660 						goto fail;
661 					}
662 					/* delete the requested id */
663 					if ( id == hi ) {
664 						/* skip lo */
665 						rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
666 						if ( rc != 0 ) {
667 							err = "c_get dup2";
668 							goto fail;
669 						}
670 					}
671 					rc = mdb_cursor_del( cursor, 0 );
672 					if ( rc != 0 ) {
673 						err = "c_del dup2";
674 						goto fail;
675 					}
676 				} else {
677 					/* position on lo */
678 					rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
679 					if ( id == lo )
680 						data.mv_data = &lo2;
681 					else {
682 						/* position on hi */
683 						rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
684 						data.mv_data = &hi2;
685 					}
686 					/* Replace the current lo/hi */
687 					data.mv_size = sizeof(ID);
688 					rc = mdb_cursor_put( cursor, &key, &data, MDB_CURRENT );
689 					if ( rc != 0 ) {
690 						err = "c_put lo/hi";
691 						goto fail;
692 					}
693 				}
694 			}
695 		}
696 	} else {
697 		/* initial c_get failed, nothing was done */
698 fail:
699 		if ( rc == MDB_NOTFOUND )
700 			rc = 0;
701 		if ( rc ) {
702 			Debug( LDAP_DEBUG_ANY, "=> mdb_idl_delete_key: "
703 				"%s failed: %s (%d)\n", err, mdb_strerror(rc), rc );
704 			break;
705 		}
706 	}
707 	}
708 	return rc;
709 }
710 
711 
712 /*
713  * idl_intersection - return a = a intersection b
714  */
715 int
mdb_idl_intersection(ID * a,ID * b)716 mdb_idl_intersection(
717 	ID *a,
718 	ID *b )
719 {
720 	ID ida, idb;
721 	ID idmax, idmin;
722 	ID cursora = 0, cursorb = 0, cursorc;
723 	int swap = 0;
724 
725 	if ( MDB_IDL_IS_ZERO( a ) || MDB_IDL_IS_ZERO( b ) ) {
726 		a[0] = 0;
727 		return 0;
728 	}
729 
730 	idmin = IDL_MAX( MDB_IDL_FIRST(a), MDB_IDL_FIRST(b) );
731 	idmax = IDL_MIN( MDB_IDL_LAST(a), MDB_IDL_LAST(b) );
732 	if ( idmin > idmax ) {
733 		a[0] = 0;
734 		return 0;
735 	} else if ( idmin == idmax ) {
736 		a[0] = 1;
737 		a[1] = idmin;
738 		return 0;
739 	}
740 
741 	if ( MDB_IDL_IS_RANGE( a ) ) {
742 		if ( MDB_IDL_IS_RANGE(b) ) {
743 		/* If both are ranges, just shrink the boundaries */
744 			a[1] = idmin;
745 			a[2] = idmax;
746 			return 0;
747 		} else {
748 		/* Else swap so that b is the range, a is a list */
749 			ID *tmp = a;
750 			a = b;
751 			b = tmp;
752 			swap = 1;
753 		}
754 	}
755 
756 	/* If a range completely covers the list, the result is
757 	 * just the list.
758 	 */
759 	if ( MDB_IDL_IS_RANGE( b )
760 		&& MDB_IDL_RANGE_FIRST( b ) <= MDB_IDL_FIRST( a )
761 		&& MDB_IDL_RANGE_LAST( b ) >= MDB_IDL_LLAST( a ) ) {
762 		goto done;
763 	}
764 
765 	/* Fine, do the intersection one element at a time.
766 	 * First advance to idmin in both IDLs.
767 	 */
768 	cursora = cursorb = idmin;
769 	ida = mdb_idl_first( a, &cursora );
770 	idb = mdb_idl_first( b, &cursorb );
771 	cursorc = 0;
772 
773 	while( ida <= idmax || idb <= idmax ) {
774 		if( ida == idb ) {
775 			a[++cursorc] = ida;
776 			ida = mdb_idl_next( a, &cursora );
777 			idb = mdb_idl_next( b, &cursorb );
778 		} else if ( ida < idb ) {
779 			ida = mdb_idl_next( a, &cursora );
780 		} else {
781 			idb = mdb_idl_next( b, &cursorb );
782 		}
783 	}
784 	a[0] = cursorc;
785 done:
786 	if (swap)
787 		MDB_IDL_CPY( b, a );
788 
789 	return 0;
790 }
791 
792 
793 /*
794  * idl_union - return a = a union b
795  */
796 int
mdb_idl_union(ID * a,ID * b)797 mdb_idl_union(
798 	ID	*a,
799 	ID	*b )
800 {
801 	ID ida, idb;
802 	ID cursora = 0, cursorb = 0, cursorc;
803 
804 	if ( MDB_IDL_IS_ZERO( b ) ) {
805 		return 0;
806 	}
807 
808 	if ( MDB_IDL_IS_ZERO( a ) ) {
809 		MDB_IDL_CPY( a, b );
810 		return 0;
811 	}
812 
813 	if ( MDB_IDL_IS_RANGE( a ) || MDB_IDL_IS_RANGE(b) ) {
814 over:		ida = IDL_MIN( MDB_IDL_FIRST(a), MDB_IDL_FIRST(b) );
815 		idb = IDL_MAX( MDB_IDL_LAST(a), MDB_IDL_LAST(b) );
816 		a[0] = NOID;
817 		a[1] = ida;
818 		a[2] = idb;
819 		return 0;
820 	}
821 
822 	ida = mdb_idl_first( a, &cursora );
823 	idb = mdb_idl_first( b, &cursorb );
824 
825 	cursorc = b[0];
826 
827 	/* The distinct elements of a are cat'd to b */
828 	while( ida != NOID || idb != NOID ) {
829 		if ( ida < idb ) {
830 			if( ++cursorc > MDB_idl_um_max ) {
831 				goto over;
832 			}
833 			b[cursorc] = ida;
834 			ida = mdb_idl_next( a, &cursora );
835 
836 		} else {
837 			if ( ida == idb )
838 				ida = mdb_idl_next( a, &cursora );
839 			idb = mdb_idl_next( b, &cursorb );
840 		}
841 	}
842 
843 	/* b is copied back to a in sorted order */
844 	a[0] = cursorc;
845 	cursora = 1;
846 	cursorb = 1;
847 	cursorc = b[0]+1;
848 	while (cursorb <= b[0] || cursorc <= a[0]) {
849 		if (cursorc > a[0])
850 			idb = NOID;
851 		else
852 			idb = b[cursorc];
853 		if (cursorb <= b[0] && b[cursorb] < idb)
854 			a[cursora++] = b[cursorb++];
855 		else {
856 			a[cursora++] = idb;
857 			cursorc++;
858 		}
859 	}
860 
861 	return 0;
862 }
863 
864 
865 #if 0
866 /*
867  * mdb_idl_notin - return a intersection ~b (or a minus b)
868  */
869 int
870 mdb_idl_notin(
871 	ID	*a,
872 	ID	*b,
873 	ID *ids )
874 {
875 	ID ida, idb;
876 	ID cursora = 0, cursorb = 0;
877 
878 	if( MDB_IDL_IS_ZERO( a ) ||
879 		MDB_IDL_IS_ZERO( b ) ||
880 		MDB_IDL_IS_RANGE( b ) )
881 	{
882 		MDB_IDL_CPY( ids, a );
883 		return 0;
884 	}
885 
886 	if( MDB_IDL_IS_RANGE( a ) ) {
887 		MDB_IDL_CPY( ids, a );
888 		return 0;
889 	}
890 
891 	ida = mdb_idl_first( a, &cursora ),
892 	idb = mdb_idl_first( b, &cursorb );
893 
894 	ids[0] = 0;
895 
896 	while( ida != NOID ) {
897 		if ( idb == NOID ) {
898 			/* we could shortcut this */
899 			ids[++ids[0]] = ida;
900 			ida = mdb_idl_next( a, &cursora );
901 
902 		} else if ( ida < idb ) {
903 			ids[++ids[0]] = ida;
904 			ida = mdb_idl_next( a, &cursora );
905 
906 		} else if ( ida > idb ) {
907 			idb = mdb_idl_next( b, &cursorb );
908 
909 		} else {
910 			ida = mdb_idl_next( a, &cursora );
911 			idb = mdb_idl_next( b, &cursorb );
912 		}
913 	}
914 
915 	return 0;
916 }
917 #endif
918 
mdb_idl_first(ID * ids,ID * cursor)919 ID mdb_idl_first( ID *ids, ID *cursor )
920 {
921 	ID pos;
922 
923 	if ( ids[0] == 0 ) {
924 		*cursor = NOID;
925 		return NOID;
926 	}
927 
928 	if ( MDB_IDL_IS_RANGE( ids ) ) {
929 		if( *cursor < ids[1] ) {
930 			*cursor = ids[1];
931 		}
932 		return *cursor;
933 	}
934 
935 	if ( *cursor == 0 )
936 		pos = 1;
937 	else
938 		pos = mdb_idl_search( ids, *cursor );
939 
940 	if( pos > ids[0] ) {
941 		return NOID;
942 	}
943 
944 	*cursor = pos;
945 	return ids[pos];
946 }
947 
mdb_idl_next(ID * ids,ID * cursor)948 ID mdb_idl_next( ID *ids, ID *cursor )
949 {
950 	if ( MDB_IDL_IS_RANGE( ids ) ) {
951 		if( ids[2] < ++(*cursor) ) {
952 			return NOID;
953 		}
954 		return *cursor;
955 	}
956 
957 	if ( ++(*cursor) <= ids[0] ) {
958 		return ids[*cursor];
959 	}
960 
961 	return NOID;
962 }
963 
964 /* Add one ID to an unsorted list. We ensure that the first element is the
965  * minimum and the last element is the maximum, for fast range compaction.
966  *   this means IDLs up to length 3 are always sorted...
967  */
mdb_idl_append_one(ID * ids,ID id)968 int mdb_idl_append_one( ID *ids, ID id )
969 {
970 	if (MDB_IDL_IS_RANGE( ids )) {
971 		/* if already in range, treat as a dup */
972 		if (id >= MDB_IDL_RANGE_FIRST(ids) && id <= MDB_IDL_RANGE_LAST(ids))
973 			return -1;
974 		if (id < MDB_IDL_RANGE_FIRST(ids))
975 			ids[1] = id;
976 		else if (id > MDB_IDL_RANGE_LAST(ids))
977 			ids[2] = id;
978 		return 0;
979 	}
980 	if ( ids[0] ) {
981 		ID tmp;
982 
983 		if (id < ids[1]) {
984 			tmp = ids[1];
985 			ids[1] = id;
986 			id = tmp;
987 		}
988 		if ( ids[0] > 1 && id < ids[ids[0]] ) {
989 			tmp = ids[ids[0]];
990 			ids[ids[0]] = id;
991 			id = tmp;
992 		}
993 	}
994 	ids[0]++;
995 	if ( ids[0] >= MDB_idl_um_max ) {
996 		ids[0] = NOID;
997 		ids[2] = id;
998 	} else {
999 		ids[ids[0]] = id;
1000 	}
1001 	return 0;
1002 }
1003 
1004 /* Append sorted list b to sorted list a. The result is unsorted but
1005  * a[1] is the min of the result and a[a[0]] is the max.
1006  */
mdb_idl_append(ID * a,ID * b)1007 int mdb_idl_append( ID *a, ID *b )
1008 {
1009 	ID ida, idb, tmp, swap = 0;
1010 
1011 	if ( MDB_IDL_IS_ZERO( b ) ) {
1012 		return 0;
1013 	}
1014 
1015 	if ( MDB_IDL_IS_ZERO( a ) ) {
1016 		MDB_IDL_CPY( a, b );
1017 		return 0;
1018 	}
1019 
1020 	ida = MDB_IDL_LAST( a );
1021 	idb = MDB_IDL_LAST( b );
1022 	if ( MDB_IDL_IS_RANGE( a ) || MDB_IDL_IS_RANGE(b) ||
1023 		a[0] + b[0] >= MDB_idl_um_max ) {
1024 		a[2] = IDL_MAX( ida, idb );
1025 		a[1] = IDL_MIN( a[1], b[1] );
1026 		a[0] = NOID;
1027 		return 0;
1028 	}
1029 
1030 	if ( b[0] > 1 && ida > idb ) {
1031 		swap = idb;
1032 		a[a[0]] = idb;
1033 		b[b[0]] = ida;
1034 	}
1035 
1036 	if ( b[1] < a[1] ) {
1037 		tmp = a[1];
1038 		a[1] = b[1];
1039 	} else {
1040 		tmp = b[1];
1041 	}
1042 	a[0]++;
1043 	a[a[0]] = tmp;
1044 
1045 	if ( b[0] > 1 ) {
1046 		int i = b[0] - 1;
1047 		AC_MEMCPY(a+a[0]+1, b+2, i * sizeof(ID));
1048 		a[0] += i;
1049 	}
1050 	if ( swap ) {
1051 		b[b[0]] = swap;
1052 	}
1053 	return 0;
1054 }
1055 
1056 #if 1
1057 
1058 /* Quicksort + Insertion sort for small arrays */
1059 
1060 #define SMALL	8
1061 #define	SWAP(a,b)	itmp=(a);(a)=(b);(b)=itmp
1062 
1063 void
mdb_idl_sort(ID * ids,ID * tmp)1064 mdb_idl_sort( ID *ids, ID *tmp )
1065 {
1066 	int *istack = (int *)tmp; /* Private stack, not used by caller */
1067 	int i,j,k,l,ir,jstack;
1068 	ID a, itmp;
1069 
1070 	if ( MDB_IDL_IS_RANGE( ids ))
1071 		return;
1072 
1073 	ir = ids[0];
1074 	l = 1;
1075 	jstack = 0;
1076 	for(;;) {
1077 		if (ir - l < SMALL) {	/* Insertion sort */
1078 			for (j=l+1;j<=ir;j++) {
1079 				a = ids[j];
1080 				for (i=j-1;i>=1;i--) {
1081 					if (ids[i] <= a) break;
1082 					ids[i+1] = ids[i];
1083 				}
1084 				ids[i+1] = a;
1085 			}
1086 			if (jstack == 0) break;
1087 			ir = istack[jstack--];
1088 			l = istack[jstack--];
1089 		} else {
1090 			k = (l + ir) >> 1;	/* Choose median of left, center, right */
1091 			SWAP(ids[k], ids[l+1]);
1092 			if (ids[l] > ids[ir]) {
1093 				SWAP(ids[l], ids[ir]);
1094 			}
1095 			if (ids[l+1] > ids[ir]) {
1096 				SWAP(ids[l+1], ids[ir]);
1097 			}
1098 			if (ids[l] > ids[l+1]) {
1099 				SWAP(ids[l], ids[l+1]);
1100 			}
1101 			i = l+1;
1102 			j = ir;
1103 			a = ids[l+1];
1104 			for(;;) {
1105 				do i++; while(ids[i] < a);
1106 				do j--; while(ids[j] > a);
1107 				if (j < i) break;
1108 				SWAP(ids[i],ids[j]);
1109 			}
1110 			ids[l+1] = ids[j];
1111 			ids[j] = a;
1112 			jstack += 2;
1113 			if (ir-i+1 >= j-l) {
1114 				istack[jstack] = ir;
1115 				istack[jstack-1] = i;
1116 				ir = j-1;
1117 			} else {
1118 				istack[jstack] = j-1;
1119 				istack[jstack-1] = l;
1120 				l = i;
1121 			}
1122 		}
1123 	}
1124 }
1125 
1126 #else
1127 
1128 /* 8 bit Radix sort + insertion sort
1129  *
1130  * based on code from http://www.cubic.org/docs/radix.htm
1131  * with improvements by ebackes@symas.com and hyc@symas.com
1132  *
1133  * This code is O(n) but has a relatively high constant factor. For lists
1134  * up to ~50 Quicksort is slightly faster; up to ~100 they are even.
1135  * Much faster than quicksort for lists longer than ~100. Insertion
1136  * sort is actually superior for lists <50.
1137  */
1138 
1139 #define BUCKETS	(1<<8)
1140 #define SMALL	50
1141 
1142 void
mdb_idl_sort(ID * ids,ID * tmp)1143 mdb_idl_sort( ID *ids, ID *tmp )
1144 {
1145 	int count, soft_limit, phase = 0, size = ids[0];
1146 	ID *idls[2];
1147 	unsigned char *maxv = (unsigned char *)&ids[size];
1148 
1149  	if ( MDB_IDL_IS_RANGE( ids ))
1150  		return;
1151 
1152 	/* Use insertion sort for small lists */
1153 	if ( size <= SMALL ) {
1154 		int i,j;
1155 		ID a;
1156 
1157 		for (j=1;j<=size;j++) {
1158 			a = ids[j];
1159 			for (i=j-1;i>=1;i--) {
1160 				if (ids[i] <= a) break;
1161 				ids[i+1] = ids[i];
1162 			}
1163 			ids[i+1] = a;
1164 		}
1165 		return;
1166 	}
1167 
1168 	tmp[0] = size;
1169 	idls[0] = ids;
1170 	idls[1] = tmp;
1171 
1172 #if BYTE_ORDER == BIG_ENDIAN
1173     for (soft_limit = 0; !maxv[soft_limit]; soft_limit++);
1174 #else
1175     for (soft_limit = sizeof(ID)-1; !maxv[soft_limit]; soft_limit--);
1176 #endif
1177 
1178 	for (
1179 #if BYTE_ORDER == BIG_ENDIAN
1180 	count = sizeof(ID)-1; count >= soft_limit; --count
1181 #else
1182 	count = 0; count <= soft_limit; ++count
1183 #endif
1184 	) {
1185 		unsigned int num[BUCKETS], * np, n, sum;
1186 		int i;
1187         ID *sp, *source, *dest;
1188         unsigned char *bp, *source_start;
1189 
1190 		source = idls[phase]+1;
1191 		dest = idls[phase^1]+1;
1192 		source_start =  ((unsigned char *) source) + count;
1193 
1194         np = num;
1195         for ( i = BUCKETS; i > 0; --i ) *np++ = 0;
1196 
1197 		/* count occurrences of every byte value */
1198 		bp = source_start;
1199         for ( i = size; i > 0; --i, bp += sizeof(ID) )
1200 				num[*bp]++;
1201 
1202 		/* transform count into index by summing elements and storing
1203 		 * into same array
1204 		 */
1205         sum = 0;
1206         np = num;
1207         for ( i = BUCKETS; i > 0; --i ) {
1208                 n = *np;
1209                 *np++ = sum;
1210                 sum += n;
1211         }
1212 
1213 		/* fill dest with the right values in the right place */
1214 		bp = source_start;
1215         sp = source;
1216         for ( i = size; i > 0; --i, bp += sizeof(ID) ) {
1217                 np = num + *bp;
1218                 dest[*np] = *sp++;
1219                 ++(*np);
1220         }
1221 		phase ^= 1;
1222 	}
1223 
1224 	/* copy back from temp if needed */
1225 	if ( phase ) {
1226 		ids++; tmp++;
1227 		for ( count = 0; count < size; ++count )
1228 			*ids++ = *tmp++;
1229 	}
1230 }
1231 #endif	/* Quick vs Radix */
1232 
mdb_id2l_search(ID2L ids,ID id)1233 unsigned mdb_id2l_search( ID2L ids, ID id )
1234 {
1235 	/*
1236 	 * binary search of id in ids
1237 	 * if found, returns position of id
1238 	 * if not found, returns first position greater than id
1239 	 */
1240 	unsigned base = 0;
1241 	unsigned cursor = 1;
1242 	int val = 0;
1243 	unsigned n = ids[0].mid;
1244 
1245 	while( 0 < n ) {
1246 		unsigned pivot = n >> 1;
1247 		cursor = base + pivot + 1;
1248 		val = IDL_CMP( id, ids[cursor].mid );
1249 
1250 		if( val < 0 ) {
1251 			n = pivot;
1252 
1253 		} else if ( val > 0 ) {
1254 			base = cursor;
1255 			n -= pivot + 1;
1256 
1257 		} else {
1258 			return cursor;
1259 		}
1260 	}
1261 
1262 	if( val > 0 ) {
1263 		++cursor;
1264 	}
1265 	return cursor;
1266 }
1267 
mdb_id2l_insert(ID2L ids,ID2 * id)1268 int mdb_id2l_insert( ID2L ids, ID2 *id )
1269 {
1270 	unsigned x, i;
1271 
1272 	x = mdb_id2l_search( ids, id->mid );
1273 	assert( x > 0 );
1274 
1275 	if( x < 1 ) {
1276 		/* internal error */
1277 		return -2;
1278 	}
1279 
1280 	if ( x <= ids[0].mid && ids[x].mid == id->mid ) {
1281 		/* duplicate */
1282 		return -1;
1283 	}
1284 
1285 	if ( ids[0].mid >= MDB_idl_um_max ) {
1286 		/* too big */
1287 		return -2;
1288 
1289 	} else {
1290 		/* insert id */
1291 		ids[0].mid++;
1292 		for (i=ids[0].mid; i>x; i--)
1293 			ids[i] = ids[i-1];
1294 		ids[x] = *id;
1295 	}
1296 
1297 	return 0;
1298 }
1299