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 #define IDL_DEBUG
  18 #ifdef IDL_DEBUG
  19 void idl_dump( ID *ids )
  20 {
  21         if( BDB_IDL_IS_RANGE( ids ) ) {
  22                 Debug( LDAP_DEBUG_ANY,
  23                         "IDL: range %ld - %ld\n", (long) ids[0], 0, 0 );
  24
  25         } else {
  26                 ID i;
  27                 Debug( LDAP_DEBUG_ANY, "IDL: size %ld", (long) ids[0], 0, 0 );
  28
  29                 for( i=1; i<=ids[0]; i++ ) {
  30                         if( i % 16 == 1 ) {
  31                                 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
  32                         }
  33                         Debug( LDAP_DEBUG_ANY, "  %02lx", ids[i], 0, 0 );
  34                 }
  35
  36                 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
  37         }
  38 }
  39 #endif
  40
  41 unsigned bdb_idl_search( ID *ids, ID id )
  42 {
  43 #define IDL_BINARY_SEARCH
  44 #ifdef IDL_BINARY_SEARCH
  45         /*
  46          * binary search of id in ids
  47          * if found, returns position of id
  48          * if not found, returns first postion greater than id
  49          */
  50         unsigned base = 0;
  51         unsigned cursor = 0;
  52         int val;
  53         unsigned n = ids[0];
  54
  55         while( 0 < n ) {
  56                 int pivot = n >> 1;
  57                 cursor = base + pivot;
  58                 val = IDL_CMP( id, ids[cursor + 1] );
  59
  60                 if( val < 0 ) {
  61                         n = pivot;
  62
  63                 } else if ( val > 0 ) {
  64                         base = cursor + 1;
  65                         n -= pivot + 1;
  66
  67                 } else {
  68                         return cursor + 1;
  69                 }
  70         }
  71
  72         if( val > 0 ) {
  73                 return cursor + 2;
  74         } else {
  75                 return cursor + 1;
  76         }
  77
  78 #else
  79         /* (reverse) linear search */
  80         int i;
  81         for( i=ids[0]; i; i-- ) {
  82                 if( id > ids[i] ) {
  83                         break;
  84                 }
  85         }
  86         return i+1;
  87 #endif
  88 }
  89
  90 static int idl_insert( ID *ids, ID id )
  91 {
  92         unsigned x = bdb_idl_search( ids, id );
  93
  94 #ifdef IDL_DEBUG
  95         Debug( LDAP_DEBUG_ANY, "insert: %04lx at %d\n", id, x, 0 );
  96         idl_dump( ids );
  97 #endif
  98
  99         assert( x > 0 );
 100
 101         if( x < 1 ) {
 102                 /* internal error */
 103                 return -2;
 104         }
 105
 106         if ( x <= ids[0] && ids[x] == id ) {
 107                 /* duplicate */
 108                 return -1;
 109         }
 110
 111         if ( ++ids[0] >= BDB_IDL_DB_MAX ) {
 112                 if( id < ids[1] ) {
 113                         ids[1] = id;
 114                         ids[2] = ids[ids[0]-1];
 115                 } else if ( ids[ids[0]-1] < id ) {
 116                         ids[2] = id;
 117                 } else {
 118                         ids[2] = ids[ids[0]-1];
 119                 }
 120                 ids[0] = NOID;
 121
 122         } else {
 123                 /* insert id */
 124                 AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
 125                 ids[x] = id;
 126         }
 127
 128 #ifdef IDL_DEBUG
 129         idl_dump( ids );
 130 #endif
 131
 132         return 0;
 133 }
 134
 135 static int idl_delete( ID *ids, ID id )
 136 {
 137         unsigned x = bdb_idl_search( ids, id );
 138
 139 #ifdef IDL_DEBUG
 140         Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", id, x, 0 );
 141         idl_dump( ids );
 142 #endif
 143
 144         assert( x > 0 );
 145
 146         if( x <= 0 ) {
 147                 /* internal error */
 148                 return -2;
 149         }
 150
 151         if( x > ids[0] || ids[x] != id ) {
 152                 /* not found */
 153                 return -1;
 154
 155         } else if ( --ids[0] == 0 ) {
 156                 if( x != 1 ) {
 157                         return -3;
 158                 }
 159
 160         } else {
 161                 AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
 162         }
 163
 164 #ifdef IDL_DEBUG
 165         idl_dump( ids );
 166 #endif
 167
 168         return 0;
 169 }
 170
 171 int
 172 bdb_idl_insert_key(
 173         BackendDB       *be,
 174         DB                      *db,
 175         DB_TXN          *tid,
 176         DBT                     *key,
 177         ID                      id )
 178 {
 179         int     rc;
 180         ID ids[BDB_IDL_DB_SIZE];
 181         DBT data;
 182
 183         /* for printable keys only */
 184         Debug( LDAP_DEBUG_ARGS,
 185                 "=> bdb_idl_insert_key: %s %ld\n",
 186                 key->data, (long) id, 0 );
 187
 188         assert( id != NOID );
 189
 190         data.data = ids;
 191         data.ulen = sizeof( ids );
 192         data.flags = DB_DBT_USERMEM;
 193
 194         /* fetch the key for read/modify/write */
 195         rc = db->get( db, tid, key, &data, DB_RMW );
 196
 197         if( rc == DB_NOTFOUND ) {
 198                 ids[0] = 1;
 199                 ids[1] = id;
 200                 data.size = 2 * sizeof( ID );
 201
 202         } else if ( rc != 0 ) {
 203                 Debug( LDAP_DEBUG_ANY,
 204                         "=> bdb_idl_insert_key: get failed: %s (%d)\n",
 205                         db_strerror(rc), rc, 0 );
 206                 return rc;
 207
 208         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 209                 /* size not multiple of ID size */
 210                 Debug( LDAP_DEBUG_ANY,
 211                         "=> bdb_idl_insert_key: odd size: expected %ld multiple, got %ld\n",
 212                         (long) sizeof( ID ), (long) data.size, 0 );
 213                 return -1;
 214
 215         } else if ( BDB_IDL_IS_RANGE(ids) ) {
 216                 if( id < ids[1] ) {
 217                         ids[1] = id;
 218                 } else if ( ids[2] > id ) {
 219                         ids[2] = id;
 220                 } else {
 221                         return 0;
 222                 }
 223
 224         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 225                 /* size mismatch */
 226                 Debug( LDAP_DEBUG_ANY,
 227                         "=> bdb_idl_insert_key: get size mismatch: expected %ld, got %ld\n",
 228                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 229                 return -1;
 230
 231         } else {
 232                 rc = idl_insert( ids, id );
 233
 234                 if( rc != 0 ) {
 235                         Debug( LDAP_DEBUG_ANY,
 236                                 "=> bdb_idl_insert_key: idl_insert failed (%d)\n",
 237                                 rc, 0, 0 );
 238                         return rc;
 239                 }
 240
 241                 if( BDB_IDL_IS_RANGE( ids ) ) {
 242                         data.size = BDB_IDL_RANGE_SIZE;
 243                 } else {
 244                         data.size = (ids[0]+1) * sizeof( ID );
 245                 }
 246         }
 247
 248         /* store the key */
 249         rc = db->put( db, tid, key, &data, 0 );
 250
 251         if( rc != 0 ) {
 252                 Debug( LDAP_DEBUG_ANY,
 253                         "=> bdb_idl_insert_key: get failed: %s (%d)\n",
 254                         db_strerror(rc), rc, 0 );
 255         }
 256         return rc;
 257 }
 258
 259 int
 260 bdb_idl_delete_key(
 261         BackendDB       *be,
 262         DB                      *db,
 263         DB_TXN          *tid,
 264         DBT                     *key,
 265         ID                      id )
 266 {
 267         int     rc;
 268         ID ids[BDB_IDL_DB_SIZE];
 269         DBT data;
 270
 271         /* for printable keys only */
 272         Debug( LDAP_DEBUG_ARGS,
 273                 "=> bdb_idl_delete_key: %s %ld\n",
 274                 key->data, (long) id, 0 );
 275
 276         assert( id != NOID );
 277
 278         data.data = ids;
 279         data.ulen = sizeof( ids );
 280         data.flags = DB_DBT_USERMEM;
 281
 282         /* fetch the key for read/modify/write */
 283         rc = db->get( db, tid, key, &data, DB_RMW );
 284
 285         if ( rc != 0 ) {
 286                 Debug( LDAP_DEBUG_ANY,
 287                         "=> bdb_idl_delete_key: get failed: %s (%d)\n",
 288                         db_strerror(rc), rc, 0 );
 289                 return rc;
 290
 291         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 292                 /* size not multiple of ID size */
 293                 Debug( LDAP_DEBUG_ANY,
 294                         "=> bdb_idl_delete_key: odd size: expected %ld multiple, got %ld\n",
 295                         (long) sizeof( ID ), (long) data.size, 0 );
 296                 return -1;
 297
 298         } else if ( BDB_IDL_IS_RANGE(ids) ) {
 299                 return 0;
 300
 301         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 302                 /* size mismatch */
 303                 Debug( LDAP_DEBUG_ANY,
 304                         "=> bdb_idl_delete_key: get size mismatch: expected %ld, got %ld\n",
 305                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 306                 return -1;
 307
 308         } else {
 309                 rc = idl_delete( ids, id );
 310
 311                 if( rc != 0 ) {
 312                         Debug( LDAP_DEBUG_ANY,
 313                                 "=> bdb_idl_delete_key: idl_delete failed (%d)\n",
 314                                 rc, 0, 0 );
 315                         return rc;
 316                 }
 317
 318                 if( ids[0] == 0 ) {
 319                         /* delete the key */
 320                         rc = db->del( db, tid, key, 0 );
 321                         if( rc != 0 ) {
 322                                 Debug( LDAP_DEBUG_ANY,
 323                                         "=> bdb_idl_delete_key: delete failed: %s (%d)\n",
 324                                         db_strerror(rc), rc, 0 );
 325                         }
 326                         return rc;
 327                 }
 328
 329                 data.size = (ids[0]+1) * sizeof( ID );
 330         }
 331
 332         /* store the key */
 333         rc = db->put( db, tid, key, &data, 0 );
 334
 335         if( rc != 0 ) {
 336                 Debug( LDAP_DEBUG_ANY,
 337                         "=> bdb_idl_delete_key: put failed: %s (%d)\n",
 338                         db_strerror(rc), rc, 0 );
 339         }
 340
 341         return rc;
 342 }