/* $OpenLDAP$ */
/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
*
- * Copyright 2000-2004 The OpenLDAP Foundation.
+ * Copyright 2000-2005 The OpenLDAP Foundation.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* a B-Tree with sorted duplicates to store all the children of a node under
* the same key. Also, the first item under the key contains the entry's own
* rdn and the ID of the node's parent, to allow bottom-up tree traversal as
- * well as top-down. To keep this info first in the list, the nrdnlen is set
- * to the negative of its value.
+ * well as top-down. To keep this info first in the list, the high bit of all
+ * subsequent nrdnlen's is always set. This means we can only accomodate
+ * RDNs up to length 32767, but that's fine since full DNs are already
+ * restricted to 8192.
*
* The diskNode is a variable length structure. This definition is not
* directly usable for in-memory manipulation.
*/
typedef struct diskNode {
- ID entryID;
- short nrdnlen;
- char nrdn[1];
- char rdn[1];
+ unsigned char nrdnlen[2];
+ unsigned char nrdn[1];
+ unsigned char rdn[1];
+ unsigned char entryID[sizeof(ID)];
} diskNode;
-/* Sort function for the sorted duplicate data items of a dn2id key.
- * Sorts based on normalized RDN, in length order.
- */
-int
-hdb_dup_compare(
- DB *db,
- const DBT *usrkey,
- const DBT *curkey )
-{
- signed char *u = (signed char *)&(((diskNode *)(usrkey->data))->nrdnlen);
- signed char *c = (signed char *)&(((diskNode *)(curkey->data))->nrdnlen);
- int rc, i;
-
- /* data is not aligned, cannot compare directly */
-#ifdef WORDS_BIGENDIAN
- for( i = 0; i < (int)sizeof(short); i++)
-#else
- for( i = sizeof(short)-1; i >= 0; i--)
-#endif
- {
- rc = u[i] - c[i];
- if( rc ) return rc;
- }
- return strcmp( u+sizeof(short), c+sizeof(short) );
-}
-
/* This function constructs a full DN for a given entry.
*/
int hdb_fix_dn(
struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
DB *db = bdb->bi_dn2id->bdi_db;
DBT key, data;
+ ID nid;
int rc, rlen, nrlen;
diskNode *d;
char *ptr;
}
d = op->o_tmpalloc(sizeof(diskNode) + rlen + nrlen, op->o_tmpmemctx);
- d->entryID = e->e_id;
- d->nrdnlen = nrlen;
+ d->nrdnlen[1] = nrlen & 0xff;
+ d->nrdnlen[0] = (nrlen >> 8) | 0x80;
ptr = lutil_strncopy( d->nrdn, e->e_nname.bv_val, nrlen );
*ptr++ = '\0';
ptr = lutil_strncopy( ptr, e->e_name.bv_val, rlen );
- *ptr = '\0';
+ *ptr++ = '\0';
+ BDB_ID2DISK( e->e_id, ptr );
DBTzero(&key);
DBTzero(&data);
- key.data = &eip->bei_id;
+ key.data = &nid;
key.size = sizeof(ID);
key.flags = DB_DBT_USERMEM;
+ BDB_ID2DISK( eip->bei_id, &nid );
/* Need to make dummy root node once. Subsequent attempts
* will fail harmlessly.
rc = db->put( db, txn, &key, &data, DB_NODUPDATA );
if (rc == 0) {
- key.data = &e->e_id;
- d->entryID = eip->bei_id;
- d->nrdnlen = 0 - nrlen;
+ BDB_ID2DISK( e->e_id, &nid );
+ BDB_ID2DISK( eip->bei_id, ptr );
+ d->nrdnlen[0] ^= 0x80;
rc = db->put( db, txn, &key, &data, DB_NODUPDATA );
}
DBC *cursor;
diskNode *d;
int rc, nrlen;
+ ID nid;
DBTzero(&key);
key.size = sizeof(ID);
key.ulen = key.size;
- key.data = &eip->bei_id;
+ key.data = &nid;
key.flags = DB_DBT_USERMEM;
+ BDB_ID2DISK( eip->bei_id, &nid );
DBTzero(&data);
- data.size = sizeof(diskNode) + BEI(e)->bei_nrdn.bv_len;
+ data.size = sizeof(diskNode) + BEI(e)->bei_nrdn.bv_len - sizeof(ID) - 1;
data.ulen = data.size;
data.dlen = data.size;
data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
if ( rc ) return rc;
d = op->o_tmpalloc( data.size, op->o_tmpmemctx );
- d->entryID = e->e_id;
- d->nrdnlen = BEI(e)->bei_nrdn.bv_len;
+ d->nrdnlen[1] = BEI(e)->bei_nrdn.bv_len & 0xff;
+ d->nrdnlen[0] = (BEI(e)->bei_nrdn.bv_len >> 8) | 0x80;
strcpy( d->nrdn, BEI(e)->bei_nrdn.bv_val );
data.data = d;
/* Delete our ID from the parent's list */
- rc = cursor->c_get( cursor, &key, &data, DB_GET_BOTH | DB_RMW );
- if ( rc == 0 )
- rc = cursor->c_del( cursor, 0 );
+ rc = cursor->c_get( cursor, &key, &data, DB_GET_BOTH_RANGE | DB_RMW );
+ if ( rc == 0 ) {
+ if ( !strcmp( d->nrdn, BEI(e)->bei_nrdn.bv_val ))
+ rc = cursor->c_del( cursor, 0 );
+ else
+ rc = DB_NOTFOUND;
+ }
/* Delete our ID from the tree. With sorted duplicates, this
* will leave any child nodes still hanging around. This is OK
* for modrdn, which will add our info back in later.
*/
if ( rc == 0 ) {
- key.data = &e->e_id;
+ BDB_ID2DISK( e->e_id, &nid );
rc = cursor->c_get( cursor, &key, &data, DB_SET | DB_RMW );
if ( rc == 0 )
rc = cursor->c_del( cursor, 0 );
int rc = 0, nrlen;
diskNode *d;
char *ptr;
- ID idp = ei->bei_parent->bei_id;
+ ID idp;
nrlen = dn_rdnlen( op->o_bd, in );
if (!nrlen) nrlen = in->bv_len;
key.data = &idp;
key.ulen = sizeof(ID);
key.flags = DB_DBT_USERMEM;
+ BDB_ID2DISK( ei->bei_parent->bei_id, &idp );
DBTzero(&data);
- data.size = sizeof(diskNode) + nrlen;
+ data.size = sizeof(diskNode) + nrlen - sizeof(ID) - 1;
data.ulen = data.size * 3;
- data.flags = DB_DBT_USERMEM;
+ data.dlen = data.ulen;
+ data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags );
if ( rc ) return rc;
d = op->o_tmpalloc( data.size * 3, op->o_tmpmemctx );
- d->nrdnlen = nrlen;
+ d->nrdnlen[1] = nrlen & 0xff;
+ d->nrdnlen[0] = (nrlen >> 8) | 0x80;
ptr = lutil_strncopy( d->nrdn, in->bv_val, nrlen );
*ptr = '\0';
data.data = d;
- rc = cursor->c_get( cursor, &key, &data, DB_GET_BOTH );
+ rc = cursor->c_get( cursor, &key, &data, DB_GET_BOTH_RANGE );
+ if ( rc == 0 && strncmp( d->nrdn, in->bv_val, nrlen )) {
+ rc = DB_NOTFOUND;
+ }
if ( rc == 0 ) {
- ei->bei_id = d->entryID;
+ ptr = data.data + data.size - sizeof(ID);
+ BDB_DISK2ID( ptr, &ei->bei_id );
ei->bei_rdn.bv_len = data.size - sizeof(diskNode) - nrlen;
ptr = d->nrdn + nrlen + 1;
ber_str2bv( ptr, ei->bei_rdn.bv_len, 1, &ei->bei_rdn );
diskNode *d;
char *ptr;
unsigned char *pt2;
+ ID nid;
DBTzero(&key);
key.size = sizeof(ID);
- key.data = &ei->bei_id;
+ key.data = &nid;
key.ulen = sizeof(ID);
key.flags = DB_DBT_USERMEM;
+ BDB_ID2DISK( ei->bei_id, &nid );
DBTzero(&data);
data.flags = DB_DBT_USERMEM;
rc = cursor->c_get( cursor, &key, &data, DB_SET );
if ( rc == 0 ) {
- if (d->nrdnlen >= 0) {
+ if (d->nrdnlen[0] & 0x80) {
rc = LDAP_OTHER;
} else {
db_recno_t dkids;
- *idp = d->entryID;
- ei->bei_nrdn.bv_len = 0 - d->nrdnlen;
+ ptr = data.data + data.size - sizeof(ID);
+ BDB_DISK2ID( ptr, idp );
+ ei->bei_nrdn.bv_len = (d->nrdnlen[0] << 8) | d->nrdnlen[1];
ber_str2bv( d->nrdn, ei->bei_nrdn.bv_len, 1, &ei->bei_nrdn );
ei->bei_rdn.bv_len = data.size - sizeof(diskNode) -
ei->bei_nrdn.bv_len;
key.size = sizeof(ID);
key.data = &e->e_id;
key.flags = DB_DBT_USERMEM;
+ BDB_ID2DISK( e->e_id, &id );
+ /* IDL cache is in host byte order */
if ( bdb->bi_idl_cache_size ) {
rc = bdb_idl_cache_get( bdb, db, &key, NULL );
if ( rc != LDAP_NO_SUCH_OBJECT ) {
return rc;
}
}
+
+ key.data = &id;
DBTzero(&data);
data.data = &d;
data.ulen = sizeof(d);
int rc;
EntryInfo *ei;
ID id;
+ ID nid;
ID dbuf;
ID *ids;
void *ptr;
)
{
if ( cx->bdb->bi_idl_cache_size ) {
+ cx->key.data = &cx->id;
cx->rc = bdb_idl_cache_get(cx->bdb, cx->db, &cx->key, cx->tmp);
if ( cx->rc == DB_NOTFOUND ) {
return cx->rc;
cx->data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
/* The first item holds the parent ID. Ignore it. */
+ cx->key.data = &cx->nid;
cx->rc = cx->dbc->c_get( cx->dbc, &cx->key, &cx->data, DB_SET );
if ( cx->rc ) {
cx->dbc->c_close( cx->dbc );
diskNode *d = (diskNode *)j;
short nrlen;
- AC_MEMCPY( &ei.bei_id, &d->entryID, sizeof(ID) );
- AC_MEMCPY( &nrlen, &d->nrdnlen, sizeof(d->nrdnlen) );
+ BDB_DISK2ID( j + len - sizeof(ID), &ei.bei_id );
+ nrlen = ((d->nrdnlen[0] ^ 0x80) << 8) | d->nrdnlen[1];
ei.bei_nrdn.bv_len = nrlen;
/* nrdn/rdn are set in-place.
* hdb_cache_load will copy them as needed
saveit:
if ( cx->bdb->bi_idl_cache_max_size ) {
+ cx->key.data = &cx->id;
bdb_idl_cache_put( cx->bdb, cx->db, &cx->key, cx->tmp, cx->rc );
}
;
for ( cx->id = bdb_idl_first( save, &idcurs );
cx->id != NOID;
cx->id = bdb_idl_next( save, &idcurs )) {
+ BDB_ID2DISK( cx->id, &cx->nid );
cx->ei = NULL;
hdb_dn2idl_internal( cx );
if ( !BDB_IDL_IS_ZERO( cx->tmp ))
#endif
cx.id = e->e_id;
+ BDB_ID2DISK( cx.id, &cx.nid );
cx.ei = e->e_id ? BEI(e) : &bdb->bi_cache.c_dntree;
cx.bdb = bdb;
cx.db = cx.bdb->bi_dn2id->bdi_db;
}
DBTzero(&cx.key);
- cx.key.data = &cx.id;
cx.key.ulen = sizeof(ID);
cx.key.size = sizeof(ID);
cx.key.flags = DB_DBT_USERMEM;
projects / openldap / blobdiff