mingwrt/mingwex/tdelete.c

   1 /* $NetBSD: tdelete.c,v 1.3 1999/09/20 04:39:43 lukem Exp $
   2  *
   3  *
   4  * Tree search generalized from Knuth (6.2.2) Algorithm T just like
   5  * the AT&T man page says; tdelete based on Knuth's Algorithm D.
   6  *
   7  * Written by reading the System V Interface Definition, not the code.
   8  *
   9  * Totally public domain.
  10  *
  11  */
  12 #define _SEARCH_PRIVATE
  13 #include <search.h>
  14 #include <stdlib.h>
  15
  16 __CRT_ALIAS void *__tdelete
  17 (const void *key, node_t **rootp, int (*compar)(const void *, const void *))
  18 {
  19   /* Delete node with specified "key", from tree referred to by "rootp".
  20    *
  21    * NOTE: node_t is defined as a structured data type, for internal use
  22    * when _SEARCH_PRIVATE is enabled; for public consumption, it becomes
  23    * an alias for "void", (assuming _SEARCH_PRIVATE is NOT enabled).
  24    */
  25   int cmp;
  26   node_t *p, *q, *r;
  27
  28   if( (rootp == NULL) || ((p = *rootp) == NULL) || (compar == NULL) )
  29     return NULL;
  30
  31   while( (cmp = (*compar)(key, (*rootp)->key)) != 0 )
  32   {
  33     rootp = (cmp < 0)
  34       ? &(p = *rootp)->llink            /* follow llink branch */
  35       : &(p = *rootp)->rlink;           /* follow rlink branch */
  36
  37     if (*rootp == NULL)
  38       return NULL;                      /* key not found */
  39   }
  40   r = (*rootp)->rlink;                  /* D1: */
  41   if( (q = (*rootp)->llink) == NULL )   /* Left NULL? */
  42     q = r;
  43   else if( r != NULL )                  /* Right link is NULL? */
  44   { if( r->llink == NULL )              /* D2: Find successor */
  45     { r->llink = q;
  46       q = r;
  47     }
  48     else                                /* D3: Find NULL link */
  49     {
  50       for( q = r->llink; q->llink != NULL; q = r->llink )
  51         r = q;
  52       r->llink = q->rlink;
  53       q->llink = (*rootp)->llink;
  54       q->rlink = (*rootp)->rlink;
  55     }
  56   }
  57   free(*rootp);                         /* D4: Free node */
  58   *rootp = q;                           /* link parent to new node */
  59   return p;
  60 }
  61
  62 void *tdelete
  63 (const void *key, void **rootp, int (*compar)(const void *, const void *))
  64 { return __tdelete (key, (node_t **)(rootp), compar); }