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
mdb_midl_search(MDB_IDL ids,MDB_ID id)36 unsigned 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 */
72 int 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
mdb_midl_alloc(int num)106 MDB_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
mdb_midl_free(MDB_IDL ids)116 void mdb_midl_free(MDB_IDL ids)
117 {
118 if (ids)
119 free(ids-1);
120 }
121
mdb_midl_shrink(MDB_IDL * idp)122 void 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
mdb_midl_grow(MDB_IDL * idp,int num)133 static 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
mdb_midl_need(MDB_IDL * idp,unsigned num)145 int 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
mdb_midl_append(MDB_IDL * idp,MDB_ID id)159 int 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
mdb_midl_append_list(MDB_IDL * idp,MDB_IDL app)173 int 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
mdb_midl_append_range(MDB_IDL * idp,MDB_ID id,unsigned n)187 int 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
mdb_midl_xmerge(MDB_IDL idl,MDB_IDL merge)203 void 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
222 void
mdb_midl_sort(MDB_IDL ids)223 mdb_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
mdb_mid2l_search(MDB_ID2L ids,MDB_ID id)283 unsigned 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
mdb_mid2l_insert(MDB_ID2L ids,MDB_ID2 * id)318 int 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
mdb_mid2l_append(MDB_ID2L ids,MDB_ID2 * id)349 int 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