Subversion Repositories HelenOS-historic

Rev

Rev 333 | Rev 336 | Go to most recent revision | Show entire file | Regard 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)) {
35 
    if (n > 4) {
 - 
 
36 
        int i = 0, j = n - 1;
 - 
 
37 
        void * tmp = (void *) malloc(e_size);
 40 
    void * tmp = (void *) malloc(e_size);
38 
        void * pivot = (void *) malloc(e_size);
 41 
    void * pivot = (void *) malloc(e_size);
39 
 
 42 
   
40 
        memcpy(pivot, data, e_size);
 - 
 
41 
 
 - 
 
42 
        while (1) {
 - 
 
43 
            while ((cmp(data + i * e_size, pivot) < 0) && i < n) i++;
 - 
 
44 
            while ((cmp(data + j * e_size, pivot) >=0) && j > 0) j--;
 - 
 
45 
            if (i<j) {
 43 
    if (!tmp || !pivot) {
46 
                memcpy(tmp, data + i * e_size, e_size);
 44 
        panic("qsort(): Cannot allocate memory\n");
47 
                memcpy(data + i * e_size, data + j * e_size, e_size);
 - 
 
48 
                memcpy(data + j * e_size, tmp, e_size);
 - 
 
49 
            } else {
 - 
 
50 
                break;
 - 
 
51 
            }
 - 
 
52 
        }
 45 
    }
53 
 
 46 
 
- 
 
 47 
    _qsort(data, n, e_size, cmp, pivot, tmp);
- 
 
 48 
   
54 
        free(tmp);
 49 
    free(tmp);
55 
        free(pivot);
 50 
    free(pivot);
56 
 
 - 
 
57 
        qsort(data, j + 1, e_size, cmp);
 - 
 
58 
        qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp);
 - 
 
59 
    } else {
 - 
 
60 
        bubblesort(data, n, e_size, cmp);
 - 
 
61 
    }
 - 
 
62 
}
 51 
}
63 
 
 52 
 
64 
 
 53 
 
65 
void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) {
 54 
void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) {
66 
    bool done = false;
 55 
    bool done = false;
Line 80... Line 69...
80 
    }
 69 
    }
81 
   
 70 
   
82 
    free(slot);
 71 
    free(slot);
83 
}
 72 
}
84 
 
 73 
 
- 
 
 74 
static void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void * pivot, void * tmp) {
- 
 
 75 
    if (n > 4) {
- 
 
 76 
        int i = 0, j = n - 1;
- 
 
 77 
 
- 
 
 78 
        memcpy(pivot, data, e_size);
- 
 
 79 
 
- 
 
 80 
        while (1) {
- 
 
 81 
            while ((cmp(data + i * e_size, pivot) < 0) && i < n) i++;
- 
 
 82 
            while ((cmp(data + j * e_size, pivot) >=0) && j > 0) j--;
- 
 
 83 
            if (i<j) {
- 
 
 84 
                memcpy(tmp, data + i * e_size, e_size);
- 
 
 85 
                memcpy(data + i * e_size, data + j * e_size, e_size);
- 
 
 86 
                memcpy(data + j * e_size, tmp, e_size);
- 
 
 87 
            } else {
- 
 
 88 
                break;
- 
 
 89 
            }
- 
 
 90 
        }
- 
 
 91 
 
- 
 
 92 
        qsort(data, j + 1, e_size, cmp);
- 
 
 93 
        qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp);
- 
 
 94 
    } else {
- 
 
 95 
        bubblesort(data, n, e_size, cmp);
- 
 
 96 
    }
- 
 
 97 
}
- 
 
 98 
 
- 
 
 99 
 
- 
 
 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) {
89 
    return (* (int *) a > * (int*)b) ? 1 : (*(int *)a < * (int *)b) ? -1 : 0;
 105 
    return (* (int *) a > * (int*)b) ? 1 : (*(int *)a < * (int *)b) ? -1 : 0;