Implement libft Part 3 (linked lists) with tests

Add t_list struct and 9 linked list functions: ft_lstnew,
ft_lstadd_front, ft_lstsize, ft_lstlast, ft_lstadd_back,
ft_lstdelone, ft_lstclear, ft_lstiter, ft_lstmap.

14 files changed, 623 insertions, 2 deletions

diff --git a/Makefile b/Makefile
index 1411d0b..38628dd 100644
--- a/Makefile
+++ b/Makefile
@@ -17,7 +17,10 @@ SRCS = ft_isalpha.c ft_isdigit.c ft_isalnum.c ft_isascii.c ft_isprint.c \
        ft_toupper.c ft_tolower.c \
        ft_substr.c ft_strjoin.c ft_strtrim.c ft_split.c ft_itoa.c \
        ft_strmapi.c ft_striteri.c \
-       ft_putchar_fd.c ft_putstr_fd.c ft_putendl_fd.c ft_putnbr_fd.c
+       ft_putchar_fd.c ft_putstr_fd.c ft_putendl_fd.c ft_putnbr_fd.c \
+       ft_lstnew.c ft_lstadd_front.c ft_lstsize.c ft_lstlast.c \
+       ft_lstadd_back.c ft_lstdelone.c ft_lstclear.c ft_lstiter.c \
+       ft_lstmap.c
 
 OBJS = $(SRCS:%.c=$(OBJDIR)/%.o)
 
diff --git a/inc/libft.h b/inc/libft.h
index 05a5ae9..48b2c0b 100644
--- a/inc/libft.h
+++ b/inc/libft.h
@@ -135,4 +135,33 @@ void ft_putendl_fd (char *s, int fd);
 /** @brief Write integer @p n in decimal to @p fd. */
 void ft_putnbr_fd (int n, int fd);
 
+/* ======================================
+ *  Linked list
+ * ====================================== */
+
+typedef struct s_list
+{
+  void *content;       /**< Node payload (owned by the caller). */
+  struct s_list *next; /**< Next node, or NULL for the tail. */
+} t_list;
+
+/** @brief Allocate a new list node with @p content; next is NULL. */
+t_list *ft_lstnew (void *content);
+/** @brief Prepend @p new to the list pointed to by @p lst. */
+void ft_lstadd_front (t_list **lst, t_list *new);
+/** @brief Count the number of nodes in @p lst. */
+int ft_lstsize (t_list *lst);
+/** @brief Return the last node of @p lst. */
+t_list *ft_lstlast (t_list *lst);
+/** @brief Append @p new to the end of the list pointed to by @p lst. */
+void ft_lstadd_back (t_list **lst, t_list *new);
+/** @brief Delete one node's content with @p del and free the node. */
+void ft_lstdelone (t_list *lst, void (*del) (void *));
+/** @brief Delete and free all nodes in @p lst using @p del; set *lst=NULL. */
+void ft_lstclear (t_list **lst, void (*del) (void *));
+/** @brief Apply @p f to the content of each node in @p lst. */
+void ft_lstiter (t_list *lst, void (*f) (void *));
+/** @brief Map @p f over @p lst, creating a new list; use @p del on failure. */
+t_list *ft_lstmap (t_list *lst, void *(*f) (void *), void (*del) (void *));
+
 #endif
diff --git a/src/ft_lstadd_back.c b/src/ft_lstadd_back.c
new file mode 100644
index 0000000..076cae9
--- /dev/null
+++ b/src/ft_lstadd_back.c
@@ -0,0 +1,15 @@
+#include "libft.h"
+
+void
+ft_lstadd_back (t_list **lst, t_list *new)
+{
+  t_list *last;
+
+  if (!*lst)
+    {
+      *lst = new;
+      return;
+    }
+  last = ft_lstlast (*lst);
+  last->next = new;
+}
diff --git a/src/ft_lstadd_front.c b/src/ft_lstadd_front.c
new file mode 100644
index 0000000..e689412
--- /dev/null
+++ b/src/ft_lstadd_front.c
@@ -0,0 +1,8 @@
+#include "libft.h"
+
+void
+ft_lstadd_front (t_list **lst, t_list *new)
+{
+  new->next = *lst;
+  *lst = new;
+}
diff --git a/src/ft_lstclear.c b/src/ft_lstclear.c
new file mode 100644
index 0000000..4c738b7
--- /dev/null
+++ b/src/ft_lstclear.c
@@ -0,0 +1,19 @@
+#include "libft.h"
+#include <stdlib.h>
+
+void
+ft_lstclear (t_list **lst, void (*del) (void *))
+{
+  t_list *cur;
+  t_list *next;
+
+  cur = *lst;
+  while (cur)
+    {
+      next = cur->next;
+      del (cur->content);
+      free (cur);
+      cur = next;
+    }
+  *lst = NULL;
+}
diff --git a/src/ft_lstdelone.c b/src/ft_lstdelone.c
new file mode 100644
index 0000000..1fe570f
--- /dev/null
+++ b/src/ft_lstdelone.c
@@ -0,0 +1,9 @@
+#include "libft.h"
+#include <stdlib.h>
+
+void
+ft_lstdelone (t_list *lst, void (*del) (void *))
+{
+  del (lst->content);
+  free (lst);
+}
diff --git a/src/ft_lstiter.c b/src/ft_lstiter.c
new file mode 100644
index 0000000..84fc000
--- /dev/null
+++ b/src/ft_lstiter.c
@@ -0,0 +1,11 @@
+#include "libft.h"
+
+void
+ft_lstiter (t_list *lst, void (*f) (void *))
+{
+  while (lst)
+    {
+      f (lst->content);
+      lst = lst->next;
+    }
+}
diff --git a/src/ft_lstlast.c b/src/ft_lstlast.c
new file mode 100644
index 0000000..68b6337
--- /dev/null
+++ b/src/ft_lstlast.c
@@ -0,0 +1,11 @@
+#include "libft.h"
+
+t_list *
+ft_lstlast (t_list *lst)
+{
+  if (!lst)
+    return (NULL);
+  while (lst->next)
+    lst = lst->next;
+  return (lst);
+}
diff --git a/src/ft_lstmap.c b/src/ft_lstmap.c
new file mode 100644
index 0000000..c001a2d
--- /dev/null
+++ b/src/ft_lstmap.c
@@ -0,0 +1,26 @@
+#include "libft.h"
+#include <stdlib.h>
+
+t_list *
+ft_lstmap (t_list *lst, void *(*f) (void *), void (*del) (void *))
+{
+  t_list *new_list;
+  t_list *node;
+  void *content;
+
+  new_list = NULL;
+  while (lst)
+    {
+      content = f (lst->content);
+      node = ft_lstnew (content);
+      if (!node)
+        {
+          del (content);
+          ft_lstclear (&new_list, del);
+          return (NULL);
+        }
+      ft_lstadd_back (&new_list, node);
+      lst = lst->next;
+    }
+  return (new_list);
+}
diff --git a/src/ft_lstnew.c b/src/ft_lstnew.c
new file mode 100644
index 0000000..37412b4
--- /dev/null
+++ b/src/ft_lstnew.c
@@ -0,0 +1,15 @@
+#include "libft.h"
+#include <stdlib.h>
+
+t_list *
+ft_lstnew (void *content)
+{
+  t_list *node;
+
+  node = malloc (sizeof (t_list));
+  if (!node)
+    return (NULL);
+  node->content = content;
+  node->next = NULL;
+  return (node);
+}
diff --git a/src/ft_lstsize.c b/src/ft_lstsize.c
new file mode 100644
index 0000000..2986498
--- /dev/null
+++ b/src/ft_lstsize.c
@@ -0,0 +1,15 @@
+#include "libft.h"
+
+int
+ft_lstsize (t_list *lst)
+{
+  int count;
+
+  count = 0;
+  while (lst)
+    {
+      count++;
+      lst = lst->next;
+    }
+  return (count);
+}
diff --git a/src/ft_split.c b/src/ft_split.c
index bb51c85..966ce5f 100644
--- a/src/ft_split.c
+++ b/src/ft_split.c
@@ -21,6 +21,7 @@ _s_count_words (char const *s, char c)
   return (count);
 }
 
+/** Free the first @p n elements of @p arr, then @p arr itself. */
 static void
 _s_free_all (char **arr, size_t n)
 {
diff --git a/tests/Makefile b/tests/Makefile
index 3fc0322..00f69b3 100644
--- a/tests/Makefile
+++ b/tests/Makefile
@@ -8,7 +8,8 @@ LIB = ../lib/libft.a
 
 TESTS = test_strlen test_is test_mem test_cmp test_case test_strl test_search \
         test_atoi test_alloc test_substr test_strjoin test_strtrim \
-        test_split test_itoa test_strmapi test_striteri test_put
+        test_split test_itoa test_strmapi test_striteri test_put \
+        test_lst
 
 BINS = $(TESTS:%=$(BINDIR)/%)
 
diff --git a/tests/src/test_lst.c b/tests/src/test_lst.c
new file mode 100644
index 0000000..f4b6988
--- /dev/null
+++ b/tests/src/test_lst.c
@@ -0,0 +1,458 @@
+#include "libft.h"
+#include "test_utils.h"
+#include <ctype.h>
+
+/* ── helpers ─────────────────────────────────────────────────────── */
+
+static void
+_s_del (void *content)
+{
+  free (content);
+}
+
+static void
+_s_toupper_content (void *content)
+{
+  char *s;
+
+  s = content;
+  while (*s)
+    {
+      *s = toupper ((unsigned char)*s);
+      s++;
+    }
+}
+
+static void *
+_s_dup_content (void *content)
+{
+  return (strdup (content));
+}
+
+/** Build a list of @p n nodes, each containing strdup'd decimal string. */
+static t_list *
+_s_build_list (int n)
+{
+  t_list *lst;
+  char buf[32];
+  int i;
+
+  lst = NULL;
+  for (i = 0; i < n; i++)
+    {
+      snprintf (buf, sizeof (buf), "%d", i);
+      ft_lstadd_back (&lst, ft_lstnew (strdup (buf)));
+    }
+  return (lst);
+}
+
+/* ── ft_lstnew ───────────────────────────────────────────────────── */
+
+static void
+_s_test_lstnew (void)
+{
+  _s_section ("ft_lstnew");
+
+  /* basic */
+  {
+    char *s = strdup ("hello");
+    t_list *n = ft_lstnew (s);
+    _s_check ("content set", n && n->content == s);
+    _s_check ("next NULL", n && n->next == NULL);
+    free (s);
+    free (n);
+  }
+
+  /* NULL content is valid */
+  {
+    t_list *n = ft_lstnew (NULL);
+    _s_check ("NULL content ok", n && n->content == NULL);
+    _s_check ("NULL content next", n && n->next == NULL);
+    free (n);
+  }
+}
+
+/* ── ft_lstadd_front ─────────────────────────────────────────────── */
+
+static void
+_s_test_lstadd_front (void)
+{
+  int i;
+
+  _s_section ("ft_lstadd_front");
+
+  /* prepend to empty list */
+  {
+    t_list *lst = NULL;
+    t_list *n = ft_lstnew (strdup ("first"));
+    ft_lstadd_front (&lst, n);
+    _s_check ("empty→head", lst == n);
+    _s_check ("empty→next NULL", lst->next == NULL);
+    ft_lstclear (&lst, _s_del);
+  }
+
+  /* prepend to non-empty */
+  {
+    t_list *lst = ft_lstnew (strdup ("second"));
+    t_list *old = lst;
+    t_list *n = ft_lstnew (strdup ("first"));
+    ft_lstadd_front (&lst, n);
+    _s_check ("new head", lst == n);
+    _s_check ("old follows", lst->next == old);
+    ft_lstclear (&lst, _s_del);
+  }
+
+  /* randomized: build by prepending, verify reverse order */
+  for (i = 0; i < _S_RAND_ITERS; i++)
+    {
+      int count = rand () % 20 + 2;
+      t_list *lst = NULL;
+      t_list *cur;
+      int j;
+      int ok;
+
+      for (j = 0; j < count; j++)
+        {
+          char buf[32];
+          snprintf (buf, sizeof (buf), "%d", j);
+          ft_lstadd_front (&lst, ft_lstnew (strdup (buf)));
+        }
+      /* first node should contain the highest index */
+      ok = 1;
+      cur = lst;
+      for (j = count - 1; j >= 0; j--)
+        {
+          char buf[32];
+          snprintf (buf, sizeof (buf), "%d", j);
+          if (!cur || strcmp (cur->content, buf) != 0)
+            {
+              ok = 0;
+              break;
+            }
+          cur = cur->next;
+        }
+      _s_check ("prepend order", ok);
+      ft_lstclear (&lst, _s_del);
+    }
+}
+
+/* ── ft_lstsize ──────────────────────────────────────────────────── */
+
+static void
+_s_test_lstsize (void)
+{
+  int i;
+  char label[64];
+
+  _s_section ("ft_lstsize");
+
+  _s_check_eq_int ("NULL→0", ft_lstsize (NULL), 0);
+
+  {
+    t_list *lst = ft_lstnew (NULL);
+    _s_check_eq_int ("single→1", ft_lstsize (lst), 1);
+    free (lst);
+  }
+
+  /* randomized */
+  for (i = 0; i < _S_RAND_ITERS; i++)
+    {
+      int count = rand () % 100 + 1;
+      t_list *lst = _s_build_list (count);
+      snprintf (label, sizeof (label), "size=%d", count);
+      _s_check_eq_int (label, ft_lstsize (lst), count);
+      ft_lstclear (&lst, _s_del);
+    }
+}
+
+/* ── ft_lstlast ──────────────────────────────────────────────────── */
+
+static void
+_s_test_lstlast (void)
+{
+  _s_section ("ft_lstlast");
+
+  _s_check ("NULL→NULL", ft_lstlast (NULL) == NULL);
+
+  /* single node */
+  {
+    t_list *lst = ft_lstnew (strdup ("only"));
+    t_list *last = ft_lstlast (lst);
+    _s_check ("single is last", last == lst);
+    _s_check ("last->next NULL", last->next == NULL);
+    ft_lstclear (&lst, _s_del);
+  }
+
+  /* multi node */
+  {
+    t_list *lst = _s_build_list (5);
+    t_list *last = ft_lstlast (lst);
+    _s_check ("last content", last && strcmp (last->content, "4") == 0);
+    _s_check ("last->next NULL", last && last->next == NULL);
+    ft_lstclear (&lst, _s_del);
+  }
+}
+
+/* ── ft_lstadd_back ──────────────────────────────────────────────── */
+
+static void
+_s_test_lstadd_back (void)
+{
+  int i;
+  char label[64];
+
+  _s_section ("ft_lstadd_back");
+
+  /* append to empty list */
+  {
+    t_list *lst = NULL;
+    t_list *n = ft_lstnew (strdup ("first"));
+    ft_lstadd_back (&lst, n);
+    _s_check ("empty→head", lst == n);
+    _s_check ("empty→next NULL", lst->next == NULL);
+    ft_lstclear (&lst, _s_del);
+  }
+
+  /* append to non-empty */
+  {
+    t_list *lst = ft_lstnew (strdup ("first"));
+    t_list *n = ft_lstnew (strdup ("second"));
+    ft_lstadd_back (&lst, n);
+    _s_check ("head unchanged", strcmp (lst->content, "first") == 0);
+    _s_check ("tail is new", lst->next == n);
+    ft_lstclear (&lst, _s_del);
+  }
+
+  /* randomized: build by appending, verify order */
+  for (i = 0; i < _S_RAND_ITERS; i++)
+    {
+      int count = rand () % 20 + 2;
+      t_list *lst = _s_build_list (count);
+      t_list *cur;
+      int j;
+      int ok;
+
+      ok = 1;
+      cur = lst;
+      for (j = 0; j < count; j++)
+        {
+          char buf[32];
+          snprintf (buf, sizeof (buf), "%d", j);
+          if (!cur || strcmp (cur->content, buf) != 0)
+            {
+              ok = 0;
+              break;
+            }
+          cur = cur->next;
+        }
+      snprintf (label, sizeof (label), "append order n=%d", count);
+      _s_check (label, ok);
+      ft_lstclear (&lst, _s_del);
+    }
+}
+
+/* ── ft_lstdelone ────────────────────────────────────────────────── */
+
+static void
+_s_test_lstdelone (void)
+{
+  _s_section ("ft_lstdelone");
+
+  /* does not free next */
+  {
+    t_list *a = ft_lstnew (strdup ("first"));
+    t_list *b = ft_lstnew (strdup ("second"));
+    a->next = b;
+    ft_lstdelone (a, _s_del);
+    /* b must still be accessible */
+    _s_check ("next survives", strcmp (b->content, "second") == 0);
+    ft_lstdelone (b, _s_del);
+  }
+
+  /* single node */
+  {
+    t_list *n = ft_lstnew (strdup ("only"));
+    ft_lstdelone (n, _s_del);
+    _s_check ("single delone ok", 1);
+  }
+}
+
+/* ── ft_lstclear ─────────────────────────────────────────────────── */
+
+static void
+_s_test_lstclear (void)
+{
+  int i;
+  char label[64];
+
+  _s_section ("ft_lstclear");
+
+  /* NULL list */
+  {
+    t_list *lst = NULL;
+    ft_lstclear (&lst, _s_del);
+    _s_check ("NULL clear safe", lst == NULL);
+  }
+
+  /* single */
+  {
+    t_list *lst = ft_lstnew (strdup ("only"));
+    ft_lstclear (&lst, _s_del);
+    _s_check ("single cleared", lst == NULL);
+  }
+
+  /* multi */
+  {
+    t_list *lst = _s_build_list (5);
+    ft_lstclear (&lst, _s_del);
+    _s_check ("multi cleared", lst == NULL);
+  }
+
+  /* randomized */
+  for (i = 0; i < _S_RAND_ITERS; i++)
+    {
+      int count = rand () % 50 + 1;
+      t_list *lst = _s_build_list (count);
+      ft_lstclear (&lst, _s_del);
+      snprintf (label, sizeof (label), "clear n=%d", count);
+      _s_check (label, lst == NULL);
+    }
+}
+
+/* ── ft_lstiter ──────────────────────────────────────────────────── */
+
+static void
+_s_test_lstiter (void)
+{
+  _s_section ("ft_lstiter");
+
+  /* NULL list does not crash */
+  ft_lstiter (NULL, _s_toupper_content);
+  _s_check ("NULL safe", 1);
+
+  /* apply toupper */
+  {
+    t_list *lst = NULL;
+    ft_lstadd_back (&lst, ft_lstnew (strdup ("hello")));
+    ft_lstadd_back (&lst, ft_lstnew (strdup ("world")));
+    ft_lstiter (lst, _s_toupper_content);
+    _s_check ("iter[0]", strcmp (lst->content, "HELLO") == 0);
+    _s_check ("iter[1]", strcmp (lst->next->content, "WORLD") == 0);
+    ft_lstclear (&lst, _s_del);
+  }
+
+  /* randomized: build list, iter toupper, verify */
+  {
+    int i;
+    for (i = 0; i < _S_RAND_ITERS; i++)
+      {
+        int count = rand () % 20 + 1;
+        t_list *lst = _s_build_list (count);
+        t_list *cur;
+        int ok;
+
+        ft_lstiter (lst, _s_toupper_content);
+        ok = 1;
+        cur = lst;
+        while (cur)
+          {
+            char *s = cur->content;
+            while (*s)
+              {
+                if (*s >= 'a' && *s <= 'z')
+                  {
+                    ok = 0;
+                    break;
+                  }
+                s++;
+              }
+            cur = cur->next;
+          }
+        _s_check ("iter toupper", ok);
+        ft_lstclear (&lst, _s_del);
+      }
+  }
+}
+
+/* ── ft_lstmap ───────────────────────────────────────────────────── */
+
+static void
+_s_test_lstmap (void)
+{
+  int i;
+
+  _s_section ("ft_lstmap");
+
+  /* NULL list */
+  {
+    t_list *res = ft_lstmap (NULL, _s_dup_content, _s_del);
+    _s_check ("NULL→NULL", res == NULL);
+  }
+
+  /* basic map (strdup) */
+  {
+    t_list *lst = NULL;
+    t_list *mapped;
+    ft_lstadd_back (&lst, ft_lstnew (strdup ("hello")));
+    ft_lstadd_back (&lst, ft_lstnew (strdup ("world")));
+    mapped = ft_lstmap (lst, _s_dup_content, _s_del);
+    _s_check ("map[0]", mapped && strcmp (mapped->content, "hello") == 0);
+    _s_check ("map[1]", mapped && mapped->next
+                            && strcmp (mapped->next->content, "world") == 0);
+    /* original unchanged */
+    _s_check ("orig[0]", strcmp (lst->content, "hello") == 0);
+    /* independent nodes */
+    _s_check ("indep ptr", mapped->content != lst->content);
+    ft_lstclear (&lst, _s_del);
+    ft_lstclear (&mapped, _s_del);
+  }
+
+  /* randomized: build, map, verify same content but independent */
+  for (i = 0; i < _S_RAND_ITERS; i++)
+    {
+      int count = rand () % 20 + 1;
+      t_list *lst = _s_build_list (count);
+      t_list *mapped = ft_lstmap (lst, _s_dup_content, _s_del);
+      t_list *a;
+      t_list *b;
+      int ok;
+
+      ok = 1;
+      a = lst;
+      b = mapped;
+      while (a && b)
+        {
+          if (strcmp (a->content, b->content) != 0 || a->content == b->content)
+            {
+              ok = 0;
+              break;
+            }
+          a = a->next;
+          b = b->next;
+        }
+      if (a || b)
+        ok = 0;
+      _s_check ("map rand", ok);
+      ft_lstclear (&lst, _s_del);
+      ft_lstclear (&mapped, _s_del);
+    }
+}
+
+/* ── main ────────────────────────────────────────────────────────── */
+
+int
+main (void)
+{
+  srand (time (NULL));
+  _s_test_lstnew ();
+  _s_test_lstadd_front ();
+  _s_test_lstsize ();
+  _s_test_lstlast ();
+  _s_test_lstadd_back ();
+  _s_test_lstdelone ();
+  _s_test_lstclear ();
+  _s_test_lstiter ();
+  _s_test_lstmap ();
+  _s_print_results ();
+  return (_s_fail != 0);
+}