Reorganize the files.
[monolithium.git] / libraries / mlcrt / src / algorithm.c
1 /*
2  * algorithm.c
3  *
4  * Copyright (C) 2017 Aleksandar Andrejevic <theflash@sdf.lonestar.org>
5  *
6  * This program is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU Affero General Public License as
8  * published by the Free Software Foundation, either version 3 of the
9  * License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU Affero General Public License for more details.
15  *
16  * You should have received a copy of the GNU Affero General Public License
17  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
18  */
19
20 #include <string.h>
21
22 void qsort(void *base, size_t nmemb, size_t size, int (*compare)(const void*, const void*))
23 {
24     void *pivot = (void*)((uintptr_t)base + (nmemb / 2) * size);
25     void *temp = __builtin_alloca(size);
26     if (nmemb <= 1) return;
27
28     size_t low = 0;
29     size_t high = nmemb - 1;
30
31     for (;;)
32     {
33         while (compare((void*)((uintptr_t)base + low * size), pivot) < 0) low++;
34         while (compare((void*)((uintptr_t)base + high * size), pivot) > 0) high--;
35         if (low >= high) break;
36
37         memcpy(temp, (void*)((uintptr_t)base + low * size), size);
38         memcpy((void*)((uintptr_t)base + low * size), (void*)((uintptr_t)base + high * size), size);
39         memcpy((void*)((uintptr_t)base + high * size), temp, size);
40     }
41
42     qsort(base, high, size, compare);
43     qsort((void*)((size_t)base + high * size), nmemb - high, size, compare);
44 }
45
46 void *bsearch(const void *key, const void *base, size_t nmemb, size_t size, int (*compare)(const void*, const void*))
47 {
48     long low = 0;
49     long high = nmemb - 1;
50
51     while (low <= high)
52     {
53         long mid = low + (high - low) / 2;
54         void *current = (void*)((uintptr_t)base + mid * size);
55         int comp = compare(current, key);
56
57         if (comp < 0) low = mid + 1;
58         else if (comp > 0) high = mid - 1;
59         else return current;
60     }
61
62     return NULL;
63 }