+ 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(
+ char *nrdn,
+ idNode *n
+)
+{
+ return strcmp(nrdn, n->i_rdn->nrdn.bv_val);
+}