Subversion Repositories HelenOS

Rev

Rev 3386 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 3386 Rev 4581
Line 43... Line 43...
43
#include <sort.h>
43
#include <sort.h>
44
#include <panic.h>
44
#include <panic.h>
45
 
45
 
46
#define EBUFSIZE    32
46
#define EBUFSIZE    32
47
 
47
 
48
void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *tmp, void *pivot);
48
void _qsort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *tmp, void *pivot);
49
void _bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot);
49
void _bubblesort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot);
50
 
50
 
51
/** Quicksort wrapper
51
/** Quicksort wrapper
52
 *
52
 *
53
 * This is only a wrapper that takes care of memory allocations for storing
53
 * This is only a wrapper that takes care of memory allocations for storing
54
 * the pivot and temporary elements for generic quicksort algorithm.
54
 * the pivot and temporary elements for generic quicksort algorithm.
Line 59... Line 59...
59
 * @param n Number of elements to be sorted.
59
 * @param n Number of elements to be sorted.
60
 * @param e_size Size of one element.
60
 * @param e_size Size of one element.
61
 * @param cmp Comparator function.
61
 * @param cmp Comparator function.
62
 *
62
 *
63
 */
63
 */
64
void qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b))
64
void qsort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b))
65
{
65
{
66
    uint8_t buf_tmp[EBUFSIZE];
66
    uint8_t buf_tmp[EBUFSIZE];
67
    uint8_t buf_pivot[EBUFSIZE];
67
    uint8_t buf_pivot[EBUFSIZE];
68
    void * tmp = buf_tmp;
68
    void * tmp = buf_tmp;
69
    void * pivot = buf_pivot;
69
    void * pivot = buf_pivot;
Line 91... Line 91...
91
 * @param cmp Comparator function.
91
 * @param cmp Comparator function.
92
 * @param tmp Pointer to scratch memory buffer e_size bytes long.
92
 * @param tmp Pointer to scratch memory buffer e_size bytes long.
93
 * @param pivot Pointer to scratch memory buffer e_size bytes long.
93
 * @param pivot Pointer to scratch memory buffer e_size bytes long.
94
 *
94
 *
95
 */
95
 */
96
void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *tmp, void *pivot)
96
void _qsort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *tmp, void *pivot)
97
{
97
{
98
    if (n > 4) {
98
    if (n > 4) {
99
        unsigned int i = 0, j = n - 1;
99
        unsigned int i = 0, j = n - 1;
100
 
100
 
101
        memcpy(pivot, data, e_size);
101
        memcpy(pivot, data, e_size);
Line 131... Line 131...
131
 * @param n Number of elements to be sorted.
131
 * @param n Number of elements to be sorted.
132
 * @param e_size Size of one element.
132
 * @param e_size Size of one element.
133
 * @param cmp Comparator function.
133
 * @param cmp Comparator function.
134
 *
134
 *
135
 */
135
 */
136
void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b))
136
void bubblesort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b))
137
{
137
{
138
    uint8_t buf_slot[EBUFSIZE];
138
    uint8_t buf_slot[EBUFSIZE];
139
    void * slot = buf_slot;
139
    void * slot = buf_slot;
140
   
140
   
141
    if (e_size > EBUFSIZE) {
141
    if (e_size > EBUFSIZE) {
Line 158... Line 158...
158
 * @param e_size Size of one element.
158
 * @param e_size Size of one element.
159
 * @param cmp Comparator function.
159
 * @param cmp Comparator function.
160
 * @param slot Pointer to scratch memory buffer e_size bytes long.
160
 * @param slot Pointer to scratch memory buffer e_size bytes long.
161
 *
161
 *
162
 */
162
 */
163
void _bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot)
163
void _bubblesort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot)
164
{
164
{
165
    bool done = false;
165
    bool done = false;
166
    void * p;
166
    void * p;
167
 
167
 
168
    while (!done) {
168
    while (!done) {