Dynamically and "correctly" allocating memory

Discussion in 'C Programming' started by filia&sofia, Aug 29, 2007.

  1. filia&sofia

    filia&sofia Guest

    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.
     
    filia&sofia, Aug 29, 2007
    #1
    1. Advertising

  2. 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 <> 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 1998)
     
    Nick Keighley, Aug 29, 2007
    #2
    1. Advertising

  3. "filia&sofia" <> wrote in message
    news:...
    > 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
     
    Malcolm McLean, Aug 29, 2007
    #3
  4. 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;
    }
     
    August Karlstrom, Aug 29, 2007
    #4
  5. 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
     
    Richard Heathfield, Aug 29, 2007
    #5
  6. filia&sofia

    pete Guest

    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/C/get_line/get_delim.c

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

    --
    pete
     
    pete, Aug 30, 2007
    #6
  7. filia&sofia

    rsprawls Guest

    On Aug 29, 2:37 pm, Richard Heathfield <> 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?
     
    rsprawls, Aug 31, 2007
    #7
  8. rsprawls <> writes:
    > On Aug 29, 2:37 pm, Richard Heathfield <> 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.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"
     
    Keith Thompson, Aug 31, 2007
    #8
  9. Keith Thompson said:
    > rsprawls <> writes:
    >> On Aug 29, 2:37 pm, Richard Heathfield <> 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
     
    Richard Heathfield, Aug 31, 2007
    #9
  10. filia&sofia

    Guest

    On Aug 31, 12:26 pm, Richard Heathfield <> wrote:
    > Keith Thompson said:
    >
    > > rsprawls <> writes:
    > >> On Aug 29, 2:37 pm, Richard Heathfield <> 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
     
    , Aug 31, 2007
    #10

  11. > 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
     
    August Karlstrom, Aug 31, 2007
    #11
  12. filia&sofia

    rsprawls Guest

    On Aug 31, 6:26 am, Richard Heathfield <> wrote:
    > Keith Thompson said:
    >
    > > rsprawls <> writes:
    > >> On Aug 29, 2:37 pm, Richard Heathfield <> 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.


    Then don't. I'm not asking what bothers you in life, I'm asking for
    your reasoning.

    I use to to filter out nonsense, unfortunately it can't filter out
    attitudes, stupid remarks and...well...
     
    rsprawls, Aug 31, 2007
    #12
  13. filia&sofia

    rsprawls Guest

    On Aug 31, 12:45 pm, 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.
     
    rsprawls, Aug 31, 2007
    #13
  14. said:

    > On Aug 31, 12:26 pm, Richard Heathfield <> wrote:

    <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
     
    Richard Heathfield, Sep 1, 2007
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Joe Estock
    Replies:
    7
    Views:
    367
    Karl Heinz Buchegger
    Nov 18, 2003
  2. Jakob Bieling

    Q: Allocating memory correctly

    Jakob Bieling, Dec 7, 2003, in forum: C++
    Replies:
    10
    Views:
    562
    Pete Becker
    Dec 7, 2003
  3. Yodai
    Replies:
    1
    Views:
    287
    Yodai
    Aug 28, 2003
  4. smnoff
    Replies:
    94
    Views:
    1,441
    Herbert Rosenau
    Sep 9, 2006
  5. Rakesh Kumar
    Replies:
    5
    Views:
    686
    James Kanze
    Dec 21, 2007
Loading...

Share This Page