Subversion Repositories HelenOS-historic

Rev

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

Rev 349 Rev 350
Line 31... Line 31...
31 
#include <sort.h>
 31 
#include <sort.h>
32 
#include <panic.h>
 32 
#include <panic.h>
33 
 
 33 
 
34 
#define EBUFSIZE    32
 34 
#define EBUFSIZE    32
35 
 
 35 
 
36 
static void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void * pivot, void * tmp);
 36 
void qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b))
37 
 
 37 
{
38 
/*
 - 
 
39 
 * Wrapper method for quicksort algorithm to decrease amount of allocations
 - 
 
40 
 */
 - 
 
41 
void qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) {
 - 
 
42 
    __u8 buf_tmp[EBUFSIZE];
 38 
    __u8 buf_tmp[EBUFSIZE];
43 
    __u8 buf_pivot[EBUFSIZE];
 39 
    __u8 buf_pivot[EBUFSIZE];
44 
    void * tmp = buf_tmp;
 40 
    void * tmp = buf_tmp;
45 
    void * pivot = buf_pivot;
 41 
    void * pivot = buf_pivot;
46 
 
 42 
 
Line 51... Line 47...
51 
        if (!tmp || !pivot) {
 47 
        if (!tmp || !pivot) {
52 
            panic("Cannot allocate memory\n");
 48 
            panic("Cannot allocate memory\n");
53 
        }
 49 
        }
54 
    }
 50 
    }
55 
 
 51 
 
- 
 
 52 
    if (n > 4) {
- 
 
 53 
        int i = 0, j = n - 1;
- 
 
 54 
 
- 
 
 55 
        memcpy(pivot, data, e_size);
- 
 
 56 
 
- 
 
 57 
        while (1) {
- 
 
 58 
            while ((cmp(data + i * e_size, pivot) < 0) && i < n) i++;
- 
 
 59 
            while ((cmp(data + j * e_size, pivot) >=0) && j > 0) j--;
- 
 
 60 
            if (i<j) {
- 
 
 61 
                memcpy(tmp, data + i * e_size, e_size);
- 
 
 62 
                memcpy(data + i * e_size, data + j * e_size, e_size);
- 
 
 63 
                memcpy(data + j * e_size, tmp, e_size);
- 
 
 64 
            } else {
- 
 
 65 
                break;
- 
 
 66 
            }
- 
 
 67 
        }
- 
 
 68 
 
56 
    _qsort(data, n, e_size, cmp, pivot, tmp);
 69 
        qsort(data, j + 1, e_size, cmp);
- 
 
 70 
        qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp);
- 
 
 71 
    } else {
- 
 
 72 
        bubblesort(data, n, e_size, cmp);
- 
 
 73 
    }
- 
 
 74 
 
57 
   
 75 
   
58 
    if (e_size > EBUFSIZE) {
 76 
    if (e_size > EBUFSIZE) {
59 
        free(tmp);
 77 
        free(tmp);
60 
        free(pivot);
 78 
        free(pivot);
61 
    }
 79 
    }
62 
}
 80 
}
63 
 
 81 
 
64 
 
 82 
 
65 
void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) {
 83 
void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b))
- 
 
 84 
{
66 
    __u8 buf_slot[EBUFSIZE];
 85 
    __u8 buf_slot[EBUFSIZE];
67 
    bool done = false;
 86 
    bool done = false;
68 
    void * p;
 87 
    void * p;
69 
    void * slot = buf_slot;
 88 
    void * slot = buf_slot;
70 
   
 89 
   
Line 91... Line 110...
91 
    if (e_size > EBUFSIZE) {   
 110 
    if (e_size > EBUFSIZE) {   
92 
        free(slot);
 111 
        free(slot);
93 
    }
 112 
    }
94 
}
 113 
}
95 
 
 114 
 
96 
static void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void * pivot, void * tmp) {
 - 
 
97 
    if (n > 4) {
 - 
 
98 
        int i = 0, j = n - 1;
 - 
 
99 
 
 - 
 
100 
        memcpy(pivot, data, e_size);
 - 
 
101 
 
 - 
 
102 
        while (1) {
 - 
 
103 
            while ((cmp(data + i * e_size, pivot) < 0) && i < n) i++;
 - 
 
104 
            while ((cmp(data + j * e_size, pivot) >=0) && j > 0) j--;
 - 
 
105 
            if (i<j) {
 - 
 
106 
                memcpy(tmp, data + i * e_size, e_size);
 - 
 
107 
                memcpy(data + i * e_size, data + j * e_size, e_size);
 - 
 
108 
                memcpy(data + j * e_size, tmp, e_size);
 - 
 
109 
            } else {
 - 
 
110 
                break;
 - 
 
111 
            }
 - 
 
112 
        }
 - 
 
113 
 
 - 
 
114 
        qsort(data, j + 1, e_size, cmp);
 - 
 
115 
        qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp);
 - 
 
116 
    } else {
 - 
 
117 
        bubblesort(data, n, e_size, cmp);
 - 
 
118 
    }
 - 
 
119 
}
 - 
 
120 
 
 - 
 
121 
 
 - 
 
122 
 
 - 
 
123 
/*
 115 
/*
124 
 * Comparator returns 1 if a > b, 0 if a == b, -1 if a < b
 116 
 * Comparator returns 1 if a > b, 0 if a == b, -1 if a < b
125 
 */
 117 
 */
126 
int int_cmp(void * a, void * b) {
 118 
int int_cmp(void * a, void * b)
- 
 
 119 
{
127 
    return (* (int *) a > * (int*)b) ? 1 : (*(int *)a < * (int *)b) ? -1 : 0;
 120 
    return (* (int *) a > * (int*)b) ? 1 : (*(int *)a < * (int *)b) ? -1 : 0;
128 
}
 121 
}
129 
 
 122 
 
130 
int __u8_cmp(void * a, void * b) {
 123 
int __u8_cmp(void * a, void * b)
- 
 
 124 
{
131 
    return (* (__u8 *) a > * (__u8 *)b) ? 1 : (*(__u8 *)a < * (__u8 *)b) ? -1 : 0;
 125 
    return (* (__u8 *) a > * (__u8 *)b) ? 1 : (*(__u8 *)a < * (__u8 *)b) ? -1 : 0;
132 
}
 126 
}
133 
 
 127 
 
134 
int __u16_cmp(void * a, void * b) {
 128 
int __u16_cmp(void * a, void * b)
- 
 
 129 
{
135 
    return (* (__u16 *) a > * (__u16 *)b) ? 1 : (*(__u16 *)a < * (__u16 *)b) ? -1 : 0;
 130 
    return (* (__u16 *) a > * (__u16 *)b) ? 1 : (*(__u16 *)a < * (__u16 *)b) ? -1 : 0;
136 
}
 131 
}
137 
 
 132 
 
138 
int __u32_cmp(void * a, void * b) {
 133 
int __u32_cmp(void * a, void * b)
- 
 
 134 
{
139 
    return (* (__u32 *) a > * (__u32 *)b) ? 1 : (*(__u32 *)a < * (__u32 *)b) ? -1 : 0;
 135 
    return (* (__u32 *) a > * (__u32 *)b) ? 1 : (*(__u32 *)a < * (__u32 *)b) ? -1 : 0;
140 
}
 136 
}
141 
 
 -