Doubly linked list with no apparent memory leaks

Question

I've run my code through Valgrind and managed to not get any memory leaks based on the test code in main. I'm looking for things that I may not have thought to check for, and ways to improve my code in general.

Header file:

#ifndef DLL_H
#define DLL_H
struct node{
        void *data;
        struct node *next;
        struct node *prev;
};

struct dl_list{
        struct node *head;
        struct node *tail;
        int size;
};

struct node *create_empty_node();
struct node *create_node(void *);
void destroy_node(struct node *);

struct dl_list *create_empty_list();

struct node *search(struct dl_list *, void *, int (*comp)(void *,void *));

void insert_el_head(struct dl_list **, void *);
void insert_el_tail(struct dl_list **, void *);
void insert_node_head(struct dl_list **, struct node *);
void insert_node_tail(struct dl_list **, struct node *);
void insert_el_at(struct dl_list **, void *, int);
void insert_node_at(struct dl_list **, struct node *, int);

void delete_all(struct dl_list **, void *, int(*com)(void*,void*));
struct node *delete_el(struct dl_list **, void *, int (*comp)(void *, void *));
struct node *delete_head(struct dl_list **);
struct node *delete_tail(struct dl_list **);
struct node *delete_at(struct dl_list **, int);
struct node *delete_node(struct dl_list **, struct node *);

//uses delete_el, assuming comp == numcmp
struct node *delete_int(struct dl_list **, int);

void print_list(struct dl_list *);
int is_empty(struct dl_list *);
void clear_list(struct dl_list *);
void free_list(struct dl_list *);
int size(struct dl_list *);

//comparison functions
int numcmp(int *x, int *y);
#endif

Implementation:

#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stddef.h>
#include "double_linked_list.h"


struct node *create_empty_node(){
        struct node *temp = (struct node *) malloc(sizeof(struct node));
        temp->next = temp->prev = NULL;
        temp->data = NULL;
        return temp;
}

struct node *create_node(void *key){
        void *copy = malloc(sizeof(void *));
        memcpy(copy, key, sizeof(key));
        struct node *temp = create_empty_node();
        temp->data = copy;
        temp->next = temp->prev = NULL;
        return temp;
}

void destroy_node(struct node *to_die){
        free(to_die->data);
        free(to_die);
}

struct dl_list *create_empty_list(){
        struct dl_list *temp = (struct dl_list *)malloc(sizeof(struct dl_list));
        temp->head = temp->tail = NULL;
        temp->size = 0;
        return temp;
}

struct node *search(struct dl_list *list,
                void *key, int (*comp)(void *,void *)){
        struct node *cur = list->head;
        while(cur && !(*comp)(cur->data, key)){
                cur = cur->next;
        }
        return cur;
}

void insert_el_head(struct dl_list **list, void *key){
        struct node *temp = create_node(key);
        insert_node_head(list, temp);
}

void insert_el_tail(struct dl_list **list, void *key){
        struct node *temp = create_node(key);
        insert_node_tail(list, temp);
}

void insert_node_head(struct dl_list **list, struct node *temp){
        //is the list empty?
        if(is_empty(*list)){
                (*list)->head = (*list)->tail = temp;
                ++(*list)->size;
                return;
        }
        temp->next = (*list)->head;
        ((*list)->head)->prev = temp;
        (*list)->head = temp;
        ++(*list)->size;
}

void insert_node_tail(struct dl_list **list, struct node *temp){
        //is the list empty?
        if(is_empty(*list)){
                (*list)->head = (*list)->tail = temp;
                ++(*list)->size;
                return;
        }
        (*list)->tail->next = temp;
        temp->prev = (*list)->tail;
        (*list)->tail = temp;
        ++(*list)->size;
}
//if z>list->size, insert at tail;
void insert_el_at(struct dl_list **list, void *key, int z){
        struct node *temp = create_node(key);
        insert_node_at(list, temp, z);
}

//insert in the z+1 position
void insert_node_at(struct dl_list **list, struct node *dat, int z){
        if(is_empty(*list) || z == 0){
                insert_node_head(list, dat);
                return;
        }
        if(z >= (*list)->size){
                insert_node_tail(list, dat);
                return;
        }
        //0<z<list->size
        struct node *cur = (*list)->head;
        while(z-- > 0){
                cur = cur->next;
        }
        dat->next = cur->next;
        cur->next = dat;
        dat->next->prev = dat;
        dat->prev = cur;
        ++(*list)->size;
}        

void delete_all(struct dl_list **list, void *key, int (*comp)(void*,void*)){
        //nothing to delete
        if(is_empty(*list)){
                return;
        }
        //list not empty
        struct node *cur;
        struct node *temp;
        for(cur = (*list)->head; cur != NULL; ){
                //if first element is key, remove it
                if((*comp)((*list)->head->data, key)){
                        cur = cur->next;
                        destroy_node(delete_head(list));
                }
                //if tail is key, remove it
                if((*comp)((*list)->tail->data, key)){
                        cur = cur->next;
                        destroy_node(delete_tail(list));
                }
                //key found in cur->data
                else if((*comp)(cur->data, key)){
                        cur->prev->next = cur->next;
                        cur->next->prev = cur->prev;
                        temp = cur;
                        cur = (cur->next ? cur->next : NULL);
                        destroy_node(temp);
                        --(*list)->size;
                }
                //key not found
                else{
                        cur = cur->next;
                }
        }
}

struct node *delete_el(struct dl_list **list, void *key, int (*comp)(void*,void*)){
        if(is_empty(*list)){
                return NULL;
        }
        struct node *cur;
        //key not found
        if(!(cur=search(*list, key, comp))){ return NULL; }
        //delete found key
        return delete_node(list, cur);
}

struct node *delete_head(struct dl_list **list){
        //empty list
        if(is_empty(*list)){
                return NULL;
        }
        //singleton list
        if((*list)->size == 1){
                struct node *to_die = (*list)->head;
                (*list)->head = (*list)->tail = NULL;
                --(*list)->size;
                return to_die;
        }
        //(*list)->size > 1
        struct node *to_die = (*list)->head;
        (*list)->head = (*list)->head->next;
        (*list)->head->prev = NULL;
        --(*list)->size;
        return to_die;
}

struct node *delete_tail(struct dl_list **list){
        //empty list
        if(is_empty(*list)){
                return NULL;
        }
        //singleton list
        if((*list)->size == 1){
                struct node *to_die = (*list)->head;
                (*list)->head = (*list)->tail = NULL;
                --(*list)->size;
                return to_die;
        }
        //(*list)->size > 1
        struct node *to_die = (*list)->tail;
        (*list)->tail = (*list)->tail->prev;
        (*list)->tail->next = NULL;
        --(*list)->size;
        return to_die;
}

//delete tail if input is larger than list size
//delete the element immediately after the zth node
struct node *delete_at(struct dl_list **list, int z){
        if(is_empty(*list)){
                //nothing to delete
                return NULL;
        }
        else if(z == 0){
                return delete_head(list);
        }
        else if(z >= (*list)->size){
                return delete_tail(list);
        }
        else{
                struct node *temp = (*list)->head;
                while(z-- > 0){
                        temp = temp->next;
                }
                return delete_node(list, temp);
        }
}

struct node *delete_node(struct dl_list **list, struct node *to_die){
        if(!to_die->next){
                //data == (*list)->tail
                return delete_tail(list);
        }
        else if(!to_die->prev){
                //data == (*list)->head                
                return delete_head(list);
        }
        else{
                to_die->prev->next = to_die->next;
                to_die->next->prev = to_die->prev;
                --(*list)->size;
                to_die->next = to_die->prev = NULL;
                return to_die;
        }
}

struct node *delete_int(struct dl_list **list, int z){
        return delete_el(list, (void *)&z, (int(*)(void*,void*))numcmp);
}


void print_list(struct dl_list *list){
        if(list->size == 0){
                return;
        }
        int i = 0;
        struct node *cur = list->head;
        while(i++ < list->size){
                printf("%d ", *((int *)cur->data));
                cur = cur->next;
        }
        printf("\n");
}

int is_empty(struct dl_list *list){ return list == NULL || list->size == 0; }

void clear_list(struct dl_list *list){
        list->size = 0;
        struct node *cur;
        struct node *temp;
        for(cur = list->head; cur != NULL; cur = temp){
                temp = cur->next;
                destroy_node(cur);
        }
}
int size(struct dl_list *list){
        return list->size;
}

void free_list(struct dl_list *list){
        clear_list(list);
        free(list);
}

int numcmp(int *x, int *y){
        return *x == *y;
}

/*
int main(){
        int *p = (int *)malloc(sizeof(int *));
        int x = 1, y=2, z=5, a=7, m = 100;
        *p = m;
        struct dl_list *head = create_empty_list();
        insert_el_head(&head, (void *)p);
        insert_el_head(&head, (void *)&x);
        insert_el_head(&head, (void *)&y);
        print_list(head);
        insert_el_head(&head, (void *)&z);
        insert_el_head(&head, (void *)&a);
        insert_el_head(&head, (void *)&z);
        insert_el_head(&head, (void *)&a);
        print_list(head);
        insert_el_tail(&head, (void *)&z);
        insert_el_tail(&head, (void *)&a);
        insert_el_tail(&head, (void *)&z);
        insert_el_tail(&head, (void *)&a);
        insert_el_tail(&head, (void *)&y);
        insert_el_tail(&head, (void *)&y);
        insert_el_tail(&head, (void *)&y);
        insert_el_tail(&head, (void *)&y);

        print_list(head);
        destroy_node(delete_int(&head, x));
        print_list(head);
        delete_all(&head, (void *)&a, (int(*)(void*,void*))numcmp);
        print_list(head);

        struct node *temp = search(head, (void *)&z,
                (int (*)(void *,void *))numcmp);
        printf("is it found? %d\n", (temp == NULL) ? 0 : *((int *)temp->data));

        temp = search(head, (void *)&m, (int (*)(void *,void *))numcmp);
        printf("Is it found? %d\n", (temp == NULL) ? 0 : *((int *)temp->data));

        print_list(head);

        print_list(head);
        printf("Deleting head\n");
        destroy_node(delete_head(&head));
        print_list(head);
        printf("Deleting tail\n");
        destroy_node(delete_tail(&head));
        print_list(head);


        printf("Deleting: %d\n", *((int *)&x));
        printf("Null? %d\n", delete_el(&head, (void *)&x, (int(*)(void*,void*))numcmp)==NULL);
        print_list(head);
        printf("Freeing p\n");
        free(p);
        print_list(head);

        printf("Inserting %d at position %d\n", *((int *)&y), 5);
        insert_el_at(&head, (void *)&y, 4);
        print_list(head);
        destroy_node(delete_at(&head, 10000));

        print_list(head);
        printf("Size: %d\n", size(head));
        free_list(head);


        return 0;
}
*/

Answer 1

There are multiple issues with your code. The most obviously wrong is the use of double-pointers everywhere.

For example:

void insert_node_head(struct dl_list **list, struct node *temp){
    if(is_empty(*list)){
        (*list)->head = (*list)->tail = temp;
        ++(*list)->size;
        return;
    }

The double pointers result in the need to de-reference before use, as in (*list)->head. This is totally unnecessary. This and all other functions should be written with single pointers:

void insert_node_head(struct dl_list *list, struct node *temp){
    if(is_empty(list)){
        list->head = list->tail = temp;
        ++list->size;
        return;
    }

Double pointers are necessary only when you need to change a pointer (as opposed to what the pointer locates) in the calling function.

---

Your idea of data storage is odd. In your key parameters you seem to want to store just an integer value (as all of the data you store in your tests is smaller or equal to a void*). In create_node you make a copy of the key.

struct node *create_node(void *key){
        void *copy = malloc(sizeof(void *));
        memcpy(copy, key, sizeof(key));

This might be what you intended but all the same it looks wrong. Your node structure contains a void *data field and you are allocating another void* to hang off that, so at a minimum the allocation is redundant. But more to the point if you wanted to store only data up to the size of a pointer, you should just declare data differently. It would be much simpler just to store an int or long and cast integer types to that, but if you really want to store varying data types, you might use a union (although unions are not widely used):

union node_data {
    int i;
    long l;
    char ch;
};

struct node{
    union node_data data; // not a pointer
    ...

struct node *create_node(union node_data *data)
{
        struct node *n = create_empty_node();
        n->data = *data;

This also makes it clearer to the caller the nature of the data that can be stored. Your existing functions appear to offer the ability to store data of any size. As I said, storing a single scalar type is much simpler.

With variable data types, the comparator functions need to know what data they are comparing, so your existing comparisons and any based upon a union as above are unlikely to be reliable without some extra information to identify the type of data (a discriminator for the union). If any given list contains only one data type, the problem is lessened, but you have no way to enforce that.

---

You have many functions taking a callback and you have many function calls that cast a function parameter to be suitable for these functions:

struct node *search(struct dl_list *, void *, int (*comp)(void *,void *));
...
temp = search(head, (void *)&m, (int (*)(void *,void *))numcmp);

These are ugly and make reading slower than it need be. It is better to define a comparator type:

typedef int(*Comparator)(const void*,const void*);
...
struct node *search(struct dl_list *, void *, Comparator);
...
temp = search(head, (void *)&m, (Comparator) numcmp);

Note also the const in the Comparator definition.

---

The loop in your delete_all function is odd:

struct node *cur;
struct node *temp;
for(cur = (*list)->head; cur != NULL; ){
    //if first element is key, remove it
    if((*comp)((*list)->head->data, key)){
            cur = cur->next;
            destroy_node(delete_head(list));
    }
    //if tail is key, remove it
    if((*comp)((*list)->tail->data, key)){
            cur = cur->next;
            destroy_node(delete_tail(list));
    }
    //key found in cur->data
    else if((*comp)(cur->data, key)){

You call comp three times, when one should suffice, and you have a loop variable cur which traverses each entry in the list but is unused until the third call of comp. It would be more normal to examine each cur using comp and then if there is a match, adjust the list according to whether cur is the head/tail or other:

for (struct node *cur = list->head; cur != NULL; ...) {
    if (comp(cur->data, key)){
        /* do all the work in here !! */
        if (cur is head) {
            ...
        }
        else if (cur is tail) {
            ...
        }
        else {
            ...
        }
    }
}

Note that I defined cur within the for-loop and assumed removal of the list double-pointer

---

I think that is enough for really, but a few minor points occur to me:

• use const everywhere you can. Functions that don't change a pointer parameter should define that parameter const. For example:

  void insert_el_head(struct dl_list *, const void *);
  int size(const struct dl_list *);
  

• don't cast the return from malloc. This is not needed in C and can be harmful.

• functions (and their prototypes) that take no parameters should declare a void parameter list.

• function pointers can be used as if they were functions, so instead of writing

  (*comp)(cur->data, key)
  

  you can write the more understandable

  comp(cur->data, key)
  

Answer 2

typedef means you no longer have to write struct all over the place. That not only saves keystrokes, it also can make the code cleaner since it provides a smidgen more abstraction. There are some places I wouldn't use it in your code, but the structs in your header file can use them.

typedef struct {
        void *data;
        struct node *next;
        struct node *prev;
} Node;

---

Some of your if conditions only have one statement in them. This is completely optional, but I like to remove the braces and move the statement up to the same line as the condition.

if(is_empty(*list)) return;

---

I find the space between the name and the asterisks a bit hard to read. You also don't include a space sometimes. You can choose to keep the space or not, but consistency is important.

void delete_all(struct dl_list **, void *, int(*com)(void*,void*)); // inconsistent

void delete_all(struct dl_list**, void*, int(*com)(void*,void*)); // consistent

Answer 3

I don't see any memory leaks per se. However, poor naming of your delete_*() functions could mislead a user into thinking that those functions free the memory. After all, delete in C++ frees memory. Your delete_all() function frees memory.

To prevent confusion, I suggest renaming the delete_*() functions (except delete_all()) to something like remove_*(), or better yet, detach_*().