static int ldb_kv_index_dn_ordered(struct ldb_module *module,
				   struct ldb_kv_private *ldb_kv,
				   const struct ldb_parse_tree *tree,
				   struct dn_list *list, bool ascending)
{
	enum key_truncation truncation = KEY_NOT_TRUNCATED;
	struct ldb_context *ldb = ldb_module_get_ctx(module);

	struct ldb_val ldb_key = { 0 }, ldb_key2 = { 0 };
	struct ldb_val start_key, end_key;
	struct ldb_dn *key_dn = NULL;
	const struct ldb_schema_attribute *a = NULL;

	struct ldb_kv_ordered_index_context ctx;
	int ret;

	TALLOC_CTX *tmp_ctx = NULL;

	if (!ldb_kv_is_indexed(module, ldb_kv, tree->u.comparison.attr)) {
		return LDB_ERR_OPERATIONS_ERROR;
	}

	if (ldb_kv->cache->GUID_index_attribute == NULL) {
		return LDB_ERR_OPERATIONS_ERROR;
	}

	/* bail out if we're in a transaction, full search instead. */
	if (ldb_kv->kv_ops->transaction_active(ldb_kv)) {
		return LDB_ERR_OPERATIONS_ERROR;
	}

	if (ldb_kv->disallow_dn_filter &&
	    (ldb_attr_cmp(tree->u.comparison.attr, "dn") == 0)) {
		/* in AD mode we do not support "(dn=...)" search filters */
		list->dn = NULL;
		list->count = 0;
		return LDB_SUCCESS;
	}
	if (tree->u.comparison.attr[0] == '@') {
		/* Do not allow a indexed search against an @ */
		list->dn = NULL;
		list->count = 0;
		return LDB_SUCCESS;
	}

	a = ldb_schema_attribute_by_name(ldb, tree->u.comparison.attr);

	/*
	 * If there's no index format function defined for this attr, then
	 * the lexicographic order in the database doesn't correspond to the
	 * attr's ordering, so we can't use the iterate_range op.
	 */
	if (a->syntax->index_format_fn == NULL) {
		return LDB_ERR_OPERATIONS_ERROR;
	}

	tmp_ctx = talloc_new(NULL);
	if (tmp_ctx == NULL) {
		return ldb_module_oom(module);
	}

	key_dn = ldb_kv_index_key(ldb, tmp_ctx, ldb_kv, tree->u.comparison.attr,
				  &tree->u.comparison.value,
				  NULL, &truncation);
	if (!key_dn) {
		TALLOC_FREE(tmp_ctx);
		return LDB_ERR_OPERATIONS_ERROR;
	} else if (truncation == KEY_TRUNCATED) {
		ldb_debug(ldb, LDB_DEBUG_WARNING,
			  __location__
			  ": ordered index violation: key dn truncated: %s\n",
			  ldb_dn_get_linearized(key_dn));
		TALLOC_FREE(tmp_ctx);
		return LDB_ERR_OPERATIONS_ERROR;
	}
	ldb_key = ldb_kv_key_dn(tmp_ctx, key_dn);
	talloc_free(key_dn);
	if (ldb_key.data == NULL) {
		TALLOC_FREE(tmp_ctx);
		return LDB_ERR_OPERATIONS_ERROR;
	}

	key_dn = ldb_kv_index_key(ldb, tmp_ctx,
				  ldb_kv, tree->u.comparison.attr,
				  NULL, NULL, &truncation);
	if (!key_dn) {
		TALLOC_FREE(tmp_ctx);
		return LDB_ERR_OPERATIONS_ERROR;
	} else if (truncation == KEY_TRUNCATED) {
		ldb_debug(ldb, LDB_DEBUG_WARNING,
			  __location__
			  ": ordered index violation: key dn truncated: %s\n",
			  ldb_dn_get_linearized(key_dn));
		TALLOC_FREE(tmp_ctx);
		return LDB_ERR_OPERATIONS_ERROR;
	}

	ldb_key2 = ldb_kv_key_dn(tmp_ctx, key_dn);
	talloc_free(key_dn);
	if (ldb_key2.data == NULL) {
		TALLOC_FREE(tmp_ctx);
		return LDB_ERR_OPERATIONS_ERROR;
	}

	/*
	 * In order to avoid defining a start and end key for the search, we
	 * notice that each index key is of the form:
	 *
	 *     DN=@INDEX:<ATTRIBUTE>:<VALUE>\0.
	 *
	 * We can simply make our start key DN=@INDEX:<ATTRIBUTE>: and our end
	 * key DN=@INDEX:<ATTRIBUTE>; to return all index entries for a
	 * particular attribute.
	 *
	 * Our LMDB backend uses the default memcmp for key comparison.
	 */

	/* Eliminate NUL byte at the end of the empty key */
	ldb_key2.length--;

	if (ascending) {
		/* : becomes ; for pseudo end-key */
		ldb_key2.data[ldb_key2.length-1]++;
		start_key = ldb_key;
		end_key = ldb_key2;
	} else {
		start_key = ldb_key2;
		end_key = ldb_key;
	}

	ctx.module = module;
	ctx.error = 0;
	ctx.dn_list = list;
	ctx.dn_list->count = 0;
	ctx.dn_list->dn = talloc_zero_array(ctx.dn_list, struct ldb_val, 2);

	ret = ldb_kv->kv_ops->iterate_range(ldb_kv, start_key, end_key,
					    traverse_range_index, &ctx);

	if (ret != LDB_SUCCESS || ctx.error != LDB_SUCCESS) {
		TALLOC_FREE(tmp_ctx);
		return LDB_ERR_OPERATIONS_ERROR;
	}

	TYPESAFE_QSORT(ctx.dn_list->dn, ctx.dn_list->count,
		       ldb_val_equal_exact_for_qsort);

	TALLOC_FREE(tmp_ctx);

	return LDB_SUCCESS;
}
static int ldb_kv_index_dn_ordered(struct ldb_module *module,
				   struct ldb_kv_private *ldb_kv,
				   const struct ldb_parse_tree *tree,
				   struct dn_list *list, bool ascending)
{
	enum key_truncation truncation = KEY_NOT_TRUNCATED;
	struct ldb_context *ldb = ldb_module_get_ctx(module);

	struct ldb_val ldb_key = { 0 }, ldb_key2 = { 0 };
	struct ldb_val start_key, end_key;
	struct ldb_dn *key_dn = NULL;
	const struct ldb_schema_attribute *a = NULL;

	struct ldb_kv_ordered_index_context ctx;
	int ret;

	TALLOC_CTX *tmp_ctx = NULL;

	if (!ldb_kv_is_indexed(module, ldb_kv, tree->u.comparison.attr)) {
		return LDB_ERR_OPERATIONS_ERROR;
	}

	if (ldb_kv->cache->GUID_index_attribute == NULL) {
		return LDB_ERR_OPERATIONS_ERROR;
	}

	 
	if (ldb_kv->kv_ops->transaction_active(ldb_kv)) {
		return LDB_ERR_OPERATIONS_ERROR;
	}

	if (ldb_kv->disallow_dn_filter &&
	    (ldb_attr_cmp(tree->u.comparison.attr, "dn") == 0)) {
		 
		list->dn = NULL;
		list->count = 0;
		return LDB_SUCCESS;
	}
	if (tree->u.comparison.attr[0] == '@') {
		 
		list->dn = NULL;
		list->count = 0;
		return LDB_SUCCESS;
	}

	a = ldb_schema_attribute_by_name(ldb, tree->u.comparison.attr);

	 
	if (a->syntax->index_format_fn == NULL) {
		return LDB_ERR_OPERATIONS_ERROR;
	}

	tmp_ctx = talloc_new(NULL);
	if (tmp_ctx == NULL) {
		return ldb_module_oom(module);
	}

	key_dn = ldb_kv_index_key(ldb, tmp_ctx, ldb_kv, tree->u.comparison.attr,
				  &tree->u.comparison.value,
				  NULL, &truncation);
	if (!key_dn) {
		TALLOC_FREE(tmp_ctx);
		return LDB_ERR_OPERATIONS_ERROR;
	} else if (truncation == KEY_TRUNCATED) {
		ldb_debug(ldb, LDB_DEBUG_WARNING,
			  __location__
			  ": ordered index violation: key dn truncated: %s\n",
			  ldb_dn_get_linearized(key_dn));
		TALLOC_FREE(tmp_ctx);
		return LDB_ERR_OPERATIONS_ERROR;
	}
	ldb_key = ldb_kv_key_dn(tmp_ctx, key_dn);
	talloc_free(key_dn);
	if (ldb_key.data == NULL) {
		TALLOC_FREE(tmp_ctx);
		return LDB_ERR_OPERATIONS_ERROR;
	}

	key_dn = ldb_kv_index_key(ldb, tmp_ctx,
				  ldb_kv, tree->u.comparison.attr,
				  NULL, NULL, &truncation);
	if (!key_dn) {
		TALLOC_FREE(tmp_ctx);
		return LDB_ERR_OPERATIONS_ERROR;
	} else if (truncation == KEY_TRUNCATED) {
		ldb_debug(ldb, LDB_DEBUG_WARNING,
			  __location__
			  ": ordered index violation: key dn truncated: %s\n",
			  ldb_dn_get_linearized(key_dn));
		TALLOC_FREE(tmp_ctx);
		return LDB_ERR_OPERATIONS_ERROR;
	}

	ldb_key2 = ldb_kv_key_dn(tmp_ctx, key_dn);
	talloc_free(key_dn);
	if (ldb_key2.data == NULL) {
		TALLOC_FREE(tmp_ctx);
		return LDB_ERR_OPERATIONS_ERROR;
	}

	 

	 
	ldb_key2.length--;

	if (ascending) {
		 
		ldb_key2.data[ldb_key2.length-1]++;
		start_key = ldb_key;
		end_key = ldb_key2;
	} else {
		start_key = ldb_key2;
		end_key = ldb_key;
	}

	ctx.module = module;
	ctx.error = 0;
	ctx.dn_list = list;
	ctx.dn_list->count = 0;
	ctx.dn_list->dn = talloc_zero_array(ctx.dn_list, struct ldb_val, 2);

	ret = ldb_kv->kv_ops->iterate_range(ldb_kv, start_key, end_key,
					    traverse_range_index, &ctx);

	if (ret != LDB_SUCCESS || ctx.error != LDB_SUCCESS) {
		TALLOC_FREE(tmp_ctx);
		return LDB_ERR_OPERATIONS_ERROR;
	}

	TYPESAFE_QSORT(ctx.dn_list->dn, ctx.dn_list->count,
		       ldb_val_equal_exact_for_qsort);

	TALLOC_FREE(tmp_ctx);

	return LDB_SUCCESS;
}