X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=libraries%2Fliblmdb%2Fmidl.c;h=5ee2129046091f13580e605e3ac15ca966a0b950;hb=c3d84bcd06d0017a7fad5f1d7932c590605e6369;hp=3bfb61f1745dac37734bfd2e28aaa4385a9e35de;hpb=0521a7b3745cb346b7cd636a4fc144bb5a245cdc;p=openldap diff --git a/libraries/liblmdb/midl.c b/libraries/liblmdb/midl.c index 3bfb61f174..5ee2129046 100644 --- a/libraries/liblmdb/midl.c +++ b/libraries/liblmdb/midl.c @@ -18,6 +18,7 @@ #include #include #include +#include #include #include #include "midl.h" @@ -30,8 +31,7 @@ */ #define CMP(x,y) ( (x) < (y) ? -1 : (x) > (y) ) -#if 0 /* superseded by append/sort */ -static unsigned mdb_midl_search( MDB_IDL ids, MDB_ID id ) +unsigned mdb_midl_search( MDB_IDL ids, MDB_ID id ) { /* * binary search of id in ids @@ -59,28 +59,18 @@ static unsigned mdb_midl_search( MDB_IDL ids, MDB_ID id ) return cursor; } } - + if( val > 0 ) { ++cursor; } return cursor; } +#if 0 /* superseded by append/sort */ int mdb_midl_insert( MDB_IDL ids, MDB_ID id ) { unsigned x, i; - if (MDB_IDL_IS_RANGE( ids )) { - /* if already in range, treat as a dup */ - if (id >= MDB_IDL_RANGE_FIRST(ids) && id <= MDB_IDL_RANGE_LAST(ids)) - return -1; - if (id < MDB_IDL_RANGE_FIRST(ids)) - ids[1] = id; - else if (id > MDB_IDL_RANGE_LAST(ids)) - ids[2] = id; - return 0; - } - x = mdb_midl_search( ids, id ); assert( x > 0 ); @@ -96,16 +86,10 @@ int mdb_midl_insert( MDB_IDL ids, MDB_ID id ) } if ( ++ids[0] >= MDB_IDL_DB_MAX ) { - if( id < ids[1] ) { - ids[1] = id; - ids[2] = ids[ids[0]-1]; - } else if ( ids[ids[0]-1] < id ) { - ids[2] = id; - } else { - ids[2] = ids[ids[0]-1]; - } - ids[0] = MDB_NOID; - + /* no room */ + --ids[0]; + return -2; + } else { /* insert id */ for (i=ids[0]; i>x; i--) @@ -117,23 +101,28 @@ int mdb_midl_insert( MDB_IDL ids, MDB_ID id ) } #endif -MDB_IDL mdb_midl_alloc() +MDB_IDL mdb_midl_alloc(int num) { - MDB_IDL ids = malloc((MDB_IDL_UM_MAX+1) * sizeof(MDB_ID)); - *ids++ = MDB_IDL_UM_MAX; + MDB_IDL ids = malloc((num+2) * sizeof(MDB_ID)); + if (ids) { + *ids++ = num; + *ids = 0; + } return ids; } void mdb_midl_free(MDB_IDL ids) { - free(ids-1); + if (ids) + free(ids-1); } int mdb_midl_shrink( MDB_IDL *idp ) { MDB_IDL ids = *idp; - if (*(--ids) > MDB_IDL_UM_MAX) { - ids = realloc(ids, (MDB_IDL_UM_MAX+1) * sizeof(MDB_ID)); + if (*(--ids) > MDB_IDL_UM_MAX && + (ids = realloc(ids, (MDB_IDL_UM_MAX+1) * sizeof(MDB_ID)))) + { *ids++ = MDB_IDL_UM_MAX; *idp = ids; return 1; @@ -141,19 +130,40 @@ int mdb_midl_shrink( MDB_IDL *idp ) return 0; } +static int mdb_midl_grow( MDB_IDL *idp, int num ) +{ + MDB_IDL idn = *idp-1; + /* grow it */ + idn = realloc(idn, (*idn + num + 2) * sizeof(MDB_ID)); + if (!idn) + return ENOMEM; + *idn++ += num; + *idp = idn; + return 0; +} + +int mdb_midl_need( MDB_IDL *idp, unsigned num ) +{ + MDB_IDL ids = *idp; + num += ids[0]; + if (num > ids[-1]) { + num = (num + num/4 + (256 + 2)) & -256; + if (!(ids = realloc(ids-1, num * sizeof(MDB_ID)))) + return ENOMEM; + *ids++ = num -= 2; + *idp = ids; + } + return 0; +} + int mdb_midl_append( MDB_IDL *idp, MDB_ID id ) { MDB_IDL ids = *idp; /* Too big? */ if (ids[0] >= ids[-1]) { - MDB_IDL idn = ids-1; - /* grow it */ - idn = realloc(idn, (*idn + MDB_IDL_UM_MAX + 1) * sizeof(MDB_ID)); - if (!idn) - return -1; - *idn++ += MDB_IDL_UM_MAX; - ids = idn; - *idp = ids; + if (mdb_midl_grow(idp, MDB_IDL_UM_MAX)) + return ENOMEM; + ids = *idp; } ids[0]++; ids[ids[0]] = id; @@ -165,24 +175,35 @@ int mdb_midl_append_list( MDB_IDL *idp, MDB_IDL app ) MDB_IDL ids = *idp; /* Too big? */ if (ids[0] + app[0] >= ids[-1]) { - MDB_IDL idn = ids-1; - /* grow it */ - idn = realloc(idn, (*idn + app[-1]) * sizeof(MDB_ID)); - if (!idn) - return -1; - *idn++ += app[-1]; - ids = idn; - *idp = ids; + if (mdb_midl_grow(idp, app[0])) + return ENOMEM; + ids = *idp; } memcpy(&ids[ids[0]+1], &app[1], app[0] * sizeof(MDB_ID)); ids[0] += app[0]; return 0; } +int mdb_midl_append_range( MDB_IDL *idp, MDB_ID id, unsigned n ) +{ + MDB_ID *ids = *idp, len = ids[0]; + /* Too big? */ + if (len + n > ids[-1]) { + if (mdb_midl_grow(idp, n | MDB_IDL_UM_MAX)) + return ENOMEM; + ids = *idp; + } + ids[0] = len + n; + ids += len; + while (n) + ids[n--] = id++; + return 0; +} + /* Quicksort + Insertion sort for small arrays */ #define SMALL 8 -#define SWAP(a,b) { itmp=(a); (a)=(b); (b)=itmp; } +#define MIDL_SWAP(a,b) { itmp=(a); (a)=(b); (b)=itmp; } void mdb_midl_sort( MDB_IDL ids ) @@ -192,7 +213,7 @@ mdb_midl_sort( MDB_IDL ids ) int i,j,k,l,ir,jstack; MDB_ID a, itmp; - ir = ids[0]; + ir = (int)ids[0]; l = 1; jstack = 0; for(;;) { @@ -210,15 +231,15 @@ mdb_midl_sort( MDB_IDL ids ) l = istack[jstack--]; } else { k = (l + ir) >> 1; /* Choose median of left, center, right */ - SWAP(ids[k], ids[l+1]); + MIDL_SWAP(ids[k], ids[l+1]); if (ids[l] < ids[ir]) { - SWAP(ids[l], ids[ir]); + MIDL_SWAP(ids[l], ids[ir]); } if (ids[l+1] < ids[ir]) { - SWAP(ids[l+1], ids[ir]); + MIDL_SWAP(ids[l+1], ids[ir]); } if (ids[l] < ids[l+1]) { - SWAP(ids[l], ids[l+1]); + MIDL_SWAP(ids[l], ids[l+1]); } i = l+1; j = ir; @@ -227,7 +248,7 @@ mdb_midl_sort( MDB_IDL ids ) do i++; while(ids[i] > a); do j--; while(ids[j] < a); if (j < i) break; - SWAP(ids[i],ids[j]); + MIDL_SWAP(ids[i],ids[j]); } ids[l+1] = ids[j]; ids[j] = a; @@ -255,7 +276,7 @@ unsigned mdb_mid2l_search( MDB_ID2L ids, MDB_ID id ) unsigned base = 0; unsigned cursor = 1; int val = 0; - unsigned n = ids[0].mid; + unsigned n = (unsigned)ids[0].mid; while( 0 < n ) { unsigned pivot = n >> 1; @@ -304,7 +325,7 @@ int mdb_mid2l_insert( MDB_ID2L ids, MDB_ID2 *id ) } else { /* insert id */ ids[0].mid++; - for (i=ids[0].mid; i>x; i--) + for (i=(unsigned)ids[0].mid; i>x; i--) ids[i] = ids[i-1]; ids[x] = *id; }