/* dn2id.c - routines to deal with the dn2id index */
/* $OpenLDAP$ */
/*
- * Copyright 1998-2000 The OpenLDAP Foundation, All Rights Reserved.
+ * Copyright 1998-2003 The OpenLDAP Foundation, All Rights Reserved.
* COPYING RESTRICTIONS APPLY, see COPYRIGHT file
*/
#include "back-bdb.h"
#include "idl.h"
+#include "lutil.h"
#ifndef BDB_HIER
int
bdb_dn2id_add(
BackendDB *be,
DB_TXN *txn,
- struct berval *pbv,
- Entry *e )
+ EntryInfo *eip,
+ Entry *e,
+ void *ctx )
{
struct bdb_info *bdb = (struct bdb_info *) be->be_private;
DB *db = bdb->bi_dn2id->bdi_db;
int rc;
DBT key, data;
- char *buf, *ptr, *pdn;
+ char *buf;
+ struct berval ptr, pdn;
+#ifdef NEW_LOGGING
+ LDAP_LOG ( INDEX, ARGS, "bdb_dn2id_add( \"%s\", 0x%08lx )\n",
+ e->e_ndn, (long) e->e_id, 0 );
+#else
Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_add( \"%s\", 0x%08lx )\n",
e->e_ndn, (long) e->e_id, 0 );
+#endif
assert( e->e_id != NOID );
DBTzero( &key );
key.size = e->e_nname.bv_len + 2;
- buf = ch_malloc( key.size );
+ key.ulen = key.size;
+ key.flags = DB_DBT_USERMEM;
+ buf = sl_malloc( key.size, ctx );
key.data = buf;
buf[0] = DN_BASE_PREFIX;
- ptr = buf + 1;
- AC_MEMCPY( ptr, e->e_ndn, key.size - 1 );
+ 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 = (char *) &e->e_id;
/* store it -- don't override */
rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE );
if( rc != 0 ) {
+#ifdef NEW_LOGGING
+ LDAP_LOG ( INDEX, ERR, "bdb_dn2id_add: put failed: %s %d\n",
+ db_strerror(rc), rc, 0 );
+#else
Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_add: put failed: %s %d\n",
db_strerror(rc), rc, 0 );
+#endif
goto done;
}
- if( !be_issuffix( be, ptr )) {
+#ifndef BDB_MULTIPLE_SUFFIXES
+ if( !be_issuffix( be, &ptr )) {
+#endif
buf[0] = DN_SUBTREE_PREFIX;
- rc = bdb_idl_insert_key( be, db, txn, &key, e->e_id );
+ rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE );
if( rc != 0 ) {
+#ifdef NEW_LOGGING
+ LDAP_LOG ( INDEX, ERR,
+ "=> bdb_dn2id_add: subtree (%s) put failed: %d\n",
+ ptr.bv_val, rc, 0 );
+#else
Debug( LDAP_DEBUG_ANY,
- "=> bdb_dn2id_add: subtree (%s) insert failed: %d\n",
- ptr, rc, 0 );
+ "=> bdb_dn2id_add: subtree (%s) put failed: %d\n",
+ ptr.bv_val, rc, 0 );
+#endif
goto done;
}
- }
-
- pdn = dn_parent( be, ptr );
-
- if( pdn != NULL ) {
- key.size -= pdn - ptr;
- pdn[-1] = DN_ONE_PREFIX;
- key.data = pdn - 1;
+
+#ifdef BDB_MULTIPLE_SUFFIXES
+ if( !be_issuffix( be, &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( be, db, txn, &key, e->e_id );
if( rc != 0 ) {
+#ifdef NEW_LOGGING
+ LDAP_LOG ( INDEX, ERR,
+ "=> bdb_dn2id_add: parent (%s) insert failed: %d\n",
+ ptr.bv_val, rc, 0 );
+#else
Debug( LDAP_DEBUG_ANY,
"=> bdb_dn2id_add: parent (%s) insert failed: %d\n",
- pdn, rc, 0 );
+ ptr.bv_val, rc, 0 );
+#endif
goto done;
}
+#ifndef BDB_MULTIPLE_SUFFIXES
}
- while( pdn != NULL ) {
- if ( be_issuffix( be, pdn ))
- break;
- pdn[-1] = DN_SUBTREE_PREFIX;
+ while( !be_issuffix( be, &ptr )) {
+#else
+ for (;;) {
+#endif
+ ptr.bv_val[-1] = DN_SUBTREE_PREFIX;
rc = bdb_idl_insert_key( be, db, txn, &key, e->e_id );
if( rc != 0 ) {
+#ifdef NEW_LOGGING
+ LDAP_LOG ( INDEX, ERR,
+ "=> bdb_dn2id_add: subtree (%s) insert failed: %d\n",
+ ptr.bv_val, rc, 0 );
+#else
Debug( LDAP_DEBUG_ANY,
"=> bdb_dn2id_add: subtree (%s) insert failed: %d\n",
- pdn, rc, 0 );
+ ptr.bv_val, rc, 0 );
+#endif
break;
}
+#ifdef BDB_MULTIPLE_SUFFIXES
+ if( be_issuffix( be, &ptr )) break;
+#endif
+ dnParent( &ptr, &pdn );
+
+ key.size = pdn.bv_len + 2;
+ key.ulen = key.size;
+ key.data = pdn.bv_val - 1;
ptr = pdn;
- pdn = dn_parent( be, pdn );
- key.size -= pdn - ptr;
- key.data = pdn - 1;
}
+#ifdef BDB_MULTIPLE_SUFFIXES
+ }
+#endif
done:
- ch_free( buf );
+ sl_free( buf, ctx );
+#ifdef NEW_LOGGING
+ LDAP_LOG ( INDEX, RESULTS, "<= bdb_dn2id_add: %d\n", rc, 0, 0 );
+#else
Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_add: %d\n", rc, 0, 0 );
+#endif
return rc;
}
bdb_dn2id_delete(
BackendDB *be,
DB_TXN *txn,
- char *pdn,
- Entry *e )
+ EntryInfo *eip,
+ Entry *e,
+ void *ctx )
{
struct bdb_info *bdb = (struct bdb_info *) be->be_private;
DB *db = bdb->bi_dn2id->bdi_db;
int rc;
DBT key;
- char *buf, *ptr;
+ char *buf;
+ struct berval pdn, ptr;
+#ifdef NEW_LOGGING
+ LDAP_LOG ( INDEX, ARGS,
+ "=> bdb_dn2id_delete ( \"%s\", 0x%08lx )\n", e->e_ndn, e->e_id, 0);
+#else
Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_delete( \"%s\", 0x%08lx )\n",
e->e_ndn, e->e_id, 0 );
+#endif
DBTzero( &key );
key.size = e->e_nname.bv_len + 2;
- buf = ch_malloc( key.size );
+ buf = sl_malloc( key.size, ctx );
key.data = buf;
key.flags = DB_DBT_USERMEM;
buf[0] = DN_BASE_PREFIX;
- ptr = buf+1;
- AC_MEMCPY( ptr, e->e_ndn, key.size - 1 );
+ 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';
/* delete it */
rc = db->del( db, txn, &key, 0 );
if( rc != 0 ) {
+#ifdef NEW_LOGGING
+ LDAP_LOG ( INDEX, ERR,
+ "=> bdb_dn2id_delete: delete failed: %s %d\n",
+ db_strerror(rc), rc, 0 );
+#else
Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_delete: delete failed: %s %d\n",
db_strerror(rc), rc, 0 );
+#endif
goto done;
}
- if( !be_issuffix( be, ptr )) {
+#ifndef BDB_MULTIPLE_SUFFIXES
+ if( !be_issuffix( be, &ptr )) {
+#endif
buf[0] = DN_SUBTREE_PREFIX;
- rc = bdb_idl_delete_key( be, db, txn, &key, e->e_id );
+ rc = db->del( db, txn, &key, 0 );
if( rc != 0 ) {
+#ifdef NEW_LOGGING
+ LDAP_LOG ( INDEX, ERR,
+ "=> bdb_dn2id_delete: subtree (%s) delete failed: %d\n",
+ ptr.bv_val, rc, 0 );
+#else
Debug( LDAP_DEBUG_ANY,
"=> bdb_dn2id_delete: subtree (%s) delete failed: %d\n",
- ptr, rc, 0 );
+ ptr.bv_val, rc, 0 );
+#endif
goto done;
}
- }
- pdn = dn_parent( be, ptr );
+#ifdef BDB_MULTIPLE_SUFFIXES
+ if( !be_issuffix( be, &ptr )) {
+#endif
+ dnParent( &ptr, &pdn );
- if( pdn != NULL ) {
- key.size -= pdn - ptr;
- pdn[-1] = DN_ONE_PREFIX;
- key.data = pdn - 1;
+ 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( be, db, txn, &key, e->e_id );
if( rc != 0 ) {
+#ifdef NEW_LOGGING
+ LDAP_LOG ( INDEX, ERR,
+ "=> bdb_dn2id_delete: parent (%s) delete failed: %d\n",
+ ptr.bv_val, rc, 0 );
+#else
Debug( LDAP_DEBUG_ANY,
"=> bdb_dn2id_delete: parent (%s) delete failed: %d\n",
- pdn, rc, 0 );
+ ptr.bv_val, rc, 0 );
+#endif
goto done;
}
+#ifndef BDB_MULTIPLE_SUFFIXES
}
- while( pdn != NULL ) {
- if ( be_issuffix( be, pdn ))
- break;
-
- pdn[-1] = DN_SUBTREE_PREFIX;
+ while( !be_issuffix( be, &ptr )) {
+#else
+ for (;;) {
+#endif
+ ptr.bv_val[-1] = DN_SUBTREE_PREFIX;
rc = bdb_idl_delete_key( be, db, txn, &key, e->e_id );
if( rc != 0 ) {
+#ifdef NEW_LOGGING
+ LDAP_LOG ( INDEX, ERR,
+ "=> bdb_dn2id_delete: subtree (%s) delete failed: %d\n",
+ ptr.bv_val, rc, 0 );
+#else
Debug( LDAP_DEBUG_ANY,
"=> bdb_dn2id_delete: subtree (%s) delete failed: %d\n",
- pdn, rc, 0 );
+ ptr.bv_val, rc, 0 );
+#endif
goto done;
}
+#ifdef BDB_MULTIPLE_SUFFIXES
+ if( be_issuffix( be, &ptr )) break;
+#endif
+ dnParent( &ptr, &pdn );
+
+ key.size = pdn.bv_len + 2;
+ key.ulen = key.size;
+ key.data = pdn.bv_val - 1;
ptr = pdn;
- pdn = dn_parent( be, pdn );
- key.size -= pdn - ptr;
- key.data = pdn - 1;
}
+#ifdef BDB_MULTIPLE_SUFFIXES
+ }
+#endif
done:
- ch_free( buf );
+ sl_free( buf, ctx );
+#ifdef NEW_LOGGING
+ LDAP_LOG ( INDEX, RESULTS, "<= bdb_dn2id_delete %d\n", rc, 0, 0 );
+#else
Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_delete %d\n", rc, 0, 0 );
+#endif
return rc;
}
BackendDB *be,
DB_TXN *txn,
struct berval *dn,
- ID *id )
+ EntryInfo *ei,
+ void *ctx )
{
int rc;
DBT key, data;
struct bdb_info *bdb = (struct bdb_info *) be->be_private;
DB *db = bdb->bi_dn2id->bdi_db;
+#ifdef NEW_LOGGING
+ LDAP_LOG ( INDEX, ARGS, "=> bdb_dn2id( \"%s\" )\n", dn->bv_val, 0, 0 );
+#else
Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id( \"%s\" )\n", dn->bv_val, 0, 0 );
+#endif
DBTzero( &key );
key.size = dn->bv_len + 2;
- key.data = ch_malloc( key.size );
+ key.data = sl_malloc( key.size, ctx );
((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 = id;
+ data.data = &ei->bei_id;
data.ulen = sizeof(ID);
data.flags = DB_DBT_USERMEM;
rc = db->get( db, txn, &key, &data, bdb->bi_db_opflags );
if( rc != 0 ) {
+#ifdef NEW_LOGGING
+ LDAP_LOG ( INDEX, ERR, "<= bdb_dn2id: get failed %s (%d)\n",
+ db_strerror(rc), rc, 0 );
+#else
Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id: get failed: %s (%d)\n",
db_strerror( rc ), rc, 0 );
+#endif
} else {
+#ifdef NEW_LOGGING
+ LDAP_LOG ( INDEX, RESULTS,
+ "<= bdb_dn2id: got id=0x%08lx\n", ei->bei_id, 0, 0 );
+#else
Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id: got id=0x%08lx\n",
- *id, 0, 0 );
+ ei->bei_id, 0, 0 );
+#endif
}
- ch_free( key.data );
- return rc;
-}
-
-int
-bdb_dn2id_matched(
- BackendDB *be,
- DB_TXN *txn,
- struct berval *in,
- ID *id,
- char **matchedDN )
-{
- int rc;
- DBT key, data;
- struct bdb_info *bdb = (struct bdb_info *) be->be_private;
- DB *db = bdb->bi_dn2id->bdi_db;
- char *buf, *dn;
-
- Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_matched( \"%s\" )\n", in->bv_val, 0, 0 );
-
- DBTzero( &key );
- key.size = in->bv_len + 2;
- buf = ch_malloc( key.size );
- key.data = buf;
- dn = buf+1;
- AC_MEMCPY( dn, in->bv_val, key.size - 1 );
-
- /* store the ID */
- DBTzero( &data );
- data.data = id;
- data.ulen = sizeof(ID);
- data.flags = DB_DBT_USERMEM;
-
- *matchedDN = NULL;
-
- while(1) {
- dn[-1] = DN_BASE_PREFIX;
-
- *id = NOID;
-
- /* fetch it */
- rc = db->get( db, txn, &key, &data, bdb->bi_db_opflags );
-
- if( rc == DB_NOTFOUND ) {
- char *pdn = dn_parent( be, dn );
-
- if( pdn == NULL || *pdn == '\0' ) {
- Debug( LDAP_DEBUG_TRACE,
- "<= bdb_dn2id_matched: no match\n",
- 0, 0, 0 );
- break;
- }
-
- key.size -= pdn - dn;
- dn = pdn;
- key.data = pdn - 1;
-
- } else if ( rc == 0 ) {
- if( data.size != sizeof( ID ) ) {
- Debug( LDAP_DEBUG_ANY,
- "<= bdb_dn2id_matched: get size mismatch: "
- "expected %ld, got %ld\n",
- (long) sizeof(ID), (long) data.size, 0 );
- }
-
- if( dn != buf+1 ) {
- *matchedDN = (char *) dn;
- }
-
- Debug( LDAP_DEBUG_TRACE,
- "<= bdb_dn2id_matched: id=0x%08lx: %s %s\n",
- (long) *id, *matchedDN == NULL ? "entry" : "matched", dn );
- break;
-
- } else {
- Debug( LDAP_DEBUG_ANY,
- "<= bdb_dn2id_matched: get failed: %s (%d)\n",
- db_strerror(rc), rc, 0 );
- break;
- }
- }
-
- ch_free( buf );
+ sl_free( key.data, ctx );
return rc;
}
int
bdb_dn2id_children(
- BackendDB *be,
+ Operation *op,
DB_TXN *txn,
- struct berval *dn )
+ Entry *e )
{
- int rc;
DBT key, data;
- struct bdb_info *bdb = (struct bdb_info *) be->be_private;
+ struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
DB *db = bdb->bi_dn2id->bdi_db;
ID id;
+ int rc;
+#ifdef NEW_LOGGING
+ LDAP_LOG ( INDEX, ARGS,
+ "=> bdb_dn2id_children( %s )\n", e->e_nname.bv_val, 0, 0 );
+#else
Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_children( %s )\n",
- dn->bv_val, 0, 0 );
-
+ e->e_nname.bv_val, 0, 0 );
+#endif
DBTzero( &key );
- key.size = dn->bv_len + 2;
- key.data = ch_malloc( key.size );
+ key.size = e->e_nname.bv_len + 2;
+ key.data = sl_malloc( key.size, op->o_tmpmemctx );
((char *)key.data)[0] = DN_ONE_PREFIX;
- AC_MEMCPY( &((char *)key.data)[1], dn->bv_val, key.size - 1 );
+ AC_MEMCPY( &((char *)key.data)[1], e->e_nname.bv_val, key.size - 1 );
/* we actually could do a empty get... */
DBTzero( &data );
data.dlen = sizeof(id);
rc = db->get( db, txn, &key, &data, bdb->bi_db_opflags );
-
- Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_children( %s ): %schildren (%d)\n",
- dn,
+ sl_free( key.data, op->o_tmpmemctx );
+
+#ifdef NEW_LOGGING
+ LDAP_LOG ( INDEX, DETAIL1,
+ "<= bdb_dn2id_children( %s ): %s (%d)\n",
+ e->e_nname.bv_val, rc == 0 ? "" : ( rc == DB_NOTFOUND ? "no " :
+ db_strerror(rc)), rc );
+#else
+ 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 );
+#endif
return rc;
}
struct bdb_info *bdb = (struct bdb_info *) be->be_private;
DB *db = bdb->bi_dn2id->bdi_db;
+#ifdef NEW_LOGGING
+ LDAP_LOG ( INDEX, ARGS,
+ "=> bdb_dn2ididl( \"%s\" )\n", dn->bv_val, 0, 0 );
+#else
Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2idl( \"%s\" )\n", dn->bv_val, 0, 0 );
+#endif
- if (prefix == DN_SUBTREE_PREFIX && be_issuffix(be, dn->bv_val))
+#ifndef BDB_MULTIPLE_SUFFIXES
+ if (prefix == DN_SUBTREE_PREFIX && be_issuffix(be, dn))
{
BDB_IDL_ALL(bdb, ids);
return 0;
}
+#endif
DBTzero( &key );
key.size = dn->bv_len + 2;
+ key.ulen = key.size;
+ key.flags = DB_DBT_USERMEM;
key.data = ch_malloc( key.size );
((char *)key.data)[0] = prefix;
AC_MEMCPY( &((char *)key.data)[1], dn->bv_val, key.size - 1 );
rc = bdb_idl_fetch_key( be, db, NULL, &key, ids );
if( rc != 0 ) {
+#ifdef NEW_LOGGING
+ LDAP_LOG ( INDEX, ERR,
+ "<= bdb_dn2ididl: get failed: %s (%d)\n", db_strerror(rc), rc, 0 );
+#else
Debug( LDAP_DEBUG_TRACE,
"<= bdb_dn2idl: get failed: %s (%d)\n",
db_strerror( rc ), rc, 0 );
+#endif
} else {
+#ifdef NEW_LOGGING
+ LDAP_LOG ( INDEX, RESULTS,
+ "<= bdb_dn2ididl: id=%ld first=%ld last=%ld\n",
+ (long) ids[0], (long) BDB_IDL_FIRST( ids ),
+ (long) BDB_IDL_LAST( ids ) );
+#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 ) );
+#endif
}
ch_free( key.data );
}
#else /* BDB_HIER */
-/* Experimental management routines for a hierarchically structured backend.
+/* Experimental management routines for a hierarchically structured database.
*
* Unsupported! Use at your own risk!
*
- * Instead of a dn2id database, we use an id2parent database. Each entry in
- * this database is a struct diskNode, containing the ID of the node's parent
- * and the RDN of the node.
+ * 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 an empty rdn
+ * and the ID of the node's parent, to allow bottom-up tree traversal as
+ * well as top-down.
+ *
+ * The diskNode is a variable length structure. This definition is not
+ * directly usable for in-memory manipulation.
*/
typedef struct diskNode {
- ID parent;
- struct berval rdn;
- struct berval nrdn;
+ ID entryID;
+ short nrdnlen;
+ char nrdn[1];
+ char rdn[1];
} diskNode;
-/* In bdb_db_open() we call bdb_build_tree() which reads the entire id2parent
- * database into memory (into an AVL tree). Next we iterate through each node
- * of this tree, connecting each child to its parent. The nodes in this AVL
- * tree are a struct idNode. The immediate (Onelevel) children of a node are
- * referenced in the i_kids AVL tree. With this arrangement, there is no need
- * to maintain the DN_ONE_PREFIX or DN_SUBTREE_PREFIX database keys. Note that
- * the DN of an entry is constructed by walking up the list of i_parent
- * pointers, so no full DN is stored on disk anywhere. This makes modrdn
- * extremely efficient, even when operating on a populated subtree.
- *
- * The idNode tree is searched directly from the root when performing id to
- * entry lookups. The tree is traversed using the i_kids subtrees when
- * performing dn to id lookups.
- */
-typedef struct idNode {
- ID i_id;
- struct idNode *i_parent;
- diskNode *i_rdn;
- Avlnode *i_kids;
- ldap_pvt_thread_rdwr_t i_kids_rdwr;
-} idNode;
-
-
-/* The main AVL tree is sorted in ID order. The i_kids AVL trees are
- * sorted in lexical order. These are the various helper routines used
- * for the searches and sorts.
+/* Sort function for the sorted duplicate data items of a dn2id key.
+ * Sorts based on normalized RDN, in lexical order.
*/
-static int
-node_find_cmp(
- ID id,
- idNode *n
-)
-{
- return id - n->i_id;
-}
-
-static int
-node_frdn_cmp(
- char *nrdn,
- idNode *n
-)
-{
- return strcmp(nrdn, n->i_rdn->nrdn.bv_val);
-}
-
-static int
-node_add_cmp(
- idNode *a,
- idNode *b
-)
-{
- return a->i_id - b->i_id;
-}
-
-static int
-node_rdn_cmp(
- idNode *a,
- idNode *b
-)
-{
- return strcmp(a->i_rdn->nrdn.bv_val, b->i_rdn->nrdn.bv_val);
-}
-
-idNode * bdb_find_id_node(
- ID id,
- Avlnode *tree
-)
-{
- return avl_find(tree, (const void *)id, (AVL_CMP)node_find_cmp);
-}
-
-idNode * bdb_find_rdn_node(
- char *nrdn,
- Avlnode *tree
-)
-{
- return avl_find(tree, (const void *)nrdn, (AVL_CMP)node_frdn_cmp);
-}
-
-/* This function links a node into its parent's i_kids tree. */
-int bdb_insert_kid(
- idNode *a,
- Avlnode *tree
+int
+bdb_hdb_compare(
+ DB *db,
+ const DBT *usrkey,
+ const DBT *curkey
)
{
+ diskNode *usr = usrkey->data;
+ diskNode *cur = curkey->data;
+ short curlen;
+ char *ptr = (char *)&cur->nrdnlen;
int rc;
- if (a->i_rdn->parent == 0)
- return 0;
- a->i_parent = bdb_find_id_node(a->i_rdn->parent, tree);
- if (!a->i_parent)
- return -1;
- ldap_pvt_thread_rdwr_wlock(&a->i_parent->i_kids_rdwr);
- rc = avl_insert( &a->i_parent->i_kids, (caddr_t) a,
- (AVL_CMP)node_rdn_cmp, (AVL_DUP) avl_dup_error );
- ldap_pvt_thread_rdwr_wunlock(&a->i_parent->i_kids_rdwr);
- return rc;
-}
-
-/* This function adds a node into the main AVL tree */
-idNode *bdb_add_node(
- ID id,
- char *d,
- struct bdb_info *bdb
-)
-{
- idNode *node;
-
- node = (idNode *)ch_malloc(sizeof(idNode));
- node->i_id = id;
- node->i_parent = NULL;
- node->i_kids = NULL;
- node->i_rdn = (diskNode *)d;
- node->i_rdn->rdn.bv_val += (long)d;
- node->i_rdn->nrdn.bv_val += (long)d;
- ldap_pvt_thread_rdwr_init(&node->i_kids_rdwr);
- avl_insert( &bdb->bi_tree, (caddr_t) node,
- (AVL_CMP)node_add_cmp, (AVL_DUP) avl_dup_error );
- if (id == 1)
- bdb->bi_troot = node;
- return node;
-}
-
-/* This function initializes the trees at startup time. */
-int bdb_build_tree(
- Backend *be
-)
-{
- struct bdb_info *bdb = (struct bdb_info *) be->be_private;
- int i, rc;
- DBC *cursor;
- DBT key, data;
- ID id;
- idNode *node;
- char **rdns;
-
- bdb->bi_tree = NULL;
-
- rc = bdb->bi_id2parent->bdi_db->cursor(
- bdb->bi_id2parent->bdi_db, NULL, &cursor,
- bdb->bi_db_opflags );
- if( rc != 0 ) {
- return NOID;
- }
-
- /* When be_suffix is turned into struct berval or LDAPDN
- * life will get a lot easier... Since no DNs live on disk, we
- * need to operate on the be_suffix to fully qualify our DNs.
- * We need to know how many components are in the suffix DN,
- * so we can tell where the suffix ends and our nodes begin.
- *
- * Note that this code always uses be_suffix[0], so defining
- * multiple suffixes for a single backend won't work!
- */
- rdns = ldap_explode_dn(be->be_nsuffix[0]->bv_val, 0);
- for (i=0; rdns[i]; i++);
- bdb->bi_nrdns = i;
- charray_free(rdns);
-
- DBTzero( &key );
- DBTzero( &data );
- key.data = (char *)&id;
- key.ulen = sizeof( id );
- key.flags = DB_DBT_USERMEM;
- data.flags = DB_DBT_MALLOC;
-
- while (cursor->c_get( cursor, &key, &data, DB_NEXT ) == 0) {
- bdb_add_node( id, data.data, bdb );
- }
- cursor->c_close( cursor );
-
- rc = avl_apply(bdb->bi_tree, (AVL_APPLY)bdb_insert_kid, bdb->bi_tree,
- -1, AVL_INORDER );
+ curlen = ptr[0] << 8 | ptr[1];
+ rc = strncmp( usr->nrdn, cur->nrdn, usr->nrdnlen );
+ if ( rc == 0 ) rc = usrlen - curlen;
return rc;
}
-/* This function constructs a full DN for a given id. We really should
- * be passing idNodes directly, to save some effort...
+/* This function constructs a full DN for a given id.
*/
int bdb_fix_dn(
BackendDB *be,
ldap_pvt_thread_rdwr_rlock(&bdb->bi_tree_rdwr);
o = bdb_find_id_node(id, bdb->bi_tree);
- rlen = be->be_suffix[0]->bv_len + 1;
- nrlen = be->be_nsuffix[0]->bv_len + 1;
+ rlen = be->be_suffix[0].bv_len + 1;
+ nrlen = be->be_nsuffix[0].bv_len + 1;
for (n = o; n && n->i_parent; n=n->i_parent) {
rlen += n->i_rdn->rdn.bv_len + 1;
nrlen += n->i_rdn->nrdn.bv_len + 1;
ptr = e->e_name.bv_val;
nptr = e->e_nname.bv_val;
for (n = o; n && n->i_parent; n=n->i_parent) {
- ptr = slap_strcopy(ptr, n->i_rdn->rdn.bv_val);
+ ptr = lutil_strcopy(ptr, n->i_rdn->rdn.bv_val);
*ptr++ = ',';
- nptr = slap_strcopy(nptr, n->i_rdn->nrdn.bv_val);
+ nptr = lutil_strcopy(nptr, n->i_rdn->nrdn.bv_val);
*nptr++ = ',';
}
ldap_pvt_thread_rdwr_runlock(&bdb->bi_tree_rdwr);
- strcpy(ptr, be->be_suffix[0]->bv_val);
- strcpy(nptr, be->be_nsuffix[0]->bv_val);
+ strcpy(ptr, be->be_suffix[0].bv_val);
+ strcpy(nptr, be->be_nsuffix[0].bv_val);
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
bdb_dn2id_add(
BackendDB *be,
DB_TXN *txn,
- struct berval *pdn,
- Entry *e )
+ EntryInfo *eip,
+ Entry *e,
+ void *ctx )
{
struct bdb_info *bdb = (struct bdb_info *) be->be_private;
- int rc, rlen, nrlen;
+ DB *db = bdb->bi_dn2id->bdi_db;
DBT key, data;
- DB *db = bdb->bi_id2parent->bdi_db;
+ int rc, rlen, nrlen;
diskNode *d;
- idNode *n;
+ char *ptr;
nrlen = dn_rdnlen( be, &e->e_nname );
if (nrlen) {
rlen = 0;
}
- d = ch_malloc(sizeof(diskNode) + rlen + nrlen + 2);
- d->rdn.bv_len = rlen;
- d->nrdn.bv_len = nrlen;
- d->rdn.bv_val = (char *)(d+1);
- d->nrdn.bv_val = d->rdn.bv_val + rlen + 1;
- strncpy(d->rdn.bv_val, e->e_dn, rlen);
- d->rdn.bv_val[rlen] = '\0';
- strncpy(d->nrdn.bv_val, e->e_ndn, nrlen);
- d->nrdn.bv_val[nrlen] = '\0';
- d->rdn.bv_val -= (long)d;
- d->nrdn.bv_val -= (long)d;
-
- if (pdn->bv_len) {
- bdb_dn2id(be, txn, pdn, &d->parent);
- } else {
- d->parent = 0;
- }
+ d = sl_malloc(sizeof(diskNode) + rlen + nrlen, ctx);
+ d->entryID = e->e_id;
+ d->nrdnlen = nrlen;
+ 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';
DBTzero(&key);
DBTzero(&data);
- key.data = &e->e_id;
+ key.data = &eip->bei_id;
key.size = sizeof(ID);
key.flags = DB_DBT_USERMEM;
rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE );
if (rc == 0) {
- ldap_pvt_thread_rdwr_wlock(&bdb->bi_tree_rdwr);
- n = bdb_add_node( e->e_id, data.data, bdb);
- ldap_pvt_thread_rdwr_wunlock(&bdb->bi_tree_rdwr);
-
- if (d->parent) {
- ldap_pvt_thread_rdwr_rlock(&bdb->bi_tree_rdwr);
- bdb_insert_kid(n, bdb->bi_tree);
- ldap_pvt_thread_rdwr_runlock(&bdb->bi_tree_rdwr);
- }
- } else {
- free(d);
+ key.data = &e->e_id;
+ d->entryID = eip->bei_id;
+ d->nrdnlen = 0;
+ d->nrdn[0] = '\0';
+ d->rdn[0] = '\0';
+ data.size = sizeof(diskNode);
+
+ rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE );
}
+
+ sl_free( d, ctx );
+
return rc;
}
bdb_dn2id_delete(
BackendDB *be,
DB_TXN *txn,
- char *pdn,
- Entry *e )
+ EntryInfo *eip,
+ Entry *e,
+ void *ctx )
{
struct bdb_info *bdb = (struct bdb_info *) be->be_private;
- int rc;
- DBT key;
- DB *db = bdb->bi_id2parent->bdi_db;
- idNode *n;
+ DB *db = bdb->bi_dn2id->bdi_db;
+ DBT key, data;
+ DBC *cursor;
+ diskNode *d;
+ int rc, nrlen;
DBTzero(&key);
- key.size = sizeof(e->e_id);
- key.data = &e->e_id;
+ key.size = sizeof(ID);
+ key.ulen = key.size;
+ key.data = &eip->bei_id;
+ key.flags = DB_DBT_USERMEM;
- rc = db->del( db, txn, &key, 0);
+ DBTzero(&data);
+ data.size = sizeof(diskNode) + BEI(e)->nrdn.bv_len;
+ d = sl_malloc( data.size, ctx );
+ d->entryID = e->e_id;
+ d->nrdnlen = BEI(e)->nrdn.bv_len;
+ strcpy( d->nrdn, BEI(e)->nrdn.bv_val );
+ data.data = d;
+ data.ulen = data.size;
+ data.dlen = data.size;
+ data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
- ldap_pvt_thread_rdwr_wlock(&bdb->bi_tree_rdwr);
- n = avl_delete(&bdb->bi_tree, (void *)e->e_id, (AVL_CMP)node_find_cmp);
- if (n) {
- if (n->i_parent) {
- ldap_pvt_thread_rdwr_wlock(&n->i_parent->i_kids_rdwr);
- avl_delete(&n->i_parent->i_kids, n->i_rdn->nrdn.bv_val,
- (AVL_CMP)node_frdn_cmp);
- ldap_pvt_thread_rdwr_wunlock(&n->i_parent->i_kids_rdwr);
- }
- free(n->i_rdn);
- ldap_pvt_thread_rdwr_destroy(&n->i_kids_rdwr);
- free(n);
- }
- if (e->e_id == 1)
- bdb->bi_troot = NULL;
- ldap_pvt_thread_rdwr_wunlock(&bdb->bi_tree_rdwr);
+ rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags );
+ if ( rc ) return rc;
+
+ rc = cursor->c_get( cursor, &key, &data, DB_GET_BOTH | DB_RMW );
+ if ( rc == 0 )
+ rc = cursor->c_del( cursor, 0 );
+ cursor->c_close( cursor );
+
+ key.data = &e->e_id;
+ rc = db->del( db, txn, &key, 0);
+ sl_free( d, ctx );
return rc;
}
int
-bdb_dn2id_matched(
+bdb_dn2id(
BackendDB *be,
DB_TXN *txn,
struct berval *in,
- ID *id,
- char **matchedDN )
+ EntryInfo *ei,
+ void *ctx )
{
struct bdb_info *bdb = (struct bdb_info *) be->be_private;
- int i;
- char **rdns;
- idNode *n, *p;
+ DB *db = bdb->bi_dn2id->bdi_db;
+ DBT key, data;
+ DBC *cursor;
+ int rc = 0, nrlen;
+ char *ptr;
- if (!bdb->bi_troot)
- return DB_NOTFOUND;
+ nrlen = dn_rdnlen( be, &in );
- p = bdb->bi_troot;
- if (be_issuffix(be, in->bv_val)) {
- *id = p->i_id;
- return 0;
- }
+ DBTzero(&key);
+ key.size = sizeof(ID);
+ key.data = &eip->bei_id;
+ key.flags = DB_DBT_USERMEM;
- rdns = ldap_explode_dn(in->bv_val, 0);
- for (i=0; rdns[i]; i++);
- i -= bdb->bi_nrdns;
- if (i < 0)
- return -1;
- n = p;
- ldap_pvt_thread_rdwr_rlock(&bdb->bi_tree_rdwr);
- for (--i; i>=0; i--) {
- ldap_pvt_thread_rdwr_rlock(&p->i_kids_rdwr);
- n = bdb_find_rdn_node(rdns[i], p->i_kids);
- ldap_pvt_thread_rdwr_runlock(&p->i_kids_rdwr);
- if (!n) break;
- p = n;
- }
- ldap_pvt_thread_rdwr_runlock(&bdb->bi_tree_rdwr);
+ DBTzero(&data);
+ data.size = sizeof(diskNode) + nrlen;
+ d = sl_malloc( data.size * 3, ctx );
+ d->nrdnlen = nrlen;
+ ptr = lutil_strncopy( d->nrdn, BEI(e)->nrdn.bv_val, nrlen );
+ *ptr = '\0';
+ data.data = d;
+ data.ulen = data.size * 3;
+ data.flags = DB_DBT_USERMEM;
- if (n) {
- *id = n->i_id;
- } else if (matchedDN) {
- int len = 0, j;
- char *ptr;
- ++i;
- for (j=i; rdns[j]; j++)
- len += strlen(rdns[j]) + 1;
- ptr = ch_malloc(len);
- *matchedDN = ptr;
- for (;rdns[i]; i++) {
- ptr = slap_strcopy(ptr, rdns[i]);
- *ptr++ = ',';
- }
- ptr[-1] = '\0';
- }
- return n ? 0 : DB_NOTFOUND;
-}
+ rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags );
+ if ( rc ) return rc;
-int
-bdb_dn2id(
- BackendDB *be,
- DB_TXN *txn,
- struct berval *dn,
- ID *id )
-{
- return bdb_dn2id_matched(be, txn, dn, id, NULL);
+ rc = cursor->c_get( cursor, &key, &data, DB_GET_BOTH );
+ cursor->c_close( cursor );
+ if ( rc ) return rc;
+
+ AC_MEMCPY( &ei->bei_id, &d->entryID, sizeof(ID) );
+ ei->rdn.bv_len = data.size - sizeof(diskNode) - nrlen;
+ ptr = d->nrdn + nrlen + 1;
+ strcpy( ei->rdn.bv_val, ptr );
+
+ return rc;
}
int
bdb_dn2id_children(
- BackendDB *be,
+ Operation *op,
DB_TXN *txn,
- struct berval *dn )
+ Entry *e )
{
+ struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
int rc;
- struct bdb_info *bdb = (struct bdb_info *) be->be_private;
ID id;
idNode *n;
- rc = bdb_dn2id(be, txn, dn, &id);
+ rc = bdb_dn2id(be, txn, dn, &id, flags);
if (rc != 0)
return rc;
*/
static int
insert_one(
- idNode *n,
- ID *ids
+ void *v_n,
+ void *v_ids
)
{
+ idNode *n = v_n;
+ ID *ids = v_ids;
return bdb_idl_insert(ids, n->i_id);
}
static int
insert_sub(
- idNode *n,
- ID *ids
+ void *v_n,
+ void *v_ids
)
{
+ idNode *n = v_n;
+ ID *ids = v_ids;
int rc;
rc = bdb_idl_insert(ids, n->i_id);
if (rc == 0) {
ldap_pvt_thread_rdwr_rlock(&n->i_kids_rdwr);
- rc = avl_apply(n->i_kids, (AVL_APPLY)insert_sub, ids, -1,
- AVL_INORDER);
+ rc = avl_apply(n->i_kids, insert_sub, ids, -1, AVL_INORDER);
ldap_pvt_thread_rdwr_runlock(&n->i_kids_rdwr);
}
return rc;
ID id;
idNode *n;
- if (prefix == DN_SUBTREE_PREFIX && be_issuffix(be, dn->bv_val)) {
+ if (prefix == DN_SUBTREE_PREFIX && be_issuffix(be, dn)) {
BDB_IDL_ALL(bdb, ids);
return 0;
}
- rc = bdb_dn2id(be, NULL, dn, &id);
+ rc = bdb_dn2id(be, NULL, dn, &id, 0);
if (rc) return rc;
ldap_pvt_thread_rdwr_rlock(&bdb->bi_tree_rdwr);
ids[0] = 0;
ldap_pvt_thread_rdwr_rlock(&n->i_kids_rdwr);
if (prefix == DN_ONE_PREFIX) {
- rc = avl_apply(n->i_kids, (AVL_APPLY)insert_one, ids, -1,
- AVL_INORDER);
+ rc = avl_apply(n->i_kids, insert_one, ids, -1, AVL_INORDER);
} else {
- rc = avl_apply(n->i_kids, (AVL_APPLY)insert_sub, ids, -1,
- AVL_INORDER);
+ ids[0] = 1;
+ ids[1] = id;
+ if (n->i_kids)
+ rc = avl_apply(n->i_kids, insert_sub, ids, -1, AVL_INORDER);
}
ldap_pvt_thread_rdwr_runlock(&n->i_kids_rdwr);
return rc;
projects / openldap / blobdiff