I'm working on a challenge problem themed about graphs, so I decided to implement a multiply linked list (this data structure can represent directed graphs). I'm running into problems when I try to create nodes for the list. The program compiles fine, but when it runs it only goes to a certain point and exits without warning. Running it in debug mode within VS2019, the IDE shows me I'm trying to dereference a null pointer. In fact, before it even compiles it underscores the suspicious line and warns that that could happen. But I don't understand why at all. Here is the implementation of the linked list (with minimal working example, and do mean minimal, I tried my best...):
#include<stdlib.h>
#include<stdio.h>
typedef unsigned int uint;
typedef struct Node {
uint id;
uint data;
size_t num_parents;
size_t size_parents;
struct Node * parents;
size_t num_children;
size_t size_children;
struct Node * children;
} Node;
/*/ ORIGINAL PROBLEMATIC REALLOCATING FUNCTION
Node * reallocate_node_array(Node * array, size_t* size) {
Node * new_array = new_array(Node, *size * 2); // this doesn't seem to be working as I expected
for (size_t i = 0; i < *size; i ) {
new_array[i] = array[i]; // FAULTY LINE
}
*size *= 2;
return new_array;
}
/**/
//NEW VERSION EDITED TO REFLECT CRAIG ESTEY'S COMMENTS AND ANSWER
Node * reallocate_node_array(Node * array, size_t* size) {
array = realloc(array, (*size) * 2);
if (array == NULL) {
perror("realloc");
exit(1);
}
*size *= 2;
return array;
}
void remove_node(Node * array, size_t * size, size_t index) {
for (int i = index; i < *size - 1; i ) {
array[i] = array[i 1];
}
(*size)--;
}
void remove_parent (Node * node, uint id) {
for (int i = 0; i < node->num_parents; i ) {
if (node->parents[i].id == id) {
remove_node(node->parents, &node->num_parents, i);
}
}
}
void remove_child(Node * node, uint id) {
for (int i = 0; i < node->num_children; i ) {
if (node->children[i].id == id) {
remove_node(node->children, &node->num_children, i);
}
}
}
void add_child(Node * node, Node * child) {
if (node->num_children >= node->size_children) {
node->children = reallocate_node_array(node->children, &node->size_children);
}
node->children[ node->num_children] = *child;
}
void add_parent(Node * node, Node * parent) {
if (node->num_parents >= node->size_parents) {
node->parents = reallocate_node_array(node->parents, &node->size_parents);
}
node->parents[ node->num_parents] = *parent;
}
int main() {
char * file_name = "input.txt";
FILE * data_file = fopen(file_name, "r");
if (data_file == NULL) {
printf("Error: invalid file %s", file_name);
return 1;
}
uint num_nodes, num_relationships;
fscanf(data_file, "%u %u\n", &num_nodes, &num_relationships);
// I'm sorry that I'm not checking for the result of malloc in this block.
// I promise I'll be more responsible in the future.
Node * nodes = (Node*)malloc((num_nodes 1) * sizeof(Node));
for (size_t i = 1; i <= num_nodes; i ) {
nodes[i].id = i;
fscanf(data_file, "%u ", &nodes[i].data);
nodes[i].num_children = 0;
nodes[i].size_children = 10;
nodes[i].children = (Node*)malloc(10 * sizeof(Node)); // FAULTY LINE #1
nodes[i].num_parents = 0;
nodes[i].size_parents = 10;
nodes[i].parents = (Node*)malloc(10 * sizeof(Node)); // FAULTY LINE #2
}
for (uint i = 0; i < num_relationships; i ) {
uint parent_id, child_id;
fscanf(data_file, "%u %u\n", &parent_id, &child_id);
add_child(&employees[parent_id], &employees[child_id]);
add_parent(&employees[child_id], &employees[parent_id]);
}
return 0;
}
Where it says "FAULTY LINE #1" and "#2", the debugger tells me the program has reached a breakpoint (throws an exception).
The point of the main function is to build the following structure (graph):
A directed graph with small number of nodes. The most succint way to do that is by reading instructions from a file. Here is the content of input.txt:
7 8
21 33 33 18 42 22 26
1 2
1 3
2 5
3 5
3 6
4 6
4 7
6 7
First line: 7 is the number of nodes; 8 is the number of connections (relationships).
All other lines: Left number is parent node; right number is child node.
So, my problem was that I couldn't get past the reallocate_node_array function and later from "FAULTY LINE #1" and "#2".
EDIT
So I edited a lot above in order to provide a minimum working example and further clarify my context and difficulties. Whatever else I was doing wrong, I would appreciate if you'd tell me.
However, after I edited my reallocate_node_array function according to Craig Estey's critique, I was able to move further along in debugging and realized some terrible faults in the above implementation. Most importantly is that my struct Node's fields parents and children needed to be of type Node** and not Node*, because they're supposed to be arrays in order to represent a multiply-linked list. With that in mind, I rewrote the implementation as below, which is behaving as expected. I ran, nevertheless, into problems with further tasks using this code, which are not in the scope of this question. If I'm to pose a new question, I'll be sure to keep all of your critiques in mind and try to write a good question next time.
Thank you all for all your feedback.
#include<stdlib.h>
#include<stdio.h>
typedef unsigned int uint;
typedef struct Node {
uint id; // identifier of the node
int data; // actual data
size_t num_parents; // actual number of parent nodes
size_t size_parents; // current maximum capacity of array of parent nodes
struct Node** parents; // all nodes that connect from "upstream"
size_t num_children; // actual number of child nodes
size_t size_children; // current maximum capacity of array of children nodes
struct Node** children; // all nodes that connect "downstream"
} Node;
void reallocate_node_array(Node** array, size_t* size) {
array = realloc(array, sizeof(Node*) * (*size) * 2);
if (array == NULL) {
perror("realloc");
exit(1);
}
*size *= 2;
}
// The intention is to pass `num_children` or `num_parents` as `size` in order to decrease them
void remove_node(Node** array, size_t* size, size_t index) {
for (size_t i = index; i < *size - 1; i ) {
array[i] = array[i 1];
}
(*size)--; // the decrement to either `num_children` or `num_parents`
}
void remove_parent(Node* node, uint id) {
for (size_t i = 0; i < node->num_parents; i ) {
if (node->parents[i]->id == id) {
remove_node(node->parents, &node->num_parents, i);
}
}
}
void remove_child(Node* node, uint id) {
for (size_t i = 0; i < node->num_children; i ) {
if (node->children[i]->id == id) {
remove_node(node->children, &node->num_children, i);
}
}
}
void add_parent(Node* node, Node* parent) {
if (node->num_parents >= node->size_parents) {
reallocate_node_array(node->parents, &node->size_parents);
}
node->parents[node->num_parents ] = parent;
}
void add_child(Node* node, Node* child) {
if (node->num_children >= node->size_children) {
reallocate_node_array(node->children, &node->size_children);
}
node->children[node->num_children ] = child;
}
int main() {
char* file_name = "input.txt";
FILE* data_file = fopen(file_name, "r");
if (data_file == NULL) {
printf("Error: invalid file %s", file_name);
return 1;
}
uint num_nodes, num_relationships;
fscanf(data_file, "%u %u\n", &num_nodes, &num_relationships);
Node* nodes = (Node*)malloc((num_nodes 1) * sizeof(Node));
for (size_t i = 1; i <= num_nodes; i ) {
nodes[i].id = i;
fscanf(data_file, "%u ", &nodes[i].data);
nodes[i].num_children = 0;
nodes[i].size_children = 10;
nodes[i].children = (Node**)malloc(10 * sizeof(Node*));
for (size_t j = 0; j < 10; j ) nodes[i].children[j] = (Node*)malloc(sizeof(Node));
nodes[i].num_parents = 0;
nodes[i].size_parents = 10;
nodes[i].parents = (Node**)malloc(10 * sizeof(Node*));
for (size_t j = 0; j < 10; j ) nodes[i].parents[j] = (Node*)malloc(sizeof(Node));
}
for (uint i = 0; i < num_relationships; i ) {
uint parent_id, child_id;
fscanf(data_file, "%u %u\n", &parent_id, &child_id);
add_child(&nodes[parent_id], &nodes[child_id]);
add_parent(&nodes[child_id], &nodes[parent_id]);
}
return 0;
}
CodePudding user response：
From my top comment:
Where is the call to
reallocate_node_array? Please edit your question and post it. If it's (e.g.):myarray = reallocate_node_array(myarray,&myarray_size), then the original value ofmyarrayis leaked (because the function does not free the old/original array pointer). Unless you're trying to create a separate duplicate copy, why not just use realloc? – Craig Estey
Your response indicates that this is, indeed, the issue.
So, here is the simple fix:
Node *
reallocate_node_array(Node *array, size_t *size)
{
array = realloc(array,sizeof(*array) * *size * 2);
if (array == NULL) {
perror("realloc");
exit(1);
}
*size *= 2;
return array;
}
But, when I see the array size passed as a separate parameter, I want to create a new "array" struct that has the size/length in it. This is similar to what a c vector does:
typedef struct {
Node *data;
size_t size;
} NodeArray;
void
reallocate_node_array(NodeArray *array)
{
array->data = realloc(array->data,sizeof(*array->data) * array->size * 2);
if (array->data == NULL) {
perror("realloc");
exit(1);
}
array->size *= 2;
}
That's a bit excessive because the caller still has to keep track of things.
This is often a exercise for beginning C programmers.
Here's an enhancement:
typedef struct {
Node *data; // pointer to data
size_t size; // number of elements currently in use
size_t capacity; // number of elements available
} NodeArray;
void
reallocate_node_array(NodeArray *array,size_t need)
// array -- pointer to node array
// need -- number of elements to grow by
{
size_t size = array->size need;
if (size >= array->capacity) {
array->capacity = size 100;
array->data = realloc(array->data,
sizeof(*array->data) * array->capacity);
if (array->data == NULL) {
perror("realloc");
exit(1);
}
}
}