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