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 int bdb_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 = 0;
  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 + 2;
  48         } else {
  49                 return cursor + 1;
  50         }
  51 }
  52
  53 static int idl_insert( ID *ids, ID id )
  54 {
  55         int x = bdb_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_DB_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 = bdb_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_DB_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                 Debug( LDAP_DEBUG_ANY,
 126                         "=> bdb_idl_insert_key: get failed: %s (%d)\n",
 127                         db_strerror(rc), rc, 0 );
 128                 return rc;
 129
 130         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 131                 /* size not multiple of ID size */
 132                 Debug( LDAP_DEBUG_ANY,
 133                         "=> bdb_idl_insert_key: odd size: expected %ld multiple, got %ld\n",
 134                         (long) sizeof( ID ), (long) data.size, 0 );
 135                 return -1;
 136
 137         } else if ( BDB_IS_ALLIDS(ids) ) {
 138                 return 0;
 139
 140         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 141                 /* size mismatch */
 142                 Debug( LDAP_DEBUG_ANY,
 143                         "=> bdb_idl_insert_key: get size mismatch: expected %ld, got %ld\n",
 144                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 145                 return -1;
 146
 147         } else {
 148                 rc = idl_insert( ids, id );
 149
 150                 if( rc != 0 ) return rc;
 151
 152                 data.size = (ids[0]+1) * sizeof( ID );
 153         }
 154
 155         /* store the key */
 156         rc = db->put( db, tid, key, &data, 0 );
 157
 158         if( rc != 0 ) {
 159                 Debug( LDAP_DEBUG_ANY,
 160                         "=> bdb_idl_insert_key: get failed: %s (%d)\n",
 161                         db_strerror(rc), rc, 0 );
 162         }
 163         return rc;
 164 }
 165
 166 int
 167 bdb_idl_delete_key(
 168     BackendDB   *be,
 169     DB                  *db,
 170         DB_TXN          *tid,
 171     DBT                 *key,
 172     ID                  id )
 173 {
 174         int     rc;
 175         ID ids[BDB_IDL_DB_SIZE];
 176         DBT data;
 177
 178         assert( id != NOID );
 179
 180         data.data = ids;
 181         data.ulen = sizeof( ids );
 182         data.flags = DB_DBT_USERMEM;
 183
 184         /* fetch the key and grab a write lock */
 185         rc = db->get( db, tid, key, &data, DB_RMW );
 186
 187         if ( rc != 0 ) {
 188                 Debug( LDAP_DEBUG_ANY,
 189                         "=> bdb_idl_delete_key: get failed: %s (%d)\n",
 190                         db_strerror(rc), rc, 0 );
 191                 return rc;
 192
 193         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 194                 /* size not multiple of ID size */
 195                 Debug( LDAP_DEBUG_ANY,
 196                         "=> bdb_idl_delete_key: odd size: expected %ld multiple, got %ld\n",
 197                         (long) sizeof( ID ), (long) data.size, 0 );
 198                 return -1;
 199
 200         } else if ( BDB_IS_ALLIDS(ids) ) {
 201                 return 0;
 202
 203         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 204                 /* size mismatch */
 205                 Debug( LDAP_DEBUG_ANY,
 206                         "=> bdb_idl_delete_key: get size mismatch: expected %ld, got %ld\n",
 207                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 208                 return -1;
 209
 210         } else {
 211                 rc = idl_delete( ids, id );
 212
 213                 if( rc != 0 ) return rc;
 214
 215                 if( BDB_IS_ALLIDS(ids) ) {
 216                         /* delete the key */
 217                         rc = db->del( db, tid, key, 0 );
 218                         if( rc != 0 ) {
 219                                 Debug( LDAP_DEBUG_ANY,
 220                                         "=> bdb_idl_delete_key: delete failed: %s (%d)\n",
 221                                         db_strerror(rc), rc, 0 );
 222                         }
 223                         return rc;
 224                 }
 225
 226                 data.size = (ids[0]+1) * sizeof( ID );
 227         }
 228
 229         /* store the key */
 230         rc = db->put( db, tid, key, &data, 0 );
 231
 232         if( rc != 0 ) {
 233                 Debug( LDAP_DEBUG_ANY,
 234                         "=> bdb_idl_delete_key: put failed: %s (%d)\n",
 235                         db_strerror(rc), rc, 0 );
 236         }
 237
 238         return rc;
 239 }