Huffman Coding library implemented in C

I have written a small library for C that implements the Huffman coding algorithm as outlined in David Huffman’s paper on Minimum-Redundancy Codes, and a small test program to implement it. The library consists of two primary functions, huffman_encode() and huffman_decode(), and a series of helper functions. The program also uses a linked list library which I have written and included below although I am not looking for a review of the linked list in this question. Edit: The linked list library has been fully removed from the latest version of the code

Here is what I would like critiqued:

• Current runtime memory usage is quite high (my test program allocates >60kb), how can I reduce on this? Are there redundancies I can get rid of or can I improve my implementation of the algorithm? I’m fairly sure I can ditch the linked list…
• What are some ways I can reduce the header size to improve the compression ratios?
• I feel like my code is over-engineered, how could I simplify things without losing performance?
• How is my documentation/commenting (Particularly in huffman.c)? I know that the code is quite obfuscated in places but I was wondering if it made the library easy enough to understand
• Are there any general performance chokes that can be removed?
• Would there be any major issues porting my code to other systems? I have never used bit level operations before and I’ve heard that endianness can be a problem when using them
• Are there any bugs you can find? I have tested it extensively but there’s always the chance that I’ve missed something. Are there any input strings that can break my code?

I compiled this code on the latest version of Debian Linux (4.9.88-1+deb9u1) using:

clang *.c -o huffman -std=c11 -Wall -Wextra -Wpedantic -O2

huffman.h

#ifndef HUFFMAN_H
#define HUFFMAN_H

/* Header files */

#include <stdbool.h>
#include <stdint.h>

/* Return values */

#define EXIT_SUCCESS 0
#define MEM_ERROR 1
#define INPUT_ERROR 2

/* Node identifiers, might change to enumeration */

#define INTERNAL_NODE 0
#define CHARACTER_NODE 1

/* Size of the header with no characters stored */

#define HEADER_BASE_SIZE 10

/* Huffman Tree node */

typedef struct huffman_node_t {
    size_t freq;
    struct huffman_node_t * child[2];
    char c;
} huffman_node_t;

/* User Functions */

int huffman_decode(uint8_t * input, char ** output);
int huffman_encode(char * input, uint8_t ** output);

/* Helper Functions */

/* Encoding */

int huff_tree_from_freq(size_t * freq, huffman_node_t ** head_node);
int node_compare(const void * first_node, const void * second_node);
int node_compare_priority(const void * first_node, const void * second_node);
void code_array_from_tree(huffman_node_t * node, uint8_t huffman_array[256][2], uint8_t bits_set);

/* Decoding */

char is_char_node(uint8_t byte, uint8_t bits_left, huffman_node_t * node);
int huff_tree_from_codes(huffman_node_t ** head_node, uint8_t huffman_array[256][2]);
int add_char_to_tree(huffman_node_t * node, char c, uint8_t byte, uint8_t bits_left, uint8_t curr_bit);

/* Universal */

huffman_node_t * create_char_node(char c, size_t freq);
huffman_node_t * create_internal_node(huffman_node_t * first_child, huffman_node_t * second_child);
void destroy_huff_tree(huffman_node_t * node);
void node_print(const void * element);

#endif

huffman.c

/* 
 *  Filename:   huffman.c
 *  Author:     Jess Turner
 *  Date:       17/07/18
 *  Licence:    GNU GPL V3
 *
 *  Encodes and decodes a byte stream using huffman coding
 *
 *  Return/exit codes:
 *      EXIT_SUCCESS    - No error
 *      MEM_ERROR       - Memory allocation error
 *      INPUT_ERROR     - No input given
 *
 *  User Functions:
 *      - huffman_encode()      - Encodes a string using Huffman coding
 *      - huffman_decode()      - Decodes a Huffman encoded string 
 *
 *  Helper Functions:
 *
 *      Encoding:
 *          - huff_tree_from_freq()     - Generate a Huffman tree from a frequency analysis
 *          - code_array_from_tree()    - Generate a "code array" from the huffman tree, used for fast encoding
 *          - node_compare()            - Calculate the difference in frequency between two nodes
 *          - node_compare_priority()   - Modified version of node_compare() which prioritises character nodes over internal nodes when frequencies are equal
 *
 *      Decoding:
 *          - huff_tree_from_codes()    - Generates a Huffman tree from a stored "code array"
 *          - is_char_node()            - Determine if a given byte is a character node in a Huffman tree
 *          - add_char_to_tree()        - Adds a character and its encoding byte to a Huffman tree
 *
 *      Universal:
 *          - create_char_node()        - Generate a character node
 *          - create_internal_node()    - Generate an internal node
 *          - destroy_huff_tree()       - Traverses the tree and frees all memory associated with it
 *          - node_print()              - Debugging function used to print information about a node, can be passed to dlist_operate() to print all nodes in the priority queue
 *
 *  Data structures:
 *
 *      Code array:
 *          - Fast way to encode data using the information generated from a Huffman tree and an easy way to store a representation of the tree
 *          - 2D array that represents each byte to be encoded and how it is encoded allowing for O(1) time to determine how a given byte is encoded
 *          - Position in the array (i.e. code_array[0-255]) represents the byte to be encoded
 *          - The first element at each position (i.e. code_array[byte][0]) represents the way the byte is encoded
 *          - The seconde element at each position (i.e. code_array[byte][1]) represents the number of bits that encode the byte
 *
 *      Huffman tree:
 *          - Binary tree that operates much like any other Huffman tree
 *          - Contains two types of nodes, internal nodes and character nodes
 *          - Every node contains either the frequency of the character it represents or the combined frequencies of its child nodes
 *
 *  Encoded data format:
 *
 *      - Header
 *          - Compressed string length (uint32_t stored as 4 uint8_t's)
 *          - Decompressed string length (uint32_t stored as 4 uint8_t's)
 *          - Header size (uint16_t stored as 2 uint8_t's)
 *          - Huffman tree stored as a "code array" (3 bytes per character: encoded character, encoding byte, number of bits set)
 *      - Encoded data
 *
 *  The future:
 *      - (Possibly) Modify decoding algorithm to use a hash table lookup rather than tree recursion, might be faster
 *      - Find way to reduce header size, possibly using the huffman algorithm twice to encode the header?
 *      - Look into using a terminator byte instead of storing length, might reduce total size
 *      - Combine with duplicate string removal and make full LZW compression
 *
 */

#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include "dlist_library.h"
#include "huffman.h"

int huff_tree_from_freq(size_t * freq, huffman_node_t ** head_node) {
    dlist_t * node_queue;
    huffman_node_t * char_node_list[256] = { NULL };
    huffman_node_t * first_temp_node, * second_temp_node, * internal_node;
    size_t node_count = 0;

    if(!(node_queue = dlist_init(sizeof(huffman_node_t *))))
        return MEM_ERROR;

    for(uint16_t i = 0; i < 256; i++)
        if(freq[i] && !(char_node_list[node_count++] = create_char_node(i - 128, freq[i])))
            return MEM_ERROR;

    for(size_t i = 0; i < node_count; i++)
        if(dlist_push(&char_node_list[i], node_queue) != LIST_OK)
            return MEM_ERROR;

    dlist_sort(&node_compare, node_queue);

    while(node_count-- > 1) {
        dlist_pop(&first_temp_node, node_queue);
        dlist_pop(&second_temp_node, node_queue);

        if(!(internal_node = create_internal_node(first_temp_node, second_temp_node)))
            return MEM_ERROR;

        if(dlist_push(&internal_node, node_queue) != LIST_OK)
            return MEM_ERROR;

        dlist_sort(&node_compare_priority, node_queue);
    }

    dlist_pop(head_node, node_queue);
    dlist_destroy(node_queue);

    return EXIT_SUCCESS;
}

void destroy_huff_tree(huffman_node_t * node)
{
    if(node->child[0]) {
        destroy_huff_tree(node->child[0]);
        destroy_huff_tree(node->child[1]);
    }

    free(node);

    return;
}

int huffman_encode(char * input, uint8_t ** output)
{
    size_t freq[256]        = { 0 };
    uint16_t header_size    = HEADER_BASE_SIZE;
    uint32_t length         = strlen(input);

    for(size_t i = 0; i < length; i++)
        freq[input[i] + 128]++;

    for(uint16_t i = 0; i < 256; i++)
        if(freq[i])
            header_size += 3;

    /* Handle strings with either one unique byte or zero bytes */

    if(header_size == HEADER_BASE_SIZE) {
        return INPUT_ERROR;
    } else if(header_size == HEADER_BASE_SIZE + 3) {
        for(uint16_t i = 0; i < 256; i++)
            if(freq[i])
                ++freq[i > 0 ? i - 1 : i + 1];
            
        header_size += 3;
    }

    huffman_node_t * head_node = NULL;

    if(huff_tree_from_freq(freq, &head_node) != EXIT_SUCCESS)
        return MEM_ERROR;

    uint8_t codes[256][2] = {{ 0 }};

    code_array_from_tree(head_node, codes, 0);
    destroy_huff_tree(head_node);

    size_t encoded_bit_len = 0;

    /* Use the generated code array to calculate the byte length of the output */

    for(size_t i = 0; i < length; i++)
        encoded_bit_len += codes[input[i] + 128][1];

    size_t encoded_byte_len = (encoded_bit_len >> 3) + !!(encoded_bit_len & 0x7); /* Calculate bit length / 8, add one if there's a remainder */

    uint8_t * str_out = NULL;

    if(!(str_out = calloc(encoded_byte_len + header_size + 1, sizeof(uint8_t))))
        return MEM_ERROR;

    /* Write header information */

    /* Bit level hack to store uint32_t's and uint16_t's in an array of uint8_t's */

    str_out[0] = (uint8_t)length;
    str_out[1] = (uint8_t)(length >> 0x8);
    str_out[2] = (uint8_t)(length >> 0x10);
    str_out[3] = (uint8_t)(length >> 0x18); 

    str_out[4] = (uint8_t)encoded_byte_len;
    str_out[5] = (uint8_t)(encoded_byte_len >> 0x8);
    str_out[6] = (uint8_t)(encoded_byte_len >> 0x10);
    str_out[7] = (uint8_t)(encoded_byte_len >> 0x18);

    str_out[8] = (uint8_t)header_size;
    str_out[9] = (uint8_t)(header_size >> 0x8);

    size_t byte_pos = HEADER_BASE_SIZE;

    /* Store the encoding information */

    for(uint16_t i = 0; i < 256; i++) {
        if(codes[i][1]) {
            str_out[byte_pos++] = i;
            str_out[byte_pos++] = codes[i][0];
            str_out[byte_pos++] = codes[i][1];
        }
    }

    /* Encode output stream */

    for(size_t i = 0, bit_pos = 0; i < length; i++) {
        for(size_t j = 0; j < codes[input[i] + 128][1]; j++) {
            str_out[byte_pos] |= ((codes[input[i] + 128][0] >> j) & 0x1) << bit_pos;

            if(++bit_pos == 8) {
                bit_pos = 0;
                byte_pos++;
            }
        }
    }

    *output = str_out;

    return EXIT_SUCCESS;
}

int huffman_decode(uint8_t * input, char ** output)
{
    size_t byte_pos         = 0;
    uint8_t bit_pos         = 0;
    uint8_t min_length      = 8;
    uint8_t codes[256][2]   = {{ 0 }};
    uint32_t char_count     = 0;

    /* Extract header information and build code array */

    uint32_t length = * (uint32_t *) &input[0];
    uint16_t header_size = * (uint16_t *) &input[8];

    for(byte_pos = HEADER_BASE_SIZE; byte_pos < header_size; byte_pos += 3) {
        codes[input[byte_pos]][0] = input[byte_pos + 1];
        codes[input[byte_pos]][1] = input[byte_pos + 2];

        if(codes[input[byte_pos]][1] < min_length)
            min_length = codes[input[byte_pos]][1]; /* By knowing the smallest encoding length we can speed up the recursive decoding */
    }

    char * str_out = NULL;

    if(!(str_out = calloc(length + 1, sizeof(char))))
        return MEM_ERROR;

    huffman_node_t * head_node = NULL;

    if(huff_tree_from_codes(&head_node, codes) == MEM_ERROR)
        return MEM_ERROR;

    /* Decode input stream */

    while(char_count < length) {
        for(uint8_t i = 0, byte = 0; i < 8; i++) {
            byte |= ((input[byte_pos] >> bit_pos) & 0x1) << i;
            
            if(++bit_pos == 8) {
                bit_pos = 0;
                byte_pos++;
            }

            if(i + 1 >= min_length && (str_out[char_count] = is_char_node(byte, i + 1, head_node)) != '') {
                char_count++;
                break;
            }
        }
    }

    destroy_huff_tree(head_node);

    str_out[char_count] = '';
    *output = str_out;

    return EXIT_SUCCESS;
}

char is_char_node(uint8_t byte, uint8_t bits_left, huffman_node_t * node)
{
    static uint8_t bit_pos = 0;

    return (!bits_left) ?
            (bit_pos = 0, !node->child[0]) ?
                node->c :
                '' :
            is_char_node(byte, bits_left - 1, node->child[((byte >> bit_pos++) & 0x1)]); /* This return is the best and worst line of code I've ever written */
}

void code_array_from_tree(huffman_node_t * node, uint8_t huffman_array[256][2], uint8_t bits_set)
{
    static uint8_t byte = '';

    if(node->child[0]) {
        byte &= ~(0x1 << bits_set);
        code_array_from_tree(node->child[0], huffman_array, bits_set + 1);
        byte |= 0x1 << bits_set;
        code_array_from_tree(node->child[1], huffman_array, bits_set + 1);
    } else {
        huffman_array[node->c + 128][0] = byte;
        huffman_array[node->c + 128][1] = bits_set;
    }
}

int huff_tree_from_codes(huffman_node_t ** head_node, uint8_t huffman_array[256][2])
{
    if(!(*head_node = malloc(sizeof(huffman_node_t))))
        return MEM_ERROR;

    (*head_node)->child[0] = NULL;
    (*head_node)->child[1] = NULL;

    for(uint16_t i = 0; i < 256; i++)
        if(huffman_array[i][1])
            if(add_char_to_tree(*head_node, (char)(i - 128), huffman_array[i][0], huffman_array[i][1] - 1, 0) != EXIT_SUCCESS)
                return MEM_ERROR;

    return EXIT_SUCCESS;
}

int add_char_to_tree(huffman_node_t * node, char c, uint8_t byte, uint8_t bits_left, uint8_t curr_bit)
{
    const uint8_t branch = (byte >> curr_bit) & 0x1;

    if(!node->child[branch]) {
        if(!(node->child[branch] = malloc(sizeof(huffman_node_t))))
            return MEM_ERROR;
    
        node->child[branch]->child[0] = NULL;
        node->child[branch]->child[1] = NULL;
    }

    if(bits_left) {
        return add_char_to_tree(node->child[branch], c, byte, bits_left - 1, curr_bit + 1);
    } else {
        node->child[branch]->c = c;
        return EXIT_SUCCESS;
    }
}

huffman_node_t * create_char_node(char c, size_t freq) {
    huffman_node_t * node;

    if(!(node = malloc(sizeof(huffman_node_t))))
        return NULL;

    node->freq = freq;
    node->child[0] = NULL;
    node->child[1] = NULL;
    node->c = c;

    return node;
}

huffman_node_t * create_internal_node(huffman_node_t * first_child, huffman_node_t * second_child) {
    huffman_node_t * node;

    if(!(node = malloc(sizeof(huffman_node_t))))
        return NULL;

    node->freq = first_child->freq + second_child->freq;
    node->child[0] = first_child;
    node->child[1] = second_child;

    return node;
}

int node_compare_priority(const void * first_node, const void * second_node) {
    return !((*(huffman_node_t **)first_node)->freq - (*(huffman_node_t **)second_node)->freq) ?
                0 :
                (*(huffman_node_t **)second_node)->child[0] ?
                    -1 :
                    0;
}

int node_compare(const void * first_node, const void * second_node) {
    return (*(huffman_node_t **)first_node)->freq - (*(huffman_node_t **)second_node)->freq;
}

void node_print(const void * element)
{
    printf("Frequency: %zun", (*(huffman_node_t **)(element))->freq);

    if((*(huffman_node_t **)(element))->child[0])
        printf("Node has children...n");
    else
        printf("Node has no children, character is "%c"n", (*(huffman_node_t **)(element))->c);
}

main.c

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

int main()
{
    uint8_t * encoded = NULL;
    char * decoded = NULL;
    char * test_strings[] = {
                "test string",
                "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890!"£$%^&*()-=_+\|,./<>?[]{}'#@~`¬n",
                "test",
                "Hello, world!",
                "This is a test string",
                "My name is Jeff",
                "Test",
                "tteesstt",
                "test",
                "ab",
                "Ω≈ç√∫˜µ≤≥÷",
                "ЁЂЃЄЅІЇЈЉЊЋЌЍЎЏАБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯабвгдежзийклмнопрстуфхцчшщъыьэюя",
                "If you're reading this, you've been in a coma for almost 20 years now. We're trying a new technique. We don't know where this message will end up in your dream, but we hope it works. Please wake up, we miss you.",
                "a",
                "aaaaaaaaaaaaaa",
                "",
                "Powerلُلُصّبُلُلصّبُررً ॣ ॣh ॣ ॣ冗",
                "Hello, world! This is a test string test string If you're reading this, you've been in a coma for almost 20 years now. We're trying a new technique. We don't know where this message will end up in your dream, but we hope it works. Please wake up, we miss you. tteesstt"
            };

    for(size_t i = 0; i < sizeof(test_strings) / sizeof(char *); i++) {
        printf("nEncoding string %zu...", i);
        fflush(stdout);

        if(huffman_encode(test_strings[i], &encoded) != EXIT_SUCCESS) {
            fprintf(stderr, "nError: Failed to encode string "%s"!n", test_strings[i]);
            continue;
        }

        printf("Done!nAttempting to decode...");
        fflush(stdout);

        if(huffman_decode(encoded, &decoded) != EXIT_SUCCESS) {
            fprintf(stderr, "nError: Failed to decode string!nEncoded string was "%s"n", test_strings[i]);
            free(encoded);
            continue;
        }

        printf("Done!nValidating...");
        
        if(!strcmp(test_strings[i], decoded))
            printf("Success!n");
        else
            printf("Failed! Got "%s"!n", decoded);

        free(decoded);
        free(encoded);
    }

    return 0;
}

Note: I am not looking for a review of any code below here in this question, I am saving this section for another review but I’m including it here because the rest of the code relies on it.

Edit: Since I wrote this code I was able to refactor it to completely remove this section

dlist_library.h

#ifndef DLIST_H
#define DLIST_H

#include <stdlib.h>                                                     /* Needed for size_t */

/* Return values */

#define LIST_OK 0
#define MEM_ERROR 1                                                     /* Memory allocation error */
#define SIZE_ERROR 2                                                    /* list dimension error */
#define INDEX_ERROR 3                                                   /* No data at given index */

/* List element data structure */

typedef struct list_element_t
{
    void * data;                                                        /* Contains the data stored at this node */
    struct list_element_t * next;                                       /* Contains the pointer to the next element, or NULL if it's the tail node */
} dlist_element_t;

/* List master data structure */

typedef struct
{
    dlist_element_t *   head;                                           /* Pointer to the head of the list */
    dlist_element_t *   tail;                                           /* Pointer to the tail of the list */
    size_t              data_width;                                     /* The size of each element in the list */
    int                 status;
} dlist_t;

/* User Functions */

dlist_element_t * dlist_search(void const * const data, int (*compare)(const void * first_element, const void * second_element), dlist_t * list); /* Search the list for an occurance of a given data value using a user defined comparison function */
dlist_t * dlist_init(size_t data_size);                                                                     /* Initialise the list data structure */
int dlist_insert_before(void const * const data, dlist_element_t * element, dlist_t * list);                /* Insert an element into the list at the position before a specified element */
int dlist_insert_after(void const * const data, dlist_element_t * element, dlist_t * list);                 /* Insert an element into the list at the position after a specified element */
int dlist_peek(void * const data, dlist_t * list);                                                          /* Check the contents of the element at the end of the list without popping the list */
int dlist_pop(void * const data, dlist_t * list);                                                           /* Pop an element from the front of the list, deals with cleanup when the head node is empty */
int dlist_push(void const * const data, dlist_t * list);                                                    /* Push an element to the back of the list, creates a new block when tail node is full */
int dlist_remove(dlist_element_t * element, dlist_t * list);                                                /* Remove an element from the list and connect the two elements next to it */
void dlist_destroy(dlist_t * list);                                                                         /* Destroy the list data structure and any associated nodes */
void dlist_operate(void(*operation)(const void * element), dlist_t * list);                                 /* Perform a user defined action on every single element stored in the list */
void dlist_sort(int (*compare)(const void * first_element, const void * second_element), dlist_t * list);   /* Sort all elements in the list using a merge sort */

/* Internal Functions */

dlist_element_t * dlist_merge_sorted(int (*compare)(const void * first_element, const void * second_element), dlist_element_t * head, dlist_element_t * second_head);
void dlist_sort_split(dlist_element_t * source, dlist_element_t ** front, dlist_element_t ** back);
void dlist_sort_internal(int (*compare)(const void * first_element, const void * second_element), dlist_element_t ** head);

#endif

dlist_library.c

/* 
 * Filename:    dlist_library.c
 * Author:      Jess Turner
 * Date:        10/08/18
 * Licence:     GNU GPL V3
 *
 * Library for a generic, dynamically allocated singly linked list
 *
 * Return/exit codes:
 *      LIST_OK         - No error
 *      SIZE_ERROR      - list size error (invalid block size or number of datas)
 *      MEM_ERROR       - Memory allocation error
 *      INDEX_ERROR     - Couldn't pop data from the list
 *
 * All functions returning pointers will return NULL on memory allocation faliure, else they will specify an error in list->status for the user to handle
 *
 * Todo:
 *      - Add secure versions of dlist_destroy(), dlist_pop(), and dlist_remove() to overwrite memory blocks that are no longer in use
 *      - Add a parameter to dlist_destroy() and dlist_remove() containing a function pointer detailing how to delete the data stored in each node
 */

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

dlist_t * dlist_init(size_t data_width)
{
    dlist_t * list;

    if(!(list = malloc(sizeof(dlist_t))))
        return NULL;

    list->tail          = NULL;
    list->head          = NULL;
    list->data_width    = data_width;
    list->status        = LIST_OK;

    return list;
}

void dlist_destroy(dlist_t * list)
{
    if(list == NULL)
        return;

    while(list->head) {
        dlist_element_t * temp = list->head->next;
        free(list->head);
        list->head = temp;
    }
    
    list->status        = 0;
    list->data_width    = 0;
    list->tail          = NULL;

    free(list);
}

int dlist_push(void const * const data, dlist_t * list)
{
    dlist_element_t * new_element;

    if(!(new_element = malloc(sizeof(dlist_element_t))) || !(new_element->data = malloc(list->data_width))) {
        if(new_element)
            free(new_element);
        return list->status = MEM_ERROR;
    }

    memcpy(new_element->data, data, list->data_width);

    if(list->head == NULL)
        list->head = new_element;
    else
        list->tail->next = new_element;

    list->tail = new_element;
    list->tail->next = NULL;

    return list->status = LIST_OK;
}

int dlist_pop(void * const data, dlist_t * list)
{
    if(list->head == NULL)
        return list->status = INDEX_ERROR;

    memcpy(data, list->head->data, list->data_width);

    free(list->head->data);
    dlist_element_t * temp = list->head;
    list->head = list->head->next;
    free(temp);

    return list->status = LIST_OK;
}

int dlist_remove(dlist_element_t * element, dlist_t * list)
{
    if(element == NULL || list->head == NULL)
        return list->status = INDEX_ERROR;

    if(list->head == element) {
        list->head = list->head->next;
        return list->status = LIST_OK;
    }

    dlist_element_t * prev = NULL;
    dlist_element_t * curr = list->head;

    while(curr != element) {
        prev = curr;
        curr = curr->next;

        if(curr == NULL)
            return list->status = INDEX_ERROR;
    }

    prev->next = curr->next;

    return list->status = LIST_OK;
}

int dlist_insert_after(void const * const data, dlist_element_t * element, dlist_t * list)
{
    if(list->head == NULL)
        return dlist_push(data, list);

    dlist_element_t * new_element;

    if(!(new_element = malloc(sizeof(dlist_element_t))) || !(new_element->data = malloc(list->data_width))) {
        if(new_element)
            free(new_element);
        return list->status = MEM_ERROR;
    }

    memcpy(new_element->data, data, list->data_width);

    new_element->next = element->next;
    element->next = new_element;

    if(element == list->tail)
        list->tail = new_element;

    return list->status = LIST_OK;
}

int dlist_insert_before(void const * const data, dlist_element_t * element, dlist_t * list)
{
    if(list->head == NULL)
        return dlist_push(data, list);

    dlist_element_t * prev = list->head;
    dlist_element_t * curr = prev->next;

    while(curr != NULL && curr != element) {
        curr = curr->next;
        prev = prev->next;
    }

    if(curr == NULL)
        return list->status = INDEX_ERROR;

    dlist_element_t * new_element;

    if(!(new_element = malloc(sizeof(dlist_element_t))) || !(new_element->data = malloc(list->data_width))) {
        if(new_element)
            free(new_element);
        return list->status = MEM_ERROR;
    }

    memcpy(new_element->data, data, list->data_width);

    if(curr == list->head) {
        new_element->next = curr;
        list->head = new_element;
    } else {
        new_element->next = prev->next;
        prev->next = new_element;
    }

    return list->status = LIST_OK;
}

dlist_element_t * dlist_search(void const * const data, int (*compare)(const void * first_element, const void * second_element), dlist_t * list)
{
    dlist_element_t * curr;

    for(curr = list->head; curr != NULL; curr = curr->next)
        if(!(*compare)(curr->data, data))
            return curr;

    list->status = INDEX_ERROR;

    return NULL;
}

int dlist_peek(void * const data, dlist_t * list)
{
    if(list->head == NULL)
        return list->status = INDEX_ERROR;

    memcpy(data, list->head->data, list->data_width);

    return list->status = LIST_OK;
}

void dlist_sort_split(dlist_element_t * source, dlist_element_t ** front, dlist_element_t ** back)
{
    dlist_element_t * slow = source;
    dlist_element_t * fast = source->next;
 
    while(fast != NULL) {
        fast = fast->next;
        if(fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }

    *front = source;
    *back = slow->next;
    slow->next = NULL;
}

dlist_element_t * dlist_merge_sorted(int (*compare)(const void * first_element, const void * second_element), dlist_element_t * head, dlist_element_t * second_head)
{
    dlist_element_t * result = NULL;

    if(head == NULL)
        return second_head;
    else if(second_head == NULL)
        return head;
     
    if(compare(head->data, second_head->data) < 0) {
        result = head;
        result->next = dlist_merge_sorted(compare, head->next, second_head);
    } else {
        result = second_head;
        result->next = dlist_merge_sorted(compare, head, second_head->next);
    }

    return result;
}

void dlist_sort_internal(int (*compare)(const void * first_element, const void * second_element), dlist_element_t ** head)
{
    dlist_element_t * back = NULL;
    dlist_element_t * front = NULL;

    if(*head == NULL || (*head)->next == NULL)
        return;

    dlist_sort_split(*head, &front, &back);

    dlist_sort_internal(compare, &front);
    dlist_sort_internal(compare, &back);

    *head = dlist_merge_sorted(compare, front, back);
}

void dlist_sort(int (*compare)(const void * first_element, const void * second_element), dlist_t * list)
{
    if(list->head == NULL)
        list->status = INDEX_ERROR;

    dlist_sort_internal(compare, &list->head);

    for(dlist_element_t * curr = list->head; curr != NULL; curr = curr->next)
        if(curr->next == NULL)
            list->tail = curr;
}

void dlist_operate(void(*operation)(const void * element), dlist_t * list)
{
    for(dlist_element_t * curr = list->head; curr != NULL; curr = curr->next)
        operation(curr->data);
}