Date: Tue, 31 Mar 1998 21:54:05 -0800 (PST)
Message-Id: <199804010554.VAA22691@adit.ap.net>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
To: Noam Rotem <nrotem AT johnbryce DOT co DOT il>, djgpp AT delorie DOT com
From: Nate Eldredge <eldredge AT ap DOT net>
Subject: Re: Dynamic allocated memory. WAS: Linked lists
Precedence: bulk

At 10:58  3/31/1998 +0300, Noam Rotem wrote:
>Myknees wrote:
>
>> Since the way you access the data is by going down the chain of elements
>> (nodes) in order, it is very slow if you have a long list where you won't be
>> using the elements in order.  An alternative is to have a
dynamically-allocated
>> array of pointers to the structs.  That's much faster for random access and
>> doesn't cost more in memory, since the structs don't need to contain a
pointer
>> to the next struct.  Of course, when you use an array you lose the ability to
>> insert and delete elements easily and efficiently.
>
>I know that dynamic allocations by malloc are kept in  a linked list of memory
>blocks + overhead of data.  Is there any operation involving this list,
which is
>not of o(1)? (Well, except for freeing it all?) If so, why linked lists?

I understood his suggestion to be to allocate an array of pointers, at which
point every access would take a (short) constant amount of time. The
disadvantage of this is when you want to change the array. Adding elements
can require an expensive `realloc'. If you want to insert or delete an
element, you must move all following elements, which is also expensive. A
linked list means all accesses take time proportional to the distance from
the front of the list, but it's quite easy to add and delete.

As I understand DJGPP's `malloc', the data structures in which it keeps
track of allocated blocks are more similar to a hash table than a linked
list. This has the advantage of speed, though it can take more overhead.
This, of course, is only accessed when you allocate or free a block, not
merely for accessing it.
>
>BTW,
>
>This pool (heap?) of dynamic allocated memory is shared with other programs or
>tasks? If so, how come I get dynamic and non dynamic allocations in the same
>segment of memory?

As far as your program is concerned, no. You see a flat address space, all
of which belongs to you. The end of this space is adjusted with the `sbrk'
function (this is how `malloc' gets more memory).

>If not, why should I free everything (or let it be done for me)? Could this
memory
>be still marked as taken even after my program has terminated?

No, it can't. It's just considered good practice to free everything you
allocate. This is particularly important when you stop using the memory
before your program finishes (you might want the memory for something else
later in the run).

Nate Eldredge
eldredge AT ap DOT net