1
\$\begingroup\$

I have implemented generic doubly linked list in C language in which you can store any data type you want. Just like in C++ and Java, where a list can store any data type, like - string, int, long, structure, etc., you can do the same using this program.

Can someone please review the code.

The code is below:


generic_doubly_linked_list.c


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "generic_doubly_linked_list.h"

/*
 * generic_doubly_linked_list.c:
 *
 *      This program implements a linked list in which you can store any data type
 *      you want. Just like in C++ and Java, a list can store any data type, like -
 *      string, int, long, structure, etc., you can do the same using this program.
 *
 *      There are comments in generic_doubly_linked_list.h which will help in
 *      understanding the program.
 */

/*
 * char *get_error_string(int error_num):
 *
 * Function get_error_string() returns the string that corresponds to the error
 * number passed to it.
 *
 */
char *get_error_string(int error_num)
{

    if (error_num == NO_ERROR) {
        return "No error happened.";
    } else if (error_num == INVALID_DATA_TYPE) {
        return "Argument 'data_type' is neither SIMPLE_DATA_TYPE nor COMPLEX_DATA_TYPE.";
    } else if (error_num == NO_MEMORY) {
        return "No memory available.";
    } else if (error_num == INVALID_DATA_LEN) {
        return "Argument 'data_len' is <= 0.";
    } else if (error_num == ROOT_IS_NULL) {
        return "Argument 'root' is NULL.";
    } else if (error_num == MATCHING_NODE_NOT_FOUND) {
        return "No node found whose data matches the data given by the user.";
    } else if (error_num == DATA_IS_NULL) {
        return "Argument 'data' is NULL.";
    } else {
        return "Invalid error number given.";
    }

} // end of get_error_string

/*
 * dlln_ptr add_to_front(dlln_ptr root, long double data, int data_type, long data_len, int *error_num):
 *
 * Function add_to_front() adds a list node to the front of the list contaning data
 * passed to it by the user and the new root is returned. The root of the list will
 * change because the list node is added to front, so the user must update the
 * root value with the value returned by this function.
 *
 * In case any error happens, the error number is saved in the argument 'error_num'.
 *
 * If 'data_type' is SIMPLE_DATA_TYPE then the argument 'data_len' is ignored.
 *
 * The details of SIMPLE_DATA_TYPE and COMPLEX_DATA_TYPE can be found in
 * generic_doubly_linked_list.h.
 *
 *  When you pass in a simple data type, the same data is stored in the data field
 *  of the list node. So, if you pass in interger 4 then 4 will be stored in the
 *  data field. If you pass a pointer to integer (for example - 0xABABABAB)
 *  then 0xABABABAB will be stored in the data field.
 *
 *  When you pass in a complex data type, then the data pointed to by the passed
 *  in pointer is copied and not the pointer itself. So, if you pass in a pointer
 *  to a string then new memory is allocated whose length is equal to the passed
 *  in parameter 'data_len' and then contents of string are copied into this
 *  new memory. Same goes for pointers to structures, unions, etc.
 */
dlln_ptr add_to_front(dlln_ptr root, long double data, int data_type, long data_len, int *error_num)
{

    dlln_ptr temp = NULL;

    *error_num = NO_ERROR;

    if ((data_type != SIMPLE_DATA_TYPE) && (data_type != COMPLEX_DATA_TYPE)) {
        *error_num = INVALID_DATA_TYPE;
        return root;
    }

    if (data_type == COMPLEX_DATA_TYPE) {

        //check if data is NULL
        if (data == 0) {
            *error_num = DATA_IS_NULL;
            return root;
        }

        // check data_len
        if (data_len <= 0) {
            *error_num = INVALID_DATA_LEN;
            return root;
        }
    }

    temp = calloc(1, DLL_STRUCT_SIZE);
    if (!temp) {
        *error_num = NO_MEMORY;
        return root;
    }

#if DEBUG_ON
    printf("Allocated memory for list node. Number of bytes allocated = %ld.\n", DLL_STRUCT_SIZE);
#endif

    temp->data_type = data_type;

    if (data_type == SIMPLE_DATA_TYPE) {

        temp->data_len = 0;
        temp->data = data;

    } else { // COMPLEX_DATA_TYPE

        temp->data_len = data_len;
        temp->data = (long long)(calloc(data_len, 1));
        if (temp->data == 0) {
            *error_num = NO_MEMORY;
            // zero out memory before free to catch some use after free bugs if any
            memset(temp, 0, DLL_STRUCT_SIZE);
            free(temp);
            return root;
        }

#if DEBUG_ON
    printf("Allocated memory for data. Number of bytes allocated = %ld.\n", data_len);
#endif

        memcpy((void *)(long long)(temp->data), (void *)(long long)(data), data_len);

    } // end of if else condition data_type == SIMPLE_DATA_TYPE

    temp->next = root;
    if (root)
        root->prev = temp;
    temp->prev = NULL;

    return temp;

} // end of add_to_front

/*
 * dlln_ptr delete_node_matching_data(dlln_ptr root, long double data, int data_type, long data_len, int *error_num):
 *
 * Function delete_node_matching_data() deletes a list node that contains the data
 * that matches the data passed in by the user and [new] root is returned.
 * In case, the list node to be deleted is the root itself then the list will have
 * a new root, so the user must update the root value with the value returned
 * by this function.
 *
 * In case any error happens, the error number is saved in the argument 'error_num'.
 *
 * If 'data_type' is SIMPLE_DATA_TYPE then the user supplied data is directly
 * compared with the data in the list node. If both the data are same, then
 * the node is deleted else the next node is inspected. In SIMPLE_DATA_TYPE data
 * type case argument 'data_len' is ignored. 
 *
 * If 'data_type' is COMPLEX_DATA_TYPE then the value of the argument 'data_len' is
 * compared to the value of 'data_len' field of the list node. If they are not
 * equal then next node is inspected. If they are equal then the contents of the
 * memory pointed to by the user supplied data pointer is compared with the contents
 * of the memory pointed to by the data pointer in the list node and if they are
 * same then this node is deleted else the next node is inspected.
 *
 */
dlln_ptr delete_node_matching_data(dlln_ptr root, long double data, int data_type, long data_len, int *error_num)
{

    dlln_ptr temp = NULL;
    int delete_this_node = 0;

    *error_num = NO_ERROR;

    if (!root) {
        *error_num = ROOT_IS_NULL;
        return root;
    }

    if ((data_type != SIMPLE_DATA_TYPE) && (data_type != COMPLEX_DATA_TYPE)) {
        *error_num = INVALID_DATA_TYPE;
        return root;
    }

    if (data_type == COMPLEX_DATA_TYPE) {

        //check if data is NULL
        if (data == 0) {
            *error_num = DATA_IS_NULL;
            return root;
        }

        // check data_len
        if (data_len <= 0) {
            *error_num = INVALID_DATA_LEN;
            return root;
        }
    }

    for (temp = root; temp != NULL; temp = temp->next) {
        
        if (data_type == SIMPLE_DATA_TYPE) {

            if (temp->data == data) {
                root = delete_node(root, temp);
                return root;
            }

        } else { // COMPLEX_DATA_TYPE

            if (temp->data_len != data_len) {
                continue;
            }

            if (memcmp((void *)(long long)(temp->data), (void *)(long long)(data), data_len) == 0) {
                root = delete_node(root, temp);
                return root;
            }

        } // end of if else condition data_type == SIMPLE_DATA_TYPE

    } // end of for loop

    // matching node not found
    *error_num = MATCHING_NODE_NOT_FOUND;

    return root;

} // end of delete_node_matching_data

/*
 * dlln_ptr delete_node(dlln_ptr root, dlln_ptr node_to_delete):
 * 
 * Function delete_node() deletes the list node whose pointer is passed in the
 * argument 'node_to_delete' and returns [new] root.
 *
 * In case, the list node to be deleted is the root itself then the list will have
 * a new root, so the user must update the root value with the value returned
 * by this function.
 *
 */
dlln_ptr delete_node(dlln_ptr root, dlln_ptr node_to_delete)
{

    dlln_ptr new_root = root;

    if (!root) {
        return root;
    }

    if (!node_to_delete) {
        return root;
    }

    if (node_to_delete == root) { // deleting root node
        new_root = root->next;
        if (new_root) {
            new_root->prev = NULL;
        }
    } else {
        node_to_delete->prev->next = node_to_delete->next;
        if (node_to_delete->next) {
            node_to_delete->next->prev = node_to_delete->prev;
        }
    }

    if (node_to_delete->data_type == COMPLEX_DATA_TYPE) {
        void *cmp_data = (void *)(long long)(node_to_delete->data);
        // zero out memory before free to catch some use after free bugs if any
        memset(cmp_data, 0, node_to_delete->data_len);
        free(cmp_data);
#if DEBUG_ON
    printf("Freed data memory.\n");
#endif
    }

    // zero out memory before free to catch some use after free bugs if any
    memset(node_to_delete, 0, DLL_STRUCT_SIZE);
    free(node_to_delete);
#if DEBUG_ON
    printf("Freed list node memory.\n");
#endif

    return new_root;

} // end of delete_node

/*
 * dlln_ptr delete_all_nodes_from_list(dlln_ptr root):
 * 
 * Function delete_all_nodes_from_list() deletes all the nodes in the list and
 * returns NULL.
 *
 */
dlln_ptr delete_all_nodes_from_list(dlln_ptr root)
{

    while (root) {
        root = delete_node(root, root);
    }

    return NULL;

} // end of delete_all_nodes_from_list


generic_doubly_linked_list.h


#ifndef _GENERIC_DOUBLY_LINKED_LIST_H
#define _GENERIC_DOUBLY_LINKED_LIST_H

/*
 * generic_doubly_linked_list.c:
 *
 *      This program implements a linked list in which you can store any data type
 *      you want. Just like in C++ and Java, a list can store any data type, like -
 *      string, int, long, structure, etc., you can do the same using this program.
 *
 *      There are comments in in this header file which will help in understanding
 *      the program.
 */

#define NO_ERROR 0 // no error happened.
#define INVALID_DATA_TYPE -1 // argument 'data_type' is neither SIMPLE_DATA_TYPE nor COMPLEX_DATA_TYPE.
#define NO_MEMORY -2 // no memory available.
#define INVALID_DATA_LEN -3 // argument 'data_len' is <= 0.
#define ROOT_IS_NULL -4 // argument 'root' is NULL.
#define MATCHING_NODE_NOT_FOUND -5 // no node found whose data matches the data given by the user.
#define DATA_IS_NULL -6 // argument 'data' is NULL.

/*
 * SIMPLE_DATA_TYPE and COMPLEX_DATA_TYPE are used to tell the program that the
 * data is of simple type or of complex type.
 *
 * SIMPLE_DATA_TYPE:
 *      Simple data type means char, short, int, long, float, double, long long,
 *      long double, etc. and pointers to these data types. When you pass in a
 *      simple data type, the same data is stored in the data field of the list node.
 *      So, if you pass in interger 4 then 4 will be stored in the data field. If
 *      you pass a pointer to integer (for example - 0xABABABAB) then 0xABABABAB will
 *      be stored in the data field. The argument 'data_len' is ignored for
 *      SIMPLE_DATA_TYPE.
 *
 * COMPLEX_DATA_TYPE:
 *      Complex data type is always a pointer and it is a pointer to string,
 *      structures, unions, etc. But pointer to int, float, etc. (basically, pointer
 *      to basic data types) should be considered as SIMPLE_DATA_TYPE. When you
 *      pass in a complex data type, then the data pointed to by the passed in pointer
 *      is copied and not the pointer itself. So, if you pass in a pointer to a
 *      string then new memory is allocated whose length is equal to the passed in
 *      parameter 'data_len' and then contents of string are copied into this new memory.
 *      Same goes for pointers to structures, unions, etc.
 *
 * IMPORTANT NOTE: When you are passing in a pointer to string, please make sure that
 *                 the length of the data that you pass in includes 1 extra byte
 *                 for null byte.
 */
#define SIMPLE_DATA_TYPE 1  // char, short, int, long, float, double, long long, long double, etc. and pointers to these data types
#define COMPLEX_DATA_TYPE 2 // always a pointer which is pointer to string, structures, unions, etc. 

/*
 * Converting from long double to pointer and vice-versa:
 *
 *      If you want to convert long double type to pointer type then please follow
 *      the code below:
 *              long double a;
 *              char *b = (char *)(long long)(a);
 *  
 *      If you want to convert pointer type to long double type then please follow
 *      the code below:
 *              char *a;
 *              long double b = (long double)(long long)(a);
 */

struct doubly_linked_list_node {
    int data_type;
    long data_len;
    long double data;
    struct doubly_linked_list_node *prev;
    struct doubly_linked_list_node *next;
};

#define DLL_STRUCT_SIZE sizeof(struct doubly_linked_list_node)

typedef struct doubly_linked_list_node *dlln_ptr;

/*
 * NOTE:
 *
 *  If you want to loop through the list and get the data then you can use the
 *  following code:
 *
 *      dlln_ptr temp = root;
 *      while (temp) {
 *          YOUR_DATA_TYPE data = (YOUR_DATA_TYPE)(long long)(temp->data);
 *          // do something with data
 *          temp = temp->next;
 *      }
 */

/*
 * char *get_error_string(int error_num):
 *
 * Function get_error_string() returns the string that corresponds to the error
 * number passed to it.
 *
 */
char *get_error_string(int error_num);

/*
 * dlln_ptr add_to_front(dlln_ptr root, long double data, int data_type, long data_len, int *error_num):
 *
 * Function add_to_front() adds a list node to the front of the list contaning data
 * passed to it by the user and the new root is returned. The root of the list will
 * change because the list node is added to front, so the user must update the
 * root value with the value returned by this function.
 *
 * In case any error happens, the error number is saved in the argument 'error_num'.
 *
 * If 'data_type' is SIMPLE_DATA_TYPE then the argument 'data_len' is ignored.
 *
 * The details of SIMPLE_DATA_TYPE and COMPLEX_DATA_TYPE can be found in
 * generic_doubly_linked_list.h.
 *
 *  When you pass in a simple data type, the same data is stored in the data field
 *  of the list node. So, if you pass in interger 4 then 4 will be stored in the
 *  data field. If you pass a pointer to integer (for example - 0xABABABAB)
 *  then 0xABABABAB will be stored in the data field.
 *
 *  When you pass in a complex data type, then the data pointed to by the passed
 *  in pointer is copied and not the pointer itself. So, if you pass in a pointer
 *  to a string then new memory is allocated whose length is equal to the passed
 *  in parameter 'data_len' and then contents of string are copied into this
 *  new memory. Same goes for pointers to structures, unions, etc.
 */
dlln_ptr add_to_front(dlln_ptr root, long double data, int data_type, long data_len, int *error_num);

/*
 * dlln_ptr delete_node_matching_data(dlln_ptr root, long double data, int data_type, long data_len, int *error_num):
 *
 * Function delete_node_matching_data() deletes a list node that contains the data
 * that matches the data passed in by the user and [new] root is returned.
 * In case, the list node to be deleted is the root itself then the list will have
 * a new root, so the user must update the root value with the value returned
 * by this function.
 *
 * In case any error happens, the error number is saved in the argument 'error_num'.
 *
 * If 'data_type' is SIMPLE_DATA_TYPE then the user supplied data is directly
 * compared with the data in the list node. If both the data are same, then
 * the node is deleted else the next node is inspected. In SIMPLE_DATA_TYPE data
 * type case argument 'data_len' is ignored. 
 *
 * If 'data_type' is COMPLEX_DATA_TYPE then the value of the argument 'data_len' is
 * compared to the value of 'data_len' field of the list node. If they are not
 * equal then next node is inspected. If they are equal then the contents of the
 * memory pointed to by the user supplied data pointer is compared with the contents
 * of the memory pointed to by the data pointer in the list node and if they are
 * same then this node is deleted else the next node is inspected.
 *
 */
dlln_ptr delete_node_matching_data(dlln_ptr root, long double data, int data_type, long data_len, int *error_num);

/*
 * dlln_ptr delete_node(dlln_ptr root, dlln_ptr node_to_delete):
 * 
 * Function delete_node() deletes the list node whose pointer is passed in the
 * argument 'node_to_delete' and returns [new] root.
 *
 * In case, the list node to be deleted is the root itself then the list will have
 * a new root, so the user must update the root value with the value returned
 * by this function.
 *
 */
dlln_ptr delete_node(dlln_ptr root, dlln_ptr node_to_delete);

/*
 * dlln_ptr delete_all_nodes_from_list(dlln_ptr root):
 * 
 * Function delete_all_nodes_from_list() deletes all the nodes in the list and
 * returns NULL.
 *
 */
dlln_ptr delete_all_nodes_from_list(dlln_ptr root);

#endif

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I see you can add and delete nodes, but what about finding nodes, accessing the front or back of the list, and iterating over nodes? \$\endgroup\$
    – G. Sliepen
    Nov 21 '21 at 11:49
  • \$\begingroup\$ I am planning to implement them. \$\endgroup\$
    – Amit
    Nov 22 '21 at 12:32
1
\$\begingroup\$

get_error_string() needs to return const char*, since it returns pointers to string literals.

It should probably be implemented using switch. My preference is not to have a default case when dealing with enumerations (which the errors should be), so that I can have a compiler warning when I miss one of the values.

enum dll_error {
    NO_ERROR = 0,
    INVALID_DATA_TYPE = -1, 
    NO_MEMORY = -2,
    INVALID_DATA_LEN = -3,
    ROOT_IS_NULL = -4,
    MATCHING_NODE_NOT_FOUND = -5,
    DATA_IS_NULL = -6,
};
const char *get_error_string(enum dll_error error_num)
{
    switch (error_num) {
    case NO_ERROR: return "No error happened.";
    case INVALID_DATA_TYPE: return "Argument 'data_type' is neither SIMPLE_DATA_TYPE nor COMPLEX_DATA_TYPE.";
    case NO_MEMORY: return "No memory available.";
    case INVALID_DATA_LEN: return "Argument 'data_len' is <= 0.";
    case ROOT_IS_NULL: return "Argument 'root' is NULL.";
    case MATCHING_NODE_NOT_FOUND: return "No node found whose data matches the data given by the user.";
    case DATA_IS_NULL: return "Argument 'data' is NULL.";
    }
    return "Invalid error number given.";
}

I'm not a big fan of writing typedefs of pointer types like this:

typedef struct doubly_linked_list_node *dlln_ptr;

We lose the * in the code that shows we're dealing with a pointer type, and have to remember more context.


struct doubly_linked_list_node {
    int data_type;
    long data_len;
    long double data;
    struct doubly_linked_list_node *prev;
    struct doubly_linked_list_node *next;
};

data_type should probably be an enum type, rather than int.

Why is data_len a signed type? This causes quite a few warnings, as we convert to size_t when using with calloc() and memcpy(), for example.


When adding a node, we're very type-unsafe here:

    temp->data = (long long)(calloc(data_len, 1));

Firstly, casting a void* to long long may not be reversible (as long long may have a different range to intptr_t). Secondly, converting this to a long double may also lose precision.

Why is data not a suitable union type so that it can hold integer, floating or pointer types, without such risks?

Fixing that would probably eliminate the static analyser warning I get, where it's unable to track the lifetime of the pointer due to the type conversion.


What's the purpose of delete_this_node variable in delete_node_matching_data()? It seems to be always zero.

\$\endgroup\$
4
  • \$\begingroup\$ Thanks for the code review. data_len is signed type so that if user passes a negative value, then it can be caught. On my system (Ubuntu), I am using gcc 9.3.0. I don't get any warnings when I compile the program. There is no precision loss because long double is 16 bytes long and all pointers are 8 bytes. So, there is no precision loss because we are storing 8 bytes into 16 bytes. In linux kernel, they store pointers as unsigned long. Please see this: stackoverflow.com/questions/49675297/… \$\endgroup\$
    – Amit
    Nov 22 '21 at 12:43
  • 1
    \$\begingroup\$ You should get more warnings - make sure you have enabled all the ones that could be useful (I used gcc -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Wconversion -Wstrict-prototypes -fanalyzer, for example). \$\endgroup\$ Nov 22 '21 at 13:06
  • \$\begingroup\$ If you only ever target one specific platform, then you may well get away with the conversion problems (assuming that the integer value of the pointer fits into the mantissa of the floating-point type), but that unnecessarily limits portability when there are better solutions. And the question never mentioned that you only care about a single target platform. You shouldn't take Linux kernel sources to be a good guide for creating portable user programs - it has very different constraints. \$\endgroup\$ Nov 22 '21 at 13:09
  • \$\begingroup\$ Why is data not a suitable union type: If data is a union type, then how will I know in which field to copy data because I am not asking the user to specify the type of data (int, float, etc.)? Same problem is there when trying to delete a node (that matches the data) because I am not asking the user to specify the type of data (int, float, etc.), so I will not know which union field to compare. \$\endgroup\$
    – Amit
    Jan 1 at 6:53

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.