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