1 /* $NetBSD: midl.c,v 1.1.1.1 2014/05/28 09:58:42 tron 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-2014 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 MDB 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 int 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+1) * sizeof(MDB_ID)))) 126 { 127 *ids++ = MDB_IDL_UM_MAX; 128 *idp = ids; 129 return 1; 130 } 131 return 0; 132 } 133 134 static int mdb_midl_grow( MDB_IDL *idp, int num ) 135 { 136 MDB_IDL idn = *idp-1; 137 /* grow it */ 138 idn = realloc(idn, (*idn + num + 2) * sizeof(MDB_ID)); 139 if (!idn) 140 return ENOMEM; 141 *idn++ += num; 142 *idp = idn; 143 return 0; 144 } 145 146 int mdb_midl_need( MDB_IDL *idp, unsigned num ) 147 { 148 MDB_IDL ids = *idp; 149 num += ids[0]; 150 if (num > ids[-1]) { 151 num = (num + num/4 + (256 + 2)) & -256; 152 if (!(ids = realloc(ids-1, num * sizeof(MDB_ID)))) 153 return ENOMEM; 154 *ids++ = num - 2; 155 *idp = ids; 156 } 157 return 0; 158 } 159 160 int mdb_midl_append( MDB_IDL *idp, MDB_ID id ) 161 { 162 MDB_IDL ids = *idp; 163 /* Too big? */ 164 if (ids[0] >= ids[-1]) { 165 if (mdb_midl_grow(idp, MDB_IDL_UM_MAX)) 166 return ENOMEM; 167 ids = *idp; 168 } 169 ids[0]++; 170 ids[ids[0]] = id; 171 return 0; 172 } 173 174 int mdb_midl_append_list( MDB_IDL *idp, MDB_IDL app ) 175 { 176 MDB_IDL ids = *idp; 177 /* Too big? */ 178 if (ids[0] + app[0] >= ids[-1]) { 179 if (mdb_midl_grow(idp, app[0])) 180 return ENOMEM; 181 ids = *idp; 182 } 183 memcpy(&ids[ids[0]+1], &app[1], app[0] * sizeof(MDB_ID)); 184 ids[0] += app[0]; 185 return 0; 186 } 187 188 int mdb_midl_append_range( MDB_IDL *idp, MDB_ID id, unsigned n ) 189 { 190 MDB_ID *ids = *idp, len = ids[0]; 191 /* Too big? */ 192 if (len + n > ids[-1]) { 193 if (mdb_midl_grow(idp, n | MDB_IDL_UM_MAX)) 194 return ENOMEM; 195 ids = *idp; 196 } 197 ids[0] = len + n; 198 ids += len; 199 while (n) 200 ids[n--] = id++; 201 return 0; 202 } 203 204 /* Quicksort + Insertion sort for small arrays */ 205 206 #define SMALL 8 207 #define MIDL_SWAP(a,b) { itmp=(a); (a)=(b); (b)=itmp; } 208 209 void 210 mdb_midl_sort( MDB_IDL ids ) 211 { 212 /* Max possible depth of int-indexed tree * 2 items/level */ 213 int istack[sizeof(int)*CHAR_BIT * 2]; 214 int i,j,k,l,ir,jstack; 215 MDB_ID a, itmp; 216 217 ir = (int)ids[0]; 218 l = 1; 219 jstack = 0; 220 for(;;) { 221 if (ir - l < SMALL) { /* Insertion sort */ 222 for (j=l+1;j<=ir;j++) { 223 a = ids[j]; 224 for (i=j-1;i>=1;i--) { 225 if (ids[i] >= a) break; 226 ids[i+1] = ids[i]; 227 } 228 ids[i+1] = a; 229 } 230 if (jstack == 0) break; 231 ir = istack[jstack--]; 232 l = istack[jstack--]; 233 } else { 234 k = (l + ir) >> 1; /* Choose median of left, center, right */ 235 MIDL_SWAP(ids[k], ids[l+1]); 236 if (ids[l] < ids[ir]) { 237 MIDL_SWAP(ids[l], ids[ir]); 238 } 239 if (ids[l+1] < ids[ir]) { 240 MIDL_SWAP(ids[l+1], ids[ir]); 241 } 242 if (ids[l] < ids[l+1]) { 243 MIDL_SWAP(ids[l], ids[l+1]); 244 } 245 i = l+1; 246 j = ir; 247 a = ids[l+1]; 248 for(;;) { 249 do i++; while(ids[i] > a); 250 do j--; while(ids[j] < a); 251 if (j < i) break; 252 MIDL_SWAP(ids[i],ids[j]); 253 } 254 ids[l+1] = ids[j]; 255 ids[j] = a; 256 jstack += 2; 257 if (ir-i+1 >= j-l) { 258 istack[jstack] = ir; 259 istack[jstack-1] = i; 260 ir = j-1; 261 } else { 262 istack[jstack] = j-1; 263 istack[jstack-1] = l; 264 l = i; 265 } 266 } 267 } 268 } 269 270 unsigned mdb_mid2l_search( MDB_ID2L ids, MDB_ID id ) 271 { 272 /* 273 * binary search of id in ids 274 * if found, returns position of id 275 * if not found, returns first position greater than id 276 */ 277 unsigned base = 0; 278 unsigned cursor = 1; 279 int val = 0; 280 unsigned n = (unsigned)ids[0].mid; 281 282 while( 0 < n ) { 283 unsigned pivot = n >> 1; 284 cursor = base + pivot + 1; 285 val = CMP( id, ids[cursor].mid ); 286 287 if( val < 0 ) { 288 n = pivot; 289 290 } else if ( val > 0 ) { 291 base = cursor; 292 n -= pivot + 1; 293 294 } else { 295 return cursor; 296 } 297 } 298 299 if( val > 0 ) { 300 ++cursor; 301 } 302 return cursor; 303 } 304 305 int mdb_mid2l_insert( MDB_ID2L ids, MDB_ID2 *id ) 306 { 307 unsigned x, i; 308 309 x = mdb_mid2l_search( ids, id->mid ); 310 311 if( x < 1 ) { 312 /* internal error */ 313 return -2; 314 } 315 316 if ( x <= ids[0].mid && ids[x].mid == id->mid ) { 317 /* duplicate */ 318 return -1; 319 } 320 321 if ( ids[0].mid >= MDB_IDL_UM_MAX ) { 322 /* too big */ 323 return -2; 324 325 } else { 326 /* insert id */ 327 ids[0].mid++; 328 for (i=(unsigned)ids[0].mid; i>x; i--) 329 ids[i] = ids[i-1]; 330 ids[x] = *id; 331 } 332 333 return 0; 334 } 335 336 int mdb_mid2l_append( MDB_ID2L ids, MDB_ID2 *id ) 337 { 338 /* Too big? */ 339 if (ids[0].mid >= MDB_IDL_UM_MAX) { 340 return -2; 341 } 342 ids[0].mid++; 343 ids[ids[0].mid] = *id; 344 return 0; 345 } 346 347 /** @} */ 348 /** @} */ 349