+static inline isc_result_t
+previous_closest_nsec(dns_rdatatype_t type, rbtdb_search_t *search,
+ dns_name_t *name, dns_name_t *origin,
+ dns_rbtnode_t **nodep, dns_rbtnodechain_t *nsecchain,
+ isc_boolean_t *firstp)
+{
+ dns_fixedname_t ftarget;
+ dns_name_t *target;
+ dns_rbtnode_t *nsecnode;
+ isc_result_t result;
+
+ if (type == dns_rdatatype_nsec3) {
+ result = dns_rbtnodechain_prev(&search->chain, NULL, NULL);
+ if (result != ISC_R_SUCCESS && result != DNS_R_NEWORIGIN)
+ return (result);
+ result = dns_rbtnodechain_current(&search->chain, name, origin,
+ nodep);
+ if (result != ISC_R_SUCCESS)
+ return (result);
+ return (ISC_R_SUCCESS);
+ }
+
+ dns_fixedname_init(&ftarget);
+ target = dns_fixedname_name(&ftarget);
+
+ for (;;) {
+ if (*firstp) {
+ /*
+ * Construct the name of the second node to check.
+ * It is the first node sought in the NSEC tree.
+ */
+ *firstp = ISC_FALSE;
+ dns_rbtnodechain_init(nsecchain, NULL);
+ result = dns_name_concatenate(name, origin,
+ target, NULL);
+ if (result != ISC_R_SUCCESS)
+ return (result);
+ nsecnode = NULL;
+ result = dns_rbt_findnode(search->rbtdb->nsec,
+ target, NULL,
+ &nsecnode, nsecchain,
+ DNS_RBTFIND_NOOPTIONS,
+ NULL, NULL);
+ if (result == ISC_R_SUCCESS) {
+ /*
+ * Since this was the first loop, finding the
+ * name in the NSEC tree implies that the first
+ * node checked in the main tree had an
+ * unacceptable NSEC record.
+ * Try the previous node in the NSEC tree.
+ */
+ result = dns_rbtnodechain_prev(nsecchain,
+ name, origin);
+ if (result == DNS_R_NEWORIGIN)
+ result = ISC_R_SUCCESS;
+ } else if (result == ISC_R_NOTFOUND
+ || result == DNS_R_PARTIALMATCH) {
+ result = dns_rbtnodechain_current(nsecchain,
+ name, origin, NULL);
+ if (result == ISC_R_NOTFOUND)
+ result = ISC_R_NOMORE;
+ }
+ } else {
+ /*
+ * This is a second or later trip through the auxiliary
+ * tree for the name of a third or earlier NSEC node in
+ * the main tree. Previous trips through the NSEC tree
+ * must have found nodes in the main tree with NSEC
+ * records. Perhaps they lacked signature records.
+ */
+ result = dns_rbtnodechain_prev(nsecchain, name, origin);
+ if (result == DNS_R_NEWORIGIN)
+ result = ISC_R_SUCCESS;
+ if (result != ISC_R_SUCCESS)
+ return (result);
+ }
+ if (result != ISC_R_SUCCESS)
+ return (result);
+
+ /*
+ * Construct the name to seek in the main tree.
+ */
+ result = dns_name_concatenate(name, origin, target, NULL);
+ if (result != ISC_R_SUCCESS)
+ return (result);
+
+ *nodep = NULL;
+ result = dns_rbt_findnode(search->rbtdb->tree, target, NULL,
+ nodep, &search->chain,
+ DNS_RBTFIND_NOOPTIONS, NULL, NULL);
+ if (result == ISC_R_SUCCESS)
+ return (result);
+
+ /*
+ * There should always be a node in the main tree with the
+ * same name as the node in the auxiliary NSEC tree, except for
+ * nodes in the auxiliary tree that are awaiting deletion.
+ */
+ if (result == DNS_R_PARTIALMATCH)
+ result = ISC_R_NOTFOUND;
+
+ if (result != ISC_R_NOTFOUND) {
+ isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
+ DNS_LOGMODULE_CACHE, ISC_LOG_ERROR,
+ "previous_closest_nsec(): %s",
+ isc_result_totext(result));
+ return (DNS_R_BADDB);
+ }
+ }
+}
+