Loading...
#include <stdlib.h> #include <search.h> #include "tsearch.h" void *tdelete(const void *restrict key, void **restrict rootp, int(*cmp)(const void *, const void *)) { if (!rootp) return 0; void **a[MAXH+1]; struct node *n = *rootp; struct node *parent; struct node *child; int i=0; /* *a[0] is an arbitrary non-null pointer that is returned when the root node is deleted. */ a[i++] = rootp; a[i++] = rootp; for (;;) { if (!n) return 0; int c = cmp(key, n->key); if (!c) break; a[i++] = &n->a[c>0]; n = n->a[c>0]; } parent = *a[i-2]; if (n->a[0]) { /* free the preceding node instead of the deleted one. */ struct node *deleted = n; a[i++] = &n->a[0]; n = n->a[0]; while (n->a[1]) { a[i++] = &n->a[1]; n = n->a[1]; } deleted->key = n->key; child = n->a[0]; } else { child = n->a[1]; } /* freed node has at most one child, move it up and rebalance. */ free(n); *a[--i] = child; while (--i && __tsearch_balance(a[i])); return parent; } |