1*b8c99e7dSKonstantin Belousov /* 2*b8c99e7dSKonstantin Belousov * Copyright 2025 The FreeBSD Foundation 3*b8c99e7dSKonstantin Belousov * 4*b8c99e7dSKonstantin Belousov * SPDX-License-Identifier: BSD-2-Clause 5*b8c99e7dSKonstantin Belousov * 6*b8c99e7dSKonstantin Belousov * This software was developed by Konstantin Belousov <kib@FreeBSD.org> 7*b8c99e7dSKonstantin Belousov * under sponsorship from the FreeBSD Foundation. 8*b8c99e7dSKonstantin Belousov */ 9*b8c99e7dSKonstantin Belousov 10*b8c99e7dSKonstantin Belousov #define _SEARCH_PRIVATE 11*b8c99e7dSKonstantin Belousov #include <search.h> 12*b8c99e7dSKonstantin Belousov #include <stdlib.h> 13*b8c99e7dSKonstantin Belousov 14*b8c99e7dSKonstantin Belousov static void nul_node_free(void * node __unused)15*b8c99e7dSKonstantin Belousovnul_node_free(void *node __unused) 16*b8c99e7dSKonstantin Belousov { 17*b8c99e7dSKonstantin Belousov } 18*b8c99e7dSKonstantin Belousov 19*b8c99e7dSKonstantin Belousov /* Find the leftmost node. */ 20*b8c99e7dSKonstantin Belousov static posix_tnode * tdestroy_find_leftmost(posix_tnode * tn)21*b8c99e7dSKonstantin Belousovtdestroy_find_leftmost(posix_tnode *tn) 22*b8c99e7dSKonstantin Belousov { 23*b8c99e7dSKonstantin Belousov while (tn->llink != NULL) 24*b8c99e7dSKonstantin Belousov tn = tn->llink; 25*b8c99e7dSKonstantin Belousov return (tn); 26*b8c99e7dSKonstantin Belousov } 27*b8c99e7dSKonstantin Belousov 28*b8c99e7dSKonstantin Belousov /* 29*b8c99e7dSKonstantin Belousov * This algorithm for non-recursive non-allocating destruction of the tree 30*b8c99e7dSKonstantin Belousov * is described in 31*b8c99e7dSKonstantin Belousov * https://codegolf.stackexchange.com/questions/478/free-a-binary-tree/489#489P 32*b8c99e7dSKonstantin Belousov * and in https://devblogs.microsoft.com/oldnewthing/20251107-00/?p=111774. 33*b8c99e7dSKonstantin Belousov */ 34*b8c99e7dSKonstantin Belousov void tdestroy(void * rootp,void (* node_free)(void *))35*b8c99e7dSKonstantin Belousovtdestroy(void *rootp, void (*node_free)(void *)) 36*b8c99e7dSKonstantin Belousov { 37*b8c99e7dSKonstantin Belousov posix_tnode *tn, *tn_leftmost, *xtn; 38*b8c99e7dSKonstantin Belousov 39*b8c99e7dSKonstantin Belousov tn = rootp; 40*b8c99e7dSKonstantin Belousov if (tn == NULL) 41*b8c99e7dSKonstantin Belousov return; 42*b8c99e7dSKonstantin Belousov if (node_free == NULL) 43*b8c99e7dSKonstantin Belousov node_free = nul_node_free; 44*b8c99e7dSKonstantin Belousov tn_leftmost = tn; 45*b8c99e7dSKonstantin Belousov 46*b8c99e7dSKonstantin Belousov while (tn != NULL) { 47*b8c99e7dSKonstantin Belousov /* 48*b8c99e7dSKonstantin Belousov * Make the right subtree the left subtree of the 49*b8c99e7dSKonstantin Belousov * leftmost node, and recalculate the leftmost. 50*b8c99e7dSKonstantin Belousov */ 51*b8c99e7dSKonstantin Belousov tn_leftmost = tdestroy_find_leftmost(tn_leftmost); 52*b8c99e7dSKonstantin Belousov if (tn->rlink != NULL) { 53*b8c99e7dSKonstantin Belousov tn_leftmost->llink = tn->rlink; 54*b8c99e7dSKonstantin Belousov tn_leftmost = tn_leftmost->llink; 55*b8c99e7dSKonstantin Belousov } 56*b8c99e7dSKonstantin Belousov 57*b8c99e7dSKonstantin Belousov /* 58*b8c99e7dSKonstantin Belousov * At this point, all children of tn have been 59*b8c99e7dSKonstantin Belousov * arranged to be reachable via tn->left. We can 60*b8c99e7dSKonstantin Belousov * safely delete the current node and advance to its 61*b8c99e7dSKonstantin Belousov * left child as the new root. 62*b8c99e7dSKonstantin Belousov */ 63*b8c99e7dSKonstantin Belousov xtn = tn->llink; 64*b8c99e7dSKonstantin Belousov node_free(tn->key); 65*b8c99e7dSKonstantin Belousov free(tn); 66*b8c99e7dSKonstantin Belousov tn = xtn; 67*b8c99e7dSKonstantin Belousov } 68*b8c99e7dSKonstantin Belousov } 69