data_structures
list_merge_sort.c
Go to the documentation of this file.
1 /* ************************************************************************** */
3 /* */
4 /* ::: :::::::: */
5 /* list_merge_sort.c :+: :+: :+: */
6 /* +:+ +:+ +:+ */
7 /* By: unite <marvin@42.fr> +#+ +:+ +#+ */
8 /* +#+#+#+#+#+ +#+ */
9 /* Created: 2020/07/18 22:35:24 by unite #+# #+# */
10 /* Updated: 2020/09/07 22:01:56 by unite ### ########.fr */
11 /* */
12 /* ************************************************************************** */
13 
14 #include "list.h"
15 
16 static t_link *link_jump(t_list *alst, t_link *start, size_t n)
17 {
18  t_link *end;
19 
20  end = start;
21  while (n-- > 0)
22  end = end->next;
23  return (end);
24 }
25 
26 static t_link *links_sorted_merge(t_list *alst, t_link *l, t_link *m)
27 {
28  t_link *result;
29  t_link *included;
30 
31  if (!l)
32  return (m);
33  if (!m)
34  return (l);
35  if (alst->type->cmp(l->content, m->content) > 0)
36  {
37  result = m;
38  result->next = links_sorted_merge(alst, m->next, l);
39  }
40  else
41  {
42  result = l;
43  result->next = links_sorted_merge(alst, l->next, m);
44  }
45  return (result);
46 }
47 
48 static t_link *link_merge_sort_recur(t_list *alst, t_link *start, size_t size)
49 {
50  t_link *middle;
51 
52  if (size == 1)
53  return (start);
54  middle = link_jump(alst, start, size / 2);
55  middle->prev->next = NULL;
56  start = link_merge_sort_recur(alst, start, size / 2);
57  middle = link_merge_sort_recur(alst, middle, size - size / 2);
58  return (links_sorted_merge(alst, start, middle));
59 }
60 
61 static void list_fix_backlinks(t_list *alst, t_link *start)
62 {
63  t_link *link;
64 
65  link = start;
66  while (link->next)
67  {
68  link->next->prev = link;
69  link = link->next;
70  }
71  alst->head = start;
72  alst->tail = link;
73 }
74 
76 {
77  t_link *start;
78 
79  if (alst->type->cmp == NULL)
80  ds_exit_set(ENOTSUP);
81  if (alst->head == NULL)
82  return ;
83  start = link_merge_sort_recur(alst, alst->head, alst->size);
84  list_fix_backlinks(alst, start);
85 }
s_type::cmp
int(* cmp)(const void *, const void *)
(optional) A function ponter used to compare members of this data type
Definition: types.h:52
s_list::head
t_link * head
The first link.
Definition: list.h:56
s_list
Doubly-linked list of generic items.
Definition: list.h:54
s_list::tail
t_link * tail
The last link.
Definition: list.h:57
list_merge_sort
void list_merge_sort(t_list *alst)
Sorts this list in ascending order using in-place merge sort.
Definition: list_merge_sort.c:75
s_list::size
size_t size
The number of items in the list.
Definition: list.h:58
s_list::type
const t_type * type
The type of items in this list.
Definition: list.h:59
list.h
ds_exit_set
void ds_exit_set(int err)
Set errno to the specified value, print the error message, and exit the process.
Definition: ds_exit_set.c:22