12
\$\begingroup\$

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;
}
*/
\$\endgroup\$
  • 3
    \$\begingroup\$ Hmm, that's a lot of code. Sounds like a job for tomorrow :P \$\endgroup\$ – syb0rg Dec 24 '13 at 5:50
10
\$\begingroup\$

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)
    
\$\endgroup\$
  • \$\begingroup\$ My oh my, you really went all out. +1 \$\endgroup\$ – syb0rg Dec 25 '13 at 18:11
  • \$\begingroup\$ Thank you very much for this well thought out answer. Many of the concerns were on my mind, but I was unaware of how to do them (for example typedeffing the function pointer). My use of a void pointer as the data type is to gain some form of generic data type for the list, I only tested with ints for ease. Is there a better way to get a generic type effect? \$\endgroup\$ – Sunde Dec 26 '13 at 4:31
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Thank you for taking the time to read the code and give input. I'm curious about the use of typedef, I see in the Linux kernel guidelines under the typedef section that it is not suggested to typdef structures and pointers. Is there a general consensus on when, and when not to use typedefs? I'm much more experienced with Java and I mainly keep the statements such as if(is_empty(*list)){ return; } for a consistency reason (otherwise I'd spend a long time on a stupid error where I forgot brackets after a conditional). Thanks again. \$\endgroup\$ – Sunde Dec 25 '13 at 6:47
  • \$\begingroup\$ @Sunde Here is a typedef question on SO. It's fine if you keep the if(is_empty(*list)){ return; }, as long as you are consistent with them (that's what really matters). \$\endgroup\$ – syb0rg Dec 25 '13 at 16:25
2
\$\begingroup\$

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_*().

\$\endgroup\$
  • \$\begingroup\$ Thanks you for that input, as I am fairly new to C, I wasn't aware of the convention to have delete free memory. Originally the methods did free the method, but it seemed easier to implement stacks and queues using a doubly linked list, and so not freeing the data became more helpful. I appreciate the advice, this is my first attempt at C and really want to make sure I am doing everything I can to produce good code. \$\endgroup\$ – Sunde Dec 25 '13 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.