1
\$\begingroup\$

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;
}
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$
  1. Manager is a bad word, because it means everything and nothing.
    Case in point, your particular node_manager is a doubly-linked-list, though from the name it could be singly linked, a tree, an arbitrary graph, ...

  2. Your data-structure currently consists of a chain of nodes, and pointers to the first and last (if existing).

    The problem with this is that the first, last, and only node must be special-cased for inserting and deleting.

    1 Element           0 Elements          2+ Elements
    
    | # List # |        | 0 0 List |        | # List # |
      |      |                                |      |
      +----+ |                              +-+      +----------+
           | |                              |                   |
           v v                              v                   v
    0 <-> Node_1 <-> 0              0 <-> Node_1 <-> ... <-> Node_n <-> 0
    

    If you used a full circular list instead, there would be no special cases.

    1 Element       0 Elements      2+ Elements
    
    +--> List <--+  +--> List <--+  +--> List <-> Node_1 <----------+
    |            |  |            |  |                               |
    +-> Node_1 <-+  +------------+  +-> Node_n <-..(-> Node_2 <-)..-+
    

    To avoid dummy-payloads, your node would need to use a flexible array member for the payload, or you would have to create a new type to encapsulate just the links, and have it as a member for list and nodes, preferably first for easy casting.

  3. Separate finding a node from removing it. They are different tasks, and there might be many diffent useful criteria for the former.

  4. A const char* is a pointer, a simple data type. A 0-terminated string (often just string) is a data structure, specifically a 0-terminated sequence of non-0 characters, something much more complex. Even though to use the latter you generally point at it with the former, they are distinctly different.

  5. If someone wants to use dl_init(), they need to define a dl_node_manager, which means they need the definition. That definition is currently hidden in the implementation file.

    Either remove the init-function and replace it with a create-function which allocates it dynamically, or move the definition.

\$\endgroup\$
4
  • \$\begingroup\$ (5) I will allocate for them and destruct it, thanks for noticing. (4) You mean this to say I should simply call it a "string" in my comments? (2) that sounds like a different implementation, but I will likely do it also for practice. (3) What do you mean by separate, if you mean the dl_remove_node function? For (1) I stated dl_node_manager, what would you suggest for the name? (X) I notice you didn't mention me overloading dl_remove_node with dl_remove_node_ internally, so I take that as that is fine. \$\endgroup\$ Jun 15 at 0:25
  • \$\begingroup\$ 4) yes. 2) It is significantly different. 3) Yes, but currently it isn't part of the API, nor are helpers for freely iterating. 1) dl_list seems appropriate. X) That is not in itself bad, though following 3 would change it anyway. \$\endgroup\$ Jun 15 at 2:16
  • \$\begingroup\$ (X) I followed (3) and created a dl_find_node_ function, but that did not change dl_remove_node_, that was still a needed function. Thanks for your help. I think the code is significantly better. The most complex was definitely the dl_remove_node_ function. Also, (3) I didn't make it a part of API because I thought the nodes in the list should be transparent to the programmer. Maybe that's just a design decision? \$\endgroup\$ Jun 15 at 2:20
  • \$\begingroup\$ How then would you remove the 2nd of 3 nodes with value x? The good thing about having an iterator-interface isn't the interface itself, but that it can be used to build whatever you want on top. \$\endgroup\$ Jun 15 at 2:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.