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