no :of nodes

[sophia]

Dear all,

How good is this function which is used to find the no: of nodes
in each level of the binary tree. ?
int arrlev[100];

void preorder(struct btree *n,int lev)
{
if(!(n))
return;

arrlev[lev]++;
lev++;

preorder(n->left,lev);
preorder(n->right,lev);
}

[Walter Roberson]

In article <75**********************************@h1g2000prh.g ooglegroups.com>,
sophia <so**********@gmail.comwrote:

>How good is this function which is used to find the no: of nodes
in each level of the binary tree. ?

>int arrlev[100];

>void preorder(struct btree *n,int lev)
{
if(!(n))
return;

arrlev[lev]++;

When you restrict the number of levels in the counters (which
you do in your declaration of arrlev), then before you write
into arrlev[lev] you need to check that you are not overflowing
the end of the array.

lev++;

preorder(n->left,lev);
preorder(n->right,lev);

You could avoid a bunch of do-nothing calls:

if (n->left) preorder(n->left,lev);
if (n->right) preorder(n->right,lev);

>}

--
"I want to be remembered as the guy who gave his all whenever
he was on the field." -- Walter Payton

[Chris Thomasson]

"sophia" <so**********@gmail.comwrote in message
news:75**********************************@h1g2000p rh.googlegroups.com...

Dear all,

How good is this function which is used to find the no: of nodes
in each level of the binary tree. ?
int arrlev[100];

void preorder(struct btree *n,int lev)
{
if(!(n))
return;

arrlev[lev]++;
lev++;

preorder(n->left,lev);
preorder(n->right,lev);
}

Its no good. Use dynamic allocation if the level count of the tree is not
known in advance. Also, recursion is not safe. Passing some tress to this
function will blow the stack. There are ways to traverse a tree without
using recursion. Here is a simple example:

http://pastebin.com/m7ffa217c

Instead of threading the tree, you can include an auxiliary node that a
traversal function uses as an node to link into a local queue. Check the
'destroy_tree()' function...

[Chris Thomasson]

"Chris Thomasson" <cr*****@comcast.netwrote in message
news:vL******************************@comcast.com. ..

"sophia" <so**********@gmail.comwrote in message
news:75**********************************@h1g2000p rh.googlegroups.com...

>Dear all,

How good is this function which is used to find the no: of nodes
in each level of the binary tree. ?
int arrlev[100];

void preorder(struct btree *n,int lev)
{
if(!(n))
return;

arrlev[lev]++;
lev++;

preorder(n->left,lev);
preorder(n->right,lev);
}

Its no good. Use dynamic allocation if the level count of the tree is not
known in advance. Also, recursion is not safe. Passing some tress to this
function will blow the stack. There are ways to traverse a tree without
using recursion. Here is a simple example:

http://pastebin.com/m7ffa217c

ARGH!!!!

Forget that code!

Look at this one instead!

http://pastebin.com/m3e5a9fd8
Sorry about the first one. I made forgot to call free!!!!!!!

;^(...

Instead of threading the tree, you can include an auxiliary node that a
traversal function uses as an node to link into a local queue. Check the
'destroy_tree()' function...

[Richard Harter]

On Wed, 7 May 2008 17:22:50 -0700, "Chris Thomasson"
<cr*****@comcast.netwrote:

>"Chris Thomasson" <cr*****@comcast.netwrote in message
news:vL******************************@comcast.com ...

>"sophia" <so**********@gmail.comwrote in message
news:75**********************************@h1g2000 prh.googlegroups.com...

>>Dear all,

How good is this function which is used to find the no: of nodes
in each level of the binary tree. ?
int arrlev[100];

void preorder(struct btree *n,int lev)
{
if(!(n))
return;

arrlev[lev]++;
lev++;

preorder(n->left,lev);
preorder(n->right,lev);
}

Its no good. Use dynamic allocation if the level count of the tree is not
known in advance. Also, recursion is not safe. Passing some tress to this
function will blow the stack. There are ways to traverse a tree without
using recursion. Here is a simple example:

http://pastebin.com/m7ffa217c

ARGH!!!!

Forget that code!

Look at this one instead!

http://pastebin.com/m3e5a9fd8
Sorry about the first one. I made forgot to call free!!!!!!!

;^(...

>Instead of threading the tree, you can include an auxiliary node that a
traversal function uses as an node to link into a local queue. Check the
'destroy_tree()' function...

If I read the code correctly, it makes a separate malloc call for
each new node. While legal, that makes for inefficient code. It
is better to allocate space for a block of nodes and link them
into a free list. There are other alternatives, but the essence
is that one malloc per node is expensive and should be avoided in
production code.

Richard Harter, cr*@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

[Chris Thomasson]

"Richard Harter" <cr*@tiac.netwrote in message
news:48****************@news.sbtc.net...

On Wed, 7 May 2008 17:22:50 -0700, "Chris Thomasson"
<cr*****@comcast.netwrote:

>>"Chris Thomasson" <cr*****@comcast.netwrote in message
news:vL******************************@comcast.co m...

[...]

>>>
Its no good. Use dynamic allocation if the level count of the tree is
not
known in advance. Also, recursion is not safe. Passing some tress to
this
function will blow the stack. There are ways to traverse a tree without
using recursion. Here is a simple example:

[...]

>>
http://pastebin.com/m3e5a9fd8

[...]

>>Instead of threading the tree, you can include an auxiliary node that a
traversal function uses as an node to link into a local queue. Check the
'destroy_tree()' function...

If I read the code correctly, it makes a separate malloc call for
each new node. While legal, that makes for inefficient code. It
is better to allocate space for a block of nodes and link them
into a free list. There are other alternatives, but the essence
is that one malloc per node is expensive and should be avoided in
production code.

You can hook it up to the following crude region allocator I did:

http://pastebin.com/m52ba914

http://groups.google.com/group/comp....f65273b09b4229
Now, the tree program can look something like:

http://pastebin.com/m757377c3
The region allocator simply increments a counter and bumps a pointer along
the buffer until the end is reached, then another region is allocated.
Deallocations consist of decrementing the counter and resetting the
allocator state when zero is reached. It can dynamically expand and shrink.
It can also amortize calls to free into a single "reset" call. The example
code shows this...
Any thoughts?

[Richard Harter]

On Wed, 7 May 2008 21:11:29 -0700, "Chris Thomasson"
<cr*****@comcast.netwrote:

>"Richard Harter" <cr*@tiac.netwrote in message
news:48****************@news.sbtc.net...

>On Wed, 7 May 2008 17:22:50 -0700, "Chris Thomasson"
<cr*****@comcast.netwrote:

>>>"Chris Thomasson" <cr*****@comcast.netwrote in message
news:vL******************************@comcast.c om...

[...]

>>>>
Its no good. Use dynamic allocation if the level count of the tree is
not
known in advance. Also, recursion is not safe. Passing some tress to
this
function will blow the stack. There are ways to traverse a tree without
using recursion. Here is a simple example:

[...]

>>>
http://pastebin.com/m3e5a9fd8

[...]

>>>Instead of threading the tree, you can include an auxiliary node that a
traversal function uses as an node to link into a local queue. Check the
'destroy_tree()' function...

If I read the code correctly, it makes a separate malloc call for
each new node. While legal, that makes for inefficient code. It
is better to allocate space for a block of nodes and link them
into a free list. There are other alternatives, but the essence
is that one malloc per node is expensive and should be avoided in
production code.

You can hook it up to the following crude region allocator I did:

http://pastebin.com/m52ba914

http://groups.google.com/group/comp....f65273b09b4229
Now, the tree program can look something like:

http://pastebin.com/m757377c3
The region allocator simply increments a counter and bumps a pointer along
the buffer until the end is reached, then another region is allocated.
Deallocations consist of decrementing the counter and resetting the
allocator state when zero is reached. It can dynamically expand and shrink.
It can also amortize calls to free into a single "reset" call. The example
code shows this...
Any thoughts?

If you like. There is one no-no in your code - you start some of
your variables with an underscore. Don't do this; you're invading
the system implementation namespace.

There is an oddity in allocator_release - you call assert(0)
followed by a call to abort. The assert(0) calls abort.

What you have is commonly called a pool allocator; it's a good
thing to have available. Your implementation looks plausible,
though I would be happier if it had some inline documentation.

Advantages of pool allocators: Allocation can be significantly
faster than with malloc; deallocation only requires freeing the
entire pool rather than freeing each item.

That said, when all items in the pool are the same kind of thing,
e.g., tree nodes, it can pay to have a free list. Pushing items
onto the free list and popping them off is equally cheap, and you
(potentially) use less storage.

A caveat here is that execution costs in modern machines depends
upon cache hits and misses. In a tree it may pay to arrange the
code so that nodes that are near each other in the tree are near
each other in local storage as much as possible.

Richard Harter, cr*@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

[Chris Thomasson]

"Richard Harter" <cr*@tiac.netwrote in message
news:48****************@news.sbtc.net...

On Wed, 7 May 2008 21:11:29 -0700, "Chris Thomasson"
<cr*****@comcast.netwrote:

[...]

>>The region allocator simply increments a counter and bumps a pointer along
the buffer until the end is reached, then another region is allocated.
Deallocations consist of decrementing the counter and resetting the
allocator state when zero is reached. It can dynamically expand and
shrink.
It can also amortize calls to free into a single "reset" call. The example
code shows this...
Any thoughts?

If you like. There is one no-no in your code - you start some of
your variables with an underscore. Don't do this; you're invading
the system implementation namespace.

This issue has been raised:

http://groups.google.com/group/comp....5f62667b250ca3

There happens to nothing wrong with the way I am using it. E.g.:

static void
foo_something(
struct foo* const _this
) {
[...];
}

There is an oddity in allocator_release - you call assert(0)
followed by a call to abort. The assert(0) calls abort.

I want abort to still be called when NDEBUG is defined.

What you have is commonly called a pool allocator; it's a good
thing to have available. Your implementation looks plausible,
though I would be happier if it had some inline documentation.

Advantages of pool allocators: Allocation can be significantly
faster than with malloc; deallocation only requires freeing the
entire pool rather than freeing each item.

That said, when all items in the pool are the same kind of thing,
e.g., tree nodes, it can pay to have a free list. Pushing items
onto the free list and popping them off is equally cheap, and you
(potentially) use less storage.

A caveat here is that execution costs in modern machines depends
upon cache hits and misses. In a tree it may pay to arrange the
code so that nodes that are near each other in the tree are near
each other in local storage as much as possible.

Agreed.