add new linked list implementation

4 files changed, 310 insertions, 0 deletions

diff --git a/src/ply-list.c b/src/ply-list.c
new file mode 100644
index 0000000..4b08c38
--- /dev/null
+++ b/src/ply-list.c
@@ -0,0 +1,270 @@
+#include "config.h"
+#include "ply-list.h"
+
+#include <assert.h>
+#include <errno.h>
+#include <stdlib.h>
+#include <string.h>
+
+struct _ply_list
+{
+  ply_list_node_t *first_node;
+  ply_list_node_t *last_node;
+
+  int number_of_nodes;
+};
+
+struct _ply_list_node
+{
+  void   *data;
+  struct _ply_list_node *previous;
+  struct _ply_list_node *next;
+};
+
+ply_list_t *
+ply_list_new (void)
+{
+  ply_list_t *list;
+
+  list = calloc (1, sizeof (ply_list_t));
+
+  list->first_node = NULL;
+  list->last_node = NULL;
+  list->number_of_nodes = 0;
+
+  return list;
+}
+
+void 
+ply_list_free (ply_list_t *list)
+{
+  ply_list_node_t *node;
+
+  if (list == NULL)
+    return;
+
+  node = list->first_node;
+  while (node != NULL)
+    {
+      ply_list_node_t *next_node;
+      next_node = node->next;
+      ply_list_remove_node (list, node);
+      node = next_node;
+    }
+
+  free (list);
+}
+
+ply_list_node_t *
+ply_list_node_new (void *data)
+{
+  ply_list_node_t *node;
+
+  node = calloc (1, sizeof (ply_list_node_t));
+  node->data = data;
+
+  return node;
+}
+
+void 
+ply_list_node_free (ply_list_node_t *node)
+{
+  if (node == NULL)
+    return;
+
+  assert ((node->previous == NULL) && (node->next == NULL));
+
+  free (node);
+}
+
+int 
+ply_list_get_length (ply_list_t *list)
+{
+  return list->number_of_nodes;
+}
+
+ply_list_node_t *
+ply_list_find_node (ply_list_t *list,
+                    void       *data)
+{
+  ply_list_node_t *node;
+
+  node = list->first_node;
+  while (node != NULL)
+    {
+      if (node->data == data)
+        break;
+
+      node = node->next;
+    }
+  return node;
+}
+
+static void
+ply_list_insert_node (ply_list_t      *list,
+                      ply_list_node_t *node_before,
+                      ply_list_node_t *new_node)
+{
+
+  if (new_node == NULL)
+    return;
+
+  if (node_before == NULL)
+    {
+      if (list->first_node == NULL)
+        { 
+          assert (list->last_node == NULL);
+
+          list->first_node = new_node;
+          list->last_node = new_node;
+        }
+      else
+        {
+          list->first_node->previous = new_node;
+          new_node->next = list->first_node;
+          list->first_node = new_node;
+        }
+    }
+  else
+    {
+      new_node->next = node_before->next;
+      if (node_before->next != NULL)
+        node_before->next->previous = new_node;
+      node_before->next = new_node;
+      new_node->previous = node_before;
+
+      if (node_before == list->last_node)
+        list->last_node = new_node;
+    }
+
+  list->number_of_nodes++;
+}
+
+ply_list_node_t *
+ply_list_insert_data (ply_list_t      *list,
+                      void            *data,
+                      ply_list_node_t *node_before)
+{
+  ply_list_node_t *node;
+
+  node = ply_list_node_new (data);
+
+  ply_list_insert_node (list, node_before, node);
+
+  return node;
+}
+
+ply_list_node_t *
+ply_list_append_data (ply_list_t *list,
+                      void       *data)
+{
+  return ply_list_insert_data (list, data, list->last_node);
+}
+
+ply_list_node_t *
+ply_list_prepend_data (ply_list_t *list,
+                       void       *data)
+{
+  return ply_list_insert_data (list, data, NULL);
+}
+
+void 
+ply_list_remove_data (ply_list_t *list,
+                      void       *data)
+{
+  ply_list_node_t *node;
+
+  if (data == NULL)
+    return;
+
+  node = ply_list_find_node (list, data);
+
+  if (node != NULL)
+    ply_list_remove_node (list, node);
+}
+
+void 
+ply_list_remove_node (ply_list_t      *list,
+                      ply_list_node_t *node)
+{
+  if (node == NULL)
+    return;
+
+  if (node == list->first_node)
+    list->first_node = node->next;
+
+  if (node == list->last_node)
+    list->last_node = node->previous;
+
+  if (node->previous != NULL)
+    {
+      node->previous->next = node->next;
+      node->previous = NULL;
+    }
+
+  if (node->next != NULL)
+    {
+      node->next->previous = node->previous;
+      node->next = NULL;
+    }
+
+  ply_list_node_free (node);
+  list->number_of_nodes--;
+}
+
+ply_list_node_t *
+ply_list_get_first_node (ply_list_t *list)
+{
+  return list->first_node;
+}
+
+ply_list_node_t *
+ply_list_get_next_node (ply_list_t     *list,
+                       ply_list_node_t *node)
+{
+  return node->next;
+}
+
+void *
+ply_list_node_get_data (ply_list_node_t *node)
+{
+  return node->data;
+}
+
+#ifdef PLY_LIST_ENABLE_TEST
+#include <stdio.h>
+
+int
+main (int    argc,
+      char **argv)
+{
+  ply_list_t *list;
+  ply_list_node_t *node;
+  int i;
+
+  list = ply_list_new ();
+
+  ply_list_append_data (list, (void *) "foo");
+  ply_list_append_data (list, (void *) "bar");
+  ply_list_append_data (list, (void *) "baz");
+  ply_list_prepend_data (list, (void *) "qux");
+  ply_list_prepend_data (list, (void *) "quux");
+  ply_list_remove_data (list, (void *) "baz");
+  ply_list_remove_data (list, (void *) "foo");
+
+  node = ply_list_get_first_node (list);
+  i = 0;
+  while (node != NULL)
+    {
+      printf ("node '%d' has data '%s'\n", i,
+              (char *) ply_list_node_get_data (node));
+      node = ply_list_get_next_node (list, node);
+      i++;
+    }
+
+  ply_list_free (list);
+  return 0;
+}
+
+#endif
+/* vim: set ts=4 sw=4 expandtab autoindent cindent cino={.5s,(0: */
diff --git a/src/ply-list.h b/src/ply-list.h
new file mode 100644
index 0000000..9925e38
--- /dev/null
+++ b/src/ply-list.h
@@ -0,0 +1,31 @@
+#ifndef PLY_LIST_H
+#define PLY_LIST_H
+
+typedef struct _ply_list_node ply_list_node_t;
+typedef struct _ply_list ply_list_t;
+
+#ifndef PLY_HIDE_FUNCTION_DECLARATIONS
+ply_list_t *ply_list_new (void);
+void ply_list_free (ply_list_t *list);
+int ply_list_get_length (ply_list_t *list);
+ply_list_node_t *ply_list_find_node (ply_list_t *list,
+                                     void       *data);
+ply_list_node_t *ply_list_insert_data (ply_list_t *list,
+		                       void       *data,
+		                       ply_list_node_t *node_before);
+ply_list_node_t *ply_list_append_data (ply_list_t *list,
+                                       void       *data);
+ply_list_node_t *ply_list_prepend_data (ply_list_t *list,
+                                        void       *data);
+void ply_list_remove_data (ply_list_t *list,
+                          void        *data);
+void ply_list_remove_node (ply_list_t      *list,
+                           ply_list_node_t *node);
+ply_list_node_t *ply_list_get_first_node (ply_list_t *list);
+ply_list_node_t *ply_list_get_next_node (ply_list_t  *list,
+                                         ply_list_node_t *node);
+
+void *ply_list_node_get_data (ply_list_node_t *node);
+#endif
+
+#endif /* PLY_LIST_H */
diff --git a/src/tests/Makefile.am b/src/tests/Makefile.am
index 0e58d71..85f176d 100644
--- a/src/tests/Makefile.am
+++ b/src/tests/Makefile.am
@@ -10,5 +10,6 @@ include $(srcdir)/ply-terminal-test.am
 include $(srcdir)/ply-terminal-session-test.am
 include $(srcdir)/ply-init-control-test.am
 include $(srcdir)/ply-logger-test.am
+include $(srcdir)/ply-list-test.am
 
 noinst_PROGRAMS = $(TESTS)
diff --git a/src/tests/ply-list-test.am b/src/tests/ply-list-test.am
new file mode 100644
index 0000000..8beb578
--- /dev/null
+++ b/src/tests/ply-list-test.am
@@ -0,0 +1,8 @@
+TESTS += ply-list-test
+
+ply_list_test_CFLAGS = $(PLYMOUTH_CFLAGS) -DPLY_LIST_ENABLE_TEST
+ply_list_test_LDADD = $(PLYMOUTH_LIBS)
+
+ply_list_test_SOURCES =                                                     \
+                          $(srcdir)/../ply-list.h                           \
+                          $(srcdir)/../ply-list.c