473,387 Members | 1,423 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,387 software developers and data experts.

Dynamically and "correctly" allocating memory

For example I would like to dynamically allocate memory for linked
list (or complex struct etc.) that has not maximum number of elements.
All that I can remember is that I have to have allocated variable to
point to the linked list in main program and that I have to have some
kind of a method that initializes the list (plus other methods to
manipulate list, of course). "Correctly" means that there should be
pointers involved, and possibly double or triple pointers. I have do
this long ago, but I just can't remember how to do this neatly... Any
ideas or links to help me rembember (and yes, I know malloc and
realloc basics)? Thx in advance.

Aug 29 '07 #1
12 2127
please leave the subject in the body of your message as well
Subject: "Dynamically and "correctly" allocating memory"

On 29 Aug, 12:23, filia&sofia <in_tyran...@hotmail.comwrote:
For example I would like to dynamically allocate memory for linked
list (or complex struct etc.) that has not maximum number of elements.
perhaps look up linked lists in a data structures book. Or online.
Wiki probably has a good description.
All that I can remember is that I have to have allocated variable to
point to the linked list in main program
no. You have to "root" the linked list somewhere, but it doesn't have
to be the main program. It could be inside the library that implements
the linked list or global data. It could be static or dynamic.

and that I have to have some
kind of a method that initializes the list (plus other methods to
manipulate list, of course). "Correctly" means that there should be
pointers involved,
I'm nor sure how "correctly" implies pointers. Though I'd do it that
way.

and possibly double or triple pointers.
why?
I have do
this long ago, but I just can't remember how to do this neatly... Any
ideas or links to help me rembember (and yes, I know malloc and
realloc basics)? Thx in advance.
#include <stdlib.h>
#include <assert.h>

typedef struct node_tag
{
char* data; /* whatever data you want */
struct node_tag *next;
} Node;

typedef struct
{
Node *head;
Node *tail;
} List;

int main (void)
{
List list = {NULL, NULL};
Node *node;

node = create_node("red");
add (&list, node);
assert (find (&list "red"));
assert (!find (&list "blue"));

node = create_node("blue");
add (&list, node);
assert (find (&list "red"));
assert (find (&list "blue"));

node = remove (&list, "red");
destroy_node (node);
assert (!find (&list "red"));
assert (find (&list "blue"));

reurn 0;
}

now just implement the functions above. assert() halts if its
argument evaluates to false (zero).
--
Nick Keighley
"Of course I'm going to be in an aeroplane on 31st December 1999.
You scientists wouldn't be stupid enough to build things that don't
work.
Besides what have computers got to do with aeroplanes anyway?"
(Kerry Nov 1998)

Aug 29 '07 #2

"filia&sofia" <in*********@hotmail.comwrote in message
news:11**********************@r29g2000hsg.googlegr oups.com...
For example I would like to dynamically allocate memory for linked
list (or complex struct etc.) that has not maximum number of elements.
All that I can remember is that I have to have allocated variable to
point to the linked list in main program and that I have to have some
kind of a method that initializes the list (plus other methods to
manipulate list, of course). "Correctly" means that there should be
pointers involved, and possibly double or triple pointers. I have do
this long ago, but I just can't remember how to do this neatly... Any
ideas or links to help me rembember (and yes, I know malloc and
realloc basics)? Thx in advance.
typedef struct node
{
struct node *prev;
struct node *next;
void *ptr; /* hook to hang arbitrary data off */
} NODE;

Start with a node where prev and next are both zero. This is a list of one
item.

NODE *list = malloc(sizeof(NODE));
list->next = 0;
list->prev = 0;
list->ptr = strdup("item one");
(strdup() is a non-standard function that duplicates a string. If you don't
have it, write one and call it mystrdup to avoid name clashes).

To add

NODE *newnode = malloc(sizeof(NODE));
newnode->ptr = stdup("item two");
newnode->next = list;
list->prev = newnode;
list = newnode;

to print your list

void printlist(NDOE *head)
{
while(head)
{
printf("***%s***\n", (char *) head->ptr);
head = head->next;
}
}

Deletion is harder.

void del(NODE *node)
{
NODE *prev = node->prev;
NODE *next = node->next;

if(prev)
prev->next = next;
if(next)
next->prev = prev;
free(node->ptr);
free(node);
}
--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

Aug 29 '07 #3
filia&sofia skrev:
For example I would like to dynamically allocate memory for linked
list (or complex struct etc.) that has not maximum number of elements.
All that I can remember is that I have to have allocated variable to
point to the linked list in main program and that I have to have some
kind of a method that initializes the list (plus other methods to
manipulate list, of course). "Correctly" means that there should be
pointers involved, and possibly double or triple pointers. I have do
this long ago, but I just can't remember how to do this neatly... Any
ideas or links to help me rembember (and yes, I know malloc and
realloc basics)? Thx in advance.
Below is a an example.
August
#include <stdio.h>
#include <stdlib.h>

typedef struct List {
int item;
struct List *next;
} List;

int main(void)
{
List *p, *q;
int i;

/* initialize the list */
p = NULL;
for (i = 0; i < 10; i++) {
q = malloc(sizeof *q); q->item = i; q->next = p;
p = q;
}

/* print the list */
q = p;
while (q != NULL) {
printf("%d\n", q->item);
q = q->next;
}

/* free the list */
while (p != NULL) {
q = p->next;
free(p);
p = q;
}

return 0;
}
Aug 29 '07 #4
Malcolm McLean said:
typedef struct node
{
struct node *prev;
struct node *next;
void *ptr; /* hook to hang arbitrary data off */
} NODE;
Better: separate the type creation from the synonym creation.

struct node
{
struct node *prev;
struct node *next;
void *next;
};

typedef struct node NODE;
Start with a node where prev and next are both zero. This is a list of
one item.

NODE *list = malloc(sizeof(NODE));
Better: NODE *list = malloc(sizeof *list);

Don't forget to #include <stdlib.h>
list->next = 0;
Don't write to the object pointed to by list until you're sure malloc
succeeded and that such an object therefore exists.
list->prev = 0;
list->ptr = strdup("item one");
(strdup() is a non-standard function that duplicates a string. If you
don't have it, write one and call it mystrdup to avoid name clashes).
Better: don't use it at all, even if you have it.
To add

NODE *newnode = malloc(sizeof(NODE));
newnode->ptr = stdup("item two");
What is stdup?
newnode->next = list;
list->prev = newnode;
list = newnode;
The same comments apply as above. Your adding algorithm fails to take
into account the possibility that the list is empty.
to print your list

void printlist(NDOE *head)
NDOE? Where did that come from? This gets worse and worse. In fact, it's
becoming ludicrous.

<snip>

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Aug 29 '07 #5
filia&sofia wrote:
>
For example I would like to dynamically allocate memory for linked
list (or complex struct etc.) that has not maximum number of elements.
All that I can remember is that I have to have allocated variable to
point to the linked list in main program and that I have to have some
kind of a method that initializes the list (plus other methods to
manipulate list, of course). "Correctly" means that there should be
pointers involved, and possibly double or triple pointers. I have do
this long ago, but I just can't remember how to do this neatly... Any
ideas or links to help me rembember (and yes, I know malloc and
realloc basics)? Thx in advance.
realloc is not usually part of building a linked list.

This program shows one way to create a linked list:
http://www.mindspring.com/~pfilandr/...ne/get_delim.c

This is a similar one, but with more error handling:
http://www.mindspring.com/~pfilandr/...ine/get_line.c

--
pete
Aug 29 '07 #6
On Aug 29, 2:37 pm, Richard Heathfield <r...@see.sig.invalidwrote:
Malcolm McLean said:
typedef struct node
{
struct node *prev;
struct node *next;
void *ptr; /* hook to hang arbitrary data off */
} NODE;

Better: separate the type creation from the synonym creation.

struct node
{
struct node *prev;
struct node *next;
void *next;

};

typedef struct node NODE;
Why is that better?

Aug 31 '07 #7
rsprawls <rs******@gmail.comwrites:
On Aug 29, 2:37 pm, Richard Heathfield <r...@see.sig.invalidwrote:
>Malcolm McLean said:
typedef struct node
{
struct node *prev;
struct node *next;
void *ptr; /* hook to hang arbitrary data off */
} NODE;

Better: separate the type creation from the synonym creation.

struct node
{
struct node *prev;
struct node *next;
void *next;

};

typedef struct node NODE;

Why is that better?
Perhaps the point is that one declaration should do one thing.

In my opinion (and plenty of smart people disagree with me on this)
there's seldom a good reason to define a typedef for a struct type.
Just declare it as "struct node" and refer to it that way. Adding a
second name "NODE" for something that already has a perfectly good
name "struct node" is not helpful (it reduces typing, but that's
rarely a good enough reason to do something).

But if you want a typedef, why use a different identifier? Struct
tags and typedefs are in separate namespaces, since you can always
determine by context which one you're referring to. If you want a
one-word name for your type, you can declare it as:

typedef struct node {
struct node *prev;
struct node *next;
void *ptr;
} node;

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Aug 31 '07 #8
Keith Thompson said:
rsprawls <rs******@gmail.comwrites:
>On Aug 29, 2:37 pm, Richard Heathfield <r...@see.sig.invalidwrote:
>>Malcolm McLean said:

typedef struct node
{
[...]>} NODE;
>>>
Better: separate the type creation from the synonym creation.
[...]
>>>
typedef struct node NODE;

Why is that better?
Oh, how do people expect me to answer questions if they keep using
gmail? Sheesh.
Perhaps the point is that one declaration should do one thing.
Yes, it's to do with clarity. Too many C newbies have this idea that C
has a "typedef struct" concept. Separating the type creation from the
synonym creation makes the code clearer.
In my opinion (and plenty of smart people disagree with me on this)
there's seldom a good reason to define a typedef for a struct type.
Just declare it as "struct node" and refer to it that way. Adding a
second name "NODE" for something that already has a perfectly good
name "struct node" is not helpful (it reduces typing, but that's
rarely a good enough reason to do something).
Well, I must disagree with you there. Part of the reason for using C in
the first place (rather than assembly language) is that it reduces the
amount of typing we do. That's also why we use a loop to populate an
array of known size, rather than type out every assignment separately
(despite putative performance benefits concomitant with unrolling the
loop).
But if you want a typedef, why use a different identifier?
Because it helps out with some relatively brainless IDEs, such as Visual
Studio, by simplifying its task of interpreting the editor's "jump to
definition" command. (If you use the same name for type and tag, Visual
Studio doesn't know which you mean. The compiler does, of course! But
not the Intellisense thingy.)

I generally use a trailing underscore nowadays:

struct node_
{
whatever;
};
typedef struct node_ node;

which doesn't get in the way.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Aug 31 '07 #9
On Aug 31, 12:26 pm, Richard Heathfield <r...@see.sig.invalidwrote:
Keith Thompson said:
rsprawls <rspra...@gmail.comwrites:
On Aug 29, 2:37 pm, Richard Heathfield <r...@see.sig.invalidwrote:
Malcolm McLean said:
typedef struct node
{
[...]>} NODE;
>Better: separate the type creation from the synonym creation.

[...]
>typedef struct node NODE;
Why is that better?

Oh, how do people expect me to answer questions if they keep using
gmail? Sheesh.
Perhaps the point is that one declaration should do one thing.

Yes, it's to do with clarity. Too many C newbies have this idea that C
has a "typedef struct" concept. Separating the type creation from the
synonym creation makes the code clearer.
I don't see in what way it makes it clear. Refraining from using
idiomatic code on the off-chance that a newbie might see it and become
confused is surely going too far. (And perhaps the newbie will be
curious rather than confused, and read up to get clear in her mind
what the thing in question is doing.)
In my opinion (and plenty of smart people disagree with me on this)
there's seldom a good reason to define a typedef for a struct type.
Just declare it as "struct node" and refer to it that way. Adding a
second name "NODE" for something that already has a perfectly good
name "struct node" is not helpful (it reduces typing, but that's
rarely a good enough reason to do something).

Well, I must disagree with you there. Part of the reason for using C in
the first place (rather than assembly language) is that it reduces the
amount of typing we do. That's also why we use a loop to populate an
array of known size, rather than type out every assignment separately
(despite putative performance benefits concomitant with unrolling the
loop).
But if you want a typedef, why use a different identifier?

Because it helps out with some relatively brainless IDEs, such as Visual
Studio, by simplifying its task of interpreting the editor's "jump to
definition" command. (If you use the same name for type and tag, Visual
Studio doesn't know which you mean. The compiler does, of course! But
not the Intellisense thingy.)

I generally use a trailing underscore nowadays:

struct node_
{
whatever;};

typedef struct node_ node;

which doesn't get in the way.
It doesn't get in the way, but undeniably it looks ugly. I go for
typedef struct node {
/* stuff */
} node_t;
which isn't beautiful but has a certain logic to it.
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

Aug 31 '07 #10
In my opinion (and plenty of smart people disagree with me on this)
there's seldom a good reason to define a typedef for a struct type.
In my opinion though, `struct T t' is harder to parse visually compared
to `T t'.
August
Aug 31 '07 #11
On Aug 31, 12:45 pm, Francine.Ne...@googlemail.com wrote:
I don't see in what way it makes it clear. Refraining from using
idiomatic code on the off-chance that a newbie might see it and become
confused is surely going too far. (And perhaps the newbie will be
curious rather than confused, and read up to get clear in her mind
what the thing in question is doing.)
I agree. This is starting to sound more like a personal preference
rather than efficient coding.
Aug 31 '07 #12
Fr************@googlemail.com said:
On Aug 31, 12:26 pm, Richard Heathfield <r...@see.sig.invalidwrote:
<snip>
>Yes, it's to do with clarity. Too many C newbies have this idea that
C has a "typedef struct" concept. Separating the type creation from
the synonym creation makes the code clearer.

I don't see in what way it makes it clear.
Well, this is obviously a matter of opinion, so I can't prove that it's
clearer with reference to the Standard. But I remember being misled
myself by such conflated constructs when I was learning C, and I have
no desire to inflict my own re-learning curve on other people - so
nowadays I always separate type creation from type renaming.
Refraining from using
idiomatic code on the off-chance that a newbie might see it and become
confused is surely going too far.
Um, yes and no. I think it depends very much on the idiom, and how
useful it is. I don't see the ability to create a type during the
process of renaming that very type as being particularly intuitive, and
I prefer to write my code in an intuitive way.
(And perhaps the newbie will be
curious rather than confused, and read up to get clear in her mind
what the thing in question is doing.)
Oh, very much so - but I'm afraid that this hypothetical newbie will
have to provoke her curiosity elsewhere. There's plenty of
curiosity-provoking code in the world. I see no reason, however, for me
to add my own contribution to it. I prefer my code to be mind-numbingly
obvious. :-)

<snip>
>I generally use a trailing underscore nowadays:

struct node_
{
whatever;};

typedef struct node_ node;

which doesn't get in the way.

It doesn't get in the way, but undeniably it looks ugly.
Ugliosity is in the eye of the beholder.
I go for
typedef struct node {
/* stuff */
} node_t;
which isn't beautiful but has a certain logic to it.
It also violates the POSIX Standard, which reserves names ending with _t
for additional type names. Now, strictly speaking, that isn't an issue
here, since POSIX is not topical here - but I thought you might find it
thought-provoking nonetheless. (If you want to find out more about
that, comp.unix.programmer is the place to do so.)

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Sep 1 '07 #13

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

10
by: Jakob Bieling | last post by:
Hi, Whenever allocating memory using operator new or operator new I feel like I should only use it very sparingly, because otherwise memory is wasted (by additional overhead needed to manage all...
10
by: Generic Usenet Account | last post by:
I have worked out a very simple method for tracking the "memory growth" of a process at run time. It involves a header file and a shell script. Here's the header file: ////////// Header File...
15
by: fix | last post by:
Hi all, I am writing a program using some structs, it is not running and I believe it is because there's some memory leak - the debugger tells me that the code causes the problem is in the malloc...
3
by: Tod Birdsall | last post by:
Hi All, The organization I am working for has created a new corporate website that used Microsoft's Pet Shop website as their coding model, and dynamically served up content, but cached each...
17
by: darrell.blake | last post by:
I've just written a doubly linked list but when I tell the iterator to move forward in the list it removes all the previous elements in the list. i.e. If I were to do: List list; ...
5
by: mkaushik | last post by:
Hi everyone, Im just starting out with C++, and am curious to know how "delete <pointer>", knows about the number of memory locations to free. I read somewhere that delete frees up space...
94
by: smnoff | last post by:
I have searched the internet for malloc and dynamic malloc; however, I still don't know or readily see what is general way to allocate memory to char * variable that I want to assign the substring...
6
by: bwaichu | last post by:
Is my understanding of the allocation of these correct? I used fixed sized allocations for the example below, so I realize there is some optimization that can be done to those. I would like to...
7
Plater
by: Plater | last post by:
I cannot seem to achieve what I want here. It's not a FF vs IE thing because I cannot get it in either. The heirarchy of my page is effectively: <center> <div id="backing" > ...
0
by: taylorcarr | last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
by: ryjfgjl | last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
0
BarryA
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...
1
by: nemocccc | last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
1
by: Sonnysonu | last post by:
This is the data of csv file 1 2 3 1 2 3 1 2 3 1 2 3 2 3 2 3 3 the lengths should be different i have to store the data by column-wise with in the specific length. suppose the i have to...
0
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...
0
marktang
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,...
0
jinu1996
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 using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.