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]+1 >= BDB_IDL_MAX ) {
  53                 ids[0] = NOID;
  54
  55         } else {
  56                 /* insert id */
  57                 AC_MEMCPY( &ids[x+1], &ids[x], (1+ids[0]-x) * sizeof(ID) );
  58                 ids[0]++;
  59                 ids[x] = id;
  60         }
  61
  62         return 0;
  63 }
  64
  65 int
  66 bdb_idl_insert_key(
  67     BackendDB   *be,
  68     DB                  *db,
  69         DB_TXN          *tid,
  70     DBT                 *key,
  71     ID                  id )
  72 {
  73         int     rc;
  74         ID ids[BDB_IDL_SIZE];
  75         DBT data;
  76
  77         assert( id != NOID );
  78
  79         data.data = ids;
  80         data.ulen = sizeof( ids );
  81         data.flags = DB_DBT_USERMEM;
  82
  83         /* fetch the key and grab a write lock */
  84         rc = db->get( db, tid, key, &data, DB_RMW );
  85
  86         if( rc == DB_NOTFOUND ) {
  87                 ids[0] = 1;
  88                 ids[1] = id;
  89                 data.size = 2 * sizeof( ID );
  90
  91         } else if ( rc != 0 ) {
  92                 return rc;
  93
  94         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
  95                 /* size not multiple of ID size */
  96                 return -1;
  97
  98         } else if ( BDB_IS_ALLIDS(ids) ) {
  99                 return 0;
 100
 101         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 102                 /* size mismatch */
 103                 return -1;
 104
 105         } else {
 106                 rc = idl_insert( ids, id );
 107
 108                 if( rc != 0 ) return rc;
 109
 110                 data.size = (ids[0]+1) * sizeof( ID );
 111         }
 112
 113         /* store the key */
 114         rc = db->put( db, tid, key, &data, 0 );
 115
 116         return rc;
 117 }