Generic Doubly-Linked-Lists C implementation

Question

I'm trying to build step by step a C library that will include some of the major Data Structures such as Linked Lists, Stacks, Binary Trees etc., mostly in order to practice my C programming skills and study new concepts. I have posted previously about my implementation of a doubly linked list, and it had a bunch of suggestions on how to improve the code (my last post). I have worked a lot in order to fix them and I would like to recieve a kind of follow up review to be clear that I handled those problems mentioned in the proper way. The major changes are:

1. Removed typedefs that hide pointers.
2. Removed repetetive documentation & improved clarity.
3. Fixed bug on deletion of head.
4. Added a file for testing.
5. Returning values to indicate success or failure of actions such as getting an element deleting etc.
6. Inconsistency in function definitions
7. Naming conventions

There are some issues that aren't solved yet, most significant is the lack of meaning to the "doubly" property of the list, but I will add that soon. Though I believe it is enough changes in order to get a feedback. Here's the updated code with the tests file:

DLList.h

/* 
    Implements doubly linked list.

    ----------          ----------           ---------- 
    |  HEAD  | <------> |  NODE  | <------>  |  TAIL  | 
    ----------          ----------           ---------- 
    The linked list is generic and may hold any kind of pointer (from the same type!) given a proper constructor function for that type.

    Created by: @BAxBI as part of General DataStructure library for C.
 
*/
#ifndef __DLLIST__H_
#define __DLLIST__H_
#include <stddef.h>


typedef enum {false = 0, true = 1} bool;


/* 
    Creates a new empty linked list 
    @param ctor Pointer to a constructor function for an element in the list. 
    @param dtor Pointer to a destructor function for an element in the list.
    @param compare Pointer to a comparison function between two elements in the list 
    @param print Pointer to a print function of an element in the list. 
    @return Pointer to an emty linked list 
*/
struct DLList *DLList_new(void * (*ctor)(void *),void (*dtor)(void *), int (*compare)(const void *, const void *), void (*print)(void *));

/* 
    Adds a node to the head of the list.
    @returns 1 if added successfuly 0 otherwise.
*/
int DLList_add(struct DLList *list, void * const item);

/*
    Deletes the first occurrence of an item in the list.
    @return 1 if deleted successfuly 0 otherwise.
*/
int DLList_delete(struct DLList *list, void * const item);

/* 
    Destroys a linked list and frees all the allocated memory. 
    @return 1 if destroyed successfuly 0 otherwise.
*/
int DLList_destroy(struct DLList *list);

/*
    Gets an element from the Linked List.
    @param success A pointer to int, will be set to 1 upon sucess 0 otherwise.
*/
void * DLList_get_item(const struct DLList *list, void * const element, int *success);

/*
    Gets the number of elements in the linked list.
*/
size_t DLList_No_items(const struct DLList * const list);

/*
    Prints the linked list (if given a print function to print a single element!)
*/
void DLList_print(const struct DLList * const list);


#endif

DDList.c

#include "DLList.h"
#include <stdlib.h>
#include <stdio.h>


typedef struct Node{
    struct Node *prev_node;
    struct Node *next_node;
    void * node_content;
}Node; 


struct DLList {
    Node *head; 
    Node *tail; 
    size_t NoElements;
    // Functions provided by the client.
    void * (*ctor)(void *);
    void (*dtor)(void *);
    int (*compare)(const void *, const void *);  
    void (*print)(void *);
};


struct DLList *DLList_new(void * (*ctor)(void *),void (*dtor)(void *), int (*compare)(const void *, const void *), void (*print)(void *)){
    struct DLList *new_dllist = malloc(sizeof(*new_dllist));
    if (!new_dllist){
        return NULL;
    }
    new_dllist->head = NULL;
    new_dllist->tail = NULL;
    new_dllist->NoElements = 0;

    new_dllist->ctor = ctor;
    new_dllist->dtor = dtor;
    new_dllist->compare = compare;
    new_dllist->print = print;

    return new_dllist;
}


int DLList_add(struct DLList *list, void * const item){
    if(!list->ctor) return false; // If constructor is not provided.
    Node *new_node = malloc(sizeof(*new_node));
    if (!new_node) return false;
    new_node->next_node = NULL;
    new_node->prev_node = NULL;
    new_node->node_content = list->ctor(item);

    /* Empty list*/
    if(!list->head){
        list->head = new_node;
        list->tail = new_node;
    }
    else {
        new_node->next_node = list->head;
        list->head->prev_node = new_node;
        list->head = new_node;
    }
    list->NoElements++;
    return true;
}

/* Deletes first occurence of a node in a linked list */
int DLList_delete(struct DLList *list, void * const item){
    Node *ptr = list->head;
    while(ptr != NULL){
        if(list->compare(ptr->node_content, item) == 0){
            /* First node to be deleted */
            if(!ptr->prev_node){
                list->head = ptr->next_node;
                if(ptr->next_node){
                    ptr->next_node->prev_node = NULL;
                }
            }
            else if(ptr->prev_node && ptr->next_node){
                ptr->next_node->prev_node = ptr->prev_node;
                ptr->prev_node->next_node = ptr->next_node;
            }
            else {
                ptr->prev_node->next_node = NULL;
            }
            if(list->dtor){
                list->dtor(ptr->node_content);
            }
            free(ptr);
            list->NoElements--;
            return true;
        }
        ptr = ptr->next_node;
    }
    return false;
}


int DLList_destroy(struct DLList * list){
    if(list){
    Node *ptr = list->head;
    while(ptr != NULL){
        Node *tmp = ptr;
        ptr = ptr->next_node;
        if(list->dtor){
            list->dtor(tmp->node_content);
        }
        free(tmp);
    }
    free(list);
    return true;
    }
    else{
        return true;
    }
}


void * DLList_get_item(const struct DLList *list, void * const element, int *success){
    Node *ptr = list->head;
    if(!list->head){
        printf("The list is empty!\n");
        *success = false;
    }
    while(ptr!=NULL){
        if(list->compare(ptr->node_content, element) == 0){
            *success = true;
            return ptr->node_content;
        }
        ptr = ptr->next_node;
    }
    *success = false;
    return NULL;
}

size_t DLList_No_items(const struct DLList *const list){
    return list->NoElements;
}


void DLList_print(const struct DLList * const list){
    if(!list->print) {
        printf("The linked list provided doesn't have print function\n");
        return;
    }
    if (!list->head) {
        printf("The list is empty!\n");
        return;
    }
    Node *ptr = list->head;
    while(ptr){
        list->print(ptr->node_content);
        if(ptr->next_node){
            printf(" <---> ");
        }
        else{
            printf(" ---> ");
        }
        ptr = ptr->next_node;
    }
    printf("NULL\n");
}

DLList_test.c

#include "DLList.h"
#include <stdio.h>
#include <unistd.h>
#include <setjmp.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>

#ifdef assert
#undef assert
#endif
#define assert(x) (result = result && (x))

//Static variables 
static int result;
static int expected_code;
static int should_exit;
static jmp_buf jump_env;
static int done;
static int num_tests;
static int tests_passed;

void test_start(char *name){
    num_tests++;
    result = 1;
    printf("-- Testing %s ...", name);
}

void test_end(){
    if (result) tests_passed++;
    printf("%s\n", result ? " success" : " fail");
}

void exit(int code){
    if (!done){
        assert(should_exit==1);
        assert(expected_code==code);
        longjmp(jump_env, 1);
    }
    else{
        _exit(code);
    }
}

/** Vector3d for testing **/
struct Vector3d{ 
    /* data */
    int x; int y; int z;
};

void *ctor(void *item){
    struct Vector3d *vector = malloc(sizeof(*vector)); 
    if(vector){
        memcpy(vector, item, sizeof(struct Vector3d));
    }
    return vector;
}

void dtor(void *item){
    free(item);
}

int compare(const void *item1, const void *item2){
    struct Vector3d *elem1 = (struct Vector3d *)item1;
    struct Vector3d *elem2 = (struct Vector3d *)item2;
    if(elem1 == NULL || elem2 == NULL){ 
        return INT_MIN;
    }
    float size1 = sqrt(elem1->x*elem1->x + elem1->y*elem1->y + elem1->z*elem1->z);
    float size2 = sqrt(elem2->x*elem2->x + elem2->y*elem2->y + elem2->z*elem2->z);

    return (size1 > size2) - (size1 < size2); 
}

void print_vector3d(void *item){
    printf("(%d, %d, %d)", ((struct Vector3d *)item)->x ,((struct Vector3d *)item)->y, ((struct Vector3d *)item)->z);
}


/*** Testing Cases ***/
// Testing creation of DLList
void DLList_new_t(){
    int f;
    struct DLList *my_list = DLList_new(ctor, dtor, compare, print_vector3d);
    test_start("Creation of DDList");
    should_exit = 1;
    if(my_list) f  = 1;
    assert(f == 1);    
    DLList_destroy(my_list);
    test_end();
}

void destroy_empty_list(){
    test_start("Destroy an empty list");
    should_exit = 1;
    assert(DLList_destroy(NULL) == true);
    test_end();
}

void DLList_add_elements(){
    struct DLList *my_list = DLList_new(ctor, dtor, compare, print_vector3d);
    struct Vector3d vector1, vector2;
    vector1.x = 5, vector1.y = 5, vector1.z = 5;
    vector2.x = 10, vector2.y = 10, vector2.z = 5;

    test_start("Add first node");
    should_exit = 1;
    assert(DLList_add(my_list, &vector1) == true);
    assert(DLList_add(my_list, &vector2) == true);
    DLList_destroy(my_list);
    test_end();
}

void DLList_delete_head(){
    struct DLList *my_list = DLList_new(ctor, dtor, compare, print_vector3d);
    struct Vector3d vector1 = {0}, vector2 = {0}, vector3 = {0};
    vector1.x = 5, vector1.y = 5, vector1.z = 5;
    vector2.x = 10, vector2.y = 10, vector2.z = 5;
    vector3.x = 10, vector3.y = 20, vector3.z = 5;

    test_start("Head deletion");
    should_exit = 0;
    DLList_add(my_list, &vector1);
    DLList_add(my_list, &vector2);
    DLList_add(my_list, &vector3);
    assert(DLList_delete(my_list, &vector3) == true);
    DLList_destroy(my_list);
    test_end();
}

void DLList_delete_tail(){
    struct DLList *my_list = DLList_new(ctor, dtor, compare, print_vector3d);
    struct Vector3d vector1, vector2, vector3;
    vector1.x = 5, vector1.y = 5, vector1.z = 5;
    vector2.x = 10, vector2.y = 10, vector2.z = 5;
    vector3.x = 10, vector2.y = 20, vector2.z = 5;

    test_start("Tail deletion");
    should_exit = 0;
    DLList_add(my_list, &vector1);
    DLList_add(my_list, &vector2);
    DLList_add(my_list, &vector3);
    assert(DLList_delete(my_list, &vector1) == true);
    DLList_destroy(my_list);
    test_end();

}
void DLList_delete_middle(){
    struct DLList *my_list = DLList_new(ctor, dtor, compare, print_vector3d);
    struct Vector3d vector1, vector2, vector3;
    vector1.x = 5, vector1.y = 5, vector1.z = 5;
    vector2.x = 10, vector2.y = 10, vector2.z = 5;
    vector3.x = 10, vector2.y = 20, vector2.z = 5;

    test_start("Node in the middle deletion");
    should_exit = 1;
    DLList_add(my_list, &vector1);
    DLList_add(my_list, &vector2);
    DLList_add(my_list, &vector3);
    assert(DLList_delete(my_list, &vector2) == true);
    DLList_destroy(my_list);
    test_end();
}

void DLList_delete_not_in_list(){
    struct DLList *my_list = DLList_new(ctor, dtor, compare, print_vector3d);
    struct Vector3d vector1, vector2, vector3;
    vector1.x = 5, vector1.y = 5, vector1.z = 5;
    vector2.x = 10, vector2.y = 10, vector2.z = 5;
    vector3.x = 10, vector2.y = 120, vector2.z = 5;

    test_start("Node not in the list deletion");
    should_exit = 1;
    DLList_add(my_list, &vector1);
    DLList_add(my_list, &vector2);
    assert(DLList_delete(my_list, &vector3) == false);
    DLList_destroy(my_list);
    test_end();
}

void DLList_delete_not_matching_obj(){
    struct DLList *my_list = DLList_new(ctor, dtor, compare, print_vector3d);
    struct Vector3d vector1, vector2;
    vector1.x = 5, vector1.y = 5, vector1.z = 5;
    vector2.x = 10, vector2.y = 10, vector2.z = 5;

    test_start("Delete not matching object");
    should_exit = 1;
    DLList_add(my_list, &vector1);
    DLList_add(my_list, &vector2);
    int variable = 5;
    assert(DLList_delete(my_list, &variable) == false);
    DLList_destroy(my_list);
    test_end();
}

void DLList_add_not_matching_obj(){
    struct DLList *my_list = DLList_new(ctor, dtor, compare, print_vector3d);
    int num = 5;
    test_start("Add not matching object");
    should_exit = 1;
    assert(DLList_add(my_list, &num) == false);
    DLList_destroy(my_list);
    test_end();
}


int main(void){
    num_tests = 0;
    tests_passed = 0;
    done = 0;

    // Running the tests
    printf("=============================================");
    printf("\n--- DLList Tests --- \n");
    DLList_new_t();
    destroy_empty_list();
    DLList_add_elements();
    DLList_delete_head();
    DLList_delete_tail();
    DLList_delete_middle();
    DLList_delete_not_in_list();

    printf("Total tests passed: %d\n", tests_passed);
    printf("============================================\n");
    done = 1;
    return !(tests_passed == num_tests);

    return 0;
}

Answer 1

Much improvement over early question.

Object pointer v. function pointers

Goal needs modifications: "The linked list is generic and may hold any kind of pointer ..." --> "The linked list is generic and may hold any kind of object pointer ...".

Functions pointers may be wider than void pointers and so lose information when converted to void *.

void * is a useful universal object pointer.

C lacks a true universal pointer.

Why double linked list?

So far, no usage of using the link-list in the reverse direction.

Use standard bool

Rather than typedef enum {false = 0, true = 1} bool;, use bool from <stdbool.h>

const parameters not needed in function declarations

It is just noise.

// void * DLList_get_item(const struct DLList *list, void * const element, int *success);
void * DLList_get_item(const struct DLList *list, void * element, int *success);

bool functions

For functions that return true/false, use bool

// int DLList_add(struct DLList *list, void * const item){
bool DLList_add(struct DLList *list, void * const item){
  ... return false;
  ...
  return true;
}

Error message vs. error code

Rather than print an error message, drop it. Function already conveys the error via *success.

void * DLList_get_item(const struct DLList *list, void * const element, int *success){
  Node *ptr = list->head;
  if(!list->head){
    // printf("The list is empty!\n");
    *success = false;
}
...

If still wanting an error message, use stderr.

    // printf("The list is empty!\n");
    fprintf(stderr, "The list is empty!\n");

---

Next: Consider an apply function

This applies the passed in function to each list node data. Only stopping early when the function returns non-zero.

int DLList_apply(const struct DLList * list,
    int (*f)(void *state, void *node_content),
    void *state) {
  // Pseudo code
  for each item in the linked list
    int result = f(state, item->node_content);
    if (result != 0) return result;
  }
  return 0;
}

This can serve as the basis for a replacement for DLList_print() which only does a particular print.

---

Test code: Avoid casting away const

// int compare(const void *item1, const void *item2){
  struct Vector3d *elem1 = (struct Vector3d *)item1;
  struct Vector3d *elem2 = (struct Vector3d *)item2;

int compare(const void *item1, const void *item2){
  const struct Vector3d *elem1 = item1;
  const struct Vector3d *elem2 = item2;

Test code: Save double to double

Unclear why code saves a double to float

// float size1 = sqrt(...
double size1 = sqrt(...
// OR
//Preform a `float` calculation
float size1 = sqrtf(...

Test code: FP math not needed

Code risk int overflow. square root not needed.

Alternate;

long long size1 = 1LL*elem1->x*elem1->x + 1LL*elem1->y*elem1->y + elem1->z*elem1->z;
long long size2 = 1LL*elem2->x*elem2->x + 1LL*elem2->y*elem2->y + 1LL*elem2->z*elem2->z;

Answer 2

Don't repeat yourself:

int DLList_destroy(struct DLList * list){
    if(list){
    Node *ptr = list->head;
    while(ptr != NULL){
        Node *tmp = ptr;
        ptr = ptr->next_node;
        if(list->dtor){
            list->dtor(tmp->node_content);
        }
        free(tmp);
    }
    free(list);
//    return true;
    }
//    else{
//        return true;
//    }
    return true;
}

That being said, the formatting is very misleading in this specific function.

Be consistent:

if(list) /* You have this. */
while(ptr != NULL) /* And then this. */

Stick with one style.

if (!new_node) return false;

/* Why the inconsistency here? */
if(!list->head){
        list->head = new_node;
        list->tail = new_node;
    }

/* The above can be rewritten as: 
 * list->head = list->tail = new_node;
 */

Same with braces.