libnstd/lmdb/eidl.c

0001 /** @file eidl.c
0002  *  @brief ldap bdb back-end ID List functions */
0003 /* $OpenLDAP$ */
0004 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
0005  *
0006  * Copyright 2000-2020 The OpenLDAP Foundation.
0007  * Portions Copyright 2001-2020 Howard Chu, Symas Corp.
0008  * All rights reserved.
0009  *
0010  * Redistribution and use in source and binary forms, with or without
0011  * modification, are permitted only as authorized by the OpenLDAP
0012  * Public License.
0013  *
0014  * A copy of this license is available in the file LICENSE in the
0015  * top-level directory of the distribution or, alternatively, at
0016  * <http://www.OpenLDAP.org/license.html>.
0017  */
0018
0019 #include <limits.h>
0020 #include <string.h>
0021 #include <stdlib.h>
0022 #include <errno.h>
0023 #include <sys/types.h>
0024 #include "eidl.h"
0025
0026 /** @defgroup internal  EXDB Internals
0027  *  @{
0028  */
0029 /** @defgroup idls  ID List Management
0030  *  @{
0031  */
0032 #define CMP(x,y)     ( (x) < (y) ? -1 : (x) > (y) )
0033
0034 unsigned edb_eidl_search( EDB_IDL ids, EDB_ID id )
0035 {
0036     /*
0037      * binary search of id in ids
0038      * if found, returns position of id
0039      * if not found, returns first position greater than id
0040      */
0041     unsigned base = 0;
0042     unsigned cursor = 1;
0043     int val = 0;
0044     unsigned n = ids[0];
0045
0046     while( 0 < n ) {
0047         unsigned pivot = n >> 1;
0048         cursor = base + pivot + 1;
0049         val = CMP( ids[cursor], id );
0050
0051         if( val < 0 ) {
0052             n = pivot;
0053
0054         } else if ( val > 0 ) {
0055             base = cursor;
0056             n -= pivot + 1;
0057
0058         } else {
0059             return cursor;
0060         }
0061     }
0062
0063     if( val > 0 ) {
0064         ++cursor;
0065     }
0066     return cursor;
0067 }
0068
0069 #if 0   /* superseded by append/sort */
0070 int edb_eidl_insert( EDB_IDL ids, EDB_ID id )
0071 {
0072     unsigned x, i;
0073
0074     x = edb_eidl_search( ids, id );
0075     assert( x > 0 );
0076
0077     if( x < 1 ) {
0078         /* internal error */
0079         return -2;
0080     }
0081
0082     if ( x <= ids[0] && ids[x] == id ) {
0083         /* duplicate */
0084         assert(0);
0085         return -1;
0086     }
0087
0088     if ( ++ids[0] >= EDB_IDL_DB_MAX ) {
0089         /* no room */
0090         --ids[0];
0091         return -2;
0092
0093     } else {
0094         /* insert id */
0095         for (i=ids[0]; i>x; i--)
0096             ids[i] = ids[i-1];
0097         ids[x] = id;
0098     }
0099
0100     return 0;
0101 }
0102 #endif
0103
0104 EDB_IDL edb_eidl_alloc(int num)
0105 {
0106     EDB_IDL ids = malloc((num+2) * sizeof(EDB_ID));
0107     if (ids) {
0108         *ids++ = num;
0109         *ids = 0;
0110     }
0111     return ids;
0112 }
0113
0114 void edb_eidl_free(EDB_IDL ids)
0115 {
0116     if (ids)
0117         free(ids-1);
0118 }
0119
0120 void edb_eidl_shrink( EDB_IDL *idp )
0121 {
0122     EDB_IDL ids = *idp;
0123     if (*(--ids) > EDB_IDL_UM_MAX &&
0124         (ids = realloc(ids, (EDB_IDL_UM_MAX+2) * sizeof(EDB_ID))))
0125     {
0126         *ids++ = EDB_IDL_UM_MAX;
0127         *idp = ids;
0128     }
0129 }
0130
0131 static int edb_eidl_grow( EDB_IDL *idp, int num )
0132 {
0133     EDB_IDL idn = *idp-1;
0134     /* grow it */
0135     idn = realloc(idn, (*idn + num + 2) * sizeof(EDB_ID));
0136     if (!idn)
0137         return ENOMEM;
0138     *idn++ += num;
0139     *idp = idn;
0140     return 0;
0141 }
0142
0143 int edb_eidl_need( EDB_IDL *idp, unsigned num )
0144 {
0145     EDB_IDL ids = *idp;
0146     num += ids[0];
0147     if (num > ids[-1]) {
0148         num = (num + num/4 + (256 + 2)) & -256;
0149         if (!(ids = realloc(ids-1, num * sizeof(EDB_ID))))
0150             return ENOMEM;
0151         *ids++ = num - 2;
0152         *idp = ids;
0153     }
0154     return 0;
0155 }
0156
0157 int edb_eidl_append( EDB_IDL *idp, EDB_ID id )
0158 {
0159     EDB_IDL ids = *idp;
0160     /* Too big? */
0161     if (ids[0] >= ids[-1]) {
0162         if (edb_eidl_grow(idp, EDB_IDL_UM_MAX))
0163             return ENOMEM;
0164         ids = *idp;
0165     }
0166     ids[0]++;
0167     ids[ids[0]] = id;
0168     return 0;
0169 }
0170
0171 int edb_eidl_append_list( EDB_IDL *idp, EDB_IDL app )
0172 {
0173     EDB_IDL ids = *idp;
0174     /* Too big? */
0175     if (ids[0] + app[0] >= ids[-1]) {
0176         if (edb_eidl_grow(idp, app[0]))
0177             return ENOMEM;
0178         ids = *idp;
0179     }
0180     memcpy(&ids[ids[0]+1], &app[1], app[0] * sizeof(EDB_ID));
0181     ids[0] += app[0];
0182     return 0;
0183 }
0184
0185 int edb_eidl_append_range( EDB_IDL *idp, EDB_ID id, unsigned n )
0186 {
0187     EDB_ID *ids = *idp, len = ids[0];
0188     /* Too big? */
0189     if (len + n > ids[-1]) {
0190         if (edb_eidl_grow(idp, n | EDB_IDL_UM_MAX))
0191             return ENOMEM;
0192         ids = *idp;
0193     }
0194     ids[0] = len + n;
0195     ids += len;
0196     while (n)
0197         ids[n--] = id++;
0198     return 0;
0199 }
0200
0201 void edb_eidl_xmerge( EDB_IDL idl, EDB_IDL merge )
0202 {
0203     EDB_ID old_id, merge_id, i = merge[0], j = idl[0], k = i+j, total = k;
0204     idl[0] = (EDB_ID)-1;        /* delimiter for idl scan below */
0205     old_id = idl[j];
0206     while (i) {
0207         merge_id = merge[i--];
0208         for (; old_id < merge_id; old_id = idl[--j])
0209             idl[k--] = old_id;
0210         idl[k--] = merge_id;
0211     }
0212     idl[0] = total;
0213 }
0214
0215 /* Quicksort + Insertion sort for small arrays */
0216
0217 #define SMALL   8
0218 #define EIDL_SWAP(a,b)  { itmp=(a); (a)=(b); (b)=itmp; }
0219
0220 void
0221 edb_eidl_sort( EDB_IDL ids )
0222 {
0223     /* Max possible depth of int-indexed tree * 2 items/level */
0224     int istack[sizeof(int)*CHAR_BIT * 2];
0225     int i,j,k,l,ir,jstack;
0226     EDB_ID a, itmp;
0227
0228     ir = (int)ids[0];
0229     l = 1;
0230     jstack = 0;
0231     for(;;) {
0232         if (ir - l < SMALL) {   /* Insertion sort */
0233             for (j=l+1;j<=ir;j++) {
0234                 a = ids[j];
0235                 for (i=j-1;i>=1;i--) {
0236                     if (ids[i] >= a) break;
0237                     ids[i+1] = ids[i];
0238                 }
0239                 ids[i+1] = a;
0240             }
0241             if (jstack == 0) break;
0242             ir = istack[jstack--];
0243             l = istack[jstack--];
0244         } else {
0245             k = (l + ir) >> 1;  /* Choose median of left, center, right */
0246             EIDL_SWAP(ids[k], ids[l+1]);
0247             if (ids[l] < ids[ir]) {
0248                 EIDL_SWAP(ids[l], ids[ir]);
0249             }
0250             if (ids[l+1] < ids[ir]) {
0251                 EIDL_SWAP(ids[l+1], ids[ir]);
0252             }
0253             if (ids[l] < ids[l+1]) {
0254                 EIDL_SWAP(ids[l], ids[l+1]);
0255             }
0256             i = l+1;
0257             j = ir;
0258             a = ids[l+1];
0259             for(;;) {
0260                 do i++; while(ids[i] > a);
0261                 do j--; while(ids[j] < a);
0262                 if (j < i) break;
0263                 EIDL_SWAP(ids[i],ids[j]);
0264             }
0265             ids[l+1] = ids[j];
0266             ids[j] = a;
0267             jstack += 2;
0268             if (ir-i+1 >= j-l) {
0269                 istack[jstack] = ir;
0270                 istack[jstack-1] = i;
0271                 ir = j-1;
0272             } else {
0273                 istack[jstack] = j-1;
0274                 istack[jstack-1] = l;
0275                 l = i;
0276             }
0277         }
0278     }
0279 }
0280
0281 unsigned edb_mid2l_search( EDB_ID2L ids, EDB_ID id )
0282 {
0283     /*
0284      * binary search of id in ids
0285      * if found, returns position of id
0286      * if not found, returns first position greater than id
0287      */
0288     unsigned base = 0;
0289     unsigned cursor = 1;
0290     int val = 0;
0291     unsigned n = (unsigned)ids[0].mid;
0292
0293     while( 0 < n ) {
0294         unsigned pivot = n >> 1;
0295         cursor = base + pivot + 1;
0296         val = CMP( id, ids[cursor].mid );
0297
0298         if( val < 0 ) {
0299             n = pivot;
0300
0301         } else if ( val > 0 ) {
0302             base = cursor;
0303             n -= pivot + 1;
0304
0305         } else {
0306             return cursor;
0307         }
0308     }
0309
0310     if( val > 0 ) {
0311         ++cursor;
0312     }
0313     return cursor;
0314 }
0315
0316 int edb_mid2l_insert( EDB_ID2L ids, EDB_ID2 *id )
0317 {
0318     unsigned x, i;
0319
0320     x = edb_mid2l_search( ids, id->mid );
0321
0322     if( x < 1 ) {
0323         /* internal error */
0324         return -2;
0325     }
0326
0327     if ( x <= ids[0].mid && ids[x].mid == id->mid ) {
0328         /* duplicate */
0329         return -1;
0330     }
0331
0332     if ( ids[0].mid >= EDB_IDL_UM_MAX ) {
0333         /* too big */
0334         return -2;
0335
0336     } else {
0337         /* insert id */
0338         ids[0].mid++;
0339         for (i=(unsigned)ids[0].mid; i>x; i--)
0340             ids[i] = ids[i-1];
0341         ids[x] = *id;
0342     }
0343
0344     return 0;
0345 }
0346
0347 int edb_mid2l_append( EDB_ID2L ids, EDB_ID2 *id )
0348 {
0349     /* Too big? */
0350     if (ids[0].mid >= EDB_IDL_UM_MAX) {
0351         return -2;
0352     }
0353     ids[0].mid++;
0354     ids[ids[0].mid] = *id;
0355     return 0;
0356 }
0357
0358 #ifdef EDB_VL32
0359 unsigned edb_mid3l_search( EDB_ID3L ids, EDB_ID id )
0360 {
0361     /*
0362      * binary search of id in ids
0363      * if found, returns position of id
0364      * if not found, returns first position greater than id
0365      */
0366     unsigned base = 0;
0367     unsigned cursor = 1;
0368     int val = 0;
0369     unsigned n = (unsigned)ids[0].mid;
0370
0371     while( 0 < n ) {
0372         unsigned pivot = n >> 1;
0373         cursor = base + pivot + 1;
0374         val = CMP( id, ids[cursor].mid );
0375
0376         if( val < 0 ) {
0377             n = pivot;
0378
0379         } else if ( val > 0 ) {
0380             base = cursor;
0381             n -= pivot + 1;
0382
0383         } else {
0384             return cursor;
0385         }
0386     }
0387
0388     if( val > 0 ) {
0389         ++cursor;
0390     }
0391     return cursor;
0392 }
0393
0394 int edb_mid3l_insert( EDB_ID3L ids, EDB_ID3 *id )
0395 {
0396     unsigned x, i;
0397
0398     x = edb_mid3l_search( ids, id->mid );
0399
0400     if( x < 1 ) {
0401         /* internal error */
0402         return -2;
0403     }
0404
0405     if ( x <= ids[0].mid && ids[x].mid == id->mid ) {
0406         /* duplicate */
0407         return -1;
0408     }
0409
0410     /* insert id */
0411     ids[0].mid++;
0412     for (i=(unsigned)ids[0].mid; i>x; i--)
0413         ids[i] = ids[i-1];
0414     ids[x] = *id;
0415
0416     return 0;
0417 }
0418 #endif /* EDB_VL32 */
0419
0420 /** @} */
0421 /** @} */