midl.c 7.91 KB
Newer Older
1
2
/**	@file midl.c
 *	@brief ldap bdb back-end ID List functions */
Howard Chu's avatar
Howard Chu committed
3
4
5
/* $OpenLDAP$ */
/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
 *
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
6
7
 * Copyright 2000-2018 The OpenLDAP Foundation.
 * Portions Copyright 2001-2018 Howard Chu, Symas Corp.
Howard Chu's avatar
Howard Chu committed
8
9
10
11
12
13
14
15
16
17
 * 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>.
 */
Howard Chu's avatar
Howard Chu committed
18

19
#include <limits.h>
Howard Chu's avatar
Howard Chu committed
20
#include <string.h>
Howard Chu's avatar
Howard Chu committed
21
#include <stdlib.h>
22
#include <errno.h>
Howard Chu's avatar
Howard Chu committed
23
#include <sys/types.h>
Howard Chu's avatar
Howard Chu committed
24
#include "midl.h"
Howard Chu's avatar
Howard Chu committed
25

Howard Chu's avatar
Howard Chu committed
26
/** @defgroup internal	LMDB Internals
27
28
29
30
31
32
 *	@{
 */
/** @defgroup idls	ID List Management
 *	@{
 */
#define CMP(x,y)	 ( (x) < (y) ? -1 : (x) > (y) )
Howard Chu's avatar
Howard Chu committed
33

Howard Chu's avatar
Howard Chu committed
34
unsigned mdb_midl_search( MDB_IDL ids, MDB_ID id )
Howard Chu's avatar
Howard Chu committed
35
36
37
38
39
40
41
{
	/*
	 * binary search of id in ids
	 * if found, returns position of id
	 * if not found, returns first position greater than id
	 */
	unsigned base = 0;
Hallvard Furuseth's avatar
Hallvard Furuseth committed
42
	unsigned cursor = 1;
Howard Chu's avatar
Howard Chu committed
43
44
45
46
	int val = 0;
	unsigned n = ids[0];

	while( 0 < n ) {
Hallvard Furuseth's avatar
Hallvard Furuseth committed
47
48
49
		unsigned pivot = n >> 1;
		cursor = base + pivot + 1;
		val = CMP( ids[cursor], id );
Howard Chu's avatar
Howard Chu committed
50
51
52
53
54

		if( val < 0 ) {
			n = pivot;

		} else if ( val > 0 ) {
Hallvard Furuseth's avatar
Hallvard Furuseth committed
55
			base = cursor;
Howard Chu's avatar
Howard Chu committed
56
57
58
			n -= pivot + 1;

		} else {
Hallvard Furuseth's avatar
Hallvard Furuseth committed
59
			return cursor;
Howard Chu's avatar
Howard Chu committed
60
61
		}
	}
62

Howard Chu's avatar
Howard Chu committed
63
	if( val > 0 ) {
Hallvard Furuseth's avatar
Hallvard Furuseth committed
64
		++cursor;
Howard Chu's avatar
Howard Chu committed
65
	}
Hallvard Furuseth's avatar
Hallvard Furuseth committed
66
	return cursor;
Howard Chu's avatar
Howard Chu committed
67
68
}

Howard Chu's avatar
Howard Chu committed
69
#if 0	/* superseded by append/sort */
70
int mdb_midl_insert( MDB_IDL ids, MDB_ID id )
Howard Chu's avatar
Howard Chu committed
71
{
Howard Chu's avatar
Howard Chu committed
72
	unsigned x, i;
Howard Chu's avatar
Howard Chu committed
73

Howard Chu's avatar
Howard Chu committed
74
	x = mdb_midl_search( ids, id );
Howard Chu's avatar
Howard Chu committed
75
76
77
78
79
80
81
82
83
	assert( x > 0 );

	if( x < 1 ) {
		/* internal error */
		return -2;
	}

	if ( x <= ids[0] && ids[x] == id ) {
		/* duplicate */
84
		assert(0);
Howard Chu's avatar
Howard Chu committed
85
86
87
88
		return -1;
	}

	if ( ++ids[0] >= MDB_IDL_DB_MAX ) {
89
90
91
		/* no room */
		--ids[0];
		return -2;
92

Howard Chu's avatar
Howard Chu committed
93
94
	} else {
		/* insert id */
Howard Chu's avatar
Howard Chu committed
95
96
		for (i=ids[0]; i>x; i--)
			ids[i] = ids[i-1];
Howard Chu's avatar
Howard Chu committed
97
98
99
100
101
		ids[x] = id;
	}

	return 0;
}
102
103
#endif

104
MDB_IDL mdb_midl_alloc(int num)
105
{
106
	MDB_IDL ids = malloc((num+2) * sizeof(MDB_ID));
107
	if (ids) {
108
		*ids++ = num;
109
110
		*ids = 0;
	}
Howard Chu's avatar
Howard Chu committed
111
112
113
	return ids;
}

114
void mdb_midl_free(MDB_IDL ids)
Howard Chu's avatar
Howard Chu committed
115
{
116
117
	if (ids)
		free(ids-1);
Howard Chu's avatar
Howard Chu committed
118
119
}

120
void mdb_midl_shrink( MDB_IDL *idp )
Howard Chu's avatar
Howard Chu committed
121
{
122
	MDB_IDL ids = *idp;
Hallvard Furuseth's avatar
Hallvard Furuseth committed
123
	if (*(--ids) > MDB_IDL_UM_MAX &&
124
		(ids = realloc(ids, (MDB_IDL_UM_MAX+2) * sizeof(MDB_ID))))
Hallvard Furuseth's avatar
Hallvard Furuseth committed
125
	{
Howard Chu's avatar
Howard Chu committed
126
127
128
129
130
		*ids++ = MDB_IDL_UM_MAX;
		*idp = ids;
	}
}

Hallvard Furuseth's avatar
Hallvard Furuseth committed
131
static int mdb_midl_grow( MDB_IDL *idp, int num )
132
133
134
135
136
137
138
139
140
141
142
{
	MDB_IDL idn = *idp-1;
	/* grow it */
	idn = realloc(idn, (*idn + num + 2) * sizeof(MDB_ID));
	if (!idn)
		return ENOMEM;
	*idn++ += num;
	*idp = idn;
	return 0;
}

Hallvard Furuseth's avatar
Hallvard Furuseth committed
143
144
145
146
147
148
149
150
int mdb_midl_need( MDB_IDL *idp, unsigned num )
{
	MDB_IDL ids = *idp;
	num += ids[0];
	if (num > ids[-1]) {
		num = (num + num/4 + (256 + 2)) & -256;
		if (!(ids = realloc(ids-1, num * sizeof(MDB_ID))))
			return ENOMEM;
Hallvard Furuseth's avatar
Hallvard Furuseth committed
151
		*ids++ = num - 2;
Hallvard Furuseth's avatar
Hallvard Furuseth committed
152
153
154
155
156
		*idp = ids;
	}
	return 0;
}

157
int mdb_midl_append( MDB_IDL *idp, MDB_ID id )
Howard Chu's avatar
Howard Chu committed
158
{
159
	MDB_IDL ids = *idp;
160
	/* Too big? */
Howard Chu's avatar
Howard Chu committed
161
	if (ids[0] >= ids[-1]) {
162
163
164
		if (mdb_midl_grow(idp, MDB_IDL_UM_MAX))
			return ENOMEM;
		ids = *idp;
Howard Chu's avatar
Howard Chu committed
165
	}
166
167
168
169
170
	ids[0]++;
	ids[ids[0]] = id;
	return 0;
}

171
int mdb_midl_append_list( MDB_IDL *idp, MDB_IDL app )
172
{
173
	MDB_IDL ids = *idp;
174
175
	/* Too big? */
	if (ids[0] + app[0] >= ids[-1]) {
176
177
178
		if (mdb_midl_grow(idp, app[0]))
			return ENOMEM;
		ids = *idp;
179
	}
180
	memcpy(&ids[ids[0]+1], &app[1], app[0] * sizeof(MDB_ID));
181
182
183
184
	ids[0] += app[0];
	return 0;
}

Hallvard Furuseth's avatar
Hallvard Furuseth committed
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
int mdb_midl_append_range( MDB_IDL *idp, MDB_ID id, unsigned n )
{
	MDB_ID *ids = *idp, len = ids[0];
	/* Too big? */
	if (len + n > ids[-1]) {
		if (mdb_midl_grow(idp, n | MDB_IDL_UM_MAX))
			return ENOMEM;
		ids = *idp;
	}
	ids[0] = len + n;
	ids += len;
	while (n)
		ids[n--] = id++;
	return 0;
}

201
202
203
204
205
206
207
208
209
210
211
212
213
214
void mdb_midl_xmerge( MDB_IDL idl, MDB_IDL merge )
{
	MDB_ID old_id, merge_id, i = merge[0], j = idl[0], k = i+j, total = k;
	idl[0] = (MDB_ID)-1;		/* delimiter for idl scan below */
	old_id = idl[j];
	while (i) {
		merge_id = merge[i--];
		for (; old_id < merge_id; old_id = idl[--j])
			idl[k--] = old_id;
		idl[k--] = merge_id;
	}
	idl[0] = total;
}

215
216
217
/* Quicksort + Insertion sort for small arrays */

#define SMALL	8
218
#define	MIDL_SWAP(a,b)	{ itmp=(a); (a)=(b); (b)=itmp; }
219
220

void
221
mdb_midl_sort( MDB_IDL ids )
222
{
223
224
	/* Max possible depth of int-indexed tree * 2 items/level */
	int istack[sizeof(int)*CHAR_BIT * 2];
225
	int i,j,k,l,ir,jstack;
226
	MDB_ID a, itmp;
227

Howard Chu's avatar
Howard Chu committed
228
	ir = (int)ids[0];
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
	l = 1;
	jstack = 0;
	for(;;) {
		if (ir - l < SMALL) {	/* Insertion sort */
			for (j=l+1;j<=ir;j++) {
				a = ids[j];
				for (i=j-1;i>=1;i--) {
					if (ids[i] >= a) break;
					ids[i+1] = ids[i];
				}
				ids[i+1] = a;
			}
			if (jstack == 0) break;
			ir = istack[jstack--];
			l = istack[jstack--];
		} else {
			k = (l + ir) >> 1;	/* Choose median of left, center, right */
246
			MIDL_SWAP(ids[k], ids[l+1]);
247
			if (ids[l] < ids[ir]) {
248
				MIDL_SWAP(ids[l], ids[ir]);
249
250
			}
			if (ids[l+1] < ids[ir]) {
251
				MIDL_SWAP(ids[l+1], ids[ir]);
252
253
			}
			if (ids[l] < ids[l+1]) {
254
				MIDL_SWAP(ids[l], ids[l+1]);
255
256
257
258
259
260
261
262
			}
			i = l+1;
			j = ir;
			a = ids[l+1];
			for(;;) {
				do i++; while(ids[i] > a);
				do j--; while(ids[j] < a);
				if (j < i) break;
263
				MIDL_SWAP(ids[i],ids[j]);
264
265
266
267
			}
			ids[l+1] = ids[j];
			ids[j] = a;
			jstack += 2;
268
			if (ir-i+1 >= j-l) {
269
270
271
272
273
274
275
276
277
278
279
				istack[jstack] = ir;
				istack[jstack-1] = i;
				ir = j-1;
			} else {
				istack[jstack] = j-1;
				istack[jstack-1] = l;
				l = i;
			}
		}
	}
}
Howard Chu's avatar
Howard Chu committed
280

281
unsigned mdb_mid2l_search( MDB_ID2L ids, MDB_ID id )
Howard Chu's avatar
Howard Chu committed
282
283
284
285
286
287
288
{
	/*
	 * binary search of id in ids
	 * if found, returns position of id
	 * if not found, returns first position greater than id
	 */
	unsigned base = 0;
Hallvard Furuseth's avatar
Hallvard Furuseth committed
289
	unsigned cursor = 1;
Howard Chu's avatar
Howard Chu committed
290
	int val = 0;
Howard Chu's avatar
Howard Chu committed
291
	unsigned n = (unsigned)ids[0].mid;
Howard Chu's avatar
Howard Chu committed
292
293

	while( 0 < n ) {
Hallvard Furuseth's avatar
Hallvard Furuseth committed
294
295
296
		unsigned pivot = n >> 1;
		cursor = base + pivot + 1;
		val = CMP( id, ids[cursor].mid );
Howard Chu's avatar
Howard Chu committed
297
298
299
300
301

		if( val < 0 ) {
			n = pivot;

		} else if ( val > 0 ) {
Hallvard Furuseth's avatar
Hallvard Furuseth committed
302
			base = cursor;
Howard Chu's avatar
Howard Chu committed
303
304
305
			n -= pivot + 1;

		} else {
Hallvard Furuseth's avatar
Hallvard Furuseth committed
306
			return cursor;
Howard Chu's avatar
Howard Chu committed
307
308
309
310
		}
	}

	if( val > 0 ) {
Hallvard Furuseth's avatar
Hallvard Furuseth committed
311
		++cursor;
Howard Chu's avatar
Howard Chu committed
312
	}
Hallvard Furuseth's avatar
Hallvard Furuseth committed
313
	return cursor;
Howard Chu's avatar
Howard Chu committed
314
315
}

316
int mdb_mid2l_insert( MDB_ID2L ids, MDB_ID2 *id )
Howard Chu's avatar
Howard Chu committed
317
318
319
{
	unsigned x, i;

320
	x = mdb_mid2l_search( ids, id->mid );
Howard Chu's avatar
Howard Chu committed
321
322
323
324
325
326
327
328
329
330
331

	if( x < 1 ) {
		/* internal error */
		return -2;
	}

	if ( x <= ids[0].mid && ids[x].mid == id->mid ) {
		/* duplicate */
		return -1;
	}

Howard Chu's avatar
Howard Chu committed
332
	if ( ids[0].mid >= MDB_IDL_UM_MAX ) {
Howard Chu's avatar
Howard Chu committed
333
334
335
336
337
338
		/* too big */
		return -2;

	} else {
		/* insert id */
		ids[0].mid++;
Howard Chu's avatar
Howard Chu committed
339
		for (i=(unsigned)ids[0].mid; i>x; i--)
Howard Chu's avatar
Howard Chu committed
340
341
342
343
344
345
			ids[i] = ids[i-1];
		ids[x] = *id;
	}

	return 0;
}
346
347
348
349
350
351
352
353
354
355

int mdb_mid2l_append( MDB_ID2L ids, MDB_ID2 *id )
{
	/* Too big? */
	if (ids[0].mid >= MDB_IDL_UM_MAX) {
		return -2;
	}
	ids[0].mid++;
	ids[ids[0].mid] = *id;
	return 0;
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
}

MDB_ID2L mdb_mid2l_alloc(int num)
{
	MDB_ID2L ids = malloc((num+2) * sizeof(MDB_ID2));
	if (ids) {
		ids->mid = num;
		ids++;
		ids->mid = 0;
	}
	return ids;
}

void mdb_mid2l_free(MDB_ID2L ids)
{
	if (ids)
		free(ids-1);
}

int mdb_mid2l_need( MDB_ID2L *idp, unsigned num )
{
	MDB_ID2L ids = *idp;
	num += ids[0].mid;
	if (num > ids[-1].mid) {
		num = (num + num/4 + (256 + 2)) & -256;
		if (!(ids = realloc(ids-1, num * sizeof(MDB_ID2))))
			return ENOMEM;
		ids[0].mid = num - 2;
		*idp = ids+1;
	}
	return 0;
387
388
}

Howard Chu's avatar
Howard Chu committed
389
#if MDB_RPAGE_CACHE
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
unsigned mdb_mid3l_search( MDB_ID3L ids, MDB_ID id )
{
	/*
	 * binary search of id in ids
	 * if found, returns position of id
	 * if not found, returns first position greater than id
	 */
	unsigned base = 0;
	unsigned cursor = 1;
	int val = 0;
	unsigned n = (unsigned)ids[0].mid;

	while( 0 < n ) {
		unsigned pivot = n >> 1;
		cursor = base + pivot + 1;
		val = CMP( id, ids[cursor].mid );

		if( val < 0 ) {
			n = pivot;

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

		} else {
			return cursor;
		}
	}

	if( val > 0 ) {
		++cursor;
	}
	return cursor;
}

int mdb_mid3l_insert( MDB_ID3L ids, MDB_ID3 *id )
{
	unsigned x, i;

	x = mdb_mid3l_search( ids, id->mid );

	if( x < 1 ) {
		/* internal error */
		return -2;
	}

	if ( x <= ids[0].mid && ids[x].mid == id->mid ) {
		/* duplicate */
		return -1;
	}

	/* insert id */
	ids[0].mid++;
	for (i=(unsigned)ids[0].mid; i>x; i--)
		ids[i] = ids[i-1];
	ids[x] = *id;

	return 0;
}
Howard Chu's avatar
Howard Chu committed
449
#endif /* MDB_RPAGE_CACHE */
450

451
452
/** @} */
/** @} */