pointer vs pointer to pointer

[arnuld]

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

 

[Barry Schwarz]

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");
}

 

[Ike Naar]

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]

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;
}

 

[Ben Bacarisse]

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.

}

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>