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 #define IDL_CMP(x,y)    ( x < y ? -1 : ( x > y ? 1 : 0 ) )
  24
  25 static int idl_search( ID *ids, ID id )
  26 {
  27         /*
  28          * binary search of id in ids
  29          * if found, returns position of id
  30          * if not found, returns first postion greater than id
  31          */
  32         int base = 0;
  33         int cursor;
  34         int val;
  35         int n = ids[0];
  36
  37         while( 0 < n ) {
  38                 int pivot = n >> 1;
  39                 cursor = base + pivot;
  40                 val = IDL_CMP( id, ids[cursor + 1] );
  41
  42                 if( val < 0 ) {
  43                         n = pivot;
  44
  45                 } else if ( val > 0 ) {
  46                         base = cursor + 1;
  47                         n -= pivot + 1;
  48
  49                 } else {
  50                         return cursor + 1;
  51                 }
  52         }
  53
  54         if( val < 0 ) {
  55                 return cursor + 1;
  56         } else {
  57                 return cursor + 2;
  58         }
  59 }
  60
  61 static int idl_insert( ID *ids, ID id )
  62 {
  63         int x = idl_search( ids, id );
  64
  65         if( ids[x] == id ) {
  66                 /* duplicate */
  67                 return -1;
  68         }
  69
  70         if( x == 0 ) {
  71                 /* append the id */
  72                 ids[0]++;
  73                 ids[ids[0]] = id;
  74
  75         } else if ( ++ids[0] >= BDB_IDL_MAX ) {
  76                 ids[0] = NOID;
  77
  78         } else {
  79                 /* insert id */
  80                 AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
  81                 ids[0]++;
  82                 ids[x] = id;
  83         }
  84
  85         return 0;
  86 }
  87
  88 static int idl_delete( ID *ids, ID id )
  89 {
  90         int x = idl_search( ids, id );
  91
  92         if( x == 0 || ids[x] != id ) {
  93                 /* not found */
  94                 return -1;
  95
  96         } else if ( --ids[0] == 0 ) {
  97                 if( x != 1 ) return -1;
  98
  99         } else {
 100                 AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
 101         }
 102
 103         return 0;
 104 }
 105
 106 int
 107 bdb_idl_insert_key(
 108     BackendDB   *be,
 109     DB                  *db,
 110         DB_TXN          *tid,
 111     DBT                 *key,
 112     ID                  id )
 113 {
 114         int     rc;
 115         ID ids[BDB_IDL_SIZE];
 116         DBT data;
 117
 118         assert( id != NOID );
 119
 120         data.data = ids;
 121         data.ulen = sizeof( ids );
 122         data.flags = DB_DBT_USERMEM;
 123
 124         /* fetch the key and grab a write lock */
 125         rc = db->get( db, tid, key, &data, DB_RMW );
 126
 127         if( rc == DB_NOTFOUND ) {
 128                 ids[0] = 1;
 129                 ids[1] = id;
 130                 data.size = 2 * sizeof( ID );
 131
 132         } else if ( rc != 0 ) {
 133                 return rc;
 134
 135         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 136                 /* size not multiple of ID size */
 137                 return -1;
 138
 139         } else if ( BDB_IS_ALLIDS(ids) ) {
 140                 return 0;
 141
 142         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 143                 /* size mismatch */
 144                 return -1;
 145
 146         } else {
 147                 rc = idl_insert( ids, id );
 148
 149                 if( rc != 0 ) return rc;
 150
 151                 data.size = (ids[0]+1) * sizeof( ID );
 152         }
 153
 154         /* store the key */
 155         rc = db->put( db, tid, key, &data, 0 );
 156
 157         return rc;
 158 }
 159
 160 int
 161 bdb_idl_delete_key(
 162     BackendDB   *be,
 163     DB                  *db,
 164         DB_TXN          *tid,
 165     DBT                 *key,
 166     ID                  id )
 167 {
 168         int     rc;
 169         ID ids[BDB_IDL_SIZE];
 170         DBT data;
 171
 172         assert( id != NOID );
 173
 174         data.data = ids;
 175         data.ulen = sizeof( ids );
 176         data.flags = DB_DBT_USERMEM;
 177
 178         /* fetch the key and grab a write lock */
 179         rc = db->get( db, tid, key, &data, DB_RMW );
 180
 181         if ( rc != 0 ) {
 182                 return rc;
 183
 184         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 185                 /* size not multiple of ID size */
 186                 return -1;
 187
 188         } else if ( BDB_IS_ALLIDS(ids) ) {
 189                 return 0;
 190
 191         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 192                 /* size mismatch */
 193                 return -1;
 194
 195         } else {
 196                 rc = idl_delete( ids, id );
 197
 198                 if( rc != 0 ) return rc;
 199
 200                 if( BDB_IS_ALLIDS(ids) ) {
 201                         /* delete the key */
 202                         rc = db->del( db, tid, key, 0 );
 203                         return rc;
 204                 }
 205
 206                 data.size = (ids[0]+1) * sizeof( ID );
 207         }
 208
 209         /* store the key */
 210         rc = db->put( db, tid, key, &data, 0 );
 211
 212         return rc;
 213 }