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 36unsigned 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 */ 72int 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 106MDB_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 116void mdb_midl_free(MDB_IDL ids) 117{ 118 if (ids) 119 free(ids-1); 120} 121 122void 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 133static 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 145int 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 159int 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 173int 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 187int 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 203void 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 222void 223mdb_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 283unsigned 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 318int 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 349int 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