Changeset 0a50f59 in mainline
- Timestamp:
- 2005-09-15T21:19:40Z (19 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 6799505
- Parents:
- 01e48c1
- Location:
- src
- Files:
-
- 2 edited
- 1 moved
Legend:
- Unmodified
- Added
- Removed
-
src/Makefile
r01e48c1 r0a50f59 9 9 proc/thread.c \ 10 10 proc/task.c \ 11 proc/the.c \ 11 12 mm/heap.c \ 12 13 mm/frame.c \ … … 17 18 lib/list.c \ 18 19 lib/memstr.c \ 19 lib/the.c \20 20 lib/sort.c \ 21 21 debug/print.c \ -
src/lib/sort.c
r01e48c1 r0a50f59 34 34 #define EBUFSIZE 32 35 35 36 static void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void * pivot, void * tmp); 37 38 /* 39 * Wrapper method for quicksort algorithm to decrease amount of allocations 40 */ 41 void qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) { 36 void qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) 37 { 42 38 __u8 buf_tmp[EBUFSIZE]; 43 39 __u8 buf_pivot[EBUFSIZE]; … … 54 50 } 55 51 56 _qsort(data, n, e_size, cmp, pivot, tmp); 52 if (n > 4) { 53 int i = 0, j = n - 1; 54 55 memcpy(pivot, data, e_size); 56 57 while (1) { 58 while ((cmp(data + i * e_size, pivot) < 0) && i < n) i++; 59 while ((cmp(data + j * e_size, pivot) >=0) && j > 0) j--; 60 if (i<j) { 61 memcpy(tmp, data + i * e_size, e_size); 62 memcpy(data + i * e_size, data + j * e_size, e_size); 63 memcpy(data + j * e_size, tmp, e_size); 64 } else { 65 break; 66 } 67 } 68 69 qsort(data, j + 1, e_size, cmp); 70 qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp); 71 } else { 72 bubblesort(data, n, e_size, cmp); 73 } 74 57 75 58 76 if (e_size > EBUFSIZE) { … … 63 81 64 82 65 void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) { 83 void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) 84 { 66 85 __u8 buf_slot[EBUFSIZE]; 67 86 bool done = false; … … 94 113 } 95 114 96 static void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void * pivot, void * tmp) {97 if (n > 4) {98 int i = 0, j = n - 1;99 100 memcpy(pivot, data, e_size);101 102 while (1) {103 while ((cmp(data + i * e_size, pivot) < 0) && i < n) i++;104 while ((cmp(data + j * e_size, pivot) >=0) && j > 0) j--;105 if (i<j) {106 memcpy(tmp, data + i * e_size, e_size);107 memcpy(data + i * e_size, data + j * e_size, e_size);108 memcpy(data + j * e_size, tmp, e_size);109 } else {110 break;111 }112 }113 114 qsort(data, j + 1, e_size, cmp);115 qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp);116 } else {117 bubblesort(data, n, e_size, cmp);118 }119 }120 121 122 123 115 /* 124 116 * Comparator returns 1 if a > b, 0 if a == b, -1 if a < b 125 117 */ 126 int int_cmp(void * a, void * b) { 118 int int_cmp(void * a, void * b) 119 { 127 120 return (* (int *) a > * (int*)b) ? 1 : (*(int *)a < * (int *)b) ? -1 : 0; 128 121 } 129 122 130 int __u8_cmp(void * a, void * b) { 123 int __u8_cmp(void * a, void * b) 124 { 131 125 return (* (__u8 *) a > * (__u8 *)b) ? 1 : (*(__u8 *)a < * (__u8 *)b) ? -1 : 0; 132 126 } 133 127 134 int __u16_cmp(void * a, void * b) { 128 int __u16_cmp(void * a, void * b) 129 { 135 130 return (* (__u16 *) a > * (__u16 *)b) ? 1 : (*(__u16 *)a < * (__u16 *)b) ? -1 : 0; 136 131 } 137 132 138 int __u32_cmp(void * a, void * b) { 133 int __u32_cmp(void * a, void * b) 134 { 139 135 return (* (__u32 *) a > * (__u32 *)b) ? 1 : (*(__u32 *)a < * (__u32 *)b) ? -1 : 0; 140 136 } 141
Note:
See TracChangeset
for help on using the changeset viewer.