Consider implementing a (doubly) linked list.
The simplest strategy is to provide functions
item_t add_item(item_t predecessor);
void delete_item(item_t item);
where add_item allocates memory for a new list item and returns it (or
NULL), and delete_item frees that memory.
However, if at startup the program immediately adds a large number of
items to a list, then all those calls to malloc() become expensive.
An alternative I thought of was that add_item should allocate a block,
say of size (100 * size-needed-by-an-item), then use pointers inside
this block until the time comes to allocate a new block for 100 items.
The problem with this is that deleting items becomes a mess - you can
only free a block when all 100 items in it have been deleted, so in the
worst case (where the programmer allocates 101 items, frees 99, adds
101, ...) you end up with for all intents and purposes a memory leak.
Is there a better solution?
8  2709 
Jeff wrote:
) Consider implementing a (doubly) linked list.
)
) The simplest strategy is to provide functions
) item_t add_item(item_t predecessor);
) void delete_item(item_t item);
) where add_item allocates memory for a new list item and returns it (or
) NULL), and delete_item frees that memory.
)
) However, if at startup the program immediately adds a large number of
) items to a list, then all those calls to malloc() become expensive.
)
) An alternative I thought of was that add_item should allocate a block,
) say of size (100 * size-needed-by-an-item), then use pointers inside
) this block until the time comes to allocate a new block for 100 items.
)
) The problem with this is that deleting items becomes a mess - you can
) only free a block when all 100 items in it have been deleted, so in the
) worst case (where the programmer allocates 101 items, frees 99, adds
) 101, ...) you end up with for all intents and purposes a memory leak.
)
) Is there a better solution?
It's very difficult for a solution to be strictly 'better' than another
solution. So, you'll need to examine several solutions and see which best
fits your needs.
For example: With your alternative, you can reuse spots within a block if
you can mark them 'empty'. This induces an extra cost of searching for
empty blocks, however.
For another example: You can store groups of items, together with a count,
into larger blocks. This is tricky to get right, though, and you need to
move memory inside a block around when deleting or adding items.
For yet another example: You can periodically 'rehash' the list, sticking
it into one or more big blocks sequentially. Like defragmenting a filesystem.
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
Jeff Bown <no****@nospam.invalidwrites:
Consider implementing a (doubly) linked list.
The simplest strategy is to provide functions
item_t add_item(item_t predecessor);
void delete_item(item_t item);
where add_item allocates memory for a new list item and returns it (or
NULL), and delete_item frees that memory.
However, if at startup the program immediately adds a large number of
items to a list, then all those calls to malloc() become expensive.
A better solution is sometimes to embed the list elements
directly in the elements being added to the list. If each
element is only on at most a fixed number of lists, this approach
is cheaper in terms of the number of necessary allocations.
--
Ben Pfaff http://benpfaff.org
Jeff Bown wrote:
>
Consider implementing a (doubly) linked list.
The simplest strategy is to provide functions
item_t add_item(item_t predecessor);
void delete_item(item_t item);
where add_item allocates memory for a new list item and returns it (or
NULL), and delete_item frees that memory.
However, if at startup the program immediately adds a large number of
items to a list, then all those calls to malloc() become expensive.
An alternative I thought of was that add_item should allocate a block,
say of size (100 * size-needed-by-an-item), then use pointers inside
this block until the time comes to allocate a new block for 100 items.
The problem with this is that deleting items becomes a mess - you can
only free a block when all 100 items in it have been deleted,
so in the
worst case (where the programmer allocates 101 items, frees 99, adds
101, ...) you end up with for all intents and purposes a memory leak.
Is there a better solution?
Yes.
The solution is to realise that the problem does not exist.
The scenario that you describe
of a whole bunch of malloc at startup
to the extent that it makes a noticable difference
and also of mallocing one big object
for parts of your list to occupy,
suggests that
you have no idea of why you're using a list intsead of an array.
The best use for a list,
is when you want to grow your data format
as data becomes available to the program.
Freeing a list isn't supposed to be difficult.
typedef struct list_node {
struct list_node *next;
void *data;
} list_type;
void list_free(list_type *node, void (*free_data)(void *))
{
list_type *next_node;
while (node != NULL) {
next_node = node -next;
free_data(node -data);
free(node);
node = next_node;
}
}
--
pete
On Dec 17, 1:51 pm, Jeff Bown <nos...@nospam.invalidwrote:
Consider implementing a (doubly) linked list.
The simplest strategy is to provide functions
item_t add_item(item_t predecessor);
void delete_item(item_t item);
where add_item allocates memory for a new list item and returns it (or
NULL), and delete_item frees that memory.
However, if at startup the program immediately adds a large number of
items to a list, then all those calls to malloc() become expensive.
An alternative I thought of was that add_item should allocate a block,
say of size (100 * size-needed-by-an-item), then use pointers inside
this block until the time comes to allocate a new block for 100 items.
The problem with this is that deleting items becomes a mess - you can
only free a block when all 100 items in it have been deleted, so in the
worst case (where the programmer allocates 101 items, frees 99, adds
101, ...) you end up with for all intents and purposes a memory leak.
Is there a better solution?
The usual idea is to maintain a free list where deleted cells are held
pending future allocations. There aren't many cases where it would pay
to return blocks to the malloc() heap. Unused free blocks will be
paged out in due course, where they consume only some swap space - of
interest only for _really_ long lists.
Pete's rather condescending suggestion that you don't need lists and
ought to use vectors instead has a flaw: O(1) time deletion of an
arbitrary element can't be accomplished with a vector. It's perfectly
reasonable to build up a big list at program startup if e.g. future
computations involve decimating the list by arbitrary deletions.
On Mon, 17 Dec 2007 19:51:32 +0100 (CET), Jeff Bown
<no****@nospam.invalidwrote:
>Consider implementing a (doubly) linked list.
The simplest strategy is to provide functions
item_t add_item(item_t predecessor);
void delete_item(item_t item);
where add_item allocates memory for a new list item and returns it (or
NULL), and delete_item frees that memory.
However, if at startup the program immediately adds a large number of
items to a list, then all those calls to malloc() become expensive.
An alternative I thought of was that add_item should allocate a block,
say of size (100 * size-needed-by-an-item), then use pointers inside
this block until the time comes to allocate a new block for 100 items.
The problem with this is that deleting items becomes a mess - you can
only free a block when all 100 items in it have been deleted, so in the
worst case (where the programmer allocates 101 items, frees 99, adds
101, ...) you end up with for all intents and purposes a memory leak.
Is there a better solution?
Your description is a little confusing - to me anyway, and
perhaps to others judging from the variety of answers you got.
Ordinarily a linked list (single, or double) consists of nodes,
where a node (doubly linked) looks something like this:
struct node {
node * prev; /* Link to previous node */
node * next; /* Link to next node */
void * data; /* generic pointer to data */
};
and the prototypes look something like this:
node * add_item(node * predecessor, void * datum);
void delete_item(node * item);
Usually you would have a few more routines but set that aside for
the moment. The point I am after is that you seem to be mixing
up nodes and data.
Now, supposing these are your prototypes, how do you go about
implementing them? I will suppose that you can write the code
for inserting and deleting nodes from linked lists. The question
at hand is: what about storage allocation and deallocation? It
is important to recognize that there are two different kinds of
things being allocated and freed, nodes and data.
A generic linked list package shouldn't be responsible for
allocating or freeing data, though there are standard techniques
that can be used.
For nodes a common technique is to (a) use a free list, and (b)
allocate blocks of nodes, link them together, and add them to the
free list. When adding items nodes are popped off the free list;
when deleting items nodes are pushed onto the free list.
HTH. HAND.
Jeff Bown wrote:
Consider implementing a (doubly) linked list.
The simplest strategy is to provide functions
item_t add_item(item_t predecessor);
void delete_item(item_t item);
where add_item allocates memory for a new list item and returns it (or
NULL), and delete_item frees that memory.
However, if at startup the program immediately adds a large number of
items to a list, then all those calls to malloc() become expensive.
An alternative I thought of was that add_item should allocate a block,
say of size (100 * size-needed-by-an-item), then use pointers inside
this block until the time comes to allocate a new block for 100 items.
The problem with this is that deleting items becomes a mess - you can
only free a block when all 100 items in it have been deleted, so in the
worst case (where the programmer allocates 101 items, frees 99, adds
101, ...) you end up with for all intents and purposes a memory leak.
Is there a better solution?
You can use a pool of linked list structs, and some malloc
implementations actually create a sort of pool for objects of the same
size. Perhaps a different type of data structure would be a better fit
though. Often times programmers will use a linked list when an array of
structs will do.
There are also certain advantages to using a linked-list pool, or a
specialized pool for any data structure. For instance if you're dumping
a tree or linked list to the disk, and want to restore with minimal
relocation and cost for the ability to dump the data structure to the
disk, and restore. For the relocation you generally want to use an
optional part of C99 (an intptr_t or uintptr_t) though.
George
On Dec 17, 9:34 pm, c...@tiac.net (Richard Harter) wrote:
On Mon, 17 Dec 2007 19:51:32 +0100 (CET), Jeff Bown
<nos...@nospam.invalidwrote:
Consider implementing a (doubly) linked list.
The simplest strategy is to provide functions
item_t add_item(item_t predecessor);
void delete_item(item_t item);
where add_item allocates memory for a new list item and returns it (or
NULL), and delete_item frees that memory.
However, if at startup the program immediately adds a large number of
items to a list, then all those calls to malloc() become expensive.
An alternative I thought of was that add_item should allocate a block,
say of size (100 * size-needed-by-an-item), then use pointers inside
this block until the time comes to allocate a new block for 100 items.
The problem with this is that deleting items becomes a mess - you can
only free a block when all 100 items in it have been deleted, so in the
worst case (where the programmer allocates 101 items, frees 99, adds
101, ...) you end up with for all intents and purposes a memory leak.
Is there a better solution?
Your description is a little confusing - to me anyway, and
perhaps to others judging from the variety of answers you got.
Ordinarily a linked list (single, or double) consists of nodes,
where a node (doubly linked) looks something like this:
struct node {
node * prev; /* Link to previous node */
node * next; /* Link to next node */
void * data; /* generic pointer to data */
};
and the prototypes look something like this:
node * add_item(node * predecessor, void * datum);
void delete_item(node * item);
Usually you would have a few more routines but set that aside for
the moment. The point I am after is that you seem to be mixing
up nodes and data.
Now, supposing these are your prototypes, how do you go about
implementing them? I will suppose that you can write the code
for inserting and deleting nodes from linked lists. The question
at hand is: what about storage allocation and deallocation? It
is important to recognize that there are two different kinds of
things being allocated and freed, nodes and data.
A generic linked list package shouldn't be responsible for
allocating or freeing data, though there are standard techniques
that can be used.
For nodes a common technique is to (a) use a free list, and (b)
allocate blocks of nodes, link them together, and add them to the
free list. When adding items nodes are popped off the free list;
when deleting items nodes are pushed onto the free list.
HTH. HAND.
I see some list add item using ** such as
node * add_item(node ** predecessor, void * datum);
Any benefit compare to node * add_item(node * predecessor, void *
datum);?
On Wed, 26 Dec 2007 11:20:26 -0800 (PST), henry
<he**********@yahoo.comwrote:
>On Dec 17, 9:34 pm, c...@tiac.net (Richard Harter) wrote:
>On Mon, 17 Dec 2007 19:51:32 +0100 (CET), Jeff Bown
<nos...@nospam.invalidwrote:
>Consider implementing a (doubly) linked list.
>The simplest strategy is to provide functions
item_t add_item(item_t predecessor);
void delete_item(item_t item);
where add_item allocates memory for a new list item and returns it (or
NULL), and delete_item frees that memory.
>However, if at startup the program immediately adds a large number of
items to a list, then all those calls to malloc() become expensive.
>An alternative I thought of was that add_item should allocate a block,
say of size (100 * size-needed-by-an-item), then use pointers inside
this block until the time comes to allocate a new block for 100 items.
>The problem with this is that deleting items becomes a mess - you can
only free a block when all 100 items in it have been deleted, so in the
worst case (where the programmer allocates 101 items, frees 99, adds
101, ...) you end up with for all intents and purposes a memory leak.
>Is there a better solution?
Your description is a little confusing - to me anyway, and
perhaps to others judging from the variety of answers you got.
Ordinarily a linked list (single, or double) consists of nodes,
where a node (doubly linked) looks something like this:
struct node {
node * prev; /* Link to previous node */
node * next; /* Link to next node */
void * data; /* generic pointer to data */
};
and the prototypes look something like this:
node * add_item(node * predecessor, void * datum);
void delete_item(node * item);
Usually you would have a few more routines but set that aside for
the moment. The point I am after is that you seem to be mixing
up nodes and data.
Now, supposing these are your prototypes, how do you go about
implementing them? I will suppose that you can write the code
for inserting and deleting nodes from linked lists. The question
at hand is: what about storage allocation and deallocation? It
is important to recognize that there are two different kinds of
things being allocated and freed, nodes and data.
A generic linked list package shouldn't be responsible for
allocating or freeing data, though there are standard techniques
that can be used.
For nodes a common technique is to (a) use a free list, and (b)
allocate blocks of nodes, link them together, and add them to the
free list. When adding items nodes are popped off the free list;
when deleting items nodes are pushed onto the free list.
HTH. HAND.
I see some list add item using ** such as
node * add_item(node ** predecessor, void * datum);
Any benefit compare to node * add_item(node * predecessor, void *
datum);?
Actually there can be. If the argument points directly to the
predecessor node the implementation cannot change the location of
the predecesssor node; if the argument is an indirect pointer
(**) the implementation can change the location. The down side,
such as it is, is that the code goes through an extra level of
indirection. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Francis Bell |
last post by:
Hello,
I'm trying to read data from a file and then insert that into a linked
list. The way I have it, the program compiles, however, I'm getting a
segmentation fault error message when I run...
|
by: dam_fool_2003 |
last post by:
friends,
I wanted to learn the various ways of inserting a single list. so:
Method 1:
#include<stdlib.h>
#include<stdio.h>
struct node
{
unsigned int data;
struct node *next;
|
by: Kieran Simkin |
last post by:
Hi all,
I'm having some trouble with a linked list function and was wondering if
anyone could shed any light on it. Basically I have a singly-linked list
which stores pid numbers of a process's...
|
by: JS |
last post by:
I have a file called test.c. There I create a pointer to a pcb struct:
struct pcb {
void *(*start_routine) (void *);
void *arg;
jmp_buf state;
int stack;
};
...
|
by: Clunixchit |
last post by:
How can i read lines of a file and place each line read in an array?
for exemple;
array=line1
array=line2
...
|
by: fool |
last post by:
Dear group,
Thanks for all those who helped previously.
Now I get some value printed. Is that the value of the list getting
printed? Am I
really polluted the list?
Previous thread link...
|
by: Joerg Schoen |
last post by:
Hi folks!
Everyone knows how to sort arrays (e. g. quicksort, heapsort etc.)
For linked lists, mergesort is the typical choice.
While I was looking for a optimized implementation of mergesort...
|
by: mattmao |
last post by:
Okay, this is just my exercise in order to prepare for the coming assignment regarding the damned Linked List issue...
The task is simple and I am about to finish it. However, I couldn't go around...
|
by: arnuld |
last post by:
This program follows from the section 6.5 of K&R2 where authors created a
doubly-linked list using a binary-tree based approach. The only thing I
have rewritten myself is the getword function. I am...
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and...
| |
