The five functions on this page complete the list section of libtciutil. Four of them take a function pointer as a parameter.
You have seen void * make data generic — the list stores any type
because content is a pointer to anything. Function pointers do the
same for behaviour: they let you pass a function as an argument.
The list cannot know how to free a char * versus a struct you
defined. The caller knows. So the caller passes a function that
handles it, and the list calls that function for each node.
Function pointer syntax
A regular pointer stores the address of a value. A function pointer stores the address of a function. Declaring them looks similar:
int *x; /* x is a pointer to an int */
void (*del)(void *); /* del is a pointer to a function */For the function pointer, the declaration also describes what the
function looks like: what it takes and what it returns. del points
to a function that takes void * and returns nothing.
The parentheses around *del are not optional. Without them, the
declaration means something different:
void *del(void *); /* a function named del that returns void * */
void (*del)(void *); /* a pointer to a function */Calling through a function pointer uses the same syntax as a regular call:
del(node->content);C lets you call through a function pointer without explicitly
dereferencing it. The longer form (*del)(node->content) means the
same thing and is also valid — the short form is more common.
Passing a function as an argument uses its name without parentheses:
void my_free(void *p)
{
free(p);
}
tciu_lstclear(&list, my_free);my_free is the address of the function. my_free(p) calls it.
The name alone is the address; the parentheses invoke it — the same
distinction as arr (the array's start address) versus arr[0]
(the first element).
tciu_lstdelone
tciu_lstdelone frees one node. It calls del on the content before
freeing the node itself. Two separate allocations, two separate frees:
Create tciu_lstdelone.c:
#include "libtciutil.h"
#include <stdlib.h>
void tciu_lstdelone(t_list *lst, void (*del)(void *))
{
del(lst->content); /* caller's function frees whatever content points at */
free(lst); /* we free the node struct itself */
}The del function is responsible for the content. The free(lst)
call is responsible for the node. Both must happen: if you only
free(lst) and the content is heap-allocated, you leak the content.
If you only call del and not free(lst), you leak the node.
Who should del be? Whatever frees the content correctly. For a
list of heap-allocated strings, del is just free. For a list of
structs that themselves contain pointers, del is a function that
frees the struct's fields and then the struct itself.
Add tciu_lstdelone.c to libtciutil's SRCS and its declaration to libtciutil.h:
void tciu_lstdelone(t_list *lst, void (*del)(void *));tciu_lstclear
tciu_lstclear frees every node in the list and sets *lst to
NULL. Before writing the implementation, meet the mechanism it uses.
Recursion
A function is recursive when it solves a problem by calling itself on a smaller version of that problem. The classic pattern:
solve(problem):
if problem is trivial → solve directly
otherwise → solve(smaller_problem); finish this step
tciu_lstclear fits this pattern exactly. Freeing a list of three
nodes means: free the rest of the list (a list of two nodes, the same
problem), then free this node. The base case is an empty list, which
needs no work.
In c01/05
you learned that nested allocations must be freed inside-out — the
inner allocation first, the outer second. A list of three nodes is a
nested allocation: the last node must be freed before the first node's
next pointer disappears. The recursive call handles the inside
automatically: it descends to the end of the list before freeing
anything, then unwinds.
The chain of calls descends to the base case, then the actual freeing happens on the way back up — last node freed first, first node freed last.
Create tciu_lstclear.c:
#include "libtciutil.h"
void tciu_lstclear(t_list **lst, void (*del)(void *))
{
if (!lst || !*lst)
return;
tciu_lstclear(&(*lst)->next, del); /* free the rest first */
tciu_lstdelone(*lst, del); /* then free this node */
*lst = NULL; /* null the caller's pointer */
}The recursive call passes &(*lst)->next — a pointer to this node's
next field. When the recursion unwinds, next has already been
nulled. tciu_lstdelone frees the content and the node struct.
*lst = NULL nulls the pointer in the calling frame, so every
pointer in the chain is zeroed by the time the stack fully unwinds.
Add tciu_lstclear.c to libtciutil's SRCS and its declaration to libtciutil.h:
void tciu_lstclear(t_list **lst, void (*del)(void *));tciu_lstiter
tciu_lstiter calls f on the content of every node in the list,
in order. The original list is not modified:
Create tciu_lstiter.c:
#include "libtciutil.h"
void tciu_lstiter(t_list *lst, void (*f)(void *))
{
while (lst) {
f(lst->content); /* call f on this node's content; f owns any side effects */
lst = lst->next; /* navigation only — does not modify the list */
}
}f receives a void * — the content of each node. It is the
caller's job to know what the pointer actually points at and cast
accordingly inside f.
A common use: print every element.
void print_str(void *content)
{
tci_printf("%s\n", (char *)content);
}
tciu_lstiter(list, print_str);Add tciu_lstiter.c to libtciutil's SRCS and its declaration to libtciutil.h:
void tciu_lstiter(t_list *lst, void (*f)(void *));tciu_lstmap
tciu_lstmap builds a new list by applying f to each node's content
and collecting the results. The original list is not modified. If any
allocation fails, del is called on already-computed results and the
function returns NULL:
Create tciu_lstmap.c:
#include "libtciutil.h"
t_list *tciu_lstmap(t_list *lst, void *(*f)(void *),
void (*del)(void *))
{
t_list *result;
t_list *node;
void *content;
result = NULL;
while (lst) {
content = f(lst->content); /* transform this node's content */
if (!content) {
tciu_lstclear(&result, del); /* f failed: clean up what we built so far */
return (NULL);
}
node = tciu_lstnew(content);
if (!node) {
del(content); /* lstnew failed: del the just-transformed content */
tciu_lstclear(&result, del); /* clean up the rest */
return (NULL);
}
tciu_lstadd_back(&result, node);
lst = lst->next;
}
return (result);
}void *(*f)(void *) is the declaration of a function pointer that
takes void * and returns void * — a transformation function.
f(lst->content) produces the new content for each corresponding
node. If f returns NULL on failure, del is called on the
accumulated result list and the function returns NULL. If
tciu_lstnew fails, del is called on the just-computed content
to avoid leaking it.
Note that tciu_lstmap does not modify or free the original list.
The caller owns both the original and the result.
Add tciu_lstmap.c to libtciutil's SRCS and its declaration to libtciutil.h:
t_list *tciu_lstmap(t_list *lst, void *(*f)(void *),
void (*del)(void *));The final libtciutil.h
The list block belongs in libtciutil.h, after the tciu_split
declaration. The complete list addition:
/* lists */
typedef struct s_list {
void *content;
struct s_list *next;
} t_list;
t_list *tciu_lstnew(void *content);
void tciu_lstadd_front(t_list **lst, t_list *new);
void tciu_lstadd_back(t_list **lst, t_list *new);
int tciu_lstsize(t_list *lst);
t_list *tciu_lstlast(t_list *lst);
void tciu_lstdelone(t_list *lst, void (*del)(void *));
void tciu_lstclear(t_list **lst, void (*del)(void *));
void tciu_lstiter(t_list *lst, void (*f)(void *));
t_list *tciu_lstmap(t_list *lst, void *(*f)(void *),
void (*del)(void *));The libtciutil Makefile
Add the nine list source files to libtciutil's SRCS:
SRCS = tciu_split.c \
tciu_lstnew.c tciu_lstadd_front.c tciu_lstadd_back.c \
tciu_lstsize.c tciu_lstlast.c \
tciu_lstdelone.c tciu_lstclear.c tciu_lstiter.c tciu_lstmap.cRun make re in the libtciutil directory:
make re10 compile lines. One ar line. No warnings. libtciutil.a now
contains tciu_split and all nine list functions.
The list functions will be verified as part of the c05 pipeline
tester in 08.
The pipeline binary uses tciu_lstnew, tciu_lstadd_back, and
tciu_lstclear to build and free the command chain — the list
implementation is exercised by running the program.
The next page uses the list to represent a chain of N commands and generalises the two-command pipeline to arbitrary length.