lyd_diff(struct lyd_node *first, struct lyd_node *second, int options)
{
    struct ly_ctx *ctx;
    int rc;
    struct lyd_node *elem1, *elem2, *iter, *aux, *parent = NULL, *next1, *next2;
    struct lyd_difflist *result, *result2 = NULL;
    void *new;
    unsigned int size, size2, index = 0, index2 = 0, i, j, k;
    struct matchlist_s {
        struct matchlist_s *prev;
        struct ly_set *match;
        unsigned int i;
    } *matchlist = NULL, *mlaux;
    struct ly_set *ordset = NULL;
    struct diff_ordered *ordered;
    struct diff_ordered_dist *dist_aux, *dist_iter;
    struct diff_ordered_item item_aux;

    if (!first) {
        /* all nodes in second were created,
         * but the second must be top level */
        if (second && second->parent) {
            LOGERR(second->schema->module->ctx, LY_EINVAL, "%s: \"first\" parameter is NULL and \"second\" is not top level.", __func__);
            return NULL;
        }
        result = lyd_diff_init_difflist(NULL, &size);
        LY_TREE_FOR(second, iter) {
            if (!iter->dflt || (options & LYD_DIFFOPT_WITHDEFAULTS)) { /* skip the implicit nodes */
                if (lyd_difflist_add(result, &size, index++, LYD_DIFF_CREATED, NULL, iter)) {
                    goto error;
                }
            }
            if (options & LYD_DIFFOPT_NOSIBLINGS) {
                break;
            }
        }
        return result;
    } else if (!second) {
        /* all nodes from first were deleted */
        result = lyd_diff_init_difflist(first->schema->module->ctx, &size);
        LY_TREE_FOR(first, iter) {
            if (!iter->dflt || (options & LYD_DIFFOPT_WITHDEFAULTS)) { /* skip the implicit nodes */
                if (lyd_difflist_add(result, &size, index++, LYD_DIFF_DELETED, iter, NULL)) {
                    goto error;
                }
            }
            if (options & LYD_DIFFOPT_NOSIBLINGS) {
                break;
            }
        }
        return result;
    }

    ctx = first->schema->module->ctx;

    if (options & LYD_DIFFOPT_NOSIBLINGS) {
        /* both trees must start at the same (schema) node */
        if (first->schema != second->schema) {
            LOGERR(ctx, LY_EINVAL, "%s: incompatible trees to compare with LYD_OPT_NOSIBLINGS option.", __func__);
            return NULL;
        }
        /* use first's and second's child to make comparison the same as without LYD_OPT_NOSIBLINGS */
        first = first->child;
        second = second->child;
    } else {
        /* go to the first sibling in both trees */
        if (first->parent) {
            first = first->parent->child;
        } else {
            while (first->prev->next) {
                first = first->prev;
            }
        }

        if (second->parent) {
            second = second->parent->child;
        } else {
            for (; second->prev->next; second = second->prev);
        }

        /* check that both has the same (schema) parent or that they are top-level nodes */
        if ((first->parent && second->parent && first->parent->schema != second->parent->schema) ||
                (!first->parent && first->parent != second->parent)) {
            LOGERR(ctx, LY_EINVAL, "%s: incompatible trees with different parents.", __func__);
            return NULL;
        }
    }
    if (first == second) {
        LOGERR(ctx, LY_EINVAL, "%s: comparing the same tree does not make sense.", __func__);
        return NULL;
    }

    /* initiate resulting structure */
    result = lyd_diff_init_difflist(ctx, &size);
    LY_CHECK_ERR_GOTO(!result, , error);

    /* the records about created and moved items are created in
     * bad order, so the records about created nodes (and their
     * possible moving) is stored separately and added to the
     * main result at the end.
     */
    result2 = lyd_diff_init_difflist(ctx, &size2);
    LY_CHECK_ERR_GOTO(!result2, , error);

    matchlist = malloc(sizeof *matchlist);
    LY_CHECK_ERR_GOTO(!matchlist, LOGMEM(ctx), error);

    matchlist->i = 0;
    matchlist->match = ly_set_new();
    matchlist->prev = NULL;

    ordset = ly_set_new();
    LY_CHECK_ERR_GOTO(!ordset, , error);

    /*
     * compare trees
     */
    /* 1) newly created nodes + changed leafs/anyxmls */
    next1 = first;
    for (elem2 = next2 = second; elem2; elem2 = next2) {
        /* keep right pointer for searching in the first tree */
        elem1 = next1;

        if (elem2->dflt && !(options & LYD_DIFFOPT_WITHDEFAULTS)) {
            /* skip default elements, they could not be created or changed, just deleted */
            goto cmp_continue;
        }

#ifdef LY_ENABLED_CACHE
        struct lyd_node **iter_p;

        if (elem1 && elem1->parent && elem1->parent->ht) {
            iter = NULL;
            if (!lyht_find(elem1->parent->ht, &elem2, elem2->hash, (void **)&iter_p)) {
                iter = *iter_p;
                /* we found a match */
                if (iter->dflt && !(options & LYD_DIFFOPT_WITHDEFAULTS)) {
                    /* the second one cannot be default (see lyd_diff()),
                     * so the nodes differs (first one is default node) */
                    iter = NULL;
                }
                while (iter && (iter->validity & LYD_VAL_INUSE)) {
                    /* state lists, find one not-already-found */
                    assert((iter->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) && (iter->schema->flags & LYS_CONFIG_R));
                    if (lyht_find_next(elem1->parent->ht, &iter, iter->hash, (void **)&iter_p)) {
                        iter = NULL;
                    } else {
                        iter = *iter_p;
                    }
                }
            }
        } else
#endif
        {
            /* search for elem2 instance in the first */
            LY_TREE_FOR(elem1, iter) {
                if (iter->schema != elem2->schema) {
                    continue;
                }

                /* elem2 instance found */
                rc = lyd_diff_compare(iter, elem2, options);
                if (rc == -1) {
                    goto error;
                } else if (rc == 0) {
                    /* match */
                    break;
                } /* else, continue */
            }
        }
        /* we have a match */
        if (iter && lyd_diff_match(iter, elem2, result, &size, &index, matchlist->match, ordset, options)) {
            goto error;
        }

        if (!iter) {
            /* elem2 not found in the first tree */
            if (lyd_difflist_add(result2, &size2, index2++, LYD_DIFF_CREATED, elem1 ? elem1->parent : parent, elem2)) {
                goto error;
            }

            if (elem1 && (elem2->schema->flags & LYS_USERORDERED)) {
                /* store the correct place where the node is supposed to be moved after creation */
                /* if elem1 does not exist, all nodes were created and they will be created in
                 * correct order, so it is not needed to detect moves */
                for (aux = elem2->prev; aux->next; aux = aux->prev) {
                    if (aux->schema == elem2->schema) {
                        /* predecessor found */
                        break;
                    }
                }
                if (!aux->next) {
                    /* predecessor not found */
                    aux = NULL;
                }
                if (lyd_difflist_add(result2, &size2, index2++, LYD_DIFF_MOVEDAFTER2, aux, elem2)) {
                    goto error;
                }
            }
        }

cmp_continue:
        /* select element for the next run                                    1     2
         * - first, process all siblings of a single parent                  / \   / \
         * - then, go to children (deep)                                    3   4 7   8
         * - return to the parent's next sibling children                  / \
         *                                                                5   6
         */
        /* siblings first */
        next1 = elem1;
        next2 = elem2->next;

        if (!next2) {
            /* children */

            /* first pass of the siblings done, some additional work for future
             * detection of move may be needed */
            for (i = ordset->number; i > 0; i--) {
                ordered = (struct diff_ordered *)ordset->set.g[i - 1];
                if (ordered->items) {
                    /* already preprocessed ordered structure */
                    break;
                }
                ordered->items = calloc(ordered->count, sizeof *ordered->items);
                LY_CHECK_ERR_GOTO(!ordered->items, LOGMEM(ctx), error);
                ordered->dist = NULL;
                /* zero the count to be used as a node position in lyd_diff_move_preprocess() */
                ordered->count = 0;
            }

            /* first, get the first sibling */
            if (elem2->parent == second->parent) {
                elem2 = second;
            } else {
                elem2 = elem2->parent->child;
            }

            /* and then find the first child */
            LY_TREE_FOR(elem2, iter) {
                if (!(iter->validity & LYD_VAL_INUSE)) {
                    /* the iter is not present in both trees */
                    continue;
                } else if (matchlist->i == matchlist->match->number) {
                    if (iter == elem2) {
                        /* we already went through all the matching nodes and now we are just supposed to stop
                         * the loop with no iter */
                        iter = NULL;
                        break;
                    } else {
                        /* we have started with some not processed data in matchlist, but now we have
                         * the INUSE iter and no nodes in matchlist to find its equivalent,
                         * so something went wrong somewhere */
                        LOGINT(ctx);
                        goto error;
                    }
                }

                iter->validity &= ~LYD_VAL_INUSE;
                if ((iter->schema->nodetype & (LYS_LEAFLIST | LYS_LIST)) && (iter->schema->flags & LYS_USERORDERED)) {
                    for (j = ordset->number; j > 0; j--) {
                        ordered = (struct diff_ordered *)ordset->set.g[j - 1];
                        if (ordered->schema != iter->schema || !lyd_diff_equivnode(ordered->parent, iter->parent)) {
                            continue;
                        }

                        /* store necessary information for move detection */
                        lyd_diff_move_preprocess(ordered, matchlist->match->set.d[matchlist->i], iter);
                        break;
                    }
                }

                if (((iter->schema->nodetype == LYS_CONTAINER) || ((iter->schema->nodetype == LYS_LIST)
                        && ((struct lys_node_list *)iter->schema)->keys_size)) && iter->child) {
                    while (matchlist->i < matchlist->match->number && matchlist->match->set.d[matchlist->i]->schema != iter->schema) {
                        matchlist->i++;
                    }
                    if (matchlist->i == matchlist->match->number) {
                        /* we have the INUSE iter, so we have to find its equivalent in match list */
                        LOGINT(ctx);
                        goto error;
                    }
                    next1 = matchlist->match->set.d[matchlist->i]->child;
                    if (!next1) {
                        parent = matchlist->match->set.d[matchlist->i];
                    }
                    matchlist->i++;
                    next2 = iter->child;
                    break;
                }
                matchlist->i++;
            }

            if (!iter) {
                /* no child/data on next level */
                if (elem2 == second) {
                    /* done */
                    break;
                }
            } else {
                /* create new matchlist item */
                mlaux = malloc(sizeof *mlaux);
                LY_CHECK_ERR_GOTO(!mlaux, LOGMEM(ctx), error);
                mlaux->i = 0;
                mlaux->match = ly_set_new();
                mlaux->prev = matchlist;
                matchlist = mlaux;
            }
        }

        while (!next2) {
            /* parent */

            /* clean the last match set */
            ly_set_clean(matchlist->match);
            matchlist->i = 0;

            /* try to go to a cousin - child of the next parent's sibling */
            mlaux = matchlist->prev;
            LY_TREE_FOR(elem2->parent->next, iter) {
                if (!(iter->validity & LYD_VAL_INUSE)) {
                    continue;
                } else if (mlaux->i == mlaux->match->number) {
                    if (iter == elem2->parent->next) {
                        /* we already went through all the matching nodes and now we are just supposed to stop
                         * the loop with no iter */
                        iter = NULL;
                        break;
                    } else {
                        /* we have started with some not processed data in matchlist, but now we have
                         * the INUSE iter and no nodes in matchlist to find its equivalent,
                         * so something went wrong somewhere */
                        LOGINT(ctx);
                        goto error;
                    }
                }

                iter->validity &= ~LYD_VAL_INUSE;
                if ((iter->schema->nodetype & (LYS_LEAFLIST | LYS_LIST)) && (iter->schema->flags & LYS_USERORDERED)) {
                    for (j = ordset->number ; j > 0; j--) {
                        ordered = (struct diff_ordered *)ordset->set.g[j - 1];
                        if (ordered->schema != iter->schema || !lyd_diff_equivnode(ordered->parent, iter->parent)) {
                            continue;
                        }

                        /* store necessary information for move detection */
                        lyd_diff_move_preprocess(ordered, mlaux->match->set.d[mlaux->i], iter);
                        break;
                    }
                }

                if (((iter->schema->nodetype == LYS_CONTAINER) || ((iter->schema->nodetype == LYS_LIST)
                        && ((struct lys_node_list *)iter->schema)->keys_size)) && iter->child) {
                    while (mlaux->i < mlaux->match->number && mlaux->match->set.d[mlaux->i]->schema != iter->schema) {
                        mlaux->i++;
                    }
                    if (mlaux->i == mlaux->match->number) {
                        /* we have the INUSE iter, so we have to find its equivalent in match list */
                        LOGINT(ctx);
                        goto error;
                    }
                    next1 = mlaux->match->set.d[mlaux->i]->child;
                    if (!next1) {
                        parent = mlaux->match->set.d[mlaux->i];
                    }
                    mlaux->i++;
                    next2 = iter->child;
                    break;
                }
                mlaux->i++;
            }

            /* if no cousin exists, continue next loop on higher level */
            if (!iter) {
                elem2 = elem2->parent;

                /* remove matchlist item */
                ly_set_free(matchlist->match);
                mlaux = matchlist;
                matchlist = matchlist->prev;
                free(mlaux);

                if (!matchlist->prev) { /* elem2->parent == second->parent */
                    /* done */
                    break;
                }
            }
        }
    }

    ly_set_free(matchlist->match);
    free(matchlist);
    matchlist = NULL;

    /* 2) deleted nodes */
    LY_TREE_DFS_BEGIN(first, next1, elem1) {
        /* search for elem1s deleted in the second */
        if (elem1->validity & LYD_VAL_INUSE) {
            /* erase temporary LYD_VAL_INUSE flag and continue into children */
            elem1->validity &= ~LYD_VAL_INUSE;
        } else if (!elem1->dflt || (options & LYD_DIFFOPT_WITHDEFAULTS)) {
            /* elem1 has no matching node in second, add it into result */
            if (lyd_difflist_add(result, &size, index++, LYD_DIFF_DELETED, elem1, NULL)) {
                goto error;
            }

            /* skip subtree processing of data missing in the second tree */
            goto dfs_nextsibling;
        }

        /* modified LY_TREE_DFS_END() */
        /* select element for the next run - children first */
        if ((elem1->schema->nodetype & (LYS_LEAF | LYS_LEAFLIST | LYS_ANYDATA)) || ((elem1->schema->nodetype == LYS_LIST)
                && !((struct lys_node_list *)elem1->schema)->keys_size)) {
            next1 = NULL;
        } else {
            next1 = elem1->child;
        }
        if (!next1) {
dfs_nextsibling:
            /* try siblings */
            next1 = elem1->next;
        }
        while (!next1) {
            /* parent is already processed, go to its sibling */

            elem1 = elem1->parent;
            if (elem1 == first->parent) {
                /* we are done, no next element to process */
                break;
            }

            next1 = elem1->next;
        }
    }

    /* 3) moved nodes (when user-ordered) */
    for (i = 0; i < ordset->number; i++) {
        ordered = (struct diff_ordered *)ordset->set.g[i];
        if (!ordered->dist->dist) {
            /* the dist list is sorted here, but the biggest dist is 0,
             * so nothing changed in order of these items between first
             * and second. We can continue with another user-ordered list.
             */
            continue;
        }

        /* get needed movements
         * - from the biggest distances try to apply node movements
         * on first tree node until they will be ordered as in the
         * second tree - i.e. until there will be no position difference
         */

        for (dist_iter = ordered->dist; ; dist_iter = dist_iter->next) {
            /* dist list is sorted at the beginning, since applying a move causes
             * just a small change in other distances, we assume that the biggest
             * dist is the next one (note that dist list is implemented as ring
             * list). This way we avoid sorting distances after each move. The loop
             * stops when all distances are zero.
             */
            dist_aux = dist_iter;
            while (!dist_iter->dist) {
                /* no dist, so no move. Try another, but when
                 * there is no dist at all, stop the loop
                 */
                dist_iter = dist_iter->next;
                if (dist_iter == dist_aux) {
                    /* all dist we zeroed */
                    goto movedone;
                }
            }
            /* something to move */

            /* get the item to move */
            for (k = 0; k < ordered->count; k++) {
                if (ordered->items[k].dist == dist_iter) {
                    break;
                }
            }

            /* apply the move (distance) */
            memcpy(&item_aux, &ordered->items[k], sizeof item_aux);
            if (dist_iter->dist > 0) {
                /* move to right (other move to left) */
                while (dist_iter->dist) {
                    memcpy(&ordered->items[k], &ordered->items[k + 1], sizeof *ordered->items);
                    ordered->items[k].dist->dist++; /* update moved item distance */
                    dist_iter->dist--;
                    k++;
                }
            } else {
                /* move to left (other move to right) */
                while (dist_iter->dist) {
                    memcpy(&ordered->items[k], &ordered->items[k - 1], sizeof *ordered->items);
                    ordered->items[k].dist->dist--; /* update moved item distance */
                    dist_iter->dist++;
                    k--;
                }
            }
            memcpy(&ordered->items[k], &item_aux, sizeof *ordered->items);

            /* store the transaction into the difflist */
            if (lyd_difflist_add(result, &size, index++, LYD_DIFF_MOVEDAFTER1, item_aux.first,
                                 (k > 0) ? ordered->items[k - 1].first : NULL)) {
                goto error;
            }
            continue;

movedone:
            break;
        }
    }

    diff_ordset_free(ordset);
    ordset = NULL;

    if (index2) {
        /* append result2 with newly created
         * (and possibly moved) nodes */
        if (index + index2 + 1 >= size) {
            /* result must be enlarged */
            size = index + index2 + 1;
            new = realloc(result->type, size * sizeof *result->type);
            LY_CHECK_ERR_GOTO(!new, LOGMEM(ctx), error);
            result->type = new;

            new = realloc(result->first, size * sizeof *result->first);
            LY_CHECK_ERR_GOTO(!new, LOGMEM(ctx), error);
            result->first = new;

            new = realloc(result->second, size * sizeof *result->second);
            LY_CHECK_ERR_GOTO(!new, LOGMEM(ctx), error);
            result->second = new;
        }

        /* append */
        memcpy(&result->type[index], result2->type, (index2 + 1) * sizeof *result->type);
        memcpy(&result->first[index], result2->first, (index2 + 1) * sizeof *result->first);
        memcpy(&result->second[index], result2->second, (index2 + 1) * sizeof *result->second);
    }
    lyd_free_diff(result2);

    return result;

error:
    while (matchlist) {
        mlaux = matchlist;
        matchlist = mlaux->prev;
        ly_set_free(mlaux->match);
        free(mlaux);

    }
    diff_ordset_free(ordset);

    lyd_free_diff(result);
    lyd_free_diff(result2);

    return NULL;
}