dn2id.c

/* dn2id.c - routines to deal with the dn2id index */
/* $OpenLDAP$ */
/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
 *
 * Copyright 2000-2007 The OpenLDAP Foundation.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted only as authorized by the OpenLDAP
 * Public License.
 *
 * A copy of this license is available in the file LICENSE in the
 * top-level directory of the distribution or, alternatively, at
 * <http://www.OpenLDAP.org/license.html>.
 */

#include "portable.h"

#include <stdio.h>
#include <ac/string.h>

#include "back-bdb.h"
#include "idl.h"
#include "lutil.h"

#define bdb_dn2id_lock					BDB_SYMBOL(dn2id_lock)

static int
bdb_dn2id_lock( struct bdb_info *bdb, struct berval *dn,
	int rw, u_int32_t locker, DB_LOCK *lock )
{
	int       rc;
	DBT       lockobj;
	int       db_rw;

	if (!locker)
		return 0;

	if (rw)
		db_rw = DB_LOCK_WRITE;
	else
		db_rw = DB_LOCK_READ;

	lockobj.data = dn->bv_val;
	lockobj.size = dn->bv_len;

	rc = LOCK_GET(bdb->bi_dbenv, locker, DB_LOCK_NOWAIT,
					&lockobj, db_rw, lock);
	return rc;
}

#ifndef BDB_HIER
int
bdb_dn2id_add(
	Operation *op,
	DB_TXN *txn,
	EntryInfo *eip,
	Entry		*e )
{
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
	DB *db = bdb->bi_dn2id->bdi_db;
	int		rc;
	DBT		key, data;
	ID		nid;
	char		*buf;
	struct berval	ptr, pdn;

	Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_add 0x%lx: \"%s\"\n",
		e->e_id, e->e_ndn, 0 );
	assert( e->e_id != NOID );

	DBTzero( &key );
	key.size = e->e_nname.bv_len + 2;
	key.ulen = key.size;
	key.flags = DB_DBT_USERMEM;
	buf = op->o_tmpalloc( key.size, op->o_tmpmemctx );
	key.data = buf;
	buf[0] = DN_BASE_PREFIX;
	ptr.bv_val = buf + 1;
	ptr.bv_len = e->e_nname.bv_len;
	AC_MEMCPY( ptr.bv_val, e->e_nname.bv_val, e->e_nname.bv_len );
	ptr.bv_val[ptr.bv_len] = '\0';

	DBTzero( &data );
	data.data = &nid;
	data.size = sizeof( nid );
	BDB_ID2DISK( e->e_id, &nid );

	/* store it -- don't override */
	rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE );
	if( rc != 0 ) {
		Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_add 0x%lx: put failed: %s %d\n",
			e->e_id, db_strerror(rc), rc );
		goto done;
	}

#ifndef BDB_MULTIPLE_SUFFIXES
	if( !be_issuffix( op->o_bd, &ptr ))
#endif
	{
		buf[0] = DN_SUBTREE_PREFIX;
		rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE );
		if( rc != 0 ) {
			Debug( LDAP_DEBUG_ANY,
			"=> bdb_dn2id_add 0x%lx: subtree (%s) put failed: %d\n",
			e->e_id, ptr.bv_val, rc );
			goto done;
		}
		
#ifdef BDB_MULTIPLE_SUFFIXES
	if( !be_issuffix( op->o_bd, &ptr ))
#endif
	{
		dnParent( &ptr, &pdn );
	
		key.size = pdn.bv_len + 2;
		key.ulen = key.size;
		pdn.bv_val[-1] = DN_ONE_PREFIX;
		key.data = pdn.bv_val-1;
		ptr = pdn;

		rc = bdb_idl_insert_key( op->o_bd, db, txn, &key, e->e_id );

		if( rc != 0 ) {
			Debug( LDAP_DEBUG_ANY,
				"=> bdb_dn2id_add 0x%lx: parent (%s) insert failed: %d\n",
					e->e_id, ptr.bv_val, rc );
			goto done;
		}
	}

#ifndef BDB_MULTIPLE_SUFFIXES
	while( !be_issuffix( op->o_bd, &ptr ))
#else
	for (;;)
#endif
	{
		ptr.bv_val[-1] = DN_SUBTREE_PREFIX;

		rc = bdb_idl_insert_key( op->o_bd, db, txn, &key, e->e_id );

		if( rc != 0 ) {
			Debug( LDAP_DEBUG_ANY,
				"=> bdb_dn2id_add 0x%lx: subtree (%s) insert failed: %d\n",
					e->e_id, ptr.bv_val, rc );
			break;
		}
#ifdef BDB_MULTIPLE_SUFFIXES
		if( be_issuffix( op->o_bd, &ptr )) break;
#endif
		dnParent( &ptr, &pdn );

		key.size = pdn.bv_len + 2;
		key.ulen = key.size;
		key.data = pdn.bv_val - 1;
		ptr = pdn;
	}
	}

done:
	op->o_tmpfree( buf, op->o_tmpmemctx );
	Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_add 0x%lx: %d\n", e->e_id, rc, 0 );
	return rc;
}

int
bdb_dn2id_delete(
	Operation *op,
	DB_TXN *txn,
	EntryInfo	*eip,
	Entry		*e )
{
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
	DB *db = bdb->bi_dn2id->bdi_db;
	char		*buf;
	DBT		key;
	DB_LOCK	lock;
	struct berval	pdn, ptr;
	int		rc;

	Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_delete 0x%lx: \"%s\"\n",
		e->e_id, e->e_ndn, 0 );

	DBTzero( &key );
	key.size = e->e_nname.bv_len + 2;
	buf = op->o_tmpalloc( key.size, op->o_tmpmemctx );
	key.data = buf;
	key.flags = DB_DBT_USERMEM;
	buf[0] = DN_BASE_PREFIX;
	ptr.bv_val = buf+1;
	ptr.bv_len = e->e_nname.bv_len;
	AC_MEMCPY( ptr.bv_val, e->e_nname.bv_val, e->e_nname.bv_len );
	ptr.bv_val[ptr.bv_len] = '\0';

	/* We hold this lock until the TXN completes */
	rc = bdb_dn2id_lock( bdb, &e->e_nname, 1, TXN_ID( txn ), &lock );
	if ( rc ) goto done;

	/* delete it */
	rc = db->del( db, txn, &key, 0 );
	if( rc != 0 ) {
		Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_delete 0x%lx: delete failed: %s %d\n",
			e->e_id, db_strerror(rc), rc );
		goto done;
	}

#ifndef BDB_MULTIPLE_SUFFIXES
	if( !be_issuffix( op->o_bd, &ptr ))
#endif
	{
		buf[0] = DN_SUBTREE_PREFIX;
		rc = bdb_idl_delete_key( op->o_bd, db, txn, &key, e->e_id );
		if( rc != 0 ) {
			Debug( LDAP_DEBUG_ANY,
			"=> bdb_dn2id_delete 0x%lx: subtree (%s) delete failed: %d\n",
			e->e_id, ptr.bv_val, rc );
			goto done;
		}

#ifdef BDB_MULTIPLE_SUFFIXES
	if( !be_issuffix( op->o_bd, &ptr ))
#endif
	{
		dnParent( &ptr, &pdn );

		key.size = pdn.bv_len + 2;
		key.ulen = key.size;
		pdn.bv_val[-1] = DN_ONE_PREFIX;
		key.data = pdn.bv_val - 1;
		ptr = pdn;

		rc = bdb_idl_delete_key( op->o_bd, db, txn, &key, e->e_id );

		if( rc != 0 ) {
			Debug( LDAP_DEBUG_ANY,
				"=> bdb_dn2id_delete 0x%lx: parent (%s) delete failed: %d\n",
				e->e_id, ptr.bv_val, rc );
			goto done;
		}
	}

#ifndef BDB_MULTIPLE_SUFFIXES
	while( !be_issuffix( op->o_bd, &ptr ))
#else
	for (;;)
#endif
	{
		ptr.bv_val[-1] = DN_SUBTREE_PREFIX;

		rc = bdb_idl_delete_key( op->o_bd, db, txn, &key, e->e_id );
		if( rc != 0 ) {
			Debug( LDAP_DEBUG_ANY,
				"=> bdb_dn2id_delete 0x%lx: subtree (%s) delete failed: %d\n",
				e->e_id, ptr.bv_val, rc );
			goto done;
		}
#ifdef BDB_MULTIPLE_SUFFIXES
		if( be_issuffix( op->o_bd, &ptr )) break;
#endif
		dnParent( &ptr, &pdn );

		key.size = pdn.bv_len + 2;
		key.ulen = key.size;
		key.data = pdn.bv_val - 1;
		ptr = pdn;
	}
	}

done:
	op->o_tmpfree( buf, op->o_tmpmemctx );
	Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_delete 0x%lx: %d\n", e->e_id, rc, 0 );
	return rc;
}

int
bdb_dn2id(
	Operation *op,
	struct berval	*dn,
	EntryInfo *ei,
	u_int32_t locker,
	DB_LOCK *lock )
{
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
	DB *db = bdb->bi_dn2id->bdi_db;
	DBC	*cursor;
	int		rc;
	DBT		key, data;
	ID		nid;

	Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id(\"%s\")\n", dn->bv_val, 0, 0 );

	DBTzero( &key );
	key.size = dn->bv_len + 2;
	key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx );
	((char *)key.data)[0] = DN_BASE_PREFIX;
	AC_MEMCPY( &((char *)key.data)[1], dn->bv_val, key.size - 1 );

	/* store the ID */
	DBTzero( &data );
	data.data = &nid;
	data.ulen = sizeof(ID);
	data.flags = DB_DBT_USERMEM;

	rc = db->cursor( db, NULL, &cursor, bdb->bi_db_opflags );
	if ( rc ) goto leave;

	rc = bdb_dn2id_lock( bdb, dn, 0, locker, lock );
	if ( rc ) goto nolock;

	if ( locker ) {
		cursor->locker = locker;
	}

	/* fetch it */
	rc = cursor->c_get( cursor, &key, &data, DB_SET );

nolock:
	cursor->c_close( cursor );
leave:

	if( rc != 0 ) {
		Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id: get failed: %s (%d)\n",
			db_strerror( rc ), rc, 0 );
	} else {
		BDB_DISK2ID( &nid, &ei->bei_id );
		Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id: got id=0x%lx\n",
			ei->bei_id, 0, 0 );
	}
	op->o_tmpfree( key.data, op->o_tmpmemctx );
	return rc;
}

int
bdb_dn2id_children(
	Operation *op,
	DB_TXN *txn,
	Entry *e )
{
	DBT		key, data;
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
	DB *db = bdb->bi_dn2id->bdi_db;
	ID		id;
	int		rc;

	Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_children(\"%s\")\n",
		e->e_nname.bv_val, 0, 0 );
	DBTzero( &key );
	key.size = e->e_nname.bv_len + 2;
	key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx );
	((char *)key.data)[0] = DN_ONE_PREFIX;
	AC_MEMCPY( &((char *)key.data)[1], e->e_nname.bv_val, key.size - 1 );

	if ( bdb->bi_idl_cache_size ) {
		rc = bdb_idl_cache_get( bdb, db, &key, NULL );
		if ( rc != LDAP_NO_SUCH_OBJECT ) {
			op->o_tmpfree( key.data, op->o_tmpmemctx );
			return rc;
		}
	}
	/* we actually could do a empty get... */
	DBTzero( &data );
	data.data = &id;
	data.ulen = sizeof(id);
	data.flags = DB_DBT_USERMEM;
	data.doff = 0;
	data.dlen = sizeof(id);

	rc = db->get( db, txn, &key, &data, bdb->bi_db_opflags );
	op->o_tmpfree( key.data, op->o_tmpmemctx );

	Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_children(\"%s\"): %s (%d)\n",
		e->e_nname.bv_val,
		rc == 0 ? "" : ( rc == DB_NOTFOUND ? "no " :
			db_strerror(rc) ), rc );

	return rc;
}

int
bdb_dn2idl(
	Operation *op,
	Entry *e,
	ID *ids,
	ID *stack )
{
	int		rc;
	DBT		key;
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
	DB *db = bdb->bi_dn2id->bdi_db;
	int prefix = ( op->ors_scope == LDAP_SCOPE_ONELEVEL )
		? DN_ONE_PREFIX : DN_SUBTREE_PREFIX;

	Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2idl(\"%s\")\n",
		e->e_nname.bv_val, 0, 0 );

#ifndef	BDB_MULTIPLE_SUFFIXES
	if ( prefix == DN_SUBTREE_PREFIX && BEI(e)->bei_parent->bei_id == 0 ) {
		BDB_IDL_ALL(bdb, ids);
		return 0;
	}
#endif

	DBTzero( &key );
	key.size = e->e_nname.bv_len + 2;
	key.ulen = key.size;
	key.flags = DB_DBT_USERMEM;
	key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx );
	((char *)key.data)[0] = prefix;
	AC_MEMCPY( &((char *)key.data)[1], e->e_nname.bv_val, key.size - 1 );

	BDB_IDL_ZERO( ids );
	rc = bdb_idl_fetch_key( op->o_bd, db, NULL, &key, ids, NULL, 0 );

	if( rc != 0 ) {
		Debug( LDAP_DEBUG_TRACE,
			"<= bdb_dn2idl: get failed: %s (%d)\n",
			db_strerror( rc ), rc, 0 );

	} else {
		Debug( LDAP_DEBUG_TRACE,
			"<= bdb_dn2idl: id=%ld first=%ld last=%ld\n",
			(long) ids[0],
			(long) BDB_IDL_FIRST( ids ), (long) BDB_IDL_LAST( ids ) );
	}

	op->o_tmpfree( key.data, op->o_tmpmemctx );
	return rc;
}

#else	/* BDB_HIER */
/* Management routines for a hierarchically structured database.
 *
 * Instead of a ldbm-style dn2id database, we use a hierarchical one. Each
 * entry in this database is a struct diskNode, keyed by entryID and with
 * the data containing the RDN and entryID of the node's children. We use
 * 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 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 {
	unsigned char nrdnlen[2];
	char nrdn[1];
	char rdn[1];                        /* variable placement */
	unsigned char entryID[sizeof(ID)];  /* variable placement */
} 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
)
{
	diskNode *un, *cn;
	int rc, ul, cl;

	un = (diskNode *)usrkey->data;
	cn = (diskNode *)curkey->data;

	/* data is not aligned, cannot compare directly */
	rc = un->nrdnlen[0] - cn->nrdnlen[0];
	if ( rc ) return rc;
	rc = un->nrdnlen[1] - cn->nrdnlen[1];
	if ( rc ) return rc;

	return strcmp( un->nrdn, cn->nrdn );
}

/* This function constructs a full DN for a given entry.
 */
int hdb_fix_dn(
	Entry *e,
	int checkit )
{
	EntryInfo *ei;
	int rlen = 0, nrlen = 0;
	char *ptr, *nptr;
	int max = 0;

	if ( !e->e_id )
		return 0;

	/* count length of all DN components */
	for ( ei = BEI(e); ei && ei->bei_id; ei=ei->bei_parent ) {
		rlen += ei->bei_rdn.bv_len + 1;
		nrlen += ei->bei_nrdn.bv_len + 1;
		if (ei->bei_modrdns > max) max = ei->bei_modrdns;
	}

	/* See if the entry DN was invalidated by a subtree rename */
	if ( checkit ) {
		if ( BEI(e)->bei_modrdns >= max ) {
			return 0;
		}
		/* We found a mismatch, tell the caller to lock it */
		if ( checkit == 1 ) {
			return 1;
		}
		/* checkit == 2. do the fix. */
		free( e->e_name.bv_val );
		free( e->e_nname.bv_val );
	}

	e->e_name.bv_len = rlen - 1;
	e->e_nname.bv_len = nrlen - 1;
	e->e_name.bv_val = ch_malloc(rlen);
	e->e_nname.bv_val = ch_malloc(nrlen);
	ptr = e->e_name.bv_val;
	nptr = e->e_nname.bv_val;
	for ( ei = BEI(e); ei && ei->bei_id; ei=ei->bei_parent ) {
		ptr = lutil_strcopy(ptr, ei->bei_rdn.bv_val);
		nptr = lutil_strcopy(nptr, ei->bei_nrdn.bv_val);
		if ( ei->bei_parent ) {
			*ptr++ = ',';
			*nptr++ = ',';
		}
	}
	BEI(e)->bei_modrdns = max;
	ptr[-1] = '\0';
	nptr[-1] = '\0';

	return 0;
}

/* We add two elements to the DN2ID database - a data item under the parent's
 * entryID containing the child's RDN and entryID, and an item under the
 * child's entryID containing the parent's entryID.
 */
int
hdb_dn2id_add(
	Operation	*op,
	DB_TXN *txn,
	EntryInfo	*eip,
	Entry		*e )
{
	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;

	Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2id_add 0x%lx: \"%s\"\n",
		e->e_id, e->e_ndn, 0 );

	nrlen = dn_rdnlen( op->o_bd, &e->e_nname );
	if (nrlen) {
		rlen = dn_rdnlen( op->o_bd, &e->e_name );
	} else {
		nrlen = e->e_nname.bv_len;
		rlen = e->e_name.bv_len;
	}

	d = op->o_tmpalloc(sizeof(diskNode) + rlen + nrlen, op->o_tmpmemctx);
	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';
	BDB_ID2DISK( e->e_id, ptr );

	DBTzero(&key);
	DBTzero(&data);
	key.size = sizeof(ID);
	key.flags = DB_DBT_USERMEM;
	BDB_ID2DISK( eip->bei_id, &nid );

	key.data = &nid;

	/* Need to make dummy root node once. Subsequent attempts
	 * will fail harmlessly.
	 */
	if ( eip->bei_id == 0 ) {
		diskNode dummy = {{0, 0}, "", "", ""};
		data.data = &dummy;
		data.size = sizeof(diskNode);
		data.flags = DB_DBT_USERMEM;

		db->put( db, txn, &key, &data, DB_NODUPDATA );
	}

	data.data = d;
	data.size = sizeof(diskNode) + rlen + nrlen;
	data.flags = DB_DBT_USERMEM;

	rc = db->put( db, txn, &key, &data, DB_NODUPDATA );

	if (rc == 0) {
		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 );
	}

	/* Update all parents' IDL cache entries */
	if ( rc == 0 && bdb->bi_idl_cache_size ) {
		ID tmp[2];
		char *ptr = ((char *)&tmp[1])-1;
		key.data = ptr;
		key.size = sizeof(ID)+1;
		tmp[1] = eip->bei_id;
		*ptr = DN_ONE_PREFIX;
		bdb_idl_cache_add_id( bdb, db, &key, e->e_id );
		*ptr = DN_SUBTREE_PREFIX;
		for (; eip && eip->bei_parent->bei_id; eip = eip->bei_parent) {
			tmp[1] = eip->bei_id;
			bdb_idl_cache_add_id( bdb, db, &key, e->e_id );
		}
	}

leave:
	op->o_tmpfree( d, op->o_tmpmemctx );
	Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id_add 0x%lx: %d\n", e->e_id, rc, 0 );

	return rc;
}

int
hdb_dn2id_delete(
	Operation	*op,
	DB_TXN *txn,
	EntryInfo	*eip,
	Entry	*e )
{
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
	DB *db = bdb->bi_dn2id->bdi_db;
	DBT		key, data;
	DBC	*cursor;
	diskNode *d;
	int rc;
	ID	nid;
	unsigned char dlen[2];
	DB_LOCK	lock;

	Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2id_delete 0x%lx: \"%s\"\n",
		e->e_id, e->e_ndn, 0 );

	DBTzero(&key);
	key.size = sizeof(ID);
	key.ulen = key.size;
	key.flags = DB_DBT_USERMEM;
	BDB_ID2DISK( eip->bei_id, &nid );

	DBTzero(&data);
	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;

	key.data = &nid;

	d = op->o_tmpalloc( data.size, op->o_tmpmemctx );
	d->nrdnlen[1] = BEI(e)->bei_nrdn.bv_len & 0xff;
	d->nrdnlen[0] = (BEI(e)->bei_nrdn.bv_len >> 8) | 0x80;
	dlen[0] = d->nrdnlen[0];
	dlen[1] = d->nrdnlen[1];
	strcpy( d->nrdn, BEI(e)->bei_nrdn.bv_val );
	data.data = d;

	rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags );
	if ( rc ) goto leave;

	/* We hold this lock until the TXN completes */
	rc = bdb_dn2id_lock( bdb, &e->e_nname, 1, TXN_ID( txn ), &lock );
	if ( rc ) goto nolock;

	/* Delete our ID from the parent's list */
	rc = cursor->c_get( cursor, &key, &data, DB_GET_BOTH_RANGE );
	if ( rc == 0 ) {
		if ( dlen[1] == d->nrdnlen[1] && dlen[0] == d->nrdnlen[0] &&
			!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 ) {
		BDB_ID2DISK( e->e_id, &nid );
		rc = cursor->c_get( cursor, &key, &data, DB_SET );
		if ( rc == 0 )
			rc = cursor->c_del( cursor, 0 );
	}

nolock:
	cursor->c_close( cursor );
leave:
	op->o_tmpfree( d, op->o_tmpmemctx );

	/* Delete IDL cache entries */
	if ( rc == 0 && bdb->bi_idl_cache_size ) {
		ID tmp[2];
		char *ptr = ((char *)&tmp[1])-1;
		key.data = ptr;
		key.size = sizeof(ID)+1;
		tmp[1] = eip->bei_id;
		*ptr = DN_ONE_PREFIX;
		bdb_idl_cache_del_id( bdb, db, &key, e->e_id );
		*ptr = DN_SUBTREE_PREFIX;
		for (; eip && eip->bei_parent->bei_id; eip = eip->bei_parent) {
			tmp[1] = eip->bei_id;
			bdb_idl_cache_del_id( bdb, db, &key, e->e_id );
		}
	}
	Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id_delete 0x%lx: %d\n", e->e_id, rc, 0 );
	return rc;
}


int
hdb_dn2id(
	Operation	*op,
	struct berval	*in,
	EntryInfo	*ei,
	u_int32_t locker,
	DB_LOCK *lock )
{
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
	DB *db = bdb->bi_dn2id->bdi_db;
	DBT		key, data;
	DBC	*cursor;
	int		rc = 0, nrlen;
	diskNode *d;
	char	*ptr;
	unsigned char dlen[2];
	ID idp, parentID;

	Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2id(\"%s\")\n", in->bv_val, 0, 0 );

	nrlen = dn_rdnlen( op->o_bd, in );
	if (!nrlen) nrlen = in->bv_len;

	DBTzero(&key);
	key.size = sizeof(ID);
	key.data = &idp;
	key.ulen = sizeof(ID);
	key.flags = DB_DBT_USERMEM;
	parentID = ( ei->bei_parent != NULL ) ? ei->bei_parent->bei_id : 0;
	BDB_ID2DISK( parentID, &idp );

	DBTzero(&data);
	data.size = sizeof(diskNode) + nrlen - sizeof(ID) - 1;
	data.ulen = data.size * 3;
	data.dlen = data.ulen;
	data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;

	rc = db->cursor( db, NULL, &cursor, bdb->bi_db_opflags );
	if ( rc ) return rc;
	if ( locker ) {
		cursor->locker = locker;
	}

	d = op->o_tmpalloc( data.size * 3, op->o_tmpmemctx );
	d->nrdnlen[1] = nrlen & 0xff;
	d->nrdnlen[0] = (nrlen >> 8) | 0x80;
	dlen[0] = d->nrdnlen[0];
	dlen[1] = d->nrdnlen[1];
	ptr = lutil_strncopy( d->nrdn, in->bv_val, nrlen );
	*ptr = '\0';
	data.data = d;

	rc = bdb_dn2id_lock( bdb, in, 0, locker, lock );
	if ( rc ) goto leave;

	rc = cursor->c_get( cursor, &key, &data, DB_GET_BOTH_RANGE );
	if ( rc == 0 && (dlen[1] != d->nrdnlen[1] || dlen[0] != d->nrdnlen[0] ||
		strncmp( d->nrdn, in->bv_val, nrlen ))) {
		rc = DB_NOTFOUND;
	}
	if ( rc == 0 ) {
		ptr = (char *) 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 );
		if ( ei->bei_parent != NULL && !ei->bei_parent->bei_dkids ) {
			db_recno_t dkids;
			/* How many children does the parent have? */
			/* FIXME: do we need to lock the parent
			 * entryinfo? Seems safe...
			 */
			cursor->c_count( cursor, &dkids, 0 );
			ei->bei_parent->bei_dkids = dkids;
		}
	}

leave:
	cursor->c_close( cursor );
	op->o_tmpfree( d, op->o_tmpmemctx );
	if( rc != 0 ) {
		Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id: get failed: %s (%d)\n",
			db_strerror( rc ), rc, 0 );
	} else {
		Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id: got id=0x%lx\n",
			ei->bei_id, 0, 0 );
	}

	return rc;
}

int