Home > Software design >  C: Copy content of variable without reference
C: Copy content of variable without reference

Time：11-03

I defined a display function to display the content of a queue:

void display(queue_t* s) {
    queue_t* c = s;
    int i = c->size;
    while (i > 0) {
        const char* elem = dequeue(c).value;
        printf("Item n°%d : %s\n",i,elem);
        i--;
    };
};

where queue_t is defined as follow:

typedef struct queue {
    node_t* head;
    node_t* tail;
    int size;
} queue_t;

and dequeue is a function that removes a node from the queue and frees it. This function works as intended.

The function display should display the content of the queue without deleting its content but when testing it, the queue is empty if I call display before removing each element one by one by hand by calling dequeue. I thought that queue_t* c = s; would copy the element without any link between c and s.

How can I copy the content of s into c without any link between the two variables ?

EDIT - MWE

Header file - queue.h

#ifndef QUEUE_H
#define QUEUE_H

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

typedef struct element {
    bool type;
    const char* value;
} element_t;

typedef struct node {
    element_t content;
    struct node* previous;
    struct node* next;
} node_t;

typedef struct queue {
    node_t* head;
    node_t* tail;
    int size;
} queue_t;

queue_t* init_queue(void);

node_t* init_node(element_t e);

void queue(queue_t* s, element_t e);

element_t dequeue(queue_t* s);

void display(queue_t* s);

#endif

Source code - queue.c

#include "queue.h"

queue_t* init_queue(void) {
    queue_t* new = (queue_t*)malloc(sizeof(queue_t));
    new->head = NULL;
    new->tail = NULL;
    new->size = 0;
    return new;
};

node_t* init_node(element_t e) {
    node_t* new = (node_t*)malloc(sizeof(node_t));
    new->content = e;
    new->next = NULL;
    new->previous = NULL;
    return new;
};

void queue(queue_t* s, element_t e) {
    node_t* n = init_node(e);
    if (s->size == 0) {
        s->head = n;
        s->tail = n;
        s->size = 1;
    } else {
        n->previous = s->tail;
        s->tail = n;
        s->size  ;
    };
};

element_t dequeue(queue_t* s) {
    if (s->size == 0) {
        element_t empty;
        empty.type = true;
        empty.value = "0";
        return empty;
    } if (s->size == 1) {
        element_t c = s->head->content;
        node_t* old = s->head;
        s->head = NULL;
        s->size = 0;
        s->tail = NULL;
        free(old);
        return c;
    } else {
        element_t c = s->tail->content;
        node_t* old = s->tail;
        s->tail = s->tail->previous;
        s->tail->next = NULL;
        s->size--;
        free(old);
        return c;
    };
};

void display(queue_t* s) {
    queue_t* c = s;
    int i = c->size;
    while (i > 0) {
        const char* elem = dequeue(c).value;
        printf("Item n°%d : %s\n",i,elem);
        i--;
    };
};

Test file - test.c

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include "queue.h"

int main(void) {
    element_t e1 = {.type = false, .value = "1"};
    element_t e2 = {.type = false, .value = "5"};
    element_t e3 = {.type = false, .value = "10"};

    queue_t* test = init_queue();
    queue(test,e1);
    queue(test,e2);
    queue(test,e3);

    display(test);
    element_t e4 = dequeue(test);
    printf("%s\n",e4.value);
    element_t e5 = dequeue(test);
    printf("%s\n",e5.value);
    element_t e6 = dequeue(test);
    printf("%s\n",e6.value);
    element_t e7 = dequeue(test);
    printf("%s\n",e7.value);
    return 0;
}

Run the test file using

gcc -g -std=c99 -Wall -o test.o -c test.c
gcc -g -std=c99 -Wall -o queue.o -c queue.c
gcc -g -std=c99 -Wall -o test queue.o test.o

CodePudding user response：

I thought that queue_t* c = s; would copy the element without any link between c and s.

No. It only makes a copy of the pointer s that you passed in the function.

Copying would require you to define "copy semantics", in other words:

  • What happens if you copy a queue, will the "elements" in your queue be copied too? (This is trivial for primitive types, but not so easy for objects).

  • If your elements are objects, what copy semantic do they have?

(in the case of strings, you'll need something like strncpy or memcpy to copy all characters into a new buffer)

Also, making a "true" (truly independent) copy you will need to make a complete copy of the entire queue.

This means setting up a completely new queue with all needed element data copied.

I'm phrasing it this way, because you certainly cannot re-use the head, tail, next and previous pointers from your existing queue, otherwise it would not be independent.

And... it's a bad design choice to have a method that is supposedly to be read-only* to modify your queue (data).

To display the contents of your queue you don't need to modify it.

You need to be aware, especially in C, when, how, by whom and for how long your data structures are being accessed. Just a single dangling pointer makes your whole program unpredictable.

*displaying data is considered a read-only operation by most (if not all) programmers.

CodePudding user response：

A few issues ...

  1. You're leaking memory.
  2. Passing structs by value doesn't scale.
  3. queue does not set next for s->tail so forward list traversal doesn't work.
  4. queue is much more complicated than it needs to be
  5. dequeue should be split into two functions: dequeue and destroy
  6. display should just display a list by traversal.
  7. init_node should do a deep copy of content.value

You're leaking memory.

dequeue doesn't free old->value.

It returns a copy that has a valid value.

But, in display, you do:

const char *elem = dequeue(c).value;

You never free elem

Here is the valgrind output:

==2168790== Memcheck, a memory error detector
==2168790== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2168790== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==2168790== Command: ./fix1
==2168790==
Item n°3 : 10
Item n°2 : 5
Item n°1 : 1
0
0
0
0
==2168790==
==2168790== HEAP SUMMARY:
==2168790==     in use at exit: 24 bytes in 1 blocks
==2168790==   total heap usage: 5 allocs, 4 frees, 4,216 bytes allocated
==2168790==
==2168790== LEAK SUMMARY:
==2168790==    definitely lost: 24 bytes in 1 blocks
==2168790==    indirectly lost: 0 bytes in 0 blocks
==2168790==      possibly lost: 0 bytes in 0 blocks
==2168790==    still reachable: 0 bytes in 0 blocks
==2168790==         suppressed: 0 bytes in 0 blocks
==2168790== Rerun with --leak-check=full to see details of leaked memory
==2168790==
==2168790== For lists of detected and suppressed errors, rerun with: -s
==2168790== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

dequeue returns "by value" -- this doesn't scale

Add int data[10000000]; to element_t and watch the stack blow up ;-)

In general, passing around a struct by value has similar issues in other places.

dequeue should just dequeue the element.

Do one thing well. dequeue does a dequeue and a [partial/incomplete] destroy.

We should have a separate function destroy that fully frees the node_t/element_t

And, dequeue [as written] should be renamed as pop or dequeue_back because it works from tail to head.

Also, we'd probably like a dequeue_front that works from head to tail

And, it's much more useful if the functions return pointers to the dequeued elements and let the caller use destroy on them when the caller is finished with them.

display should just display the queue and not alter/destroy it.

It could be split [after fixup] into two functions (e.g.) display_reverse and display_forward

Here is the refactored code. It is annotated:

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

#ifndef DEEPCOPY
#define DEEPCOPY        1
#endif

typedef struct element {
    bool type;
#if DEEPCOPY
    char *value;
#else
    const char *value;
#endif
} element_t;

typedef struct node {
    element_t content;
    struct node *previous;
    struct node *next;
} node_t;

typedef struct queue {
    node_t *head;
    node_t *tail;
    int size;
} queue_t;

queue_t *init_queue(void);
node_t *init_node(const element_t *e);
void queue(queue_t *s, const element_t *e);
node_t *dequeue_back(queue_t *s);
void display_forward(const queue_t *s);
void display_reverse(const queue_t *s);

queue_t *
init_queue(void)
{
    queue_t *new = malloc(sizeof(queue_t));

    new->head = NULL;
    new->tail = NULL;
    new->size = 0;

    return new;
}

node_t *
init_node(const element_t *e)
{
    node_t *new = malloc(sizeof(node_t));

    new->content = *e;

// NOTE/FIX: we should deep copy the element
#if DEEPCOPY
    new->content.value = strdup(e->value);
#endif

    new->next = NULL;
    new->previous = NULL;

    return new;
}

void
queue(queue_t *s, const element_t *e)
{
    node_t *n = init_node(e);

    if (s->size == 0) {
        s->head = n;
        s->tail = n;
        s->size = 1;
    }
    else {
        n->previous = s->tail;
// NOTE/BUG: without this forward traversal doesn't work
#if 1
        s->tail->next = n;
#endif
        s->tail = n;
        s->size  ;
    }
}

void
destroy_element(element_t *elem)
{

    free(elem->value);

    // reduce unintentional reuse after free
    elem->value = NULL;
}

node_t *
destroy_node(node_t *node)
{

    destroy_element(&node->content);

    free(node);
    node = NULL;

    // convenience to caller
    return node;
}

node_t *
dequeue_back(queue_t *s)
{
    node_t *ret = s->tail;

    if (ret != NULL) {
        s->tail = ret->previous;
        if (s->head == ret)
            s->head = ret->next;
        s->size -= 1;
    }

    return ret;
}

void
display_forward(const queue_t *s)
{
    int i = 0;
    const node_t *node = s->head;

    for (;  node != NULL;  node = node->next) {
        printf("Item n°%d : %s\n", i, node->content.value);
        i  ;
    }
}

void
display_reverse(const queue_t *s)
{
    int i = s->size;
    const node_t *node = s->tail;

    for (;  node != NULL;  node = node->previous) {
        printf("Item n°%d : %s\n", i, node->content.value);
        i--;
    }
}

int
main(void)
{
    element_t e1 = {.type = false,.value = "1" };
    element_t e2 = {.type = false,.value = "5" };
    element_t e3 = {.type = false,.value = "10" };

    queue_t *test = init_queue();

    queue(test, &e1);
    queue(test, &e2);
    queue(test, &e3);

    printf("display_reverse:\n");
    display_reverse(test);

    printf("display_forward:\n");
    display_forward(test);

    for (int i = 4;  i <= 7;    i) {
        node_t *node = dequeue_back(test);

        if (node == NULL)
            break;

        printf("main: %s (dequeue_back)\n", node->content.value);

        destroy_node(node);
    }

#if 1
    free(test);
#endif

    return 0;
}

In the above code, I've used cpp conditionals to denote old vs. new code:

#if 0
// old code
#else
// new code
#endif

#if 1
// new code
#endif

Note: this can be cleaned up by running the file through unifdef -k

Here is the program output:

display_reverse:
Item n°3 : 10
Item n°2 : 5
Item n°1 : 1
display_forward:
Item n°0 : 1
Item n°1 : 5
Item n°2 : 10
main: 10 (dequeue_back)
main: 5 (dequeue_back)
main: 1 (dequeue_back)

Page link：https//www.codepudding.com/Softwaredesign/597090.html

Prev:Why isn't my function (using multithreading) correctly taking the average?
Next:inconsistent results with left shift operator (<<)
  •  Tags：  
    • c
  • Related

About Us:  Contact Us      Terms of Service       Privacy Policy

Copyright © 2010-2023，Powered By CodePudding