Subversion Repositories HelenOS

Rev

Rev 350 | Rev 430 | Go to most recent revision | Show entire file | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 350 Rev 351
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
void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *tmp, void *pivot);
-
 
37
void _bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot);
-
 
38
 
-
 
39
/** Quicksort wrapper
-
 
40
 *
-
 
41
 * This is only a wrapper that takes care of memory allocations for storing
-
 
42
 * the pivot and temporary elements for generic quicksort algorithm.
-
 
43
 *
-
 
44
 * @param data Pointer to data to be sorted.
-
 
45
 * @param n Number of elements to be sorted.
-
 
46
 * @param e_size Size of one element.
-
 
47
 * @param cmp Comparator function.
-
 
48
 *
-
 
49
 */
36
void qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b))
50
void qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b))
37
{
51
{
38
    __u8 buf_tmp[EBUFSIZE];
52
    __u8 buf_tmp[EBUFSIZE];
39
    __u8 buf_pivot[EBUFSIZE];
53
    __u8 buf_pivot[EBUFSIZE];
40
    void * tmp = buf_tmp;
54
    void * tmp = buf_tmp;
Line 47... Line 61...
47
        if (!tmp || !pivot) {
61
        if (!tmp || !pivot) {
48
            panic("Cannot allocate memory\n");
62
            panic("Cannot allocate memory\n");
49
        }
63
        }
50
    }
64
    }
51
 
65
 
-
 
66
    _qsort(data, n, e_size, cmp, tmp, pivot);
-
 
67
   
-
 
68
    if (e_size > EBUFSIZE) {
-
 
69
        free(tmp);
-
 
70
        free(pivot);
-
 
71
    }
-
 
72
}
-
 
73
 
-
 
74
/** Quicksort
-
 
75
 *
-
 
76
 * Apply generic quicksort algorithm on supplied data, using pre-allocated buffers.
-
 
77
 *
-
 
78
 * @param data Pointer to data to be sorted.
-
 
79
 * @param n Number of elements to be sorted.
-
 
80
 * @param e_size Size of one element.
-
 
81
 * @param cmp Comparator function.
-
 
82
 * @param tmp Pointer to scratch memory buffer e_size bytes long.
-
 
83
 * @param pivot Pointer to scratch memory buffer e_size bytes long.
-
 
84
 *
-
 
85
 */
-
 
86
void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *tmp, void *pivot)
-
 
87
{
52
    if (n > 4) {
88
    if (n > 4) {
53
        int i = 0, j = n - 1;
89
        int i = 0, j = n - 1;
54
 
90
 
55
        memcpy(pivot, data, e_size);
91
        memcpy(pivot, data, e_size);
56
 
92
 
Line 64... Line 100...
64
            } else {
100
            } else {
65
                break;
101
                break;
66
            }
102
            }
67
        }
103
        }
68
 
104
 
69
        qsort(data, j + 1, e_size, cmp);
105
        _qsort(data, j + 1, e_size, cmp, tmp, pivot);
70
        qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp);
106
        _qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp, tmp, pivot);
71
    } else {
107
    } else {
72
        bubblesort(data, n, e_size, cmp);
108
        _bubblesort(data, n, e_size, cmp, tmp);
73
    }
109
    }
74
 
-
 
75
   
-
 
76
    if (e_size > EBUFSIZE) {
-
 
77
        free(tmp);
-
 
78
        free(pivot);
-
 
79
    }
110
}
80
}
-
 
81
 
-
 
82
 
111
 
-
 
112
/** Bubblesort wrapper
-
 
113
 *
-
 
114
 * This is only a wrapper that takes care of memory allocation for storing
-
 
115
 * the slot element for generic bubblesort algorithm.
-
 
116
 *
-
 
117
 * @param data Pointer to data to be sorted.
-
 
118
 * @param n Number of elements to be sorted.
-
 
119
 * @param e_size Size of one element.
-
 
120
 * @param cmp Comparator function.
-
 
121
 *
-
 
122
 */
83
void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b))
123
void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b))
84
{
124
{
85
    __u8 buf_slot[EBUFSIZE];
125
    __u8 buf_slot[EBUFSIZE];
86
    bool done = false;
-
 
87
    void * p;
-
 
88
    void * slot = buf_slot;
126
    void * slot = buf_slot;
89
   
127
   
90
    if (e_size > EBUFSIZE) {
128
    if (e_size > EBUFSIZE) {
91
        slot = (void *) malloc(e_size);
129
        slot = (void *) malloc(e_size);
92
       
130
       
93
        if (!slot) {
131
        if (!slot) {
94
            panic("Cannot allocate memory\n");
132
            panic("Cannot allocate memory\n");
95
        }
133
        }
96
    }
134
    }
97
 
135
 
-
 
136
    _bubblesort(data, n, e_size, cmp, slot);
-
 
137
   
-
 
138
    if (e_size > EBUFSIZE) {
-
 
139
        free(slot);
-
 
140
    }
-
 
141
}
-
 
142
 
-
 
143
/** Bubblesort
-
 
144
 *
-
 
145
 * Apply generic bubblesort algorithm on supplied data, using pre-allocated buffer.
-
 
146
 *
-
 
147
 * @param data Pointer to data to be sorted.
-
 
148
 * @param n Number of elements to be sorted.
-
 
149
 * @param e_size Size of one element.
-
 
150
 * @param cmp Comparator function.
-
 
151
 * @param slot Pointer to scratch memory buffer e_size bytes long.
-
 
152
 *
-
 
153
 */
-
 
154
void _bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot)
-
 
155
{
-
 
156
    bool done = false;
-
 
157
    void * p;
-
 
158
 
98
    while (!done) {
159
    while (!done) {
99
        done = true;
160
        done = true;
100
        for (p = data; p < data + e_size * (n - 1); p = p + e_size) {
161
        for (p = data; p < data + e_size * (n - 1); p = p + e_size) {
101
            if (cmp(p, p + e_size) == 1) {
162
            if (cmp(p, p + e_size) == 1) {
102
                memcpy(slot, p, e_size);
163
                memcpy(slot, p, e_size);
Line 105... Line 166...
105
                done = false;
166
                done = false;
106
            }
167
            }
107
        }
168
        }
108
    }
169
    }
109
   
170
 
110
    if (e_size > EBUFSIZE) {   
-
 
111
        free(slot);
-
 
112
    }
-
 
113
}
171
}
114
 
172
 
115
/*
173
/*
116
 * Comparator returns 1 if a > b, 0 if a == b, -1 if a < b
174
 * Comparator returns 1 if a > b, 0 if a == b, -1 if a < b
117
 */
175
 */