1/*	$NetBSD: midl.c,v 1.3 2021/08/14 16:14:57 christos Exp $	*/
2
3/**	@file midl.c
4 *	@brief ldap bdb back-end ID List functions */
5/* $OpenLDAP$ */
6/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
7 *
8 * Copyright 2000-2021 The OpenLDAP Foundation.
9 * Portions Copyright 2001-2021 Howard Chu, Symas Corp.
10 * All rights reserved.
11 *
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted only as authorized by the OpenLDAP
14 * Public License.
15 *
16 * A copy of this license is available in the file LICENSE in the
17 * top-level directory of the distribution or, alternatively, at
18 * <http://www.OpenLDAP.org/license.html>.
19 */
20
21#include <limits.h>
22#include <string.h>
23#include <stdlib.h>
24#include <errno.h>
25#include <sys/types.h>
26#include "midl.h"
27
28/** @defgroup internal	LMDB Internals
29 *	@{
30 */
31/** @defgroup idls	ID List Management
32 *	@{
33 */
34#define CMP(x,y)	 ( (x) < (y) ? -1 : (x) > (y) )
35
36unsigned mdb_midl_search( MDB_IDL ids, MDB_ID id )
37{
38	/*
39	 * binary search of id in ids
40	 * if found, returns position of id
41	 * if not found, returns first position greater than id
42	 */
43	unsigned base = 0;
44	unsigned cursor = 1;
45	int val = 0;
46	unsigned n = ids[0];
47
48	while( 0 < n ) {
49		unsigned pivot = n >> 1;
50		cursor = base + pivot + 1;
51		val = CMP( ids[cursor], id );
52
53		if( val < 0 ) {
54			n = pivot;
55
56		} else if ( val > 0 ) {
57			base = cursor;
58			n -= pivot + 1;
59
60		} else {
61			return cursor;
62		}
63	}
64
65	if( val > 0 ) {
66		++cursor;
67	}
68	return cursor;
69}
70
71#if 0	/* superseded by append/sort */
72int mdb_midl_insert( MDB_IDL ids, MDB_ID id )
73{
74	unsigned x, i;
75
76	x = mdb_midl_search( ids, id );
77	assert( x > 0 );
78
79	if( x < 1 ) {
80		/* internal error */
81		return -2;
82	}
83
84	if ( x <= ids[0] && ids[x] == id ) {
85		/* duplicate */
86		assert(0);
87		return -1;
88	}
89
90	if ( ++ids[0] >= MDB_IDL_DB_MAX ) {
91		/* no room */
92		--ids[0];
93		return -2;
94
95	} else {
96		/* insert id */
97		for (i=ids[0]; i>x; i--)
98			ids[i] = ids[i-1];
99		ids[x] = id;
100	}
101
102	return 0;
103}
104#endif
105
106MDB_IDL mdb_midl_alloc(int num)
107{
108	MDB_IDL ids = malloc((num+2) * sizeof(MDB_ID));
109	if (ids) {
110		*ids++ = num;
111		*ids = 0;
112	}
113	return ids;
114}
115
116void mdb_midl_free(MDB_IDL ids)
117{
118	if (ids)
119		free(ids-1);
120}
121
122void mdb_midl_shrink( MDB_IDL *idp )
123{
124	MDB_IDL ids = *idp;
125	if (*(--ids) > MDB_IDL_UM_MAX &&
126		(ids = realloc(ids, (MDB_IDL_UM_MAX+2) * sizeof(MDB_ID))))
127	{
128		*ids++ = MDB_IDL_UM_MAX;
129		*idp = ids;
130	}
131}
132
133static int mdb_midl_grow( MDB_IDL *idp, int num )
134{
135	MDB_IDL idn = *idp-1;
136	/* grow it */
137	idn = realloc(idn, (*idn + num + 2) * sizeof(MDB_ID));
138	if (!idn)
139		return ENOMEM;
140	*idn++ += num;
141	*idp = idn;
142	return 0;
143}
144
145int mdb_midl_need( MDB_IDL *idp, unsigned num )
146{
147	MDB_IDL ids = *idp;
148	num += ids[0];
149	if (num > ids[-1]) {
150		num = (num + num/4 + (256 + 2)) & -256;
151		if (!(ids = realloc(ids-1, num * sizeof(MDB_ID))))
152			return ENOMEM;
153		*ids++ = num - 2;
154		*idp = ids;
155	}
156	return 0;
157}
158
159int mdb_midl_append( MDB_IDL *idp, MDB_ID id )
160{
161	MDB_IDL ids = *idp;
162	/* Too big? */
163	if (ids[0] >= ids[-1]) {
164		if (mdb_midl_grow(idp, MDB_IDL_UM_MAX))
165			return ENOMEM;
166		ids = *idp;
167	}
168	ids[0]++;
169	ids[ids[0]] = id;
170	return 0;
171}
172
173int mdb_midl_append_list( MDB_IDL *idp, MDB_IDL app )
174{
175	MDB_IDL ids = *idp;
176	/* Too big? */
177	if (ids[0] + app[0] >= ids[-1]) {
178		if (mdb_midl_grow(idp, app[0]))
179			return ENOMEM;
180		ids = *idp;
181	}
182	memcpy(&ids[ids[0]+1], &app[1], app[0] * sizeof(MDB_ID));
183	ids[0] += app[0];
184	return 0;
185}
186
187int mdb_midl_append_range( MDB_IDL *idp, MDB_ID id, unsigned n )
188{
189	MDB_ID *ids = *idp, len = ids[0];
190	/* Too big? */
191	if (len + n > ids[-1]) {
192		if (mdb_midl_grow(idp, n | MDB_IDL_UM_MAX))
193			return ENOMEM;
194		ids = *idp;
195	}
196	ids[0] = len + n;
197	ids += len;
198	while (n)
199		ids[n--] = id++;
200	return 0;
201}
202
203void mdb_midl_xmerge( MDB_IDL idl, MDB_IDL merge )
204{
205	MDB_ID old_id, merge_id, i = merge[0], j = idl[0], k = i+j, total = k;
206	idl[0] = (MDB_ID)-1;		/* delimiter for idl scan below */
207	old_id = idl[j];
208	while (i) {
209		merge_id = merge[i--];
210		for (; old_id < merge_id; old_id = idl[--j])
211			idl[k--] = old_id;
212		idl[k--] = merge_id;
213	}
214	idl[0] = total;
215}
216
217/* Quicksort + Insertion sort for small arrays */
218
219#define SMALL	8
220#define	MIDL_SWAP(a,b)	{ itmp=(a); (a)=(b); (b)=itmp; }
221
222void
223mdb_midl_sort( MDB_IDL ids )
224{
225	/* Max possible depth of int-indexed tree * 2 items/level */
226	int istack[sizeof(int)*CHAR_BIT * 2];
227	int i,j,k,l,ir,jstack;
228	MDB_ID a, itmp;
229
230	ir = (int)ids[0];
231	l = 1;
232	jstack = 0;
233	for(;;) {
234		if (ir - l < SMALL) {	/* Insertion sort */
235			for (j=l+1;j<=ir;j++) {
236				a = ids[j];
237				for (i=j-1;i>=1;i--) {
238					if (ids[i] >= a) break;
239					ids[i+1] = ids[i];
240				}
241				ids[i+1] = a;
242			}
243			if (jstack == 0) break;
244			ir = istack[jstack--];
245			l = istack[jstack--];
246		} else {
247			k = (l + ir) >> 1;	/* Choose median of left, center, right */
248			MIDL_SWAP(ids[k], ids[l+1]);
249			if (ids[l] < ids[ir]) {
250				MIDL_SWAP(ids[l], ids[ir]);
251			}
252			if (ids[l+1] < ids[ir]) {
253				MIDL_SWAP(ids[l+1], ids[ir]);
254			}
255			if (ids[l] < ids[l+1]) {
256				MIDL_SWAP(ids[l], ids[l+1]);
257			}
258			i = l+1;
259			j = ir;
260			a = ids[l+1];
261			for(;;) {
262				do i++; while(ids[i] > a);
263				do j--; while(ids[j] < a);
264				if (j < i) break;
265				MIDL_SWAP(ids[i],ids[j]);
266			}
267			ids[l+1] = ids[j];
268			ids[j] = a;
269			jstack += 2;
270			if (ir-i+1 >= j-l) {
271				istack[jstack] = ir;
272				istack[jstack-1] = i;
273				ir = j-1;
274			} else {
275				istack[jstack] = j-1;
276				istack[jstack-1] = l;
277				l = i;
278			}
279		}
280	}
281}
282
283unsigned mdb_mid2l_search( MDB_ID2L ids, MDB_ID id )
284{
285	/*
286	 * binary search of id in ids
287	 * if found, returns position of id
288	 * if not found, returns first position greater than id
289	 */
290	unsigned base = 0;
291	unsigned cursor = 1;
292	int val = 0;
293	unsigned n = (unsigned)ids[0].mid;
294
295	while( 0 < n ) {
296		unsigned pivot = n >> 1;
297		cursor = base + pivot + 1;
298		val = CMP( id, ids[cursor].mid );
299
300		if( val < 0 ) {
301			n = pivot;
302
303		} else if ( val > 0 ) {
304			base = cursor;
305			n -= pivot + 1;
306
307		} else {
308			return cursor;
309		}
310	}
311
312	if( val > 0 ) {
313		++cursor;
314	}
315	return cursor;
316}
317
318int mdb_mid2l_insert( MDB_ID2L ids, MDB_ID2 *id )
319{
320	unsigned x, i;
321
322	x = mdb_mid2l_search( ids, id->mid );
323
324	if( x < 1 ) {
325		/* internal error */
326		return -2;
327	}
328
329	if ( x <= ids[0].mid && ids[x].mid == id->mid ) {
330		/* duplicate */
331		return -1;
332	}
333
334	if ( ids[0].mid >= MDB_IDL_UM_MAX ) {
335		/* too big */
336		return -2;
337
338	} else {
339		/* insert id */
340		ids[0].mid++;
341		for (i=(unsigned)ids[0].mid; i>x; i--)
342			ids[i] = ids[i-1];
343		ids[x] = *id;
344	}
345
346	return 0;
347}
348
349int mdb_mid2l_append( MDB_ID2L ids, MDB_ID2 *id )
350{
351	/* Too big? */
352	if (ids[0].mid >= MDB_IDL_UM_MAX) {
353		return -2;
354	}
355	ids[0].mid++;
356	ids[ids[0].mid] = *id;
357	return 0;
358}
359
360/** @} */
361/** @} */
362