software-rasterizer/sort.h at main · RNU4/software-rasterizer · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#ifndef _SORT_H
#define _SORT_H
#include "init.h"
#include <stdio.h>
#include <stdlib.h>
#include "SDL2/SDL.h"
#include "SDL2/SDL_thread.h"
#include "draw.h"
#define MAX_THREADS 8
#define MULTI_THREAD 0


#if MULTI_THREAD == 1

typedef struct {
    shape_triangle_t* arr;
    int low;
    int high;
} ThreadData;

int partition(shape_triangle_t* arr, int low, int high) {
    float pivot = (arr[high].p[0].z + arr[high].p[1].z + arr[high].p[2].z) / 3.0f;
    int i = low - 1;

    for (int j = low; j <= high - 1; j++) {
        if ((arr[j].p[0].z + arr[j].p[1].z + arr[j].p[2].z) / 3.0f > pivot) {
            i++;
            shape_triangle_t temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    shape_triangle_t temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return (i + 1);
}

void quicksort(shape_triangle_t* arr, int low, int high);

int quicksort_thread(void* data) {
    ThreadData* threadData = (ThreadData*)data;
    shape_triangle_t* arr = threadData->arr;
    int low = threadData->low;
    int high = threadData->high;

    quicksort(arr, low, high);

    free(threadData);

    return 0;
}

void quicksort(shape_triangle_t* arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);

        if (SDL_GetThreadID(NULL) != SDL_ThreadID()) {
            SDL_Thread* thread;
            ThreadData* threadData;

            thread = SDL_CreateThread(quicksort_thread, "QuicksortThread", (void*)threadData);

            if (thread == NULL) {
                printf("SDL_CreateThread failed: %s\n", SDL_GetError());
                return;
            }

            threadData = (ThreadData*)malloc(sizeof(ThreadData));
            threadData->arr = arr;
            threadData->low = low;
            threadData->high = pivotIndex - 1;

            quicksort(arr, pivotIndex + 1, high);

            SDL_WaitThread(thread, NULL);
        } else {
            quicksort(arr, low, pivotIndex - 1);
            quicksort(arr, pivotIndex + 1, high);
        }
    }
}
#else
int partition(shape_triangle_t *arr, int low, int high)
{
    float pivot = (arr[high].p[0].z + arr[high].p[1].z + arr[high].p[2].z) / 3.0f;
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++)
    {
        if ((arr[j].p[0].z + arr[j].p[1].z + arr[j].p[2].z) / 3.0f > pivot)
        {
            i++;
            // Swap arr[i] and arr[j]
            shape_triangle_t temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // Swap arr[i+1] and arr[high] (pivot)
    shape_triangle_t temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return (i + 1);
}

void quicksort(shape_triangle_t *arr, int low, int high)
{
    if (low < high)
    {
        int pi = partition(arr, low, high);

        quicksort(arr, low, pi - 1);
        quicksort(arr, pi + 1, high);
    }
}

#endif
#endif