+ 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 );
+ return rc;
+}
+#else /* BDB_HIER */
+
+/* Experimental management routines for a hierarchically structured backend.
+ *
+ * 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.
+ */
+typedef struct diskNode {
+ ID parent;
+ struct berval rdn;
+ struct berval nrdn;
+} 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.
+ */
+static int
+node_find_cmp(
+ ID id,
+ idNode *n
+)
+{
+ return id - n->i_id;
+}
+
+static int
+node_frdn_cmp(
+ struct berval *nrdn,
+ idNode *n
+)
+{
+ return ber_bvcmp(nrdn, &n->i_rdn->nrdn);
+}