midl.c (6589B)
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-2021 The OpenLDAP Foundation. 7 * Portions Copyright 2001-2021 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 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 /** @} */