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 */