Keine Lust Keine Lust - 10 months ago 50
C Question

twalk without globals

I am trying to traverse a binary tree using


#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");

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

return 0;

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

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

int i, *ptr;
void *val;

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

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

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 Source

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.