compat/tdestroy.c

   1 /**
   2  * @file tdestroy.c
   3  * @brief replacement for GNU tdestroy()
   4  */
   5 /*****************************************************************************
   6  * Copyright (C) 2009, 2018 Rémi Denis-Courmont
   7  *
   8  * This program is free software; you can redistribute it and/or modify it
   9  * under the terms of the GNU Lesser General Public License as published by
  10  * the Free Software Foundation; either version 2.1 of the License, or
  11  * (at your option) any later version.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  16  * GNU Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public License
  19  * along with this program; if not, write to the Free Software Foundation,
  20  * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
  21  *****************************************************************************/
  22
  23 #ifdef HAVE_CONFIG_H
  24 # include "config.h"
  25 #endif
  26
  27 #include <assert.h>
  28 #include <stdlib.h>
  29 #ifdef HAVE_SEARCH_H
  30 # include <search.h>
  31 #endif
  32
  33 #ifdef HAVE_TFIND
  34 static __thread struct
  35 {
  36     const void **tab;
  37     size_t count;
  38 } list = { NULL, 0 };
  39
  40 static void list_nodes(const void *node, const VISIT which, const int depth)
  41 {
  42     (void) depth;
  43
  44     if (which != postorder && which != leaf)
  45         return;
  46
  47     const void **tab = realloc(list.tab, sizeof (*tab) * (list.count + 1));
  48     if (tab == NULL)
  49         abort();
  50
  51     tab[list.count] = *(const void **)node;
  52     list.tab = tab;
  53     list.count++;
  54 }
  55
  56 static __thread const void *smallest;
  57
  58 static int cmp_smallest(const void *a, const void *b)
  59 {
  60     if (a == b)
  61         return 0;
  62     if (a == smallest)
  63         return -1;
  64     if (b == smallest)
  65         return +1;
  66     abort();
  67 }
  68
  69 void tdestroy(void *root, void (*freenode)(void *))
  70 {
  71     const void **tab;
  72     size_t count;
  73
  74     assert(freenode != NULL);
  75
  76     /* Enumerate nodes in order */
  77     assert(list.count == 0);
  78     twalk(root, list_nodes);
  79     tab = list.tab;
  80     count = list.count;
  81     list.tab = NULL;
  82     list.count = 0;
  83
  84     /* Destroy the tree */
  85     for (size_t i = 0; i < count; i++)
  86     {
  87          void *node = (void *)(tab[i]);
  88
  89          smallest = node;
  90          node = tdelete(node, &root, cmp_smallest);
  91          assert(node != NULL);
  92     }
  93     assert (root == NULL);
  94
  95     /* Destroy the nodes */
  96     for (size_t i = 0; i < count; i++)
  97          freenode((void *)(tab[i]));
  98     free(tab);
  99 }
 100 #endif /* HAVE_TFIND */