Home | History | Annotate | Line # | Download | only in liblmdb 
      1 /*	$NetBSD: midl.c,v 1.4 2025/09/05 21:16:22 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-2024 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 
     36 unsigned 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 */
     72 int 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 
    106 MDB_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 
    116 void mdb_midl_free(MDB_IDL ids)
    117 {
    118 	if (ids)
    119 		free(ids-1);
    120 }
    121 
    122 void 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 
    133 static 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 
    145 int 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 
    159 int 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 
    173 int 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 
    187 int 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 
    203 void 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 
    222 void
    223 mdb_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 
    283 unsigned 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 
    318 int 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 
    349 int 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