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 * Swaps two different nodes in the same linked list.
112 *
113 * @param x A node to swap
114 * @param y Another node to swap
115 */
116void swap(Node *x, Node *y) {
117  if (x == y)
118    return;
119  if (!x || !y)
120    return;
121  if (x->prev == y && y->next == x)
122    return swap(y, x);
123
124  Node *xp = x->prev, *xn = x->next, *yp = y->prev, *yn = y->next;
125
126  // if adjacent
127  if (x->next == y && y->prev == x) {
128    assign_next(x, yn);
129    assign_prev(x, y);
130    assign_prev(y, xp);
131  } else {
132    assign_prev(x, yp);
133    assign_next(x, yn);
134    assign_prev(y, xp);
135    assign_next(y, xn);
136  }
137}
138
139/**
140 * Generates a string representation of the Node usable for printing to stdout
141 *
142 * @param node The node to represent as a string
143 * @return The string that represents the node
144 */
145char *to_s(Node *node) {
146  const int buffer_size = 32;
147  char *buffer = malloc(buffer_size);
148  memset(buffer, buffer_size, '\0');
149
150  if (node->prev && node->next)
151    snprintf(buffer, buffer_size, "(%d<%d>%d) ", node->prev->data, node->data,
152             node->next->data);
153  else if (node->next)
154    snprintf(buffer, buffer_size, "(nil<%d>%d) ", node->data, node->next->data);
155  else
156    snprintf(buffer, buffer_size, "(%d<%d>nil) ", node->prev->data, node->data);
157  return buffer;
158}
159
160/**
161 * Prints the previous, data and next pointers for a node
162 *
163 * @param node The node to print
164 */
165static void print(Node *node) {
166  char *message = to_s(node);
167  printf("%s", message);
168  free(message);
169}
170
171/**
172 * Iterates through each node in a linked list.
173 *
174 * @param self The node to start iterating from.
175 * @param block The callback function to invoke on each node.
176 */
177void each(Node *self, Visitor block) {
178  Node *tmp = self;
179
180  while (tmp) {
181    block(tmp);
182    tmp = tmp->next;
183  }
184}
185
186/**
187 * Renders a visual output of a full linked list.
188 *
189 * @param node The head of the linked list
190 */
191void inspect(Node *node) {
192  printf("[ ");
193  each(node, &print);
194  printf("]\n");
195}