On Wed, 7 May 2008 21:11:29 -0700, "Chris Thomasson"
<cristom@[EMAIL PROTECTED]
> wrote:
>"Richard Harter" <cri@[EMAIL PROTECTED]
> wrote in message
>news:482268d8.100836171@[EMAIL PROTECTED]
>> On Wed, 7 May 2008 17:22:50 -0700, "Chris Thomasson"
>> <cristom@[EMAIL PROTECTED]
> wrote:
>>
>>>"Chris Thomasson" <cristom@[EMAIL PROTECTED]
> wrote in message
>>>news:vLGdndQrSbqk2L_VnZ2dnUVZ_rjinZ2d@[EMAIL PROTECTED]
>[...]
>>>>
>>>> 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?
>
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 do***entation.
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. Pu****ng 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@[EMAIL PROTECTED]
http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
|
