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

   1 /* idl.c - ldap bdb back-end ID list functions */
   2 /* $OpenLDAP$ */
   3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
   4  *
   5  * Copyright 2000-2011 The OpenLDAP Foundation.
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted only as authorized by the OpenLDAP
  10  * Public License.
  11  *
  12  * A copy of this license is available in the file LICENSE in the
  13  * top-level directory of the distribution or, alternatively, at
  14  * <http://www.OpenLDAP.org/license.html>.
  15  */
  16
  17 #include <string.h>
  18 #include <sys/types.h>
  19 #include <assert.h>
  20 #include "midl.h"
  21
  22 typedef unsigned long pgno_t;
  23
  24 /* Sort the IDLs from highest to lowest */
  25 #define IDL_CMP(x,y)     ( (x) > (y) ? -1 : (x) < (y) )
  26
  27 /* Sort the IDL2s from lowest to highest */
  28 #define IDL2_CMP(x,y)    ( (x) < (y) ? -1 : (x) > (y) )
  29
  30 unsigned mdb_midl_search( ID *ids, ID id )
  31 {
  32         /*
  33          * binary search of id in ids
  34          * if found, returns position of id
  35          * if not found, returns first position greater than id
  36          */
  37         unsigned base = 0;
  38         unsigned cursor = 0;
  39         int val = 0;
  40         unsigned n = ids[0];
  41
  42         while( 0 < n ) {
  43                 int pivot = n >> 1;
  44                 cursor = base + pivot;
  45                 val = IDL_CMP( id, ids[cursor + 1] );
  46
  47                 if( val < 0 ) {
  48                         n = pivot;
  49
  50                 } else if ( val > 0 ) {
  51                         base = cursor + 1;
  52                         n -= pivot + 1;
  53
  54                 } else {
  55                         return cursor + 1;
  56                 }
  57         }
  58
  59         if( val > 0 ) {
  60                 return cursor + 2;
  61         } else {
  62                 return cursor + 1;
  63         }
  64 }
  65
  66 int mdb_midl_insert( ID *ids, ID id )
  67 {
  68         unsigned x, i;
  69
  70         if (MDB_IDL_IS_RANGE( ids )) {
  71                 /* if already in range, treat as a dup */
  72                 if (id >= MDB_IDL_FIRST(ids) && id <= MDB_IDL_LAST(ids))
  73                         return -1;
  74                 if (id < MDB_IDL_FIRST(ids))
  75                         ids[1] = id;
  76                 else if (id > MDB_IDL_LAST(ids))
  77                         ids[2] = id;
  78                 return 0;
  79         }
  80
  81         x = mdb_midl_search( ids, id );
  82         assert( x > 0 );
  83
  84         if( x < 1 ) {
  85                 /* internal error */
  86                 return -2;
  87         }
  88
  89         if ( x <= ids[0] && ids[x] == id ) {
  90                 /* duplicate */
  91                 return -1;
  92         }
  93
  94         if ( ++ids[0] >= MDB_IDL_DB_MAX ) {
  95                 if( id < ids[1] ) {
  96                         ids[1] = id;
  97                         ids[2] = ids[ids[0]-1];
  98                 } else if ( ids[ids[0]-1] < id ) {
  99                         ids[2] = id;
 100                 } else {
 101                         ids[2] = ids[ids[0]-1];
 102                 }
 103                 ids[0] = NOID;
 104
 105         } else {
 106                 /* insert id */
 107                 for (i=ids[0]; i>x; i--)
 108                         ids[i] = ids[i-1];
 109                 ids[x] = id;
 110         }
 111
 112         return 0;
 113 }
 114
 115 unsigned mdb_midl2_search( MIDL2 *ids, MIDL2 *id )
 116 {
 117         /*
 118          * binary search of id in ids
 119          * if found, returns position of id
 120          * if not found, returns first position greater than id
 121          */
 122         unsigned base = 0;
 123         unsigned cursor = 0;
 124         int val = 0;
 125         unsigned n = ids[0].mid;
 126
 127         while( 0 < n ) {
 128                 int pivot = n >> 1;
 129                 cursor = base + pivot;
 130                 val = IDL2_CMP( id->mid, ids[cursor + 1].mid );
 131
 132                 if( val < 0 ) {
 133                         n = pivot;
 134
 135                 } else if ( val > 0 ) {
 136                         base = cursor + 1;
 137                         n -= pivot + 1;
 138
 139                 } else {
 140                         return cursor + 1;
 141                 }
 142         }
 143
 144         if( val > 0 ) {
 145                 return cursor + 2;
 146         } else {
 147                 return cursor + 1;
 148         }
 149 }
 150
 151 int mdb_midl2_insert( MIDL2 *ids, MIDL2 *id )
 152 {
 153         unsigned x, i;
 154
 155         x = mdb_midl2_search( ids, id );
 156         assert( x > 0 );
 157
 158         if( x < 1 ) {
 159                 /* internal error */
 160                 return -2;
 161         }
 162
 163         if ( x <= ids[0].mid && ids[x].mid == id->mid ) {
 164                 /* duplicate */
 165                 return -1;
 166         }
 167
 168         if ( ids[0].mid >= MDB_IDL_DB_MAX ) {
 169                 /* too big */
 170                 return -2;
 171
 172         } else {
 173                 /* insert id */
 174                 ids[0].mid++;
 175                 for (i=ids[0].mid; i>x; i--)
 176                         ids[i] = ids[i-1];
 177                 ids[x] = *id;
 178         }
 179
 180         return 0;
 181 }