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