tdelete.c raw

   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  	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