Consider implementing a (doubly) linked list.
The simplest strategy is to provide functions
item_t add_item(item_t predecessor);
void delete_item(ite m_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  2729 
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(ite m_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(ite m_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(ite m_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)(vo id *))
{
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(ite m_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(ite m_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(nod e * 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(ite m_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(ite m_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(nod e * 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**********@y ahoo.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(ite m_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(nod e * 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 the program. I'm fairly new
at the pointer business, and I'd appreciate any advice. Here's my code:
int main()
{
ifstream fin;
|
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 children - when a child is fork()ed
its pid is added to the linked list. I then have a SIGCHLD handler which is
supposed to remove the pid from the list when a child exits. The problem I'm
having is that very very occasionally and seemingly...
|
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;
};
struct pcb *pcb_pointer;
|
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 (sorry for google)
http://groups.google.com/group/comp.lang.c/browse_thread/thread/346d99317e6b772b/578ac16a2ed4ed35?hl=en#578ac16a2ed4ed35
|
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 for
linked lists, I couldn't find one. I read something about Mcilroy's
"Optimistic Merge Sort" and studied some implementation, but they
were for arrays. Does anybody know if Mcilroys optimization is applicable to
truly linked lists at all?
|
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 one last bit: how to print out the elements?
Here is so far what I've got:
#include <stdio.h>
#include <stdlib.h>
struct intRecord
|
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 using it because there
are many concepts involved in this program that I want to understand like:
1.) degree of efficiency of this program as compared to sort using hash-table
based approach.
2.) Keeping the program well structured so...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
| | |
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 tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
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 presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
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 then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| | |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |
