I have revised the implementation I originally posted here. Thank you all who responded; I took your comments to heart. Please let me know if you have any additional feedback.
Here are some notes to make:
- I implemented all changes suggested by @vnp
- I implemented all by @chux, except for the "apply" function and the sample improvements (due to the improvements being fixed by changes suggested by @vnp)
- I implemented points (1), (5), (7) and (8) by Deduplicator
I am left with a couple questions, notably:
- Is it necessary to always include a header file even if the prototypes are not necessary? I noticed that in my case, it helped me catch a compile error because I did not originally forward declare the struct.
- It seems to me that it's possible to have undefined behavior even when using FAMs in a standard-compliant format ... though this likely wouldn't occur in my case due padding (on x86-64) not being needed within my structure
- Is it bad practice to use an
_
at the end of internal functions (I even used this to overload a function name)?
I do not think there should be any bugs this time (hopefully) as I've taken care to modularize it heavily (which was the key advice in the other post -- due to lots of code repeat). Please let me know if you spot any. As before, I'm open to any and all advice -- whether it is general style, formatting or correctness.
I would appreciate any advice on how to unit test my data structures, as I am inexperienced when it comes to it, and might've caught the bug myself if I'd known how to in a structured format.
doubly-linked-list.h
#ifndef DOUBLY_LINKED_LIST
#define DOUBLY_LINKED_LIST
#include <stdbool.h>
struct dl_node_manager;
// Initialize the linked list.
void
dl_init(struct dl_node_manager *);
// Destroy the linked list.
void
dl_destoy(struct dl_node_manager *);
// Returns true if linked list is empty.
bool
dl_empty(struct dl_node_manager *);
// Insert node at head with value of @(const char *).
// May fail on allocation error.
bool
dl_insert_head(struct dl_node_manager *, const char *);
// Insert node at tail with value of @(const char *).
// May fail on allocation error.
bool
dl_insert_tail(struct dl_node_manager *, const char *);
// Return true if node with value of @(const char *) found.
// Will fail if node not found.
bool
dl_contains(struct dl_node_manager *, const char *);
// Remove node at head of linked list.
// Will fail if no nodes exist.
bool
dl_remove_head(struct dl_node_manager *);
// Remove node at tail of linked list.
// Will fail if no nodes exist.
bool
dl_remove_tail(struct dl_node_manager *);
// Remove first node found when traversing from head with value
// of @(const char*).
// Will fail if no nodes exist.
bool
dl_remove_node(struct dl_node_manager *, const char *);
#endif
doubly-linked-list.c
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include "doubly-linked-list.h"
// BEGIN: IMPLEMENTATION INTERNAL
struct dl_node
{
char * str;
struct dl_node * prev;
struct dl_node * next;
};
struct dl_node_manager
{
struct dl_node * head;
struct dl_node * tail;
};
struct dl_node *
dl_create_node_(const char * str)
{
struct dl_node * node = malloc(sizeof *node);
if (!node)
{
return NULL;
}
node->str = strdup(str);
if (!node->str)
{
free(node);
return NULL;
}
return node;
}
bool
dl_remove_node_(struct dl_node_manager * manager, struct dl_node * node)
{
if (!node)
return false;
if (node->next && node->prev)
{
// Middle node.
node->prev->next = node->next;
node->next->prev = node->prev;
}
else if (node->next)
{
// Head node with a node after.
node->next->prev = NULL;
manager->head = node->next;
}
else if (node->prev)
{
// Tail with a node before.
node->prev->next = NULL;
manager->tail = node->prev;
}
else
{
// Only node.
manager->tail = NULL;
manager->head = NULL;
}
free(node->str);
free(node);
return true;
}
// END: IMPLEMENTATION INTERNAL
void
dl_init(struct dl_node_manager * manager)
{
manager->head = NULL;
manager->tail = NULL;
}
void
dl_destroy(struct dl_node_manager * manager)
{
for (struct dl_node * tmp = manager->head;
tmp;
tmp = tmp->next)
dl_remove_node_(manager, tmp);
}
bool
dl_empty(struct dl_node_manager * manager)
{
return !manager->head;
}
bool
dl_insert_head(struct dl_node_manager * manager, const char * str)
{
struct dl_node * node = dl_create_node_(str);
if (!node)
return false;
node->next = manager->head;
if (!manager->head)
manager->tail = node;
else
manager->head->prev = node;
manager->head = node;
return node;
}
bool
dl_insert_tail(struct dl_node_manager * manager, const char * str)
{
struct dl_node * node = dl_create_node_(str);
if (!node)
return false;
node->prev = manager->tail;
if (!manager->tail)
manager->head = node;
else
manager->tail->next = node;
manager->tail = node;
return node;
}
bool
dl_contains(struct dl_node_manager * manager, const char * str)
{
for (struct dl_node * tmp = manager->head;
tmp;
tmp = tmp->next)
if (strcmp(tmp->str, str) == 0)
return true;
return false;
}
bool
dl_remove_head(struct dl_node_manager * manager)
{
if (!manager->head)
return false;
return dl_remove_node_(manager, manager->head);
}
bool
dl_remove_tail(struct dl_node_manager * manager)
{
if (!manager->tail)
return false;
return dl_remove_node_(manager, manager->tail);
}
bool
dl_remove_node(struct dl_node_manager * manager, const char * str)
{
for (struct dl_node *tmp = manager->head;
tmp;
tmp = tmp->next)
if (strcmp(tmp->str, str) == 0)
return dl_remove_node_(manager, tmp);
return false;
}