00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00041 #include <mm/slab.h>
00042 #include <memstr.h>
00043 #include <sort.h>
00044 #include <panic.h>
00045
00046 #define EBUFSIZE 32
00047
00048 void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *tmp, void *pivot);
00049 void _bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot);
00050
00064 void qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b))
00065 {
00066 __u8 buf_tmp[EBUFSIZE];
00067 __u8 buf_pivot[EBUFSIZE];
00068 void * tmp = buf_tmp;
00069 void * pivot = buf_pivot;
00070
00071 if (e_size > EBUFSIZE) {
00072 pivot = (void *) malloc(e_size, 0);
00073 tmp = (void *) malloc(e_size, 0);
00074 }
00075
00076 _qsort(data, n, e_size, cmp, tmp, pivot);
00077
00078 if (e_size > EBUFSIZE) {
00079 free(tmp);
00080 free(pivot);
00081 }
00082 }
00083
00096 void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *tmp, void *pivot)
00097 {
00098 if (n > 4) {
00099 int i = 0, j = n - 1;
00100
00101 memcpy(pivot, data, e_size);
00102
00103 while (1) {
00104 while ((cmp(data + i * e_size, pivot) < 0) && i < n) i++;
00105 while ((cmp(data + j * e_size, pivot) >=0) && j > 0) j--;
00106 if (i<j) {
00107 memcpy(tmp, data + i * e_size, e_size);
00108 memcpy(data + i * e_size, data + j * e_size, e_size);
00109 memcpy(data + j * e_size, tmp, e_size);
00110 } else {
00111 break;
00112 }
00113 }
00114
00115 _qsort(data, j + 1, e_size, cmp, tmp, pivot);
00116 _qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp, tmp, pivot);
00117 } else {
00118 _bubblesort(data, n, e_size, cmp, tmp);
00119 }
00120 }
00121
00133 void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b))
00134 {
00135 __u8 buf_slot[EBUFSIZE];
00136 void * slot = buf_slot;
00137
00138 if (e_size > EBUFSIZE) {
00139 slot = (void *) malloc(e_size, 0);
00140 }
00141
00142 _bubblesort(data, n, e_size, cmp, slot);
00143
00144 if (e_size > EBUFSIZE) {
00145 free(slot);
00146 }
00147 }
00148
00160 void _bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot)
00161 {
00162 bool done = false;
00163 void * p;
00164
00165 while (!done) {
00166 done = true;
00167 for (p = data; p < data + e_size * (n - 1); p = p + e_size) {
00168 if (cmp(p, p + e_size) == 1) {
00169 memcpy(slot, p, e_size);
00170 memcpy(p, p + e_size, e_size);
00171 memcpy(p + e_size, slot, e_size);
00172 done = false;
00173 }
00174 }
00175 }
00176
00177 }
00178
00179
00180
00181
00182 int int_cmp(void * a, void * b)
00183 {
00184 return (* (int *) a > * (int*)b) ? 1 : (*(int *)a < * (int *)b) ? -1 : 0;
00185 }
00186
00187 int __u8_cmp(void * a, void * b)
00188 {
00189 return (* (__u8 *) a > * (__u8 *)b) ? 1 : (*(__u8 *)a < * (__u8 *)b) ? -1 : 0;
00190 }
00191
00192 int __u16_cmp(void * a, void * b)
00193 {
00194 return (* (__u16 *) a > * (__u16 *)b) ? 1 : (*(__u16 *)a < * (__u16 *)b) ? -1 : 0;
00195 }
00196
00197 int __u32_cmp(void * a, void * b)
00198 {
00199 return (* (__u32 *) a > * (__u32 *)b) ? 1 : (*(__u32 *)a < * (__u32 *)b) ? -1 : 0;
00200 }
00201