pointer vs pointer to pointer

Discussion in 'C Programming' started by arnuld, Jun 11, 2012.

  1. arnuld

    arnuld Guest

    AIM: To write a queue with 3 operations.
    WHAT I GOT: It works
    PROBLEM: Have a question: Why do "pointer to pointer" in enqueue() and "a
    pointer" to deleteElement() both work fine ? Will enqueue() work fine if
    I pass just "a pointer" to it ? Will deleteElement() work fine if I pass
    "pointer to pointer" ?

    /* A queue implementataion with the operations that I need:
    * (1) Add element to the front of the queue
    * (2) remove an element with a unique ID (string constant)
    * (3) compare 2 elements (string comparison)
    * (4) print queue
    *
    * VERSION 0.1
    */

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    enum { SIZE_ID = 100 };

    struct myQ
    {
    char id[SIZE_ID+1];
    struct myQ* next;
    };

    struct myList
    {
    struct myQ* head;
    };



    int enqueue(struct myList** s, const char* id);
    void deleteElement(struct myList* s, const char* id);
    int compareElements(struct myQ* e1, struct myQ* e2);
    void printQ(struct myList* s);



    int main(void)
    {
    struct myList* s = malloc(1 * (sizeof *s));
    if(NULL == s) exit(EXIT_FAILURE);

    enqueue(&s, "1");
    enqueue(&s, "2");enqueue(&s, "3");
    printQ(s);
    deleteElement(s, "3");
    printQ(s);
    deleteElement(s, "2");
    printQ(s);
    deleteElement(s, "1");
    printQ(s);

    free(s);
    return 0;
    }


    int enqueue(struct myList** s, const char* id)
    {
    struct myQ *p, *h;
    if(NULL == s || NULL == id) return -1;
    p = malloc(1 * (sizeof *p));
    if(NULL == p) return -1;
    strcpy(p->id, id);
    p->next = NULL;

    h = (*s)->head;
    (*s)->head = p;
    p->next = h;

    return 1;
    }


    void deleteElement(struct myList* s, const char* id)
    {
    struct myQ *prev, *curr;
    if(NULL == s || NULL == id) return;
    prev = s->head;
    for(curr = s->head; curr; curr = curr->next)
    {
    if(0 == strcmp(curr->id, id))
    {
    prev->next = curr->next;
    if(0 == strcmp(s->head->id, curr->id)) s->head = curr->next;
    free(curr);
    break;
    }
    else
    {
    prev = curr;
    }
    }
    }


    void printQ(struct myList* s)
    {
    if(s)
    {
    struct myQ* t;
    for(t = s->head; t; t = t->next) printf("ID = %s\n", t->id);
    }
    else
    {
    printf("Nothing to print\n");
    }

    printf("--------------------------------\n");
    }


    ====================== OUTPUT ========================
    /home/arnuld/programs/C $ gcc -ansi -pedantic -Wall -Wextra queue.c
    /home/arnuld/programs/C $ ./a.out
    ID = 3
    ID = 2
    ID = 1
    --------------------------------
    ID = 2
    ID = 1
    --------------------------------
    ID = 1
    --------------------------------
    --------------------------------
    /home/arnuld/programs/C $


    --
    arnuld
    http://LispMachine.Wordpress.com
    arnuld, Jun 11, 2012
    #1
    1. Advertising

  2. On 11 Jun 2012 07:13:05 GMT, arnuld <> wrote:

    >AIM: To write a queue with 3 operations.
    >WHAT I GOT: It works
    >PROBLEM: Have a question: Why do "pointer to pointer" in enqueue() and "a
    >pointer" to deleteElement() both work fine ? Will enqueue() work fine if
    >I pass just "a pointer" to it ? Will deleteElement() work fine if I pass


    Since enqueue() uses *s ONLY as the left operand of ->, main() could
    call enqueue() with s instead of &s and enqueue() could use s instead
    of *s. This would "improve" enqueue (both performance and
    readability) and is worth doing.

    >"pointer to pointer" ?


    Similarly, deleteElement() uses s only as the left operand of -> so
    main() could call deleteElement() with &s and deleteElement could use
    *s in place of s. This would detract from deleteElement (both
    performance and readability) and is worth not doing.

    If you want a function to update an object directly, you can pass a
    pointer to that object and the function can dereference the pointer to
    update the object. If the object to be updated happens to be a
    pointer, then the pointer argument in question just happens to be a
    pointer to pointer.

    Since neither of your functions want to update the pointer (they only
    update the structure eventually pointed to), there is no need to pass
    the address of the pointer.

    >
    >/* A queue implementataion with the operations that I need:
    > * (1) Add element to the front of the queue
    > * (2) remove an element with a unique ID (string constant)
    > * (3) compare 2 elements (string comparison)
    > * (4) print queue
    > *
    > * VERSION 0.1
    > */
    >
    >#include <stdio.h>
    >#include <stdlib.h>
    >#include <string.h>
    >
    >enum { SIZE_ID = 100 };
    >
    >struct myQ
    >{
    > char id[SIZE_ID+1];
    > struct myQ* next;
    >};
    >
    >struct myList
    >{
    > struct myQ* head;
    >};
    >
    >
    >
    >int enqueue(struct myList** s, const char* id);
    >void deleteElement(struct myList* s, const char* id);
    >int compareElements(struct myQ* e1, struct myQ* e2);
    >void printQ(struct myList* s);
    >
    >
    >
    >int main(void)
    >{
    > struct myList* s = malloc(1 * (sizeof *s));
    > if(NULL == s) exit(EXIT_FAILURE);
    >
    > enqueue(&s, "1");
    > enqueue(&s, "2");enqueue(&s, "3");
    > printQ(s);
    > deleteElement(s, "3");
    > printQ(s);
    > deleteElement(s, "2");
    > printQ(s);
    > deleteElement(s, "1");
    > printQ(s);
    >
    > free(s);
    > return 0;
    >}
    >
    >
    >int enqueue(struct myList** s, const char* id)
    >{
    > struct myQ *p, *h;
    > if(NULL == s || NULL == id) return -1;
    > p = malloc(1 * (sizeof *p));
    > if(NULL == p) return -1;
    > strcpy(p->id, id);
    > p->next = NULL;
    >
    > h = (*s)->head;
    > (*s)->head = p;
    > p->next = h;
    >
    > return 1;
    >}
    >
    >
    >void deleteElement(struct myList* s, const char* id)
    >{
    > struct myQ *prev, *curr;
    > if(NULL == s || NULL == id) return;
    > prev = s->head;
    > for(curr = s->head; curr; curr = curr->next)
    > {
    > if(0 == strcmp(curr->id, id))
    > {
    > prev->next = curr->next;
    > if(0 == strcmp(s->head->id, curr->id)) s->head = curr->next;
    > free(curr);
    > break;
    > }
    > else
    > {
    > prev = curr;
    > }
    > }
    >}
    >
    >
    >void printQ(struct myList* s)
    >{
    > if(s)
    > {
    > struct myQ* t;
    > for(t = s->head; t; t = t->next) printf("ID = %s\n", t->id);
    > }
    > else
    > {
    > printf("Nothing to print\n");
    > }
    >
    > printf("--------------------------------\n");
    >}


    --
    Remove del for email
    Barry Schwarz, Jun 11, 2012
    #2
    1. Advertising

  3. arnuld

    Ike Naar Guest

    On 2012-06-11, arnuld <> wrote:
    > AIM: To write a queue with 3 operations.
    > WHAT I GOT: It works


    Sorry, there is a problem.

    > int main(void)
    > {
    > struct myList* s = malloc(1 * (sizeof *s));


    Here, you allocate enough space for a struct Mylist.
    The space is uninitialized, in particular s->head
    contains garbage.

    > enqueue(&s, "1");


    Looking at enqueue:

    > int enqueue(struct myList** s, const char* id)
    > {
    > struct myQ *p, *h;
    > if(NULL == s || NULL == id) return -1;


    You might also want to bail out if *s == NULL .

    > p = malloc(1 * (sizeof *p));
    > if(NULL == p) return -1;
    > strcpy(p->id, id);
    > p->next = NULL;


    This assignment is useless, as p->next is re-assigned
    another value a few lines below.

    >
    > h = (*s)->head;


    where (*s)->head contains garbage.

    > (*s)->head = p;
    > p->next = h;


    The list that starts at (*s)->head is not
    properly terminated (it's supposed to be terminated
    by a null pointer, but in fact it's terminated by
    garbage). That may lead to problems when walking through
    the list, which happens e.g. in the for loops in printQ()
    or deleteElement().

    To fix this, set s->head to NULL after allocating the
    space for struct myList *s in main().

    Or it might be a better idea to write a constructor
    function that returns a properly initialized empty list,
    and use the constructor instead of using a bare malloc call.
    Ike Naar, Jun 11, 2012
    #3
  4. arnuld

    Ike Naar Guest

    On 2012-06-11, arnuld <> wrote:
    > PROBLEM: Have a question: Why do "pointer to pointer" in enqueue() and "a
    > pointer" to deleteElement() both work fine ? Will enqueue() work fine if
    > I pass just "a pointer" to it ? Will deleteElement() work fine if I pass
    > "pointer to pointer" ?


    Yes and yes. Looking at enqueue:

    > int enqueue(struct myList** s, const char* id)
    > {
    > struct myQ *p, *h;
    > if(NULL == s || NULL == id) return -1;
    > p = malloc(1 * (sizeof *p));
    > if(NULL == p) return -1;
    > strcpy(p->id, id);
    > p->next = NULL;
    >
    > h = (*s)->head;
    > (*s)->head = p;
    > p->next = h;
    >
    > return 1;
    > }


    in enqueue, s is never used (only *s is),
    and *s is never modified, so you might as well
    substitute s for *s everywhere in this function.

    > p->next = NULL;
    > h = (*s)->head;
    > (*s)->head = p;
    > p->next = h;


    can be written more simply as

    p->next = (*s)->head;
    (*s)->head = p;

    eliminating h.

    Combining all this, enqueue would look somewhat like

    int enqueue(struct myList* s, const char* id)
    {
    struct myQ *p;
    if (NULL == s || NULL == id) return -1;
    p = malloc(sizeof *p);
    if (NULL == p) return -1;
    strcpy(p->id, id);
    p->next = s->head;
    s->head = p;
    return 1;
    }
    Ike Naar, Jun 11, 2012
    #4
  5. arnuld <> writes:

    A couple of things not yet said...

    > AIM: To write a queue with 3 operations.
    > WHAT I GOT: It works
    > PROBLEM: Have a question: Why do "pointer to pointer" in enqueue() and "a
    > pointer" to deleteElement() both work fine ? Will enqueue() work fine if
    > I pass just "a pointer" to it ? Will deleteElement() work fine if I pass
    > "pointer to pointer" ?
    >
    > /* A queue implementataion with the operations that I need:
    > * (1) Add element to the front of the queue
    > * (2) remove an element with a unique ID (string constant)
    > * (3) compare 2 elements (string comparison)
    > * (4) print queue
    > *
    > * VERSION 0.1
    > */
    >
    > #include <stdio.h>
    > #include <stdlib.h>
    > #include <string.h>
    >
    > enum { SIZE_ID = 100 };


    I like to distinguish between length and size for strings. The size is
    at least one move than the length. Since you allocate space for
    SIZE_ID+1 bytes, SIZE_ID is really the maximum length, not the maximum
    size. Small point, but I think these things really help with +1 and -1
    errors.

    > struct myQ
    > {
    > char id[SIZE_ID+1];
    > struct myQ* next;
    > };
    >
    > struct myList
    > {
    > struct myQ* head;
    > };


    To my mind, these two structs are the wrong way round. struct myQ is a
    list node, and struct myList represents a queue!

    > int enqueue(struct myList** s, const char* id);
    > void deleteElement(struct myList* s, const char* id);
    > int compareElements(struct myQ* e1, struct myQ* e2);
    > void printQ(struct myList* s);
    >
    >
    >
    > int main(void)
    > {
    > struct myList* s = malloc(1 * (sizeof *s));
    > if(NULL == s) exit(EXIT_FAILURE);


    Why not

    struct myList s = {0};

    ? It's much simpler, especially for testing and initialisation is easy.

    By the way, if you possibly can, try using valgrind. It is, to my mind,
    one of the best tools a beginner can use.

    <snip>
    > }
    >

    <snip>
    > void deleteElement(struct myList* s, const char* id)
    > {
    > struct myQ *prev, *curr;
    > if(NULL == s || NULL == id) return;
    > prev = s->head;
    > for(curr = s->head; curr; curr = curr->next)
    > {
    > if(0 == strcmp(curr->id, id))
    > {
    > prev->next = curr->next;
    > if(0 == strcmp(s->head->id, curr->id)) s->head = curr->next;
    > free(curr);
    > break;
    > }
    > else
    > {
    > prev = curr;
    > }
    > }
    > }


    Adding a test for strcmp(s->head->id, curr->id) just to see if this is
    the head of the queue is yucky! Much simpler would be cur == s->head.

    However, you can this code so that the head element is not special. The
    only reason you have 'prev', is that you can set its 'next' member to
    the tail of the current location (curr->next). I do this be keeping a
    pointer to where this new list tail should be written:

    struct myQ **tail_loc = &s->head;
    for (curr = s->head; curr; curr = curr->next)
    {
    if (0 == strcmp(curr->id, id))
    {
    *tail_loc = curr->next;
    free(curr);
    break;
    }
    tail_loc = &curr->next;
    }

    You can avoid 'curr' and using break altogether:

    struct myQ **tail_loc = &s->head;
    while (*tail_loc && strcmp((*tail_loc)->id, id))
    tail_loc = &(*tail_loc)->next;
    if (*tail_loc) {
    struct myQ *np = *tail_loc;
    *tail_loc = np->next;
    free(np);
    }

    but that's maybe too fiddly. It's much nicer in a language with
    references because you loose all those *s.

    <snip>
    --
    Ben.
    Ben Bacarisse, Jun 11, 2012
    #5
    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. Replies:
    10
    Views:
    672
    Chris Torek
    Feb 4, 2005
  2. jimjim
    Replies:
    16
    Views:
    822
    Jordan Abel
    Mar 28, 2006
  3. Replies:
    4
    Views:
    1,230
    Fred Zwarts
    Jul 2, 2009
  4. A
    Replies:
    7
    Views:
    625
  5. , India

    pointer to an array vs pointer to pointer

    , India, Sep 20, 2011, in forum: C Programming
    Replies:
    5
    Views:
    441
    James Kuyper
    Sep 23, 2011
Loading...

Share This Page