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 
 */