Keine Lust Keine Lust - 1 month ago 17
C Question

twalk without globals

I am trying to traverse a binary tree using

twalk()
with
<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);
}


As you can see there is no way to pass to or return any variable from action().
why is so hermetic? I can't use any global because the program uses threads, my question is: how can I traverse (and share nodep with non-global variable) in thread-safe mode?
Excuse my poor english

EDIT:
As unwind said, the solution is to re-invent this particular wheel, redefine the structure used at tsearch.c solves the problem:

/* 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

I guess nobody can answer the "why" exactly, except those who specified and implemented the functions. I guess "shortsightedness", or maybe "historical reasons" (they did it before thread programming became a common thing).

Anyway, this API seems a bit "toyish" to me due to this limitation, as do in fact all APIs that fail to include a user-owned void * that is just opaquely passed around between API and any callbacks.

So, the solution I guess is to re-invent this particular wheel, and write your own functions to traverse a binary tree.