12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849 |
- #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;
- }
|