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
mdb_midl_search(MDB_IDL ids,MDB_ID id)34 unsigned 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 */
70 int 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
mdb_midl_alloc(int num)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 *ids = 0;
110 }
111 return ids;
112 }
113
mdb_midl_free(MDB_IDL ids)114 void mdb_midl_free(MDB_IDL ids)
115 {
116 if (ids)
117 free(ids-1);
118 }
119
mdb_midl_shrink(MDB_IDL * idp)120 void 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
mdb_midl_grow(MDB_IDL * idp,int num)131 static 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
mdb_midl_need(MDB_IDL * idp,unsigned num)143 int 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
mdb_midl_append(MDB_IDL * idp,MDB_ID id)157 int 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
mdb_midl_append_list(MDB_IDL * idp,MDB_IDL app)171 int 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
mdb_midl_append_range(MDB_IDL * idp,MDB_ID id,unsigned n)185 int 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
mdb_midl_xmerge(MDB_IDL idl,MDB_IDL merge)201 void 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
220 void
mdb_midl_sort(MDB_IDL ids)221 mdb_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
mdb_mid2l_search(MDB_ID2L ids,MDB_ID id)281 unsigned 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
mdb_mid2l_insert(MDB_ID2L ids,MDB_ID2 * id)316 int 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
mdb_mid2l_append(MDB_ID2L ids,MDB_ID2 * id)347 int 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 /** @} */
359 /** @} */
360