OT twalk


D

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
 
Ad

Advertisements

E

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
 
N

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.
 
D

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
 
E

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
 
Ad

Advertisements

Ad

Advertisements


Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads


Top