/*
 * Copyright 2025 The FreeBSD Foundation
 *
 * SPDX-License-Identifier: BSD-2-Clause
 *
 * This software was developed by Konstantin Belousov <kib@FreeBSD.org>
 * under sponsorship from the FreeBSD Foundation.
 */

#define _SEARCH_PRIVATE
#include <search.h>
#include <stdlib.h>

static void
nul_node_free(void *node __unused)
{
}

void
tdestroy(void *rootp, void (*node_free)(void *))
{
        posix_tnode *back, *curr, **front;

        if (rootp == NULL)
                return;
        if (node_free == NULL)
                node_free = nul_node_free;

        back = rootp;
        front = &back;

        for (;;) {
                /*
                 * The sequence of nodes from back to just before *front linked
                 * by llink have been found to have non-NULL rlink.
                 *
                 * Extend *front to (*front)->llink, deleting *front from the
                 * sequence if it has a NULL rlink.
                 */
                curr = *front;
                if (curr->rlink != NULL)
                        front = &curr->llink;
                else {
                        *front = curr->llink;
                        node_free(curr->key);
                        free(curr);
                }
                if (*front != NULL)
                        continue;
                if (back == NULL)
                        break;

                /*
                 * The sequence cannot be extended because *front is NULL.  Make
                 * the rlink of the back node the new *front, the llink of the
                 * back node the new back, and free the old back node.
                 */
                curr = back;
                back = curr->llink;
                if (back == NULL)
                        front = &back;
                *front = curr->rlink;
                node_free(curr->key);
                free(curr);
        }
}