1#include "doubly_linked_list.h"
  2#include <stdio.h>
  3#include <stdlib.h>
  4#include <string.h>
  5
  6/**
  7 * The equivalent of a constructor
  8 * to initialize a new node in a doubly linked list.
  9 *
 10 * @param data The data to initialize the head node with.
 11 * @return new Node bound to the data specified
 12 */
 13Node *initialize(int data) {
 14  Node *node = malloc(sizeof(Node));
 15  node->data = data;
 16  node->next = NULL;
 17  node->prev = NULL;
 18  return node;
 19}
 20
 21/**
 22 * Returns the tail of the list.
 23 *
 24 * @param head The head of the linked list
 25 * @return The tail of the linked list
 26 */
 27Node *tail(Node *head) {
 28  Node *tmp = head;
 29  while (tmp) {
 30    if (!tmp->next)
 31      break;
 32    tmp = tmp->next;
 33  }
 34  return tmp;
 35}
 36
 37/**
 38 * Adds data to the tail of a doubly linked list.
 39 *
 40 * @param head The head of the doubly linked list
 41 * @param data The data to append to the list
 42 * @return Returns the new node.
 43 */
 44Node *add(Node *head, int data) {
 45  Node *t = tail(head);
 46  t->next = initialize(data);
 47  t->next->prev = t;
 48  return t->next;
 49}
 50
 51/**
 52 * Returns a specific node in the list by index starting from 0.
 53 *
 54 * @param from The node to start scanning from.
 55 * @param index The zero based index of the node to retrieve.
 56 * @return The node at the specified index.
 57 */
 58Node *get(Node *from, int index) {
 59  if (!from || index < 0)
 60    return NULL;
 61
 62  while (index > 0 && from) {
 63    from = from->next;
 64    index--;
 65  }
 66  return from;
 67}
 68
 69/**
 70 * Returns the number of items in the linked list.
 71 *
 72 * @param head The head of the linked list
 73 * @return The number of items in the list.
 74 */
 75static int size(Node *head) {
 76  int i = 0;
 77  for (Node *tmp = head; tmp && tmp != NULL; tmp = tmp->next)
 78    i++;
 79  return i;
 80}
 81
 82/**
 83 * Assigns the next pointer of a node.
 84 *
 85 * @param self The node struct to alter.
 86 * @param other The other node to point to.
 87 */
 88static void assign_next(Node *self, Node *other) {
 89  if (self)
 90    self->next = other;
 91
 92  if (other)
 93    other->prev = self;
 94}
 95
 96/**
 97 * Assigns the previous pointer of a node.
 98 *
 99 * @param self The node struct to alter.
100 * @param other The other node to point to.
101 */
102static void assign_prev(Node *self, Node *other) {
103  if (self)
104    self->prev = other;
105
106  if (other)
107    other->next = self;
108}
109
110/**
111 * Reverses a linked list.
112 *
113 * @param head The head of the linked list.
114 * @return The new head of the linked list.
115 */
116Node *reverse(Node *head) {
117  Node *tmp = NULL;
118  Node *current = head;
119
120  while (current != NULL) {
121    tmp = current->prev;
122    current->prev = current->next;
123    current->next = tmp;
124    current = current->prev;
125  }
126  return tmp ? tmp->prev : head;
127}
128
129/**
130 * Generates a string representation of the Node usable for printing to stdout
131 *
132 * @param node The node to represent as a string
133 * @return The string that represents the node
134 */
135char *to_s(Node *node) {
136  const int buffer_size = 32;
137  char *buffer = malloc(buffer_size);
138  memset(buffer, buffer_size, '\0');
139
140  if (node->prev && node->next)
141    snprintf(buffer, buffer_size, "(%d<%d>%d) ", node->prev->data, node->data,
142             node->next->data);
143  else if (node->next)
144    snprintf(buffer, buffer_size, "(nil<%d>%d) ", node->data, node->next->data);
145  else
146    snprintf(buffer, buffer_size, "(%d<%d>nil) ", node->prev->data, node->data);
147  return buffer;
148}
149
150/**
151 * Prints the previous, data and next pointers for a node
152 *
153 * @param node The node to print
154 */
155static void print(Node *node) {
156  char *message = to_s(node);
157  printf("%s", message);
158  free(message);
159}
160
161/**
162 * Iterates through each node in a linked list.
163 *
164 * @param self The node to start iterating from.
165 * @param block The callback function to invoke on each node.
166 */
167void each(Node *self, Visitor block) {
168  Node *tmp = self;
169
170  while (tmp) {
171    block(tmp);
172    tmp = tmp->next;
173  }
174}
175
176/**
177 * Renders a visual output of a full linked list.
178 *
179 * @param node The head of the linked list
180 */
181void inspect(Node *node) {
182  printf("[ ");
183  each(node, &print);
184  printf("]\n");
185}