git.sur5r.net Git - openldap/blob - servers/slapd/back-bdb/idl.c

   1 /* idl.c - ldap id list handling routines */
   2 /* $OpenLDAP$ */
   3 /*
   4  * Copyright 1998-2000 The OpenLDAP Foundation, All Rights Reserved.
   5  * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
   6  */
   7
   8 #include "portable.h"
   9
  10 #include <stdio.h>
  11 #include <ac/string.h>
  12
  13 #include "back-bdb.h"
  14
  15 #define IDL_CMP(x,y)    ( x < y ? -1 : ( x > y ? 1 : 0 ) )
  16
  17 static int idl_search( ID *ids, ID id )
  18 {
  19         /*
  20          * binary search of id in ids
  21          * if found, returns position of id
  22          * if not found, returns first postion greater than id
  23          */
  24         int base = 0;
  25         int cursor;
  26         int val;
  27         int n = ids[0];
  28
  29         while( 0 < n ) {
  30                 int pivot = n >> 1;
  31                 cursor = base + pivot;
  32                 val = IDL_CMP( id, ids[cursor + 1] );
  33
  34                 if( val < 0 ) {
  35                         n = pivot;
  36
  37                 } else if ( val > 0 ) {
  38                         base = cursor + 1;
  39                         n -= pivot + 1;
  40
  41                 } else {
  42                         return cursor + 1;
  43                 }
  44         }
  45
  46         if( val < 0 ) {
  47                 return cursor + 1;
  48         } else {
  49                 return cursor + 2;
  50         }
  51 }
  52
  53 static int idl_insert( ID *ids, ID id )
  54 {
  55         int x = idl_search( ids, id );
  56
  57         if( ids[x] == id ) {
  58                 /* duplicate */
  59                 return -1;
  60         }
  61
  62         if( x == 0 ) {
  63                 /* append the id */
  64                 ids[0]++;
  65                 ids[ids[0]] = id;
  66
  67         } else if ( ++ids[0] >= BDB_IDL_MAX ) {
  68                 ids[0] = NOID;
  69
  70         } else {
  71                 /* insert id */
  72                 AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
  73                 ids[0]++;
  74                 ids[x] = id;
  75         }
  76
  77         return 0;
  78 }
  79
  80 static int idl_delete( ID *ids, ID id )
  81 {
  82         int x = idl_search( ids, id );
  83
  84         if( x == 0 || ids[x] != id ) {
  85                 /* not found */
  86                 return -1;
  87
  88         } else if ( --ids[0] == 0 ) {
  89                 if( x != 1 ) return -1;
  90
  91         } else {
  92                 AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
  93         }
  94
  95         return 0;
  96 }
  97
  98 int
  99 bdb_idl_insert_key(
 100     BackendDB   *be,
 101     DB                  *db,
 102         DB_TXN          *tid,
 103     DBT                 *key,
 104     ID                  id )
 105 {
 106         int     rc;
 107         ID ids[BDB_IDL_SIZE];
 108         DBT data;
 109
 110         assert( id != NOID );
 111
 112         data.data = ids;
 113         data.ulen = sizeof( ids );
 114         data.flags = DB_DBT_USERMEM;
 115
 116         /* fetch the key and grab a write lock */
 117         rc = db->get( db, tid, key, &data, DB_RMW );
 118
 119         if( rc == DB_NOTFOUND ) {
 120                 ids[0] = 1;
 121                 ids[1] = id;
 122                 data.size = 2 * sizeof( ID );
 123
 124         } else if ( rc != 0 ) {
 125                 return rc;
 126
 127         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 128                 /* size not multiple of ID size */
 129                 return -1;
 130
 131         } else if ( BDB_IS_ALLIDS(ids) ) {
 132                 return 0;
 133
 134         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 135                 /* size mismatch */
 136                 return -1;
 137
 138         } else {
 139                 rc = idl_insert( ids, id );
 140
 141                 if( rc != 0 ) return rc;
 142
 143                 data.size = (ids[0]+1) * sizeof( ID );
 144         }
 145
 146         /* store the key */
 147         rc = db->put( db, tid, key, &data, 0 );
 148
 149         return rc;
 150 }
 151
 152 int
 153 bdb_idl_delete_key(
 154     BackendDB   *be,
 155     DB                  *db,
 156         DB_TXN          *tid,
 157     DBT                 *key,
 158     ID                  id )
 159 {
 160         int     rc;
 161         ID ids[BDB_IDL_SIZE];
 162         DBT data;
 163
 164         assert( id != NOID );
 165
 166         data.data = ids;
 167         data.ulen = sizeof( ids );
 168         data.flags = DB_DBT_USERMEM;
 169
 170         /* fetch the key and grab a write lock */
 171         rc = db->get( db, tid, key, &data, DB_RMW );
 172
 173         if ( rc != 0 ) {
 174                 return rc;
 175
 176         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 177                 /* size not multiple of ID size */
 178                 return -1;
 179
 180         } else if ( BDB_IS_ALLIDS(ids) ) {
 181                 return 0;
 182
 183         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 184                 /* size mismatch */
 185                 return -1;
 186
 187         } else {
 188                 rc = idl_delete( ids, id );
 189
 190                 if( rc != 0 ) return rc;
 191
 192                 if( BDB_IS_ALLIDS(ids) ) {
 193                         /* delete the key */
 194                         rc = db->del( db, tid, key, 0 );
 195                         return rc;
 196                 }
 197
 198                 data.size = (ids[0]+1) * sizeof( ID );
 199         }
 200
 201         /* store the key */
 202         rc = db->put( db, tid, key, &data, 0 );
 203
 204         return rc;
 205 }