1 #include <stdlib.h> 2 #include <search.h> 3 #include "tsearch.h" 4 5 void *tdelete(const void *__restrict key, void **__restrict rootp, 6 int(*cmp)(const void *, const void *)) 7 { 8 if (!rootp) 9 return 0; 10 11 { 12 void **a[MAXH+1]; 13 struct node *n = *rootp; 14 struct node *parent; 15 struct node *child; 16 int i=0; 17 /* *a[0] is an arbitrary non-null pointer that is returned when 18 the root node is deleted. */ 19 a[i++] = rootp; 20 a[i++] = rootp; 21 for (;;) { 22 if (!n) 23 return 0; 24 { 25 int c = cmp(key, n->key); 26 if (!c) 27 break; 28 a[i++] = &n->a[c>0]; 29 n = n->a[c>0]; 30 } 31 } 32 parent = *a[i-2]; 33 if (n->a[0]) { 34 /* free the preceding node instead of the deleted one. */ 35 struct node *deleted = n; 36 a[i++] = &n->a[0]; 37 n = n->a[0]; 38 while (n->a[1]) { 39 a[i++] = &n->a[1]; 40 n = n->a[1]; 41 } 42 deleted->key = n->key; 43 child = n->a[0]; 44 } else { 45 child = n->a[1]; 46 } 47 /* freed node has at most one child, move it up and rebalance. */ 48 free(n); 49 *a[--i] = child; 50 while (--i && __tsearch_balance(a[i])); 51 return parent; 52 } 53 } 54