Subversion Repositories HelenOS

Rev

Rev 333 | Go to most recent revision | Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
331 bondari 1
#include <mm/heap.h>
2
#include <memstr.h>
3
#include <sort.h>
4
 
5
 
6
void qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) {
7
 
8
    if (n > 4) {
9
        int i = 0, j = n - 1;
10
        void * tmp = (void *) malloc(e_size);
11
        void * pivot = (void *) malloc(e_size);
12
 
13
        memcpy(pivot, data, e_size);
14
 
15
        while (1) {
16
            while ((cmp(data + i * e_size, pivot) < 0) && i < n) i++;
17
            while ((cmp(data + j * e_size, pivot) >=0) && j > 0) j--;
18
 
19
            if (i<j) {
20
                memcpy(tmp, data + i * e_size, e_size);
21
                memcpy(data + i * e_size, data + j * e_size, e_size);
22
                memcpy(data + j * e_size, tmp, e_size);
23
            } else {
24
                break;
25
            }
26
        }
27
 
28
        free(tmp);
29
        free(pivot);
30
 
31
        qsort(data, j + 1, e_size, cmp);
32
        qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp);
33
 
34
    } else {
35
        bubblesort(data, n, e_size, cmp);
36
    }
37
 
38
 
39
}
40
 
41
 
42
void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) {
43
    bool done = false;
44
    void * p;
45
    void * slot = (void *) malloc(e_size);
46
 
47
    while (!done) {
48
        done = true;
49
        for (p = data; p < data + e_size * (n - 1); p = p + e_size) {
50
            if (cmp(p, p + e_size) == 1) {
51
                memcpy(slot, p, e_size);
52
                memcpy(p, p + e_size, e_size);
53
                memcpy(p + e_size, slot, e_size);
54
                done = false;
55
            }
56
        }
57
 
58
    }
59
 
60
    free(slot);
61
}
62
 
63
/*
64
 * Comparator returns 1 if a > b, 0 if a == b, -1 if a < b
65
 */
66
int int_cmp(void * a, void * b) {
67
    return (* (int *) a > * (int*)b) ? 1 : (*(int *)a < * (int *)b) ? -1 : 0;
68
}
69
 
70
int __u8_cmp(void * a, void * b) {
71
    return (* (__u8 *) a > * (__u8 *)b) ? 1 : (*(__u8 *)a < * (__u8 *)b) ? -1 : 0;
72
}
73
 
74
int __u16_cmp(void * a, void * b) {
75
    return (* (__u16 *) a > * (__u16 *)b) ? 1 : (*(__u16 *)a < * (__u16 *)b) ? -1 : 0;
76
}
77
 
78
int __u32_cmp(void * a, void * b) {
79
    return (* (__u32 *) a > * (__u32 *)b) ? 1 : (*(__u32 *)a < * (__u32 *)b) ? -1 : 0;
80
}
81