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 #if BDB_IDL_BINARY_SEARCH
  20         /*
  21          * binary search of id in ids
  22          * if found, returns position of id
  23          * if not found, returns first postion greater than id
  24          */
  25         int base = 0;
  26         int cursor = 0;
  27         int val;
  28         int n = ids[0];
  29
  30         while( 0 < n ) {
  31                 int pivot = n >> 1;
  32                 cursor = base + pivot;
  33                 val = IDL_CMP( id, ids[cursor + 1] );
  34
  35                 if( val < 0 ) {
  36                         n = pivot;
  37
  38                 } else if ( val > 0 ) {
  39                         base = cursor + 1;
  40                         n -= pivot + 1;
  41
  42                 } else {
  43                         return cursor + 1;
  44                 }
  45         }
  46
  47         if( val > 0 ) {
  48                 return cursor + 2;
  49         } else {
  50                 return cursor + 1;
  51         }
  52 #else
  53         /* linear search */
  54         int i;
  55         for( i=1; i<=ids[0]; i++ ) {
  56                 if( id <= ids[i] ) {
  57                         return i;
  58                 }
  59         }
  60         return i;
  61 #endif
  62 }
  63
  64 static int idl_insert( ID *ids, ID id )
  65 {
  66         int x = bdb_idl_search( ids, id );
  67
  68         if( ids[x] == id ) {
  69                 /* duplicate */
  70                 return -1;
  71         }
  72
  73         if( x == 0 ) {
  74                 /* append the id */
  75                 ids[0]++;
  76                 ids[ids[0]] = id;
  77
  78         } else if ( ++ids[0] >= BDB_IDL_DB_MAX ) {
  79                 ids[0] = NOID;
  80
  81         } else {
  82                 /* insert id */
  83                 AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
  84                 ids[0]++;
  85                 ids[x] = id;
  86         }
  87
  88         return 0;
  89 }
  90
  91 static int idl_delete( ID *ids, ID id )
  92 {
  93         int x = bdb_idl_search( ids, id );
  94
  95         if( x == 0 || ids[x] != id ) {
  96                 /* not found */
  97                 return -1;
  98
  99         } else if ( --ids[0] == 0 ) {
 100                 if( x != 1 ) return -1;
 101
 102         } else {
 103                 AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
 104         }
 105
 106         return 0;
 107 }
 108
 109 int
 110 bdb_idl_insert_key(
 111     BackendDB   *be,
 112     DB                  *db,
 113         DB_TXN          *tid,
 114     DBT                 *key,
 115     ID                  id )
 116 {
 117         int     rc;
 118         ID ids[BDB_IDL_DB_SIZE];
 119         DBT data;
 120
 121         assert( id != NOID );
 122
 123         data.data = ids;
 124         data.ulen = sizeof( ids );
 125         data.flags = DB_DBT_USERMEM;
 126
 127         /* fetch the key and grab a write lock */
 128         rc = db->get( db, tid, key, &data, DB_RMW );
 129
 130         if( rc == DB_NOTFOUND ) {
 131                 ids[0] = 1;
 132                 ids[1] = id;
 133                 data.size = 2 * sizeof( ID );
 134
 135         } else if ( rc != 0 ) {
 136                 Debug( LDAP_DEBUG_ANY,
 137                         "=> bdb_idl_insert_key: get failed: %s (%d)\n",
 138                         db_strerror(rc), rc, 0 );
 139                 return rc;
 140
 141         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 142                 /* size not multiple of ID size */
 143                 Debug( LDAP_DEBUG_ANY,
 144                         "=> bdb_idl_insert_key: odd size: expected %ld multiple, got %ld\n",
 145                         (long) sizeof( ID ), (long) data.size, 0 );
 146                 return -1;
 147
 148         } else if ( BDB_IS_ALLIDS(ids) ) {
 149                 return 0;
 150
 151         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 152                 /* size mismatch */
 153                 Debug( LDAP_DEBUG_ANY,
 154                         "=> bdb_idl_insert_key: get size mismatch: expected %ld, got %ld\n",
 155                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 156                 return -1;
 157
 158         } else {
 159                 rc = idl_insert( ids, id );
 160
 161                 if( rc != 0 ) {
 162                         Debug( LDAP_DEBUG_ANY,
 163                                 "=> bdb_idl_insert_key: idl_insert failed (%d)\n",
 164                                 rc, 0, 0 );
 165                         return rc;
 166                 }
 167
 168                 data.size = (ids[0]+1) * sizeof( ID );
 169         }
 170
 171         /* store the key */
 172         rc = db->put( db, tid, key, &data, 0 );
 173
 174         if( rc != 0 ) {
 175                 Debug( LDAP_DEBUG_ANY,
 176                         "=> bdb_idl_insert_key: get failed: %s (%d)\n",
 177                         db_strerror(rc), rc, 0 );
 178         }
 179         return rc;
 180 }
 181
 182 int
 183 bdb_idl_delete_key(
 184     BackendDB   *be,
 185     DB                  *db,
 186         DB_TXN          *tid,
 187     DBT                 *key,
 188     ID                  id )
 189 {
 190         int     rc;
 191         ID ids[BDB_IDL_DB_SIZE];
 192         DBT data;
 193
 194         assert( id != NOID );
 195
 196         data.data = ids;
 197         data.ulen = sizeof( ids );
 198         data.flags = DB_DBT_USERMEM;
 199
 200         /* fetch the key and grab a write lock */
 201         rc = db->get( db, tid, key, &data, DB_RMW );
 202
 203         if ( rc != 0 ) {
 204                 Debug( LDAP_DEBUG_ANY,
 205                         "=> bdb_idl_delete_key: get failed: %s (%d)\n",
 206                         db_strerror(rc), rc, 0 );
 207                 return rc;
 208
 209         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 210                 /* size not multiple of ID size */
 211                 Debug( LDAP_DEBUG_ANY,
 212                         "=> bdb_idl_delete_key: odd size: expected %ld multiple, got %ld\n",
 213                         (long) sizeof( ID ), (long) data.size, 0 );
 214                 return -1;
 215
 216         } else if ( BDB_IS_ALLIDS(ids) ) {
 217                 return 0;
 218
 219         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 220                 /* size mismatch */
 221                 Debug( LDAP_DEBUG_ANY,
 222                         "=> bdb_idl_delete_key: get size mismatch: expected %ld, got %ld\n",
 223                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 224                 return -1;
 225
 226         } else {
 227                 rc = idl_delete( ids, id );
 228
 229                 if( rc != 0 ) {
 230                         Debug( LDAP_DEBUG_ANY,
 231                                 "=> bdb_idl_insert_key: idl_insert failed (%d)\n",
 232                                 rc, 0, 0 );
 233                         return rc;
 234                 }
 235
 236                 if( BDB_IS_ALLIDS(ids) ) {
 237                         /* delete the key */
 238                         rc = db->del( db, tid, key, 0 );
 239                         if( rc != 0 ) {
 240                                 Debug( LDAP_DEBUG_ANY,
 241                                         "=> bdb_idl_delete_key: delete failed: %s (%d)\n",
 242                                         db_strerror(rc), rc, 0 );
 243                         }
 244                         return rc;
 245                 }
 246
 247                 data.size = (ids[0]+1) * sizeof( ID );
 248         }
 249
 250         /* store the key */
 251         rc = db->put( db, tid, key, &data, 0 );
 252
 253         if( rc != 0 ) {
 254                 Debug( LDAP_DEBUG_ANY,
 255                         "=> bdb_idl_delete_key: put failed: %s (%d)\n",
 256                         db_strerror(rc), rc, 0 );
 257         }
 258
 259         return rc;
 260 }