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
