src/search/tdelete.c

   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 }