src/libcrt/search/tdelete.c

   1 /**
   2  * @file tdelete.c
   3  * @copy 2012 MinGW.org project
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a
   6  * copy of this software and associated documentation files (the "Software"),
   7  * to deal in the Software without restriction, including without limitation
   8  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   9  * and/or sell copies of the Software, and to permit persons to whom the
  10  * Software is furnished to do so, subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice (including the next
  13  * paragraph) shall be included in all copies or substantial portions of the
  14  * Software.
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  21  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  22  * DEALINGS IN THE SOFTWARE.
  23  */
  24 #include <assert.h>
  25 #define _SEARCH_PRIVATE
  26 #include <search.h>
  27 #include <stdlib.h>
  28
  29 #define _DIAGASSERT assert
  30
  31
  32
  33 /* delete node with given key */
  34 void *
  35 tdelete(const void *vkey,       /* key to be deleted */
  36         void      **vrootp,     /* address of the root of tree */
  37         int       (*compar)(const void *, const void *))
  38 {
  39         node_t **rootp = (node_t **)vrootp;
  40         node_t *p, *q, *r;
  41         int  cmp;
  42
  43         _DIAGASSERT(compar != NULL);
  44
  45         if (rootp == NULL || (p = *rootp) == NULL)
  46                 return NULL;
  47
  48         while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) {
  49                 p = *rootp;
  50                 rootp = (cmp < 0) ?
  51                     &(*rootp)->llink :          /* follow llink branch */
  52                     &(*rootp)->rlink;           /* follow rlink branch */
  53                 if (*rootp == NULL)
  54                         return NULL;            /* key not found */
  55         }
  56         r = (*rootp)->rlink;                    /* D1: */
  57         if ((q = (*rootp)->llink) == NULL)      /* Left NULL? */
  58                 q = r;
  59         else if (r != NULL) {                   /* Right link is NULL? */
  60                 if (r->llink == NULL) {         /* D2: Find successor */
  61                         r->llink = q;
  62                         q = r;
  63                 } else {                        /* D3: Find NULL link */
  64                         for (q = r->llink; q->llink != NULL; q = r->llink)
  65                                 r = q;
  66                         r->llink = q->rlink;
  67                         q->llink = (*rootp)->llink;
  68                         q->rlink = (*rootp)->rlink;
  69                 }
  70         }
  71         free(*rootp);                           /* D4: Free node */
  72         *rootp = q;                             /* link parent to new node */
  73         return p;
  74 }