git.sur5r.net Git - openldap/blob - libraries/libmdb/midl.c

   1 /**     @file midl.c
   2  *      @brief ldap bdb back-end ID List functions */
   3 /* $OpenLDAP$ */
   4 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
   5  *
   6  * Copyright 2000-2011 The OpenLDAP Foundation.
   7  * All rights reserved.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted only as authorized by the OpenLDAP
  11  * Public License.
  12  *
  13  * A copy of this license is available in the file LICENSE in the
  14  * top-level directory of the distribution or, alternatively, at
  15  * <http://www.OpenLDAP.org/license.html>.
  16  */
  17
  18 #include <string.h>
  19 #include <sys/types.h>
  20 #include <assert.h>
  21 #include "midl.h"
  22
  23 /** @defgroup internal  MDB Internals
  24  *      @{
  25  */
  26 /** @defgroup idls      ID List Management
  27  *      @{
  28  */
  29 #define CMP(x,y)         ( (x) < (y) ? -1 : (x) > (y) )
  30
  31 #if 0
  32 static unsigned mdb_midl_search( IDL ids, ID id )
  33 {
  34         /*
  35          * binary search of id in ids
  36          * if found, returns position of id
  37          * if not found, returns first position greater than id
  38          */
  39         unsigned base = 0;
  40         unsigned cursor = 0;
  41         int val = 0;
  42         unsigned n = ids[0];
  43
  44         while( 0 < n ) {
  45                 int pivot = n >> 1;
  46                 cursor = base + pivot;
  47                 val = CMP( ids[cursor + 1], id );
  48
  49                 if( val < 0 ) {
  50                         n = pivot;
  51
  52                 } else if ( val > 0 ) {
  53                         base = cursor + 1;
  54                         n -= pivot + 1;
  55
  56                 } else {
  57                         return cursor + 1;
  58                 }
  59         }
  60
  61         if( val > 0 ) {
  62                 return cursor + 2;
  63         } else {
  64                 return cursor + 1;
  65         }
  66 }
  67
  68 int mdb_midl_insert( IDL ids, ID id )
  69 {
  70         unsigned x, i;
  71
  72         if (MDB_IDL_IS_RANGE( ids )) {
  73                 /* if already in range, treat as a dup */
  74                 if (id >= MDB_IDL_FIRST(ids) && id <= MDB_IDL_LAST(ids))
  75                         return -1;
  76                 if (id < MDB_IDL_FIRST(ids))
  77                         ids[1] = id;
  78                 else if (id > MDB_IDL_LAST(ids))
  79                         ids[2] = id;
  80                 return 0;
  81         }
  82
  83         x = mdb_midl_search( ids, id );
  84         assert( x > 0 );
  85
  86         if( x < 1 ) {
  87                 /* internal error */
  88                 return -2;
  89         }
  90
  91         if ( x <= ids[0] && ids[x] == id ) {
  92                 /* duplicate */
  93                 assert(0);
  94                 return -1;
  95         }
  96
  97         if ( ++ids[0] >= MDB_IDL_DB_MAX ) {
  98                 if( id < ids[1] ) {
  99                         ids[1] = id;
 100                         ids[2] = ids[ids[0]-1];
 101                 } else if ( ids[ids[0]-1] < id ) {
 102                         ids[2] = id;
 103                 } else {
 104                         ids[2] = ids[ids[0]-1];
 105                 }
 106                 ids[0] = NOID;
 107
 108         } else {
 109                 /* insert id */
 110                 for (i=ids[0]; i>x; i--)
 111                         ids[i] = ids[i-1];
 112                 ids[x] = id;
 113         }
 114
 115         return 0;
 116 }
 117 #endif
 118
 119 int mdb_midl_append( IDL ids, ID id )
 120 {
 121         /* Too big? */
 122         if (ids[0] >= MDB_IDL_UM_SIZE)
 123                 return -1;
 124         ids[0]++;
 125         ids[ids[0]] = id;
 126         return 0;
 127 }
 128
 129 /* Quicksort + Insertion sort for small arrays */
 130
 131 #define SMALL   8
 132 #define SWAP(a,b)       itmp=(a);(a)=(b);(b)=itmp
 133
 134 void
 135 mdb_midl_sort( ID *ids )
 136 {
 137         int istack[16*sizeof(int)];
 138         int i,j,k,l,ir,jstack;
 139         ID a, itmp;
 140
 141         ir = ids[0];
 142         l = 1;
 143         jstack = 0;
 144         for(;;) {
 145                 if (ir - l < SMALL) {   /* Insertion sort */
 146                         for (j=l+1;j<=ir;j++) {
 147                                 a = ids[j];
 148                                 for (i=j-1;i>=1;i--) {
 149                                         if (ids[i] >= a) break;
 150                                         ids[i+1] = ids[i];
 151                                 }
 152                                 ids[i+1] = a;
 153                         }
 154                         if (jstack == 0) break;
 155                         ir = istack[jstack--];
 156                         l = istack[jstack--];
 157                 } else {
 158                         k = (l + ir) >> 1;      /* Choose median of left, center, right */
 159                         SWAP(ids[k], ids[l+1]);
 160                         if (ids[l] < ids[ir]) {
 161                                 SWAP(ids[l], ids[ir]);
 162                         }
 163                         if (ids[l+1] < ids[ir]) {
 164                                 SWAP(ids[l+1], ids[ir]);
 165                         }
 166                         if (ids[l] < ids[l+1]) {
 167                                 SWAP(ids[l], ids[l+1]);
 168                         }
 169                         i = l+1;
 170                         j = ir;
 171                         a = ids[l+1];
 172                         for(;;) {
 173                                 do i++; while(ids[i] > a);
 174                                 do j--; while(ids[j] < a);
 175                                 if (j < i) break;
 176                                 SWAP(ids[i],ids[j]);
 177                         }
 178                         ids[l+1] = ids[j];
 179                         ids[j] = a;
 180                         jstack += 2;
 181                         if (ir-i+1 >= j-1) {
 182                                 istack[jstack] = ir;
 183                                 istack[jstack-1] = i;
 184                                 ir = j-1;
 185                         } else {
 186                                 istack[jstack] = j-1;
 187                                 istack[jstack-1] = l;
 188                                 l = i;
 189                         }
 190                 }
 191         }
 192 }
 193
 194 unsigned mdb_mid2l_search( ID2L ids, ID id )
 195 {
 196         /*
 197          * binary search of id in ids
 198          * if found, returns position of id
 199          * if not found, returns first position greater than id
 200          */
 201         unsigned base = 0;
 202         unsigned cursor = 0;
 203         int val = 0;
 204         unsigned n = ids[0].mid;
 205
 206         while( 0 < n ) {
 207                 int pivot = n >> 1;
 208                 cursor = base + pivot;
 209                 val = CMP( id, ids[cursor + 1].mid );
 210
 211                 if( val < 0 ) {
 212                         n = pivot;
 213
 214                 } else if ( val > 0 ) {
 215                         base = cursor + 1;
 216                         n -= pivot + 1;
 217
 218                 } else {
 219                         return cursor + 1;
 220                 }
 221         }
 222
 223         if( val > 0 ) {
 224                 return cursor + 2;
 225         } else {
 226                 return cursor + 1;
 227         }
 228 }
 229
 230 int mdb_mid2l_insert( ID2L ids, ID2 *id )
 231 {
 232         unsigned x, i;
 233
 234         x = mdb_mid2l_search( ids, id->mid );
 235         assert( x > 0 );
 236
 237         if( x < 1 ) {
 238                 /* internal error */
 239                 return -2;
 240         }
 241
 242         if ( x <= ids[0].mid && ids[x].mid == id->mid ) {
 243                 /* duplicate */
 244                 return -1;
 245         }
 246
 247         if ( ids[0].mid >= MDB_IDL_DB_MAX ) {
 248                 /* too big */
 249                 return -2;
 250
 251         } else {
 252                 /* insert id */
 253                 ids[0].mid++;
 254                 for (i=ids[0].mid; i>x; i--)
 255                         ids[i] = ids[i-1];
 256                 ids[x] = *id;
 257         }
 258
 259         return 0;
 260 }
 261 /** @} */
 262 /** @} */