X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;ds=sidebyside;f=libraries%2Flibmdb%2Fmidl.c;h=a2cb86165961ca4dc92b7336f1d5cc90c6a0260a;hb=d50d57ed63a4fd29d90da3b7de9cc105fff63a3e;hp=8b39acad6509f78e9576101ef3a698ce9befb522;hpb=985f765dc53621f8db910737f677261de4562433;p=openldap diff --git a/libraries/libmdb/midl.c b/libraries/libmdb/midl.c index 8b39acad65..a2cb861659 100644 --- a/libraries/libmdb/midl.c +++ b/libraries/libmdb/midl.c @@ -1,8 +1,9 @@ -/* idl.c - ldap bdb back-end ID list functions */ +/** @file midl.c + * @brief ldap bdb back-end ID List functions */ /* $OpenLDAP$ */ /* This work is part of OpenLDAP Software . * - * Copyright 2000-2011 The OpenLDAP Foundation. + * Copyright 2000-2012 The OpenLDAP Foundation. * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -14,17 +15,23 @@ * . */ +#include #include +#include #include #include #include "midl.h" -typedef unsigned long pgno_t; - -/* Sort the IDLs from highest to lowest */ -#define IDL_CMP(x,y) ( x > y ? -1 : ( x < y ? 1 : 0 ) ) +/** @defgroup internal MDB Internals + * @{ + */ +/** @defgroup idls ID List Management + * @{ + */ +#define CMP(x,y) ( (x) < (y) ? -1 : (x) > (y) ) -unsigned mdb_midl_search( ID *ids, ID id ) +#if 0 /* superseded by append/sort */ +static unsigned mdb_midl_search( IDL ids, ID id ) { /* * binary search of id in ids @@ -32,45 +39,44 @@ unsigned mdb_midl_search( ID *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 = IDL_CMP( id, ids[cursor + 1] ); + 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( ID *ids, ID id ) +int mdb_midl_insert( IDL ids, ID id ) { - unsigned x; + unsigned x, i; 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; } @@ -85,6 +91,7 @@ int mdb_midl_insert( ID *ids, ID id ) if ( x <= ids[0] && ids[x] == id ) { /* duplicate */ + assert(0); return -1; } @@ -101,9 +108,208 @@ int mdb_midl_insert( ID *ids, ID id ) } else { /* insert id */ - AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) ); + for (i=ids[0]; i>x; i--) + ids[i] = ids[i-1]; ids[x] = 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 ) +{ + /* + * binary search of id in ids + * if found, returns position of id + * if not found, returns first position greater than id + */ + unsigned base = 0; + unsigned cursor = 1; + int val = 0; + unsigned n = ids[0].mid; + + while( 0 < n ) { + 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; + n -= pivot + 1; + + } else { + return cursor; + } + } + + if( val > 0 ) { + ++cursor; + } + return cursor; +} + +int mdb_mid2l_insert( ID2L ids, ID2 *id ) +{ + unsigned x, i; + + x = mdb_mid2l_search( ids, id->mid ); + assert( x > 0 ); + + if( x < 1 ) { + /* internal error */ + return -2; + } + + if ( x <= ids[0].mid && ids[x].mid == id->mid ) { + /* duplicate */ + return -1; + } + + if ( ids[0].mid >= MDB_IDL_UM_MAX ) { + /* too big */ + return -2; + + } else { + /* insert id */ + ids[0].mid++; + for (i=ids[0].mid; i>x; i--) + ids[i] = ids[i-1]; + ids[x] = *id; + } + + return 0; +} +/** @} */ +/** @} */