1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 | #include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>
#include "clog.h"
// Linked list of strings on the heap
//
// BUG: Free the node before freeing what its .value field refers to.
typedef struct _Node { // canonical type name is 'struct _Node'
char* value;
struct _Node* next;
} Node; // shortcut (typedef) name is 'Node'
char* _strdup(char const* src) {
char* copy_of_src = malloc(sizeof(*copy_of_src) * (strlen(src) + 1));
return strcpy(copy_of_src, src);
}
void print_list(Node* head) {
for(Node* curr = head; curr != NULL; curr = curr -> next) {
printf("[%s]", curr -> value);
printf(curr -> next != NULL ? "→" : "\n");
}
}
void append(char* value, Node** a_head, Node** a_tail) {
// 1. Allocate memory for the new node.
Node* new_tail = malloc(sizeof(*new_tail));
// 2. Initialize the fields of the new node.
*new_tail = (Node) { .value = value, .next = NULL };
// 3. Depending on whether or not the list was initially empty…
if(*a_head == NULL) { // If list is empty (size 0)…
// … Set the head (*a_head) to the (address of) the new tail, or …
*a_head = new_tail; // type of *a_head is Node*. type of new_tail is Node*.
}
else {
// … Connect the old tail to the new tail.
(*a_tail) -> next = new_tail;
}
// 4. Set the tail (*a_tail) to the (address of the) new tail.
*a_tail = new_tail;
// IMPORTANT: This must come last.
}
void destroy_list(Node** a_head, Node** a_tail) {
while(*a_head != NULL) { // While list is not empty…
Node* new_head = (*a_head) -> next; // 1. Save (address of) new head (or NULL)
free(*a_head); // 3. Free the old head.
free((*a_head) -> value); // 2. Free whatever head node refers to.
// BUG!!!! We cannot access (*a_head)->value now, because we already freed *a_head.
*a_head = new_head; // 4. Set the head to the new_head.
}
*a_tail = NULL; // 5. Set the tail to NULL.
// Order is important. If we free before saving the (address of) new_head, we won't
// be able to access it.
assert(*a_head == NULL);
}
int main(int argc, char* argv[]) {
Node* head = NULL; // Linked list of size 0 (empty list)
Node* tail = NULL;
append(_strdup("AB"), &head, &tail);
assert(head == tail); // In a list of size 1, head and tail refer to the same Node.
append(_strdup("CD"), &head, &tail);
assert(head != tail); // In a list of size 2, head and tail DON'T refer to the same Node
//assert(tail -> value == 11);
append(_strdup("EF"), &head, &tail);
print_list(head);
destroy_list(&head, &tail);
assert(head == NULL);
assert(tail == NULL);
return EXIT_SUCCESS;
}
/*
==35123== HEAP SUMMARY:
==35123== in use at exit: 9 bytes in 3 blocks
### 3 blocks (leaked) = 3 strings not freed = 1 string/node (* 3 nodes)
==35123== total heap usage: 6 allocs, 3 frees, 57 bytes allocated
### 6 allocs = 3 for Node objects + 3 for the strings they refer to
### 3 frees = 3 for the Node objects freed in destroy_list(…)
==35123==
==35123== 3 bytes in 1 blocks are definitely lost in loss record 1 of 3
==35123== at 0x4C29F73: malloc (vg_replace_malloc.c:309)
==35123== by 0x4006E8: _strdup (r.c:16)
==35123== by 0x40087E: main (r.c:66)
==35123==
==35123== 3 bytes in 1 blocks are definitely lost in loss record 2 of 3
==35123== at 0x4C29F73: malloc (vg_replace_malloc.c:309)
==35123== by 0x4006E8: _strdup (r.c:16)
==35123== by 0x4008C4: main (r.c:68)
==35123==
==35123== 3 bytes in 1 blocks are definitely lost in loss record 3 of 3
==35123== at 0x4C29F73: malloc (vg_replace_malloc.c:309)
==35123== by 0x4006E8: _strdup (r.c:16)
==35123== by 0x40090A: main (r.c:71)
==35123==
==35123== LEAK SUMMARY:
==35123== definitely lost: 9 bytes in 3 blocks
==35123== indirectly lost: 0 bytes in 0 blocks
==35123== possibly lost: 0 bytes in 0 blocks
==35123== still reachable: 0 bytes in 0 blocks
==35123== suppressed: 0 bytes in 0 blocks
==35123==
==35123== For lists of detected and suppressed errors, rerun with: -s
==35123== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 0 from 0)
*/
/* vim: set tabstop=4 shiftwidth=4 fileencoding=utf-8 noexpandtab: */
|
© Copyright 2022 Alexander J. Quinn This content is protected and may not be shared, uploaded, or distributed.