Mercurial > hg > Game > Cerium
view example/many_task/ppe/QuickSort.cc @ 1851:637fa9a4105b draft
fix many_task ( sort )
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Sat, 21 Dec 2013 19:42:17 +0900 (2013-12-21) |
parents | 9ccfdc408d51 |
children | 7e9ebc1b08b6 |
line wrap: on
line source
#include "QuickSort.h" #include <stdio.h> #include <string.h> SchedDefineTask(QuickSort); static void quick_sort( Data *data, int begin, int end ) ; static void swap( Data *data, int left, int right ) { Data tmp = data[left]; data[left] = data[right]; data[right] = tmp; } //#define USE_MEMCPY void bubble_sort(Data *data, int begin, int end) { for (int count=0;count<end;count++) { for (int c=end;c>count;c--) { if (data[c].index<data[c-1].index)swap(data,c-1,c); } } } static int run(SchedTask *s, void* rbuff, void* wbuff) { // copy value int begin = 0; #if USE_SIMPLE_TASK int end = s->read_size()/sizeof(Data); Data *r_data = (Data*)rbuff; #ifdef USE_MEMCPY Data *w_data = (Data*)wbuff; #endif #else int end = s->get_inputSize(0)/sizeof(Data); DataPtr r_data = (DataPtr)s->get_input(0); #ifdef USE_MEMCPY DataPtr w_data = (DataPtr)s->get_output(0); #endif #endif // printf("[PPE] Quick: length:%d addr->%x \n",end, (int)rbuff); // printf("[PPE] Quick: data[0]: %ld addr->%lx\n",sizeof(r_data),(long)r_data); quick_sort(r_data, begin, end); #ifdef USE_MEMCPY memcpy(w_data, r_data, sizeof(Data)*end); #else s->swap(); #endif return 0; } void qsort_test(Data *data, int begin, int end ) { quick_sort(data, begin, end-1); } static void quick_sort( Data *data, int begin, int end ) { int stack[1024]; int sp = 0; int p; while (1) { while (begin < end) { if (end-begin <= 50) { //bubble_sort(data, begin, end); //break; } int where = (begin + end) / 2; int pivot = data[where].index; data[where].index = data[begin].index; int i; p = begin; for (i=begin+1; i<end; i++) { if (data[i].index < pivot) { p++; swap(data, p, i); } } data[begin].index = data[p].index; data[p].index = pivot; stack[sp++] = p + 1; stack[sp++] = end; end = p - 1; } if (sp == 0) return; end = stack[--sp]; begin = stack[--sp]; begin = p + 1; } } /* end */