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