1/** @file midl.c
2 * @brief ldap bdb back-end ID List functions */
3/* $OpenLDAP$ */
4/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
5 *
6 * Copyright 2000-2019 The OpenLDAP Foundation.
7 * Portions Copyright 2001-2018 Howard Chu, Symas Corp.
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 <limits.h>
20#include <string.h>
21#include <stdlib.h>
22#include <errno.h>
23#include <sys/types.h>
24#include "midl.h"
25
26/** @defgroup internal LMDB Internals
27 * @{
28 */
29/** @defgroup idls ID List Management
30 * @{
31 */
32#define CMP(x,y) ( (x) < (y) ? -1 : (x) > (y) )
33
34unsigned mdb_midl_search( MDB_IDL ids, MDB_ID id )
35{
36 /*
37 * binary search of id in ids
38 * if found, returns position of id
39 * if not found, returns first position greater than id
40 */
41 unsigned base = 0;
42 unsigned cursor = 1;
43 int val = 0;
44 unsigned n = ids[0];
45
46 while( 0 < n ) {
47 unsigned pivot = n >> 1;
48 cursor = base + pivot + 1;
49 val = CMP( ids[cursor], id );
50
51 if( val < 0 ) {
52 n = pivot;
53
54 } else if ( val > 0 ) {
55 base = cursor;
56 n -= pivot + 1;
57
58 } else {
59 return cursor;
60 }
61 }
62
63 if( val > 0 ) {
64 ++cursor;
65 }
66 return cursor;
67}
68
69#if 0 /* superseded by append/sort */
70int mdb_midl_insert( MDB_IDL ids, MDB_ID id )
71{
72 unsigned x, i;
73
74 x = mdb_midl_search( ids, id );
75 assert( x > 0 );
76
77 if( x < 1 ) {
78 /* internal error */
79 return -2;
80 }
81
82 if ( x <= ids[0] && ids[x] == id ) {
83 /* duplicate */
84 assert(0);
85 return -1;
86 }
87
88 if ( ++ids[0] >= MDB_IDL_DB_MAX ) {
89 /* no room */
90 --ids[0];
91 return -2;
92
93 } else {
94 /* insert id */
95 for (i=ids[0]; i>x; i--)
96 ids[i] = ids[i-1];
97 ids[x] = id;
98 }
99
100 return 0;
101}
102#endif
103
104MDB_IDL mdb_midl_alloc(int num)
105{
106 MDB_IDL ids = malloc((num+2) * sizeof(MDB_ID));
107 if (ids) {
108 *ids++ = num;
109 *ids = 0;
110 }
111 return ids;
112}
113
114void mdb_midl_free(MDB_IDL ids)
115{
116 if (ids)
117 free(ids-1);
118}
119
120void mdb_midl_shrink( MDB_IDL *idp )
121{
122 MDB_IDL ids = *idp;
123 if (*(--ids) > MDB_IDL_UM_MAX &&
124 (ids = realloc(ids, (MDB_IDL_UM_MAX+2) * sizeof(MDB_ID))))
125 {
126 *ids++ = MDB_IDL_UM_MAX;
127 *idp = ids;
128 }
129}
130
131static int mdb_midl_grow( MDB_IDL *idp, int num )
132{
133 MDB_IDL idn = *idp-1;
134 /* grow it */
135 idn = realloc(idn, (*idn + num + 2) * sizeof(MDB_ID));
136 if (!idn)
137 return ENOMEM;
138 *idn++ += num;
139 *idp = idn;
140 return 0;
141}
142
143int mdb_midl_need( MDB_IDL *idp, unsigned num )
144{
145 MDB_IDL ids = *idp;
146 num += ids[0];
147 if (num > ids[-1]) {
148 num = (num + num/4 + (256 + 2)) & -256;
149 if (!(ids = realloc(ids-1, num * sizeof(MDB_ID))))
150 return ENOMEM;
151 *ids++ = num - 2;
152 *idp = ids;
153 }
154 return 0;
155}
156
157int mdb_midl_append( MDB_IDL *idp, MDB_ID id )
158{
159 MDB_IDL ids = *idp;
160 /* Too big? */
161 if (ids[0] >= ids[-1]) {
162 if (mdb_midl_grow(idp, MDB_IDL_UM_MAX))
163 return ENOMEM;
164 ids = *idp;
165 }
166 ids[0]++;
167 ids[ids[0]] = id;
168 return 0;
169}
170
171int mdb_midl_append_list( MDB_IDL *idp, MDB_IDL app )
172{
173 MDB_IDL ids = *idp;
174 /* Too big? */
175 if (ids[0] + app[0] >= ids[-1]) {
176 if (mdb_midl_grow(idp, app[0]))
177 return ENOMEM;
178 ids = *idp;
179 }
180 memcpy(&ids[ids[0]+1], &app[1], app[0] * sizeof(MDB_ID));
181 ids[0] += app[0];
182 return 0;
183}
184
185int mdb_midl_append_range( MDB_IDL *idp, MDB_ID id, unsigned n )
186{
187 MDB_ID *ids = *idp, len = ids[0];
188 /* Too big? */
189 if (len + n > ids[-1]) {
190 if (mdb_midl_grow(idp, n | MDB_IDL_UM_MAX))
191 return ENOMEM;
192 ids = *idp;
193 }
194 ids[0] = len + n;
195 ids += len;
196 while (n)
197 ids[n--] = id++;
198 return 0;
199}
200
201void mdb_midl_xmerge( MDB_IDL idl, MDB_IDL merge )
202{
203 MDB_ID old_id, merge_id, i = merge[0], j = idl[0], k = i+j, total = k;
204 idl[0] = (MDB_ID)-1; /* delimiter for idl scan below */
205 old_id = idl[j];
206 while (i) {
207 merge_id = merge[i--];
208 for (; old_id < merge_id; old_id = idl[--j])
209 idl[k--] = old_id;
210 idl[k--] = merge_id;
211 }
212 idl[0] = total;
213}
214
215/* Quicksort + Insertion sort for small arrays */
216
217#define SMALL 8
218#define MIDL_SWAP(a,b) { itmp=(a); (a)=(b); (b)=itmp; }
219
220void
221mdb_midl_sort( MDB_IDL ids )
222{
223 /* Max possible depth of int-indexed tree * 2 items/level */
224 int istack[sizeof(int)*CHAR_BIT * 2];
225 int i,j,k,l,ir,jstack;
226 MDB_ID a, itmp;
227
228 ir = (int)ids[0];
229 l = 1;
230 jstack = 0;
231 for(;;) {
232 if (ir - l < SMALL) { /* Insertion sort */
233 for (j=l+1;j<=ir;j++) {
234 a = ids[j];
235 for (i=j-1;i>=1;i--) {
236 if (ids[i] >= a) break;
237 ids[i+1] = ids[i];
238 }
239 ids[i+1] = a;
240 }
241 if (jstack == 0) break;
242 ir = istack[jstack--];
243 l = istack[jstack--];
244 } else {
245 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 i = l+1;
257 j = ir;
258 a = ids[l+1];
259 for(;;) {
260 do i++; while(ids[i] > a);
261 do j--; while(ids[j] < a);
262 if (j < i) break;
263 MIDL_SWAP(ids[i],ids[j]);
264 }
265 ids[l+1] = ids[j];
266 ids[j] = a;
267 jstack += 2;
268 if (ir-i+1 >= j-l) {
269 istack[jstack] = ir;
270 istack[jstack-1] = i;
271 ir = j-1;
272 } else {
273 istack[jstack] = j-1;
274 istack[jstack-1] = l;
275 l = i;
276 }
277 }
278 }
279}
280
281unsigned mdb_mid2l_search( MDB_ID2L ids, MDB_ID id )
282{
283 /*
284 * binary search of id in ids
285 * if found, returns position of id
286 * if not found, returns first position greater than id
287 */
288 unsigned base = 0;
289 unsigned cursor = 1;
290 int val = 0;
291 unsigned n = (unsigned)ids[0].mid;
292
293 while( 0 < n ) {
294 unsigned pivot = n >> 1;
295 cursor = base + pivot + 1;
296 val = CMP( id, ids[cursor].mid );
297
298 if( val < 0 ) {
299 n = pivot;
300
301 } else if ( val > 0 ) {
302 base = cursor;
303 n -= pivot + 1;
304
305 } else {
306 return cursor;
307 }
308 }
309
310 if( val > 0 ) {
311 ++cursor;
312 }
313 return cursor;
314}
315
316int mdb_mid2l_insert( MDB_ID2L ids, MDB_ID2 *id )
317{
318 unsigned x, i;
319
320 x = mdb_mid2l_search( ids, id->mid );
321
322 if( x < 1 ) {
323 /* internal error */
324 return -2;
325 }
326
327 if ( x <= ids[0].mid && ids[x].mid == id->mid ) {
328 /* duplicate */
329 return -1;
330 }
331
332 if ( ids[0].mid >= MDB_IDL_UM_MAX ) {
333 /* too big */
334 return -2;
335
336 } else {
337 /* insert id */
338 ids[0].mid++;
339 for (i=(unsigned)ids[0].mid; i>x; i--)
340 ids[i] = ids[i-1];
341 ids[x] = *id;
342 }
343
344 return 0;
345}
346
347int mdb_mid2l_append( MDB_ID2L ids, MDB_ID2 *id )
348{
349 /* Too big? */
350 if (ids[0].mid >= MDB_IDL_UM_MAX) {
351 return -2;
352 }
353 ids[0].mid++;
354 ids[ids[0].mid] = *id;
355 return 0;
356}
357
358#ifdef MDB_VL32
359unsigned mdb_mid3l_search( MDB_ID3L ids, MDB_ID id )
360{
361 /*
362 * binary search of id in ids
363 * if found, returns position of id
364 * if not found, returns first position greater than id
365 */
366 unsigned base = 0;
367 unsigned cursor = 1;
368 int val = 0;
369 unsigned n = (unsigned)ids[0].mid;
370
371 while( 0 < n ) {
372 unsigned pivot = n >> 1;
373 cursor = base + pivot + 1;
374 val = CMP( id, ids[cursor].mid );
375
376 if( val < 0 ) {
377 n = pivot;
378
379 } else if ( val > 0 ) {
380 base = cursor;
381 n -= pivot + 1;
382
383 } else {
384 return cursor;
385 }
386 }
387
388 if( val > 0 ) {
389 ++cursor;
390 }
391 return cursor;
392}
393
394int mdb_mid3l_insert( MDB_ID3L ids, MDB_ID3 *id )
395{
396 unsigned x, i;
397
398 x = mdb_mid3l_search( ids, id->mid );
399
400 if( x < 1 ) {
401 /* internal error */
402 return -2;
403 }
404
405 if ( x <= ids[0].mid && ids[x].mid == id->mid ) {
406 /* duplicate */
407 return -1;
408 }
409
410 /* insert id */
411 ids[0].mid++;
412 for (i=(unsigned)ids[0].mid; i>x; i--)
413 ids[i] = ids[i-1];
414 ids[x] = *id;
415
416 return 0;
417}
418#endif /* MDB_VL32 */
419
420/** @} */
421/** @} */
422