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
  12 #include <ac/string.h>
  13 #include <ac/socket.h>
  14
  15 #include "back-bdb.h"
  16
  17 #define BDB_IDL_SIZE    (1<<16)
  18 #define BDB_IDL_MAX             (BDB_IDL_SIZE-16)
  19 #define BDB_IDL_ALLOC   (BDB_IDL_MAX * sizeof(ID))
  20
  21 #define BDB_IS_ALLIDS(ids)      ((ids)[0] == NOID)
  22
  23 static int idl_search( ID *ids, ID id )
  24 {
  25         /* we should replace this a binary search as ids is sorted */
  26         int i;
  27         int n = (int) ids[0];
  28
  29         for( i = 1; i <= n; i++ ) {
  30                 if( id <= ids[i] ) {
  31                         return i;
  32                 }
  33         }
  34
  35         return 0;
  36 }
  37
  38 static int idl_insert( ID *ids, ID id )
  39 {
  40         int x = idl_search( ids, id );
  41
  42         if( ids[x] == id ) {
  43                 /* duplicate */
  44                 return -1;
  45         }
  46
  47         if( x == 0 ) {
  48                 /* append the id */
  49                 ids[0]++;
  50                 ids[ids[0]] = id;
  51
  52         } else if ( ++ids[0] >= BDB_IDL_MAX ) {
  53                 ids[0] = NOID;
  54
  55         } else {
  56                 /* insert id */
  57                 AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
  58                 ids[0]++;
  59                 ids[x] = id;
  60         }
  61
  62         return 0;
  63 }
  64
  65 static int idl_delete( ID *ids, ID id )
  66 {
  67         int x = idl_search( ids, id );
  68
  69         if( x == 0 || ids[x] != id ) {
  70                 /* not found */
  71                 return -1;
  72
  73         } else if ( --ids[0] == 0 ) {
  74                 if( x != 1 ) return -1;
  75
  76         } else {
  77                 AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
  78         }
  79
  80         return 0;
  81 }
  82
  83 int
  84 bdb_idl_insert_key(
  85     BackendDB   *be,
  86     DB                  *db,
  87         DB_TXN          *tid,
  88     DBT                 *key,
  89     ID                  id )
  90 {
  91         int     rc;
  92         ID ids[BDB_IDL_SIZE];
  93         DBT data;
  94
  95         assert( id != NOID );
  96
  97         data.data = ids;
  98         data.ulen = sizeof( ids );
  99         data.flags = DB_DBT_USERMEM;
 100
 101         /* fetch the key and grab a write lock */
 102         rc = db->get( db, tid, key, &data, DB_RMW );
 103
 104         if( rc == DB_NOTFOUND ) {
 105                 ids[0] = 1;
 106                 ids[1] = id;
 107                 data.size = 2 * sizeof( ID );
 108
 109         } else if ( rc != 0 ) {
 110                 return rc;
 111
 112         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 113                 /* size not multiple of ID size */
 114                 return -1;
 115
 116         } else if ( BDB_IS_ALLIDS(ids) ) {
 117                 return 0;
 118
 119         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 120                 /* size mismatch */
 121                 return -1;
 122
 123         } else {
 124                 rc = idl_insert( ids, id );
 125
 126                 if( rc != 0 ) return rc;
 127
 128                 data.size = (ids[0]+1) * sizeof( ID );
 129         }
 130
 131         /* store the key */
 132         rc = db->put( db, tid, key, &data, 0 );
 133
 134         return rc;
 135 }
 136
 137 int
 138 bdb_idl_delete_key(
 139     BackendDB   *be,
 140     DB                  *db,
 141         DB_TXN          *tid,
 142     DBT                 *key,
 143     ID                  id )
 144 {
 145         int     rc;
 146         ID ids[BDB_IDL_SIZE];
 147         DBT data;
 148
 149         assert( id != NOID );
 150
 151         data.data = ids;
 152         data.ulen = sizeof( ids );
 153         data.flags = DB_DBT_USERMEM;
 154
 155         /* fetch the key and grab a write lock */
 156         rc = db->get( db, tid, key, &data, DB_RMW );
 157
 158         if ( rc != 0 ) {
 159                 return rc;
 160
 161         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 162                 /* size not multiple of ID size */
 163                 return -1;
 164
 165         } else if ( BDB_IS_ALLIDS(ids) ) {
 166                 return 0;
 167
 168         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 169                 /* size mismatch */
 170                 return -1;
 171
 172         } else {
 173                 rc = idl_delete( ids, id );
 174
 175                 if( rc != 0 ) return rc;
 176
 177                 if( BDB_IS_ALLIDS(ids) ) {
 178                         /* delete the key */
 179                         rc = db->del( db, tid, key, 0 );
 180                         return rc;
 181                 }
 182
 183                 data.size = (ids[0]+1) * sizeof( ID );
 184         }
 185
 186         /* store the key */
 187         rc = db->put( db, tid, key, &data, 0 );
 188
 189         return rc;
 190 }