c - 没有全局变量的 twalk

Question

我正在尝试使用 twalk() 遍历二叉树与 <search.h>

   #define _GNU_SOURCE     /* Expose declaration of tdestroy() */
   #include <search.h>
   #include <stdlib.h>
   #include <stdio.h>
   #include <time.h>

   void *root = NULL;

   void *
   xmalloc(unsigned n)
   {
       void *p;
       p = malloc(n);
       if (p)
           return p;
       fprintf(stderr, "insufficient memory\n");
       exit(EXIT_FAILURE);
   }

   int
   compare(const void *pa, const void *pb)
   {
       if (*(int *) pa < *(int *) pb)
           return -1;
       if (*(int *) pa > *(int *) pb)
           return 1;

       return 0;
   }

   void
   action(const void *nodep, const VISIT which, const int depth)
   {
       int *datap;

       switch (which) {
       case preorder:
           break;
       case postorder:
           datap = *(int **) nodep;
           printf("%6d\n", *datap);
           break;
       case endorder:
           break;
       case leaf:
           datap = *(int **) nodep;
           printf("%6d\n", *datap);
           break;
       }
   }

   int
   main(void)
   {
       int i, *ptr;
       void *val;

       srand(time(NULL));
       for (i = 0; i < 12; i++) {
           ptr = (int *) xmalloc(sizeof(int));
           *ptr = rand() & 0xff;
           val = tsearch((void *) ptr, &root, compare);
           if (val == NULL)
               exit(EXIT_FAILURE);
           else if ((*(int **) val) != ptr)
               free(ptr);
       }
       twalk(root, action);
       tdestroy(root, free);
       exit(EXIT_SUCCESS);
   }

如您所见，无法从 action() 传递或返回任何变量。为什么这么密封？我不能使用任何全局变量，因为程序使用线程，我的问题是:如何在线程安全模式下遍历(并与非全局变量共享 nodep)？请原谅我糟糕的英语

编辑:正如 unwind 所说，解决方案是重新发明这个特定的轮子，重新定义 tsearch.c 中使用的结构解决了问题:

/* twalk() fake */

struct node_t
{
    const void *key;
    struct node_t *left;
    struct node_t *right;
    unsigned int red:1;
};

static void tmycallback(const xdata *data, const void *misc)
{
    printf("%s %s\n", (const char *)misc, data->value);
}

static void tmywalk(const struct node_t *root, void (*callback)(const xdata *, const void *), const void *misc)
{
    if (root->left == NULL && root->right == NULL) {
        callback(*(xdata * const *)root, misc);
    } else {
        if (root->left != NULL) tmywalk(root->left, callback, misc);
        callback(*(xdata * const *)root, misc);
        if (root->right != NULL) tmywalk(root->right, callback, misc);
    }
}

/* END twalk() fake */

if (root) tmywalk(root, tmycallback, "Hello walker");

Answer 1

我想没有人能准确回答“为什么”，除了指定和实现功能的人。我猜是“短视”，或者可能是“历史原因”(他们在线程编程变得普遍之前就这样做了)。

无论如何，由于这个限制，这个 API 对我来说似乎有点“玩具化”，事实上，所有未能包含用户拥有的 void * 的 API 都是如此，它只是在两者之间不透明地传递API 和任何回调。

因此，我想解决方案是重新发明这个特定的轮子，并编写您自己的函数来遍历二叉树。