Generic doubly-linked list in C

Question

The goal is to write a generic doubly linked list program to handle.

Header:

#include <stdio.h>
#include <stdlib.h>
struct list {
 struct node *head;
 struct node *tail;
 size_t element_size;
 int element_count;
 void (*printFunc)(struct node *);
};
struct node {
 struct node *next;
 struct node *previous;
 void *data;
 size_t type_size;
};
struct node *init_node(void *element, size_t type_size);
struct list *init_list(size_t type_size, void (*printFunc)(struct node *));
void append(void *element, size_t type_size, struct list *l);
void prepend(void *element, size_t type_size, struct list *l);
void print_list(struct list *l);
void print_float(struct node *n);
void print_double(struct node *n);
void print_char(struct node *n);
void print_int(struct node *n);
void print_str(struct node *n);
struct node *poll(struct list *l);
struct node *rm_last(struct list *l);
struct node *peek_front(struct list *l);
struct node *peek_back(struct list *l);
void free_list(struct list *l);
void free_node(struct node *n);

Source:

#include "linked_list.h"
int main(int argc, char **argv) {
 char array[5] = {'a', 'b', 'c', 'd', 'e'};
 struct list *l = init_list(sizeof(char), &print_char);
 for (int i = 0; i < 5; i++) {
 prepend(&array[i], sizeof(char), l);
 }
 print_list(l);
 free_list(l);
 return 1;
}
struct node *init_node(void *element, size_t type_size) {
 struct node *n = malloc(sizeof(struct node));
 n->data = malloc(type_size);
 if (n != NULL && n->data != NULL) {
 n->data = element;
 n->next = NULL;
 n->previous = NULL;
 n->type_size = type_size;
 }
 return n;
}
// creates linked list with dummy head/tail
struct list *init_list(size_t type_size, void (*pf)(struct node *)) {
 struct list *l = malloc(sizeof(struct list));
 if (l != NULL) {
 l->head = NULL;
 l->tail = NULL;
 l->element_size = type_size;
 l->element_count = 0;
 l->printFunc = pf;
 }
 return l;
}
void prepend(void *element, size_t type_size, struct list *l) {
 struct node *n = init_node(element, type_size);
 if (n != NULL) {
 if (l->element_count != 0) {
 struct node *tmp = l->head;
 n->next = l->head;
 l->head = n;
 tmp->previous = n;
 }
 else {
 l->head = n;
 l->tail = n;
 }
 l->element_count += 1;
 }
}
void append(void *element, size_t type_size, struct list *l) {
 struct node *n = init_node(element, type_size);
 if (n != NULL) {
 if (l->element_count != 0) {
 struct node *tmp = l->tail;
 n->previous = l->tail;
 l->tail = n;
 tmp->next = n;
 }
 else {
 l->head = n;
 l->tail = n;
 }
 l->element_count += 1;
 }
}
void print_float(struct node *n) {
 printf("%f\n", *((float *) n->data));
}
void print_double(struct node *n) {
 printf("%lf\n", *((double *) n->data));
}
void print_char(struct node *n) { 
 printf("%c\n", *((char *) n->data));
}
void print_int(struct node *n) {
 printf("%d\n", *((int *) n->data));
}
void print_str(struct node *n) {
 printf("%s\n", *((char **) n->data));
}
// Removes node from front of linked list. Does not free memory assoc. with node.
struct node *poll(struct list *l) {
 struct node *n = NULL;
 if (l->element_count > 0) {
 n = l->head;
 l->head = n->next;
 l->head->previous = NULL;
 l->element_count -= 1;
 }
 return n;
}
// Removes node from tail of linked list.
struct node *rm_last(struct list *l) {
 struct node *n = NULL;
 if (l->element_count > 0) {
 n = l->tail;
 l->tail = n->previous;
 l->tail->next = NULL;
 l->element_count -= 1;
 }
 return n;
}
struct node *peek_front(struct list *l) {
 return l->head;
}
struct node *peek_back(struct list *l) {
 return l->tail;
}
void print_list(struct list *l) {
 struct node *cur = l->head;
 while (cur != NULL) {
 l->printFunc(cur);
 cur = cur->next;
 }
} 
void free_list(struct list *l) {
 struct node *n = l->head;
 while(n) {
 struct node *tmp = n;
 n = n->next;
 //free(tmp->data);
 tmp->previous = NULL;
 tmp->next = NULL;
 free(tmp);
 }
}
/*
void free_node(struct node **n) {
 struct node *tmp = *n;
 free(tmp->data);
 tmp->previous = NULL;
 tmp->next = NULL;
 free(tmp);
}
*/

Questions:

1. Are there any memory leaks that free_list is missing?

2. Is there any need to keep track of the size of the data type stored by the node or the size of the data type in the list struct?

• Dair: I don't think it is with free_list but running Valgrind gives some memory leak errors init_node and init_list...
• ElleJay: You can mimic OOP's classes with providing a pointer to a print function in the element struct. This way you could print any other data too
• Ciro Santilli OurBigBook.com: related: stackoverflow.com/questions/982388/…

Answer 1

Memory leak, plus confusion

In init_node(), you have this code:

 n->data = malloc(type_size);
 if (n != NULL && n->data != NULL) {
 n->data = element;

Immediately, I see a memory leak because you allocate some memory and assign it to a pointer, and then immediately reassign the pointer to something else.

I'm confused about how you intended for your list to work. Either the list should make a copy of the input element, or it should retain a pointer to input element. It looks like you tried to do a little bit of both.

To do it correctly, either:

1. Do the malloc like you did in the first line above, but instead of the third line, use memcpy to copy the contents of the input element.

2. Eliminate the first line with the malloc, and keep the assignment from the third line.

Answer 2

Unclear why //free(tmp->data); is commented out. I'd expect that to be free'd too.

---

Consider the standard function free() which allows free(NULL)

void free(void *ptr);

...If ptr is a null pointer, no action occurs. ... C11 §7.22.3.3 2

To this end, suggest allowing free_list() to tolerate free_list(NULL); and repeated free_list(l); free_list(l); This will help prevent memory leaks/errors.

void free_list(struct list *l) {
 // add
 if (l) {
 ...

Any maybe

void free_list(struct list *l) {
 if (l) {
 struct node *n = l->head;
 while(n) {
 struct node *tmp = n;
 n = n->next;
 tmp->previous = NULL;
 tmp->next = NULL;
 free(tmp);
 }
 l->head = NULL; // add
 }
}

As an aid debugging, zeroing free'd memory tends to more quickly highlight access problems to free'd memory quicker than not. This is much like OP's 2 tmp->....= NULL; assignments, but I would zero the entire structure.

 memcpy(tmp, 0, sizeof *tmp); // add
 // tmp->previous = NULL;
 // tmp->next = NULL;
 free(tmp);

---

Other

n != NULL test is too late. That test needs to happen before n->data = ...

n->data = malloc(type_size);
if (n != NULL && n->data != NULL) {

print_float() / print_double() excessively prints large numbers with lots of digits (possible hundreds) and all numbers smaller than 0.0000005 as 0.000000. Better to use "%.*e". Details: Printf width specifier to maintain precision of floating-point value

void print_float(struct node *n) {
 printf("%.*e\n", FLT_DECIMAL_DIG - 1, *((float *) n->data));
}
void print_double(struct node *n) {
 printf("%.*e\n", DBL_DECIMAL_DIG - 1, *((double *) n->data));
}

---

Is there any need to keep track of the size of the data type stored by the node or the size of the data type in the list struct?

Sort of. Function set design is inconsistent. On one hand, during initialization, the print function is passed, negated the need for that to be passed later (and potentially being the being the wrong one). Yet the add functions pass in the size of the data object.

I'd recommend either 1) specifying all this data (print function, size, etc.) up front, as part of the init_list() and store accordingly or 2) pass this data in the add/print functions as needed.

I see no need to store the size in the data node.

Code could store this data (data size, print function, sort function, etc.) in a separate structure and only that structure's pointer is store in the list head structure. This gets a bit complicated to manage, but it avoids excessive repetition of data in the list head structure.

• PellMel: In your suggested version of free_list(), variable tmp is dereferenced after it is freed.
• chux: @PellMel Fixed.
• Wrddot: n->data was commented out because free(n->data) is throwing this error " linked_list(20349,0x7fff7bb9f000) malloc: *** error for object 0x7fff54294ac0: pointer being freed was not allocated *** set a breakpoint in malloc_error_break to debug Abort trap: 6 " I know I need to free it since it was malloc-ed. But it's not clear to me how I do it if free(n->data) is incorrect.