Subversion Repositories HelenOS-historic

Rev

Rev 333 | Rev 336 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 333 Rev 335
Line 27... Line 27...
27 
 */
 27 
 */
28 
 
 28 
 
29 
#include <mm/heap.h>
 29 
#include <mm/heap.h>
30 
#include <memstr.h>
 30 
#include <memstr.h>
31 
#include <sort.h>
 31 
#include <sort.h>
- 
 
 32 
#include <panic.h>
32 
 
 33 
 
- 
 
 34 
static void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void * pivot, void * tmp);
33 
 
 35 
 
- 
 
 36 
/*
- 
 
 37 
 * Wrapper method for quicksort algorithm to decrease amount of allocations
- 
 
 38 
 */
34 
void qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) {
 39 
void qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) {
- 
 
 40 
    void * tmp = (void *) malloc(e_size);
- 
 
 41 
    void * pivot = (void *) malloc(e_size);
- 
 
 42 
   
- 
 
 43 
    if (!tmp || !pivot) {
- 
 
 44 
        panic("qsort(): Cannot allocate memory\n");
- 
 
 45 
    }
- 
 
 46 
 
- 
 
 47 
    _qsort(data, n, e_size, cmp, pivot, tmp);
- 
 
 48 
   
- 
 
 49 
    free(tmp);
- 
 
 50 
    free(pivot);
- 
 
 51 
}
- 
 
 52 
 
- 
 
 53 
 
- 
 
 54 
void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) {
- 
 
 55 
    bool done = false;
- 
 
 56 
    void * p;
- 
 
 57 
    void * slot = (void *) malloc(e_size);
- 
 
 58 
 
- 
 
 59 
    while (!done) {
- 
 
 60 
        done = true;
- 
 
 61 
        for (p = data; p < data + e_size * (n - 1); p = p + e_size) {
- 
 
 62 
            if (cmp(p, p + e_size) == 1) {
- 
 
 63 
                memcpy(slot, p, e_size);
- 
 
 64 
                memcpy(p, p + e_size, e_size);
- 
 
 65 
                memcpy(p + e_size, slot, e_size);
- 
 
 66 
                done = false;
- 
 
 67 
            }
- 
 
 68 
        }
- 
 
 69 
    }
- 
 
 70 
   
- 
 
 71 
    free(slot);
- 
 
 72 
}
- 
 
 73 
 
- 
 
 74 
static void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void * pivot, void * tmp) {
35 
    if (n > 4) {
 75 
    if (n > 4) {
36 
        int i = 0, j = n - 1;
 76 
        int i = 0, j = n - 1;
37 
        void * tmp = (void *) malloc(e_size);
 - 
 
38 
        void * pivot = (void *) malloc(e_size);
 - 
 
39 
 
 77 
 
40 
        memcpy(pivot, data, e_size);
 78 
        memcpy(pivot, data, e_size);
41 
 
 79 
 
42 
        while (1) {
 80 
        while (1) {
43 
            while ((cmp(data + i * e_size, pivot) < 0) && i < n) i++;
 81 
            while ((cmp(data + i * e_size, pivot) < 0) && i < n) i++;
Line 49... Line 87...
49 
            } else {
 87 
            } else {
50 
                break;
 88 
                break;
51 
            }
 89 
            }
52 
        }
 90 
        }
53 
 
 91 
 
54 
        free(tmp);
 - 
 
55 
        free(pivot);
 - 
 
56 
 
 - 
 
57 
        qsort(data, j + 1, e_size, cmp);
 92 
        qsort(data, j + 1, e_size, cmp);
58 
        qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp);
 93 
        qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp);
59 
    } else {
 94 
    } else {
60 
        bubblesort(data, n, e_size, cmp);
 95 
        bubblesort(data, n, e_size, cmp);
61 
    }
 96 
    }
62 
}
 97 
}
63 
 
 98 
 
64 
 
 99 
 
65 
void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) {
 - 
 
66 
    bool done = false;
 - 
 
67 
    void * p;
 - 
 
68 
    void * slot = (void *) malloc(e_size);
 - 
 
69 
 
 - 
 
70 
    while (!done) {
 - 
 
71 
        done = true;
 - 
 
72 
        for (p = data; p < data + e_size * (n - 1); p = p + e_size) {
 - 
 
73 
            if (cmp(p, p + e_size) == 1) {
 - 
 
74 
                memcpy(slot, p, e_size);
 - 
 
75 
                memcpy(p, p + e_size, e_size);
 - 
 
76 
                memcpy(p + e_size, slot, e_size);
 - 
 
77 
                done = false;
 - 
 
78 
            }
 - 
 
79 
        }
 - 
 
80 
    }
 - 
 
81 
   
 - 
 
82 
    free(slot);
 - 
 
83 
}
 - 
 
84 
 
 100 
 
85 
/*
 101 
/*
86 
 * Comparator returns 1 if a > b, 0 if a == b, -1 if a < b
 102 
 * Comparator returns 1 if a > b, 0 if a == b, -1 if a < b
87 
 */
 103 
 */
88 
int int_cmp(void * a, void * b) {
 104 
int int_cmp(void * a, void * b) {