/* $NetBSD: midl.c,v 1.1.1.3.6.1 2019/08/10 06:17:15 martin Exp $ */ /** @file midl.c * @brief ldap bdb back-end ID List functions */ /* $OpenLDAP$ */ /* This work is part of OpenLDAP Software . * * Copyright 2000-2019 The OpenLDAP Foundation. * Portions Copyright 2001-2018 Howard Chu, Symas Corp. * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted only as authorized by the OpenLDAP * Public License. * * A copy of this license is available in the file LICENSE in the * top-level directory of the distribution or, alternatively, at * . */ #include #include #include #include #include #include "midl.h" /** @defgroup internal LMDB Internals * @{ */ /** @defgroup idls ID List Management * @{ */ #define CMP(x,y) ( (x) < (y) ? -1 : (x) > (y) ) unsigned mdb_midl_search( MDB_IDL ids, MDB_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]; while( 0 < n ) { unsigned pivot = n >> 1; cursor = base + pivot + 1; val = CMP( ids[cursor], id ); if( val < 0 ) { n = pivot; } else if ( val > 0 ) { base = cursor; n -= pivot + 1; } else { 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; x = mdb_midl_search( ids, id ); assert( x > 0 ); if( x < 1 ) { /* internal error */ return -2; } if ( x <= ids[0] && ids[x] == id ) { /* duplicate */ assert(0); return -1; } if ( ++ids[0] >= MDB_IDL_DB_MAX ) { /* no room */ --ids[0]; return -2; } else { /* insert id */ for (i=ids[0]; i>x; i--) ids[i] = ids[i-1]; ids[x] = id; } return 0; } #endif MDB_IDL mdb_midl_alloc(int num) { MDB_IDL ids = malloc((num+2) * sizeof(MDB_ID)); if (ids) { *ids++ = num; *ids = 0; } return ids; } void mdb_midl_free(MDB_IDL ids) { if (ids) free(ids-1); } void mdb_midl_shrink( MDB_IDL *idp ) { MDB_IDL ids = *idp; if (*(--ids) > MDB_IDL_UM_MAX && (ids = realloc(ids, (MDB_IDL_UM_MAX+2) * sizeof(MDB_ID)))) { *ids++ = MDB_IDL_UM_MAX; *idp = ids; } } 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]) { if (mdb_midl_grow(idp, MDB_IDL_UM_MAX)) return ENOMEM; ids = *idp; } ids[0]++; ids[ids[0]] = id; return 0; } int mdb_midl_append_list( MDB_IDL *idp, MDB_IDL app ) { MDB_IDL ids = *idp; /* Too big? */ if (ids[0] + app[0] >= ids[-1]) { 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; } void mdb_midl_xmerge( MDB_IDL idl, MDB_IDL merge ) { MDB_ID old_id, merge_id, i = merge[0], j = idl[0], k = i+j, total = k; idl[0] = (MDB_ID)-1; /* delimiter for idl scan below */ old_id = idl[j]; while (i) { merge_id = merge[i--]; for (; old_id < merge_id; old_id = idl[--j]) idl[k--] = old_id; idl[k--] = merge_id; } idl[0] = total; } /* Quicksort + Insertion sort for small arrays */ #define SMALL 8 #define MIDL_SWAP(a,b) { itmp=(a); (a)=(b); (b)=itmp; } void mdb_midl_sort( MDB_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; MDB_ID a, itmp; ir = (int)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 */ MIDL_SWAP(ids[k], ids[l+1]); if (ids[l] < ids[ir]) { MIDL_SWAP(ids[l], ids[ir]); } if (ids[l+1] < ids[ir]) { MIDL_SWAP(ids[l+1], ids[ir]); } if (ids[l] < ids[l+1]) { MIDL_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; MIDL_SWAP(ids[i],ids[j]); } ids[l+1] = ids[j]; ids[j] = a; jstack += 2; if (ir-i+1 >= j-l) { 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( MDB_ID2L ids, MDB_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 = (unsigned)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( MDB_ID2L ids, MDB_ID2 *id ) { unsigned x, i; x = mdb_mid2l_search( ids, id->mid ); 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=(unsigned)ids[0].mid; i>x; i--) ids[i] = ids[i-1]; ids[x] = *id; } return 0; } int mdb_mid2l_append( MDB_ID2L ids, MDB_ID2 *id ) { /* Too big? */ if (ids[0].mid >= MDB_IDL_UM_MAX) { return -2; } ids[0].mid++; ids[ids[0].mid] = *id; return 0; } /** @} */ /** @} */