Animal Crossing: Recap those Animals! 1.0.3

double linked list, process, parsing


If there is a conflict between the subject and the skeleton or moulinette, the subject is always right.
However, please report any inconsistencies to your assistant.

Submissions

Repository structure
At the end, your git repo must follow this architecture:
epita-prepa-computer-science-prog-104-p-06-2030-firstname.lastname
├── RecapThoseAnimals
│   ├── Fundamentals
│   │   ├── double_linked_list
│   │   │   ├── Makefile
│   │   │   ├── dlist.c
│   │   │   ├── dlist.h
│   │   │   └── main.c
│   │   └── process
│   │       ├── Makefile
│   │       ├── fork.c
│   │       ├── fork.h
│   │       └── main.c
│   └── Proficiencies
│       └── double_linked_list
│           ├── Makefile
│           ├── dlist_merge_sort.c
│           ├── dlist_merge_sort.h
│           └── main.c
├── .gitignore
└── README

Do not forget to check the following requirements before submitting your work:
  • You shall obviously replace firstname.lastname with your login.
  • The .gitignore file is mandatory.
  • Remove all personal tests from your code, except those from the Tests folder.
  • The given prototypes must be strictly respected.
  • The code MUST compile! Otherwise you will not receive a grade.

.gitignore example
Here is an example of a .gitignore file:
*.a
*.lib
*.o
*.obj
*.out

.idea/
*~
*.DotSettings.user

This needs to be setup before the first submission!

Introduction


Danger(s)

Doing the recap practical alone is not enough to prepare the exam. You should also work on the previous practicals and the slides.

Due to the Minimake project, some notions are not covered (like trees, git or makefiles) but are still important to know for the exam. Make sure to work on them as well.


Hello there! In this practical, you will be working on double linked lists and processes. You will be implementing a double linked list structure and several functions to manipulate it. Then, you will be using processes to create a simple program that checks whether a number is prime or not and another one that salutes guests. I know you will not read this, but good luck anyway!

Sorry guys, no lore for this practical.


double_linked_list/dlist.c


In this header, you will define the structures used to represent a doubly linked list.

First, create a structure named node containing:
  • an integer data,
  • a pointer next to the next node,
  • a pointer prev to the previous node.

Then, create a structure named dlist containing:
  • a size_t size, representing the number of nodes in the list
  • a pointer head to the first node,
  • a pointer tail to the last node.

Next, copy paste the following declarations to finish your header file.

Code example(s)
struct dlist *dlist_init(void);
void dlist_clear(struct dlist *list);
size_t dlist_length(struct dlist *l);
void dlist_push_front(struct dlist *l, int data);
void dlist_push_back(struct dlist *l, int data);
void dlist_remove(struct dlist *list, int data);
struct dlist *dlist_from_str(char *str);
struct node *dlist_find(struct dlist *list, int data);
void dlist_concat(struct dlist *l1, struct dlist *l2);
void dlist_insert(struct dlist *l, int data, int i);

Warning(s)
Don't forget to do proper include guards (the #ifndef ...)

Implement a function named dlist_init that allocates an empty list, initialises size to 0, head and tail to NULL. It should return a pointer to the newly created list. If an error occurs during allocation, return NULL.

Finally, implement a function dlist_clear that frees all nodes in the list, as well as the list structure itself. The list should not be usable after calling this function. If the given list is NULL, don't do anything.

Prototype(s)
struct dlist *dlist_init();
void dlist_clear(struct dlist *list);

Code example(s)
struct dlist *l = dlist_init();
printf("length = %zu\n", l->size); // 0
printf("head = %p\n", (void *)l->head); // (nil) or NULL
printf("tail = %p\n", (void *)l->tail); // (nil) or NULL
dlist_clear(l);
// l is now invalid

Implement a function dlist_length that computes the number of nodes in the list.
It should return the number of nodes in the list starting from head.
Be careful: you must not modify the size field.

Information
If the given argument is NULL, the function should return 0.

Danger(s)
The use of the size field is forbidden. Iterate over nodes instead.

Prototype(s)
size_t dlist_length(struct dlist *l);

Code example(s)
struct dlist *l = dlist_init();
size_t len = dlist_length(l);
printf("Length: %zu\n", len); // 0
dlist_clear(l);

Implement a function dlist_push_front that inserts a new node with the given data at the beginning of the list.
  • If the list is empty, the new node becomes both the head and the tail of the node list.
  • Otherwise, insert the new node before the current head and update both: the next pointer of the newly created node and the prev pointer of the old head.

If an error occurs, the function must leave the list unchanged.

Prototype(s)
void dlist_push_front(struct dlist *l, int data);

Code example(s)
struct dlist *l = dlist_init(); // l: NULL
dlist_push_front(l, 10);              // l: 10 -> NULL
dlist_push_front(l, 20);              // l: 20 -> 10 -> NULL
dlist_clear(l);

Implement a function dlist_push_back that appends a new node with the given data to the end of the list.
  • If the node list is empty, the new node becomes both the head and the tail of the list.
  • Otherwise, use the tail pointer to append the new node.

Information
Make sure to correctly update the next pointer of the old tail and the prev pointer of the new node. If any error occurs, the list must remain unchanged.

Prototype(s)
void dlist_push_back(struct dlist *l, int data);

Code example(s)
struct dlist *l = dlist_init();
dlist_push_back(l, 10); // l: 10 -> NULL
dlist_push_back(l, 20); // l: 10 -> 20 -> NULL
dlist_clear(l);

Implement a function dlist_remove that removes the first node whose data matches the given value.

If the list is NULL or the given value is not found, do nothing.
Otherwise, remove the first matching node and properly update: the next and prev pointers of neighboring nodes, as well as the head and tail pointers if needed.

Don't forget to free the removed node.

Prototype(s)
void dlist_remove(struct dlist *list, int data);

Code example(s)
struct dlist *l = dlist_init();
dlist_push_back(l, 1);
dlist_push_back(l, 2);
dlist_push_back(l, 3);
dlist_push_back(l, 2);
                        // l: 1 -> 2 -> 3 -> 2 -> NULL
dlist_remove(l, 2);      // l: 1 -> 3 -> 2 -> NULL
dlist_remove(l, 2);      // l: 1 -> 3 -> NULL
dlist_remove(l, 2);      // l: 1 -> 3 -> NULL
dlist_clear(l);

You need to create a double linked list from a string passed as argument.
The string always begins with either a plus (+) or minus (-) sign, followed by a number. This pattern then repeats: a sign, followed by another number, and so on.

A plus sign indicates that the number immediately following it should be added to the end of the doubly linked list.
A minus sign indicates that the first occurrence of the number that follows should be removed from the list.

Prototype(s)
struct dlist *dlist_from_str(char *str);

Code example(s)
dlist_from_str("+2+10+42+2+223-2"); // NULL<->10<->42<->2<->223<->NULL
dlist_from_str("-2+10+42+2+223-2"); // NULL<->10<->42<->223<->NULL
dlist_from_str(""); // Return an empty list (size = 0, head = NULL, tail = NULL)
dlist_from_str("-2-10-42-2-223"); // Return an empty list too

The function dlist_find will return the first node whose data field is equal to the int passed as argument.
Implement a function dlist_find that returns a pointer to the first node whose data matches the given integer.

If the list is NULL or no matching node is found, the function should return NULL.

Prototype(s)
struct node *dlist_find(struct dlist *list, int data);

Code example(s)
struct dlist *l = dlist_init();
dlist_push_back(l, 1);
dlist_push_back(l, 2);
dlist_push_back(l, 3);
dlist_push_back(l, 2);
                            // l: 1 -> 2 -> 3 -> 2 -> NULL
struct node *n;
n = dlist_find(l, 1);        // n->data == 1
n = dlist_find(l, 3);        // n->data == 3
n = dlist_find(l, 223);      // n == NULL
dlist_clear(l);

Implement a function dlist_concat that takes two lists and will concatenate them in place into the first list.
You should update the size, head and tail fields accordingly. Don't forget to update the prev and next pointers between the two lists.
You should free what is not used anymore. Careful not to free the useful nodes!

Information
If one of the given arguments are set to NULL, there is nothing to be done.

Prototype(s)
void dlist_concat(struct dlist *l1, struct dlist *l2);

Code example(s)
struct dlist *l1 = dlist_init();
for (int i = 0 ; i < 5 ; i++)
    dlist_push_back(l1, i);
struct dlist *l2 = dlist_init();
for (int i = 0 ; i < 5 ; i++)
    dlist_push_front(l2, i);
                                          // l1: 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> NULL
                                          // l2: 4 <-> 3 <-> 2 <-> 1 <-> 0 <-> NULL
dlist_concat(l1, l2);                      // l1: 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> 4 <-> 3 <-> 2 <-> 1 <-> 0 <-> NULL
                                          // l1->size = 10
dlist_clear(l1); // If you freed correctly, no memory leaks should be displayed on your terminal

Implement a function dlist_insert that takes a list, a value to insert and an index as parameters.
The function should insert a new node containing the given data at the specified index.
If the index is 0 you should add the node at the beginning of the list and update the head and tail pointers if necessary. Make sure to correctly update the prev and next pointers.

Information
If the given argument is set to NULL or the index is not correct, the function should not do anything.

Prototype(s)
void dlist_insert(struct dlist *l, int data, int i);

Code example(s)
struct dlist *l = dlist_init();
for (int i = 0 ; i < 5 ; i++)
    dlist_push_back(l, i);
                                          // l: 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> NULL
dlist_insert(l, -4, 0);                    // l: -4 <-> 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> NULL
dlist_insert(l, 5, 6);                     // l: -4 <-> 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> NULL
dlist_insert(l, 5, 12);                    // l: -4 <-> 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> NULL

dlist_clear(l);


process/fork.c


First of all, you need to check whether the number is prime or not.

Using processes (see fork(2)), you will be printing the prime outcome:
  • Child process will print the following line: "Child speaking: my number [n] is [a prime number]/[not a prime number]\n" .
  • Parent process will print the following line: "Parent speaking: stop wasting my time of course [n] is [a prime number]/[not a prime number]\n" .
  • Both child and parent processeses will print the following line: "We both say hi!\n"

The parent process must wait for the child to finish before printing its own messages to ensure a deterministic output order.

If everything goes as expected, the function returns 1 if the number is prime, 0 otherwise.
If any error occurs, the function should return -1.

Prototype(s)
int is_prime(size_t n);

Output
./is_prime 73
Child speaking: my number 73 is a prime number
We both say hi!
Parent speaking: stop wasting my time of course 73 is a prime number
We both say hi!

./is_prime 42
Child speaking: my number 42 is not a prime number
We both say hi!
Parent speaking: stop wasting my time of course 42 is not a prime number
We both say hi!

The use of pipe is mandatory.

The child process will be writing in the pipe every guest found in the given list of guests.
Before adding guests, the cue "Adding guests..." should be printed, followed by a new line.
When a guest was successfully written in the pipe "Guest [name_of_guest] added." should be printed, followed by a new line.

Then, in the parent process, proceed to read from the pipe and print each guest, one line per guest.
Before greeting guests, you should print "My child salutes all of you:", followed by a new line.

Once the write step is over, print "All guests added successfully.", followed by a new line.
Don't forget to close the pipe in both processes and to free any allocated memory.

If any error occurs, the function should return -1. Otherwise, it should return 0.

Warning(s)
To ensure the output matches the example (interleaved output), you should use fflush(stdout) after your printf calls in both processes.

Prototype(s)
int salute(int num_guests, char *guests[]);

Output
./salute "Mister Mxyzptlk" Bubun Honney
Adding guests...
Guest [Mister Mxyzptlk] added.
Guest [Bubun] added.
Guest [Honney] added.
All guests added successfully.
My child salutes all of you:
Mister Mxyzptlk
Bubun
Honney

./salute
Adding guests...
All guests added successfully.
My child salutes all of you:

Information
The output order does matter. The parent process should wait for the child process to finish before reading from the pipe.


Good luck!


double_linked_list/dlist_merge_sort/dlist_merge_sort.c


Hint(s)
Creating a main.c file is highly recommended, feel free to use the functions you implemented in the fundamentals part to test your code.

Implement a function dlist_merge_sort that sorts the elements of the given list in increasing order based on their data values, using the merge sort algorithm.

Danger(s)
If you do not use the merge sort algorithm, this function will receive a score of 0. Additionally, the use of arrays is strictly forbidden.

Information
If the given argument is set to NULL, the function should not do anything.

Prototype(s)
void dlist_merge_sort(struct dlist *l);

Code example(s)
struct dlist *l = dlist_init();
dlist_push_back(l, 0);
dlist_push_back(l, 2);
dlist_push_back(l, 4);
dlist_push_back(l, 3);
dlist_push_back(l, 1);
                    // l: 0 <-> 2 <-> 4 <-> 3 <-> 1 <-> NULL
dlist_merge_sort(l); // l: 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> NULL

dlist_clear(l);

Information
The function dlist_print in the main.c file will not be graded, however it can be useful to test your code.



[ 1.0.1 ] 2026-04-27 15:00:00
Fundamentals
  • dlist_remove > instructions: add a reminder to free node

[ 1.0.2 ] 2026-04-27 14:00:00
Fundamentals
  • dlist_init > Example: clarify the size

[ 1.0.3 ] 2026-04-27 13:00:00
Proficiencies
  • dlist_merge_sort > Example: add explanations about dlist_print

[ 1.0.3 ] 2026-04-27 12:00:00
Fundamentals
  • process > instructions: add more instructions about the return value of the function


This page and all subpages are for internal use at EPITA only.
The use of this document must abide by the following rules:
Copyright © 2026-2027 - EPITA