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