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 void 20 tdestroy(void *rootp, void (*node_free)(void *)) 21 { 22 posix_tnode *back, *curr, **front; 23 24 if (rootp == NULL) 25 return; 26 if (node_free == NULL) 27 node_free = nul_node_free; 28 29 back = rootp; 30 front = &back; 31 32 for (;;) { 33 /* 34 * The sequence of nodes from back to just before *front linked 35 * by llink have been found to have non-NULL rlink. 36 * 37 * Extend *front to (*front)->llink, deleting *front from the 38 * sequence if it has a NULL rlink. 39 */ 40 curr = *front; 41 if (curr->rlink != NULL) 42 front = &curr->llink; 43 else { 44 *front = curr->llink; 45 node_free(curr->key); 46 free(curr); 47 } 48 if (*front != NULL) 49 continue; 50 if (back == NULL) 51 break; 52 53 /* 54 * The sequence cannot be extended because *front is NULL. Make 55 * the rlink of the back node the new *front, the llink of the 56 * back node the new back, and free the old back node. 57 */ 58 curr = back; 59 back = curr->llink; 60 if (back == NULL) 61 front = &back; 62 *front = curr->rlink; 63 node_free(curr->key); 64 free(curr); 65 } 66 } 67