Rev 350 | Rev 430 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 350 | Rev 351 | ||
---|---|---|---|
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 | #include <mm/heap.h> |
29 | #include <mm/heap.h> |
30 | #include <memstr.h> |
30 | #include <memstr.h> |
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; |
41 | void * pivot = buf_pivot; |
55 | void * pivot = buf_pivot; |
42 | 56 | ||
43 | if (e_size > EBUFSIZE) { |
57 | if (e_size > EBUFSIZE) { |
44 | pivot = (void *) malloc(e_size); |
58 | pivot = (void *) malloc(e_size); |
45 | tmp = (void *) malloc(e_size); |
59 | tmp = (void *) malloc(e_size); |
46 | 60 | ||
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 | ||
57 | while (1) { |
93 | while (1) { |
58 | while ((cmp(data + i * e_size, pivot) < 0) && i < n) i++; |
94 | while ((cmp(data + i * e_size, pivot) < 0) && i < n) i++; |
59 | while ((cmp(data + j * e_size, pivot) >=0) && j > 0) j--; |
95 | while ((cmp(data + j * e_size, pivot) >=0) && j > 0) j--; |
60 | if (i<j) { |
96 | if (i<j) { |
61 | memcpy(tmp, data + i * e_size, e_size); |
97 | memcpy(tmp, data + i * e_size, e_size); |
62 | memcpy(data + i * e_size, data + j * e_size, e_size); |
98 | memcpy(data + i * e_size, data + j * e_size, e_size); |
63 | memcpy(data + j * e_size, tmp, e_size); |
99 | memcpy(data + j * e_size, tmp, e_size); |
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 | } |
- | |
74 | - | ||
75 | - | ||
76 | if (e_size > EBUFSIZE) { |
- | |
77 | free(tmp); |
- | |
78 | free(pivot); |
- | |
79 | } |
109 | } |
80 | } |
110 | } |
81 | 111 | ||
- | 112 | /** Bubblesort wrapper |
|
82 | 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); |
103 | memcpy(p, p + e_size, e_size); |
164 | memcpy(p, p + e_size, e_size); |
104 | memcpy(p + e_size, slot, e_size); |
165 | memcpy(p + e_size, slot, e_size); |
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 | */ |
118 | int int_cmp(void * a, void * b) |
176 | int int_cmp(void * a, void * b) |
119 | { |
177 | { |
120 | return (* (int *) a > * (int*)b) ? 1 : (*(int *)a < * (int *)b) ? -1 : 0; |
178 | return (* (int *) a > * (int*)b) ? 1 : (*(int *)a < * (int *)b) ? -1 : 0; |
121 | } |
179 | } |
122 | 180 | ||
123 | int __u8_cmp(void * a, void * b) |
181 | int __u8_cmp(void * a, void * b) |
124 | { |
182 | { |
125 | return (* (__u8 *) a > * (__u8 *)b) ? 1 : (*(__u8 *)a < * (__u8 *)b) ? -1 : 0; |
183 | return (* (__u8 *) a > * (__u8 *)b) ? 1 : (*(__u8 *)a < * (__u8 *)b) ? -1 : 0; |
126 | } |
184 | } |
127 | 185 | ||
128 | int __u16_cmp(void * a, void * b) |
186 | int __u16_cmp(void * a, void * b) |
129 | { |
187 | { |
130 | return (* (__u16 *) a > * (__u16 *)b) ? 1 : (*(__u16 *)a < * (__u16 *)b) ? -1 : 0; |
188 | return (* (__u16 *) a > * (__u16 *)b) ? 1 : (*(__u16 *)a < * (__u16 *)b) ? -1 : 0; |
131 | } |
189 | } |
132 | 190 | ||
133 | int __u32_cmp(void * a, void * b) |
191 | int __u32_cmp(void * a, void * b) |
134 | { |
192 | { |
135 | return (* (__u32 *) a > * (__u32 *)b) ? 1 : (*(__u32 *)a < * (__u32 *)b) ? -1 : 0; |
193 | return (* (__u32 *) a > * (__u32 *)b) ? 1 : (*(__u32 *)a < * (__u32 *)b) ? -1 : 0; |
136 | } |
194 | } |
137 | 195 |