Rev 2071 | Rev 3386 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 2071 | Rev 2729 | ||
---|---|---|---|
1 | /* |
1 | /* |
2 | * Copyright (c) 2005 Sergey Bondari |
2 | * Copyright (c) 2005 Sergey Bondari |
3 | * All rights reserved. |
3 | * All rights reserved. |
4 | * |
4 | * |
5 | * Redistribution and use in source and binary forms, with or without |
5 | * Redistribution and use in source and binary forms, with or without |
6 | * modification, are permitted provided that the following conditions |
6 | * modification, are permitted provided that the following conditions |
7 | * are met: |
7 | * are met: |
8 | * |
8 | * |
9 | * - Redistributions of source code must retain the above copyright |
9 | * - Redistributions of source code must retain the above copyright |
10 | * notice, this list of conditions and the following disclaimer. |
10 | * notice, this list of conditions and the following disclaimer. |
11 | * - Redistributions in binary form must reproduce the above copyright |
11 | * - Redistributions in binary form must reproduce the above copyright |
12 | * notice, this list of conditions and the following disclaimer in the |
12 | * notice, this list of conditions and the following disclaimer in the |
13 | * documentation and/or other materials provided with the distribution. |
13 | * documentation and/or other materials provided with the distribution. |
14 | * - The name of the author may not be used to endorse or promote products |
14 | * - The name of the author may not be used to endorse or promote products |
15 | * derived from this software without specific prior written permission. |
15 | * derived from this software without specific prior written permission. |
16 | * |
16 | * |
17 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
17 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
18 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
18 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
19 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
19 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
20 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
20 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
21 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
21 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
22 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
22 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
23 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
23 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
24 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
24 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
25 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
25 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
26 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
26 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
27 | */ |
27 | */ |
28 | 28 | ||
29 | /** @addtogroup generic |
29 | /** @addtogroup generic |
30 | * @{ |
30 | * @{ |
31 | */ |
31 | */ |
32 | 32 | ||
33 | /** |
33 | /** |
34 | * @file |
34 | * @file |
35 | * @brief Sorting functions. |
35 | * @brief Sorting functions. |
36 | * |
36 | * |
37 | * This files contains functions implementing several sorting |
37 | * This files contains functions implementing several sorting |
38 | * algorithms (e.g. quick sort and bubble sort). |
38 | * algorithms (e.g. quick sort and bubble sort). |
39 | */ |
39 | */ |
40 | 40 | ||
41 | #include <mm/slab.h> |
41 | #include <mm/slab.h> |
42 | #include <memstr.h> |
42 | #include <memstr.h> |
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, count_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, count_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. |
55 | * |
55 | * |
56 | * This function _can_ sleep |
56 | * This function _can_ sleep |
57 | * |
57 | * |
58 | * @param data Pointer to data to be sorted. |
58 | * @param data Pointer to data to be sorted. |
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, count_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; |
70 | 70 | ||
71 | if (e_size > EBUFSIZE) { |
71 | if (e_size > EBUFSIZE) { |
72 | pivot = (void *) malloc(e_size, 0); |
72 | pivot = (void *) malloc(e_size, 0); |
73 | tmp = (void *) malloc(e_size, 0); |
73 | tmp = (void *) malloc(e_size, 0); |
74 | } |
74 | } |
75 | 75 | ||
76 | _qsort(data, n, e_size, cmp, tmp, pivot); |
76 | _qsort(data, n, e_size, cmp, tmp, pivot); |
77 | 77 | ||
78 | if (e_size > EBUFSIZE) { |
78 | if (e_size > EBUFSIZE) { |
79 | free(tmp); |
79 | free(tmp); |
80 | free(pivot); |
80 | free(pivot); |
81 | } |
81 | } |
82 | } |
82 | } |
83 | 83 | ||
84 | /** Quicksort |
84 | /** Quicksort |
85 | * |
85 | * |
86 | * Apply generic quicksort algorithm on supplied data, using pre-allocated buffers. |
86 | * Apply generic quicksort algorithm on supplied data, using pre-allocated buffers. |
87 | * |
87 | * |
88 | * @param data Pointer to data to be sorted. |
88 | * @param data Pointer to data to be sorted. |
89 | * @param n Number of elements to be sorted. |
89 | * @param n Number of elements to be sorted. |
90 | * @param e_size Size of one element. |
90 | * @param e_size Size of one element. |
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, count_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 | int i = 0, j = n - 1; |
99 | int i = 0, j = n - 1; |
100 | 100 | ||
101 | memcpy(pivot, data, e_size); |
101 | memcpy(pivot, data, e_size); |
102 | 102 | ||
103 | while (1) { |
103 | while (1) { |
104 | while ((cmp(data + i * e_size, pivot) < 0) && i < n) i++; |
104 | while ((cmp(data + i * e_size, pivot) < 0) && i < n) i++; |
105 | while ((cmp(data + j * e_size, pivot) >=0) && j > 0) j--; |
105 | while ((cmp(data + j * e_size, pivot) >=0) && j > 0) j--; |
106 | if (i<j) { |
106 | if (i<j) { |
107 | memcpy(tmp, data + i * e_size, e_size); |
107 | memcpy(tmp, data + i * e_size, e_size); |
108 | memcpy(data + i * e_size, data + j * e_size, e_size); |
108 | memcpy(data + i * e_size, data + j * e_size, e_size); |
109 | memcpy(data + j * e_size, tmp, e_size); |
109 | memcpy(data + j * e_size, tmp, e_size); |
110 | } else { |
110 | } else { |
111 | break; |
111 | break; |
112 | } |
112 | } |
113 | } |
113 | } |
114 | 114 | ||
115 | _qsort(data, j + 1, e_size, cmp, tmp, pivot); |
115 | _qsort(data, j + 1, e_size, cmp, tmp, pivot); |
116 | _qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp, tmp, pivot); |
116 | _qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp, tmp, pivot); |
117 | } else { |
117 | } else { |
118 | _bubblesort(data, n, e_size, cmp, tmp); |
118 | _bubblesort(data, n, e_size, cmp, tmp); |
119 | } |
119 | } |
120 | } |
120 | } |
121 | 121 | ||
122 | /** Bubblesort wrapper |
122 | /** Bubblesort wrapper |
123 | * |
123 | * |
124 | * This is only a wrapper that takes care of memory allocation for storing |
124 | * This is only a wrapper that takes care of memory allocation for storing |
125 | * the slot element for generic bubblesort algorithm. |
125 | * the slot element for generic bubblesort algorithm. |
126 | * |
126 | * |
127 | * @param data Pointer to data to be sorted. |
127 | * @param data Pointer to data to be sorted. |
128 | * @param n Number of elements to be sorted. |
128 | * @param n Number of elements to be sorted. |
129 | * @param e_size Size of one element. |
129 | * @param e_size Size of one element. |
130 | * @param cmp Comparator function. |
130 | * @param cmp Comparator function. |
131 | * |
131 | * |
132 | */ |
132 | */ |
133 | void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) |
133 | void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) |
134 | { |
134 | { |
135 | uint8_t buf_slot[EBUFSIZE]; |
135 | uint8_t buf_slot[EBUFSIZE]; |
136 | void * slot = buf_slot; |
136 | void * slot = buf_slot; |
137 | 137 | ||
138 | if (e_size > EBUFSIZE) { |
138 | if (e_size > EBUFSIZE) { |
139 | slot = (void *) malloc(e_size, 0); |
139 | slot = (void *) malloc(e_size, 0); |
140 | } |
140 | } |
141 | 141 | ||
142 | _bubblesort(data, n, e_size, cmp, slot); |
142 | _bubblesort(data, n, e_size, cmp, slot); |
143 | 143 | ||
144 | if (e_size > EBUFSIZE) { |
144 | if (e_size > EBUFSIZE) { |
145 | free(slot); |
145 | free(slot); |
146 | } |
146 | } |
147 | } |
147 | } |
148 | 148 | ||
149 | /** Bubblesort |
149 | /** Bubblesort |
150 | * |
150 | * |
151 | * Apply generic bubblesort algorithm on supplied data, using pre-allocated buffer. |
151 | * Apply generic bubblesort algorithm on supplied data, using pre-allocated buffer. |
152 | * |
152 | * |
153 | * @param data Pointer to data to be sorted. |
153 | * @param data Pointer to data to be sorted. |
154 | * @param n Number of elements to be sorted. |
154 | * @param n Number of elements to be sorted. |
155 | * @param e_size Size of one element. |
155 | * @param e_size Size of one element. |
156 | * @param cmp Comparator function. |
156 | * @param cmp Comparator function. |
157 | * @param slot Pointer to scratch memory buffer e_size bytes long. |
157 | * @param slot Pointer to scratch memory buffer e_size bytes long. |
158 | * |
158 | * |
159 | */ |
159 | */ |
160 | void _bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot) |
160 | void _bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot) |
161 | { |
161 | { |
162 | bool done = false; |
162 | bool done = false; |
163 | void * p; |
163 | void * p; |
164 | 164 | ||
165 | while (!done) { |
165 | while (!done) { |
166 | done = true; |
166 | done = true; |
167 | for (p = data; p < data + e_size * (n - 1); p = p + e_size) { |
167 | for (p = data; p < data + e_size * (n - 1); p = p + e_size) { |
168 | if (cmp(p, p + e_size) == 1) { |
168 | if (cmp(p, p + e_size) == 1) { |
169 | memcpy(slot, p, e_size); |
169 | memcpy(slot, p, e_size); |
170 | memcpy(p, p + e_size, e_size); |
170 | memcpy(p, p + e_size, e_size); |
171 | memcpy(p + e_size, slot, e_size); |
171 | memcpy(p + e_size, slot, e_size); |
172 | done = false; |
172 | done = false; |
173 | } |
173 | } |
174 | } |
174 | } |
175 | } |
175 | } |
176 | 176 | ||
177 | } |
177 | } |
178 | 178 | ||
179 | /* |
179 | /* |
180 | * Comparator returns 1 if a > b, 0 if a == b, -1 if a < b |
180 | * Comparator returns 1 if a > b, 0 if a == b, -1 if a < b |
181 | */ |
181 | */ |
182 | int int_cmp(void * a, void * b) |
182 | int int_cmp(void * a, void * b) |
183 | { |
183 | { |
184 | return (* (int *) a > * (int*)b) ? 1 : (*(int *)a < * (int *)b) ? -1 : 0; |
184 | return (* (int *) a > * (int*)b) ? 1 : (*(int *)a < * (int *)b) ? -1 : 0; |
185 | } |
185 | } |
186 | 186 | ||
187 | int uint8_t_cmp(void * a, void * b) |
187 | int uint8_t_cmp(void * a, void * b) |
188 | { |
188 | { |
189 | return (* (uint8_t *) a > * (uint8_t *)b) ? 1 : (*(uint8_t *)a < * (uint8_t *)b) ? -1 : 0; |
189 | return (* (uint8_t *) a > * (uint8_t *)b) ? 1 : (*(uint8_t *)a < * (uint8_t *)b) ? -1 : 0; |
190 | } |
190 | } |
191 | 191 | ||
192 | int uint16_t_cmp(void * a, void * b) |
192 | int uint16_t_cmp(void * a, void * b) |
193 | { |
193 | { |
194 | return (* (uint16_t *) a > * (uint16_t *)b) ? 1 : (*(uint16_t *)a < * (uint16_t *)b) ? -1 : 0; |
194 | return (* (uint16_t *) a > * (uint16_t *)b) ? 1 : (*(uint16_t *)a < * (uint16_t *)b) ? -1 : 0; |
195 | } |
195 | } |
196 | 196 | ||
197 | int uint32_t_cmp(void * a, void * b) |
197 | int uint32_t_cmp(void * a, void * b) |
198 | { |
198 | { |
199 | return (* (uint32_t *) a > * (uint32_t *)b) ? 1 : (*(uint32_t *)a < * (uint32_t *)b) ? -1 : 0; |
199 | return (* (uint32_t *) a > * (uint32_t *)b) ? 1 : (*(uint32_t *)a < * (uint32_t *)b) ? -1 : 0; |
200 | } |
200 | } |
201 | 201 | ||
202 | /** @} |
202 | /** @} |
203 | */ |
203 | */ |
204 | 204 |