X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=libraries%2Flibmdb%2Fmidl.c;h=500811f7d216dc4251067e5479756b001f364316;hb=68143e4532ba3b3dccdb4e80665140542170d6d6;hp=0af517dbb531c72e798840b50ad44f826a4c70c2;hpb=e91dae3ed52ea2ced5d747b3ab95534c957c8e6d;p=openldap diff --git a/libraries/libmdb/midl.c b/libraries/libmdb/midl.c index 0af517dbb5..500811f7d2 100644 --- a/libraries/libmdb/midl.c +++ b/libraries/libmdb/midl.c @@ -15,7 +15,9 @@ * . */ +#include #include +#include #include #include #include "midl.h" @@ -28,6 +30,7 @@ */ #define CMP(x,y) ( (x) < (y) ? -1 : (x) > (y) ) +#if 0 /* superseded by append/sort */ static unsigned mdb_midl_search( IDL ids, ID id ) { /* @@ -36,32 +39,31 @@ static unsigned mdb_midl_search( IDL ids, ID id ) * if not found, returns first position greater than id */ unsigned base = 0; - unsigned cursor = 0; + unsigned cursor = 1; int val = 0; unsigned n = ids[0]; while( 0 < n ) { - int pivot = n >> 1; - cursor = base + pivot; - val = CMP( ids[cursor + 1], id ); + unsigned pivot = n >> 1; + cursor = base + pivot + 1; + val = CMP( ids[cursor], id ); if( val < 0 ) { n = pivot; } else if ( val > 0 ) { - base = cursor + 1; + base = cursor; n -= pivot + 1; } else { - return cursor + 1; + return cursor; } } if( val > 0 ) { - return cursor + 2; - } else { - return cursor + 1; + ++cursor; } + return cursor; } int mdb_midl_insert( IDL ids, ID id ) @@ -70,11 +72,11 @@ int mdb_midl_insert( IDL ids, ID id ) if (MDB_IDL_IS_RANGE( ids )) { /* if already in range, treat as a dup */ - if (id >= MDB_IDL_FIRST(ids) && id <= MDB_IDL_LAST(ids)) + if (id >= MDB_IDL_RANGE_FIRST(ids) && id <= MDB_IDL_RANGE_LAST(ids)) return -1; - if (id < MDB_IDL_FIRST(ids)) + if (id < MDB_IDL_RANGE_FIRST(ids)) ids[1] = id; - else if (id > MDB_IDL_LAST(ids)) + else if (id > MDB_IDL_RANGE_LAST(ids)) ids[2] = id; return 0; } @@ -89,6 +91,7 @@ int mdb_midl_insert( IDL ids, ID id ) if ( x <= ids[0] && ids[x] == id ) { /* duplicate */ + assert(0); return -1; } @@ -112,6 +115,135 @@ int mdb_midl_insert( IDL ids, ID id ) return 0; } +#endif + +IDL mdb_midl_alloc() +{ + IDL ids = malloc((MDB_IDL_UM_MAX+1) * sizeof(ID)); + *ids++ = MDB_IDL_UM_MAX; + return ids; +} + +void mdb_midl_free(IDL ids) +{ + free(ids-1); +} + +int mdb_midl_shrink( IDL *idp ) +{ + IDL ids = *idp; + if (ids[-1] > MDB_IDL_UM_MAX) { + ids = realloc(ids, (MDB_IDL_UM_MAX+1) * sizeof(ID)); + *ids++ = MDB_IDL_UM_MAX; + *idp = ids; + return 1; + } + return 0; +} + +int mdb_midl_append( IDL *idp, ID id ) +{ + IDL ids = *idp; + /* Too big? */ + if (ids[0] >= ids[-1]) { + IDL idn = ids-1; + /* grow it */ + idn = realloc(idn, (*idn + MDB_IDL_UM_MAX + 1) * sizeof(ID)); + if (!idn) + return -1; + *idn++ += MDB_IDL_UM_MAX; + ids = idn; + *idp = ids; + } + ids[0]++; + ids[ids[0]] = id; + return 0; +} + +int mdb_midl_append_list( IDL *idp, IDL app ) +{ + IDL ids = *idp; + /* Too big? */ + if (ids[0] + app[0] >= ids[-1]) { + IDL idn = ids-1; + /* grow it */ + idn = realloc(idn, (*idn + app[-1]) * sizeof(ID)); + if (!idn) + return -1; + *idn++ += app[-1]; + ids = idn; + *idp = ids; + } + memcpy(&ids[ids[0]+1], &app[1], app[0] * sizeof(ID)); + ids[0] += app[0]; + return 0; +} + +/* Quicksort + Insertion sort for small arrays */ + +#define SMALL 8 +#define SWAP(a,b) { itmp=(a); (a)=(b); (b)=itmp; } + +void +mdb_midl_sort( IDL ids ) +{ + /* Max possible depth of int-indexed tree * 2 items/level */ + int istack[sizeof(int)*CHAR_BIT * 2]; + int i,j,k,l,ir,jstack; + ID a, itmp; + + ir = ids[0]; + l = 1; + jstack = 0; + for(;;) { + if (ir - l < SMALL) { /* Insertion sort */ + for (j=l+1;j<=ir;j++) { + a = ids[j]; + for (i=j-1;i>=1;i--) { + if (ids[i] >= a) break; + ids[i+1] = ids[i]; + } + ids[i+1] = a; + } + if (jstack == 0) break; + ir = istack[jstack--]; + l = istack[jstack--]; + } else { + k = (l + ir) >> 1; /* Choose median of left, center, right */ + SWAP(ids[k], ids[l+1]); + if (ids[l] < ids[ir]) { + SWAP(ids[l], ids[ir]); + } + if (ids[l+1] < ids[ir]) { + SWAP(ids[l+1], ids[ir]); + } + if (ids[l] < ids[l+1]) { + SWAP(ids[l], ids[l+1]); + } + i = l+1; + j = ir; + a = ids[l+1]; + for(;;) { + do i++; while(ids[i] > a); + do j--; while(ids[j] < a); + if (j < i) break; + SWAP(ids[i],ids[j]); + } + ids[l+1] = ids[j]; + ids[j] = a; + jstack += 2; + if (ir-i+1 >= j-1) { + istack[jstack] = ir; + istack[jstack-1] = i; + ir = j-1; + } else { + istack[jstack] = j-1; + istack[jstack-1] = l; + l = i; + } + } + } +} unsigned mdb_mid2l_search( ID2L ids, ID id ) { @@ -121,32 +253,31 @@ unsigned mdb_mid2l_search( ID2L ids, ID id ) * if not found, returns first position greater than id */ unsigned base = 0; - unsigned cursor = 0; + unsigned cursor = 1; int val = 0; unsigned n = ids[0].mid; while( 0 < n ) { - int pivot = n >> 1; - cursor = base + pivot; - val = CMP( id, ids[cursor + 1].mid ); + unsigned pivot = n >> 1; + cursor = base + pivot + 1; + val = CMP( id, ids[cursor].mid ); if( val < 0 ) { n = pivot; } else if ( val > 0 ) { - base = cursor + 1; + base = cursor; n -= pivot + 1; } else { - return cursor + 1; + return cursor; } } if( val > 0 ) { - return cursor + 2; - } else { - return cursor + 1; + ++cursor; } + return cursor; } int mdb_mid2l_insert( ID2L ids, ID2 *id ) @@ -166,7 +297,7 @@ int mdb_mid2l_insert( ID2L ids, ID2 *id ) return -1; } - if ( ids[0].mid >= MDB_IDL_DB_MAX ) { + if ( ids[0].mid >= MDB_IDL_UM_MAX ) { /* too big */ return -2;