1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| static void *get_tmp(size_t width)
{
static void *tmp = NULL;
if (tmp == NULL)
tmp = ft_memalloc(width); // malloc + bzero
return (tmp);
}
static void switch_value(void *left, void *right, size_t width)
{
void *tmp;
if ((tmp = get_tmp(width)) == NULL)
return ;
ft_memcpy(tmp, right, width); // like memcpy
ft_memcpy(right, left, width);
ft_memcpy(left, tmp, width);
}
static void del_tmp(void)
{
void *tmp;
if ((tmp = get_tmp(0)) != NULL)
ft_memdel((void**)&tmp); // free and ptr = NULL
}
void loop_qsort(void *base, size_t nel, size_t width,
int (*compar)(const void *, const void *))
{
void *pivot;
void *end;
void *right;
void *left;
end = (void*)base + (nel - 1) * width;
right = end;
left = base;
pivot = base;
if (nel <= 1 || width <= 0 || end < base)
return ;
while (left < right)
{
while (left < right && compar(pivot, right) < 0)
right = (void*)right - width;
switch_value(left, right, width);
pivot = right;
while (left < right && compar(pivot, left) >= 0)
left = (void*)left + width;
switch_value(left, right, width);
pivot = left;
}
loop_qsort(base, (left - base) / width, width, compar);
loop_qsort((void*)left + width, (end - left) / width, width, compar);
}
void ft_qsort(void *base, size_t nel, size_t width,
int (*compar)(const void *, const void *))
{
if (nel <= 1)
return ;
loop_qsort(base, nel, width, compar);
del_tmp();
} |
