| 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 |
|
| 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 |
|
| 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 |
|
| 114 |
void mdb_midl_free(MDB_IDL ids) |
| 115 |
{ |
| 116 |
if (ids) |
| 117 |
free(ids-1); |
| 118 |
} |
| 119 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |
/** @} */ |