Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Dynamically and "correctly" allocating memory

Reply
Thread Tools

Dynamically and "correctly" allocating memory

 
 
filia&sofia
Guest
Posts: n/a
 
      08-29-2007
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.

 
Reply With Quote
 
 
 
 
Nick Keighley
Guest
Posts: n/a
 
      08-29-2007
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 <(E-Mail Removed)> wrote:

> 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 199

 
Reply With Quote
 
 
 
 
Malcolm McLean
Guest
Posts: n/a
 
      08-29-2007

"filia&sofia" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) 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

 
Reply With Quote
 
August Karlstrom
Guest
Posts: n/a
 
      08-29-2007
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;
}
 
Reply With Quote
 
Richard Heathfield
Guest
Posts: n/a
 
      08-29-2007
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
 
Reply With Quote
 
pete
Guest
Posts: n/a
 
      08-29-2007
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
 
Reply With Quote
 
rsprawls
Guest
Posts: n/a
 
      08-31-2007
On Aug 29, 2:37 pm, Richard Heathfield <(E-Mail Removed)> wrote:
> 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?

 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      08-31-2007
rsprawls <(E-Mail Removed)> writes:
> On Aug 29, 2:37 pm, Richard Heathfield <(E-Mail Removed)> wrote:
>> 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) http://www.velocityreviews.com/forums/(E-Mail Removed) <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"
 
Reply With Quote
 
Richard Heathfield
Guest
Posts: n/a
 
      08-31-2007
Keith Thompson said:
> rsprawls <(E-Mail Removed)> writes:
>> On Aug 29, 2:37 pm, Richard Heathfield <(E-Mail Removed)> wrote:
>>> 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
 
Reply With Quote
 
Francine.Neary@googlemail.com
Guest
Posts: n/a
 
      08-31-2007
On Aug 31, 12:26 pm, Richard Heathfield <(E-Mail Removed)> wrote:
> Keith Thompson said:
>
> > rsprawls <(E-Mail Removed)> writes:
> >> On Aug 29, 2:37 pm, Richard Heathfield <(E-Mail Removed)> wrote:
> >>> 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



 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
allocating m bytes dynamically 2005 C Programming 19 02-07-2010 06:12 AM
Allocating vector of strings seem to crash. Allocating array ofstrings seems to be ok . Rakesh Kumar C++ 5 12-21-2007 10:42 AM
General method for dynamically allocating memory for a string smnoff C Programming 94 09-09-2006 08:52 PM
dynamically allocating a 2d array junky_fellow@yahoo.co.in C Programming 10 09-13-2005 04:21 AM
Data storage/retrieval and dynamically allocating memory Joe Estock C++ 7 11-18-2003 02:30 PM



Advertisments