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