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