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 static unsigned mdb_midl_search( IDL ids, ID id )
  32 {
  33         /*
  34          * binary search of id in ids
  35          * if found, returns position of id
  36          * if not found, returns first position greater than id
  37          */
  38         unsigned base = 0;
  39         unsigned cursor = 0;
  40         int val = 0;
  41         unsigned n = ids[0];
  42
  43         while( 0 < n ) {
  44                 int pivot = n >> 1;
  45                 cursor = base + pivot;
  46                 val = CMP( ids[cursor + 1], id );
  47
  48                 if( val < 0 ) {
  49                         n = pivot;
  50
  51                 } else if ( val > 0 ) {
  52                         base = cursor + 1;
  53                         n -= pivot + 1;
  54
  55                 } else {
  56                         return cursor + 1;
  57                 }
  58         }
  59
  60         if( val > 0 ) {
  61                 return cursor + 2;
  62         } else {
  63                 return cursor + 1;
  64         }
  65 }
  66
  67 int mdb_midl_insert( IDL ids, ID id )
  68 {
  69         unsigned x, i;
  70
  71         if (MDB_IDL_IS_RANGE( ids )) {
  72                 /* if already in range, treat as a dup */
  73                 if (id >= MDB_IDL_FIRST(ids) && id <= MDB_IDL_LAST(ids))
  74                         return -1;
  75                 if (id < MDB_IDL_FIRST(ids))
  76                         ids[1] = id;
  77                 else if (id > MDB_IDL_LAST(ids))
  78                         ids[2] = id;
  79                 return 0;
  80         }
  81
  82         x = mdb_midl_search( ids, id );
  83         assert( x > 0 );
  84
  85         if( x < 1 ) {
  86                 /* internal error */
  87                 return -2;
  88         }
  89
  90         if ( x <= ids[0] && ids[x] == id ) {
  91                 /* duplicate */
  92                 return -1;
  93         }
  94
  95         if ( ++ids[0] >= MDB_IDL_DB_MAX ) {
  96                 if( id < ids[1] ) {
  97                         ids[1] = id;
  98                         ids[2] = ids[ids[0]-1];
  99                 } else if ( ids[ids[0]-1] < id ) {
 100                         ids[2] = id;
 101                 } else {
 102                         ids[2] = ids[ids[0]-1];
 103                 }
 104                 ids[0] = NOID;
 105
 106         } else {
 107                 /* insert id */
 108                 for (i=ids[0]; i>x; i--)
 109                         ids[i] = ids[i-1];
 110                 ids[x] = id;
 111         }
 112
 113         return 0;
 114 }
 115
 116 unsigned mdb_mid2l_search( ID2L ids, ID id )
 117 {
 118         /*
 119          * binary search of id in ids
 120          * if found, returns position of id
 121          * if not found, returns first position greater than id
 122          */
 123         unsigned base = 0;
 124         unsigned cursor = 0;
 125         int val = 0;
 126         unsigned n = ids[0].mid;
 127
 128         while( 0 < n ) {
 129                 int pivot = n >> 1;
 130                 cursor = base + pivot;
 131                 val = CMP( id, ids[cursor + 1].mid );
 132
 133                 if( val < 0 ) {
 134                         n = pivot;
 135
 136                 } else if ( val > 0 ) {
 137                         base = cursor + 1;
 138                         n -= pivot + 1;
 139
 140                 } else {
 141                         return cursor + 1;
 142                 }
 143         }
 144
 145         if( val > 0 ) {
 146                 return cursor + 2;
 147         } else {
 148                 return cursor + 1;
 149         }
 150 }
 151
 152 int mdb_mid2l_insert( ID2L ids, ID2 *id )
 153 {
 154         unsigned x, i;
 155
 156         x = mdb_mid2l_search( ids, id->mid );
 157         assert( x > 0 );
 158
 159         if( x < 1 ) {
 160                 /* internal error */
 161                 return -2;
 162         }
 163
 164         if ( x <= ids[0].mid && ids[x].mid == id->mid ) {
 165                 /* duplicate */
 166                 return -1;
 167         }
 168
 169         if ( ids[0].mid >= MDB_IDL_DB_MAX ) {
 170                 /* too big */
 171                 return -2;
 172
 173         } else {
 174                 /* insert id */
 175                 ids[0].mid++;
 176                 for (i=ids[0].mid; i>x; i--)
 177                         ids[i] = ids[i-1];
 178                 ids[x] = *id;
 179         }
 180
 181         return 0;
 182 }
 183 /** @} */
 184 /** @} */