OT twalk

[David RF]

Hi friends, excuse my poor english and the off-topic of not standard
function twalk (in linux <search.h>)
http://www.mkssoftware.com/docs/man3/twalk.3.asp

twalk() traverses a binary search tree, but call recursively three
times for each node,
this behavior is not required when the order does not matter

typedef struct node_t
{
/* Callers expect this to be the first element in the structure - do
not
move! */
const void *key;
struct node_t *left;
struct node_t *right;
unsigned int red:1;
} *node;


static void
internal_function
trecurse (const void *vroot, __action_fn_t action, int level)
{
const_node root = (const_node) vroot;

if (root->left == NULL && root->right == NULL)
(*action) (root, leaf, level);
else
{
(*action) (root, preorder, level);
if (root->left != NULL)
trecurse (root->left, action, level + 1);
(*action) (root, postorder, level);
if (root->right != NULL)
trecurse (root->right, action, level + 1);
(*action) (root, endorder, level);
}
}

I am surprised about this bottleneck, why don't let overload this
behavior? (perphaps declaring node_t in search.h like other does)

#ifdef _SEARCH_PRIVATE
typedef struct node {
char *key;
struct node *llink, *rlink;
} node_t;

struct que_elem {
struct que_elem *next;
struct que_elem *prev;
};
#endif

 

[Ersek, Laszlo]

twalk() traverses a binary search tree, but call recursively three times
for each node,

I am surprised about this bottleneck, why don't let overload this
behavior?

Please reformulate the question, I don't understand what you mean. If you
object to "three calls being wasteful": those calls are not recursive
traversals. The tree is traversed a single time, but individual nodes are
touched multiple times during traversal.

http://www.opengroup.org/onlinepubs/9699919799/functions/twalk.html

lacos

 

[Nobody]

Hi friends, excuse my poor english and the off-topic of not standard
function twalk (in linux <search.h>)
http://www.mkssoftware.com/docs/man3/twalk.3.asp

twalk() traverses a binary search tree, but call recursively three
times for each node,

It calls the action function three times for each node; it doesn't recurse
three times for each node.

this behavior is not required when the order does not matter

I am surprised about this bottleneck, why don't let overload this
behavior?

There's no need. The action function can simply ignore the cases which it
doesn't care about. The inefficiency per node amounts to 2 indirect
function calls which immediately return. Unless the third call (the one
which actually does something) is trivial, the inefficiency is
insignificant.

 

[David RF]

It calls the action function three times for each node; it doesn't recurse
three times for each node.


There's no need. The action function can simply ignore the cases which it
doesn't care about. The inefficiency per node amounts to 2 indirect
function calls which immediately return. Unless the third call (the one
which actually does something) is trivial, the inefficiency is
insignificant.

Thanks, two indirect function calls and you have to add two calls to
itself, but you're right, to say it's a bottleneck is exaggerate, but
I could not think of another word in english

 

[Ersek, Laszlo]

Thanks, two indirect function calls and you have to add two calls to
itself, but you're right, to say it's a bottleneck is exaggerate, but I
could not think of another word in english

Were you looking for "overhead" or "waste" perhaps?

lacos

 

[David RF]

Yes, overhead, thank you