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]

Re: no :of nodes

In article <7521541f-9a67-4239-93d5-1452d442314c@h1 g2000prh.google groups.com>,
sophia <sophia.agnes@g mail.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]

Re: no :of nodes

"sophia" <sophia.agnes@g mail.comwrote in message
news:7521541f-9a67-4239-93d5-1452d442314c@h1 g2000prh.google groups.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]

Re: no :of nodes

"Chris Thomasson" <cristom@comcas t.netwrote in message
news:vLGdndQrSb qk2L_VnZ2dnUVZ_ rjinZ2d@comcast .com...

"sophia" <sophia.agnes@g mail.comwrote in message
news:7521541f-9a67-4239-93d5-1452d442314c@h1 g2000prh.google groups.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]

Re: no :of nodes

On Wed, 7 May 2008 17:22:50 -0700, "Chris Thomasson"
<cristom@comcas t.netwrote:

>"Chris Thomasson" <cristom@comcas t.netwrote in message
>news:vLGdndQrS bqk2L_VnZ2dnUVZ _rjinZ2d@comcas t.com...

>"sophia" <sophia.agnes@g mail.comwrote in message
>news:7521541 f-9a67-4239-93d5-1452d442314c@h1 g2000prh.google groups.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, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

[Chris Thomasson]

Re: no :of nodes

"Richard Harter" <cri@tiac.netwr ote in message
news:482268d8.1 00836171@news.s btc.net...

On Wed, 7 May 2008 17:22:50 -0700, "Chris Thomasson"
<cristom@comcas t.netwrote:
>

>>"Chris Thomasson" <cristom@comcas t.netwrote in message
>>news:vLGdndQr Sbqk2L_VnZ2dnUV Z_rjinZ2d@comca st.com...

[...]

>>>
>>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.lang.c/browse_frm/thread/f8f65273b09b4229

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]

Re: no :of nodes

On Wed, 7 May 2008 21:11:29 -0700, "Chris Thomasson"
<cristom@comcas t.netwrote:

>"Richard Harter" <cri@tiac.netwr ote in message
>news:482268d8. 100836171@news. sbtc.net...

>On Wed, 7 May 2008 17:22:50 -0700, "Chris Thomasson"
><cristom@comca st.netwrote:
>>

>>>"Chris Thomasson" <cristom@comcas t.netwrote in message
>>>news:vLGdndQ rSbqk2L_VnZ2dnU VZ_rjinZ2d@comc ast.com...

>[...]

>>>>
>>>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_tre e()' 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.
>Deallocation s 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_relea se - 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, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

[Chris Thomasson]

Re: no :of nodes

"Richard Harter" <cri@tiac.netwr ote in message
news:48230670.1 41180453@news.s btc.net...

On Wed, 7 May 2008 21:11:29 -0700, "Chris Thomasson"
<cristom@comcas t.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.
>>Deallocatio ns 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.lang.c/browse_frm/thread/de5f62667b250ca3

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_relea se - 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.