Add READ_ONCE and WRITE_ONCE (XCC)
[akaros.git] / kern / lib / sort.c
1 /* Copyright (c) 2015 Google Inc
2  * Davide Libenzi <dlibenzi@google.com>
3  * See LICENSE for details.
4  */
5
6 #include <stdio.h>
7
8 static void mem_swap(void *a, void *b, size_t size)
9 {
10         for (; size > 0; size--, a++, b++) {
11                 char tmp = *(char*) a;
12
13                 *(char *) a = *(char *) b;
14                 *(char *) b = tmp;
15         }
16 }
17
18 void sort(void *base, size_t count, size_t size,
19           int (*cmp)(const void *, const void *))
20 {
21         ssize_t n = count * size, c;
22
23         /* Standard heapsort algorithm. First loop creates a heap, and the
24          * second one progressively pop the top of the heap, and does re-heap
25          * operations so that we maintain the heap properties.
26          */
27         for (ssize_t i = (count / 2 - 1) * size; i >= 0; i -= size) {
28                 for (ssize_t r = i; r * 2 + size < n; r = c) {
29                         c = r * 2 + size;
30                         if (c < n - size && cmp(base + c, base + c + size) < 0)
31                                 c += size;
32                         if (cmp(base + r, base + c) >= 0)
33                                 break;
34                         mem_swap(base + r, base + c, size);
35                 }
36         }
37
38         for (ssize_t i = n - size; i > 0; i -= size) {
39                 mem_swap(base, base + i, size);
40                 for (ssize_t r = 0; r * 2 + size < i; r = c) {
41                         c = r * 2 + size;
42                         if (c < i - size && cmp(base + c, base + c + size) < 0)
43                                 c += size;
44                         if (cmp(base + r, base + c) >= 0)
45                                 break;
46                         mem_swap(base + r, base + c, size);
47                 }
48         }
49 }