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