midl.c (6588B)
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 /* 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 /** @} */