Rev 822 | Rev 1702 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 822 | Rev 1264 | ||
---|---|---|---|
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 | /** |
|
- | 30 | * @file sort.c |
|
- | 31 | * @brief Sorting functions. |
|
- | 32 | * |
|
- | 33 | * This files contains functions implementing several sorting |
|
- | 34 | * algorithms (e.g. quick sort and bubble sort). |
|
- | 35 | */ |
|
- | 36 | ||
29 | #include <mm/slab.h> |
37 | #include <mm/slab.h> |
30 | #include <memstr.h> |
38 | #include <memstr.h> |
31 | #include <sort.h> |
39 | #include <sort.h> |
32 | #include <panic.h> |
40 | #include <panic.h> |
33 | 41 | ||
34 | #define EBUFSIZE 32 |
42 | #define EBUFSIZE 32 |
35 | 43 | ||
36 | void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *tmp, void *pivot); |
44 | 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); |
45 | void _bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot); |
38 | 46 | ||
39 | /** Quicksort wrapper |
47 | /** Quicksort wrapper |
40 | * |
48 | * |
41 | * This is only a wrapper that takes care of memory allocations for storing |
49 | * This is only a wrapper that takes care of memory allocations for storing |
42 | * the pivot and temporary elements for generic quicksort algorithm. |
50 | * the pivot and temporary elements for generic quicksort algorithm. |
43 | * |
51 | * |
44 | * This function _can_ sleep |
52 | * This function _can_ sleep |
45 | * |
53 | * |
46 | * @param data Pointer to data to be sorted. |
54 | * @param data Pointer to data to be sorted. |
47 | * @param n Number of elements to be sorted. |
55 | * @param n Number of elements to be sorted. |
48 | * @param e_size Size of one element. |
56 | * @param e_size Size of one element. |
49 | * @param cmp Comparator function. |
57 | * @param cmp Comparator function. |
50 | * |
58 | * |
51 | */ |
59 | */ |
52 | void qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) |
60 | void qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) |
53 | { |
61 | { |
54 | __u8 buf_tmp[EBUFSIZE]; |
62 | __u8 buf_tmp[EBUFSIZE]; |
55 | __u8 buf_pivot[EBUFSIZE]; |
63 | __u8 buf_pivot[EBUFSIZE]; |
56 | void * tmp = buf_tmp; |
64 | void * tmp = buf_tmp; |
57 | void * pivot = buf_pivot; |
65 | void * pivot = buf_pivot; |
58 | 66 | ||
59 | if (e_size > EBUFSIZE) { |
67 | if (e_size > EBUFSIZE) { |
60 | pivot = (void *) malloc(e_size, 0); |
68 | pivot = (void *) malloc(e_size, 0); |
61 | tmp = (void *) malloc(e_size, 0); |
69 | tmp = (void *) malloc(e_size, 0); |
62 | } |
70 | } |
63 | 71 | ||
64 | _qsort(data, n, e_size, cmp, tmp, pivot); |
72 | _qsort(data, n, e_size, cmp, tmp, pivot); |
65 | 73 | ||
66 | if (e_size > EBUFSIZE) { |
74 | if (e_size > EBUFSIZE) { |
67 | free(tmp); |
75 | free(tmp); |
68 | free(pivot); |
76 | free(pivot); |
69 | } |
77 | } |
70 | } |
78 | } |
71 | 79 | ||
72 | /** Quicksort |
80 | /** Quicksort |
73 | * |
81 | * |
74 | * Apply generic quicksort algorithm on supplied data, using pre-allocated buffers. |
82 | * Apply generic quicksort algorithm on supplied data, using pre-allocated buffers. |
75 | * |
83 | * |
76 | * @param data Pointer to data to be sorted. |
84 | * @param data Pointer to data to be sorted. |
77 | * @param n Number of elements to be sorted. |
85 | * @param n Number of elements to be sorted. |
78 | * @param e_size Size of one element. |
86 | * @param e_size Size of one element. |
79 | * @param cmp Comparator function. |
87 | * @param cmp Comparator function. |
80 | * @param tmp Pointer to scratch memory buffer e_size bytes long. |
88 | * @param tmp Pointer to scratch memory buffer e_size bytes long. |
81 | * @param pivot Pointer to scratch memory buffer e_size bytes long. |
89 | * @param pivot Pointer to scratch memory buffer e_size bytes long. |
82 | * |
90 | * |
83 | */ |
91 | */ |
84 | void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *tmp, void *pivot) |
92 | void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *tmp, void *pivot) |
85 | { |
93 | { |
86 | if (n > 4) { |
94 | if (n > 4) { |
87 | int i = 0, j = n - 1; |
95 | int i = 0, j = n - 1; |
88 | 96 | ||
89 | memcpy(pivot, data, e_size); |
97 | memcpy(pivot, data, e_size); |
90 | 98 | ||
91 | while (1) { |
99 | while (1) { |
92 | while ((cmp(data + i * e_size, pivot) < 0) && i < n) i++; |
100 | while ((cmp(data + i * e_size, pivot) < 0) && i < n) i++; |
93 | while ((cmp(data + j * e_size, pivot) >=0) && j > 0) j--; |
101 | while ((cmp(data + j * e_size, pivot) >=0) && j > 0) j--; |
94 | if (i<j) { |
102 | if (i<j) { |
95 | memcpy(tmp, data + i * e_size, e_size); |
103 | memcpy(tmp, data + i * e_size, e_size); |
96 | memcpy(data + i * e_size, data + j * e_size, e_size); |
104 | memcpy(data + i * e_size, data + j * e_size, e_size); |
97 | memcpy(data + j * e_size, tmp, e_size); |
105 | memcpy(data + j * e_size, tmp, e_size); |
98 | } else { |
106 | } else { |
99 | break; |
107 | break; |
100 | } |
108 | } |
101 | } |
109 | } |
102 | 110 | ||
103 | _qsort(data, j + 1, e_size, cmp, tmp, pivot); |
111 | _qsort(data, j + 1, e_size, cmp, tmp, pivot); |
104 | _qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp, tmp, pivot); |
112 | _qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp, tmp, pivot); |
105 | } else { |
113 | } else { |
106 | _bubblesort(data, n, e_size, cmp, tmp); |
114 | _bubblesort(data, n, e_size, cmp, tmp); |
107 | } |
115 | } |
108 | } |
116 | } |
109 | 117 | ||
110 | /** Bubblesort wrapper |
118 | /** Bubblesort wrapper |
111 | * |
119 | * |
112 | * This is only a wrapper that takes care of memory allocation for storing |
120 | * This is only a wrapper that takes care of memory allocation for storing |
113 | * the slot element for generic bubblesort algorithm. |
121 | * the slot element for generic bubblesort algorithm. |
114 | * |
122 | * |
115 | * @param data Pointer to data to be sorted. |
123 | * @param data Pointer to data to be sorted. |
116 | * @param n Number of elements to be sorted. |
124 | * @param n Number of elements to be sorted. |
117 | * @param e_size Size of one element. |
125 | * @param e_size Size of one element. |
118 | * @param cmp Comparator function. |
126 | * @param cmp Comparator function. |
119 | * |
127 | * |
120 | */ |
128 | */ |
121 | void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) |
129 | void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) |
122 | { |
130 | { |
123 | __u8 buf_slot[EBUFSIZE]; |
131 | __u8 buf_slot[EBUFSIZE]; |
124 | void * slot = buf_slot; |
132 | void * slot = buf_slot; |
125 | 133 | ||
126 | if (e_size > EBUFSIZE) { |
134 | if (e_size > EBUFSIZE) { |
127 | slot = (void *) malloc(e_size, 0); |
135 | slot = (void *) malloc(e_size, 0); |
128 | } |
136 | } |
129 | 137 | ||
130 | _bubblesort(data, n, e_size, cmp, slot); |
138 | _bubblesort(data, n, e_size, cmp, slot); |
131 | 139 | ||
132 | if (e_size > EBUFSIZE) { |
140 | if (e_size > EBUFSIZE) { |
133 | free(slot); |
141 | free(slot); |
134 | } |
142 | } |
135 | } |
143 | } |
136 | 144 | ||
137 | /** Bubblesort |
145 | /** Bubblesort |
138 | * |
146 | * |
139 | * Apply generic bubblesort algorithm on supplied data, using pre-allocated buffer. |
147 | * Apply generic bubblesort algorithm on supplied data, using pre-allocated buffer. |
140 | * |
148 | * |
141 | * @param data Pointer to data to be sorted. |
149 | * @param data Pointer to data to be sorted. |
142 | * @param n Number of elements to be sorted. |
150 | * @param n Number of elements to be sorted. |
143 | * @param e_size Size of one element. |
151 | * @param e_size Size of one element. |
144 | * @param cmp Comparator function. |
152 | * @param cmp Comparator function. |
145 | * @param slot Pointer to scratch memory buffer e_size bytes long. |
153 | * @param slot Pointer to scratch memory buffer e_size bytes long. |
146 | * |
154 | * |
147 | */ |
155 | */ |
148 | void _bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot) |
156 | void _bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot) |
149 | { |
157 | { |
150 | bool done = false; |
158 | bool done = false; |
151 | void * p; |
159 | void * p; |
152 | 160 | ||
153 | while (!done) { |
161 | while (!done) { |
154 | done = true; |
162 | done = true; |
155 | for (p = data; p < data + e_size * (n - 1); p = p + e_size) { |
163 | for (p = data; p < data + e_size * (n - 1); p = p + e_size) { |
156 | if (cmp(p, p + e_size) == 1) { |
164 | if (cmp(p, p + e_size) == 1) { |
157 | memcpy(slot, p, e_size); |
165 | memcpy(slot, p, e_size); |
158 | memcpy(p, p + e_size, e_size); |
166 | memcpy(p, p + e_size, e_size); |
159 | memcpy(p + e_size, slot, e_size); |
167 | memcpy(p + e_size, slot, e_size); |
160 | done = false; |
168 | done = false; |
161 | } |
169 | } |
162 | } |
170 | } |
163 | } |
171 | } |
164 | 172 | ||
165 | } |
173 | } |
166 | 174 | ||
167 | /* |
175 | /* |
168 | * Comparator returns 1 if a > b, 0 if a == b, -1 if a < b |
176 | * Comparator returns 1 if a > b, 0 if a == b, -1 if a < b |
169 | */ |
177 | */ |
170 | int int_cmp(void * a, void * b) |
178 | int int_cmp(void * a, void * b) |
171 | { |
179 | { |
172 | return (* (int *) a > * (int*)b) ? 1 : (*(int *)a < * (int *)b) ? -1 : 0; |
180 | return (* (int *) a > * (int*)b) ? 1 : (*(int *)a < * (int *)b) ? -1 : 0; |
173 | } |
181 | } |
174 | 182 | ||
175 | int __u8_cmp(void * a, void * b) |
183 | int __u8_cmp(void * a, void * b) |
176 | { |
184 | { |
177 | return (* (__u8 *) a > * (__u8 *)b) ? 1 : (*(__u8 *)a < * (__u8 *)b) ? -1 : 0; |
185 | return (* (__u8 *) a > * (__u8 *)b) ? 1 : (*(__u8 *)a < * (__u8 *)b) ? -1 : 0; |
178 | } |
186 | } |
179 | 187 | ||
180 | int __u16_cmp(void * a, void * b) |
188 | int __u16_cmp(void * a, void * b) |
181 | { |
189 | { |
182 | return (* (__u16 *) a > * (__u16 *)b) ? 1 : (*(__u16 *)a < * (__u16 *)b) ? -1 : 0; |
190 | return (* (__u16 *) a > * (__u16 *)b) ? 1 : (*(__u16 *)a < * (__u16 *)b) ? -1 : 0; |
183 | } |
191 | } |
184 | 192 | ||
185 | int __u32_cmp(void * a, void * b) |
193 | int __u32_cmp(void * a, void * b) |
186 | { |
194 | { |
187 | return (* (__u32 *) a > * (__u32 *)b) ? 1 : (*(__u32 *)a < * (__u32 *)b) ? -1 : 0; |
195 | return (* (__u32 *) a > * (__u32 *)b) ? 1 : (*(__u32 *)a < * (__u32 *)b) ? -1 : 0; |
188 | } |
196 | } |
189 | 197 |