commit e8e9e2eb6739c670abd2da61e652887cca79f047
parent 27fae5ae15878b8f830d19228643544dd7b5187a
Author: klewer-martin <martin.cachari@gmail.com>
Date: Thu, 14 Apr 2022 00:21:38 -0300
Added sav->sort_status, communication between threads changed
wait_main_thread() deprecated, before the child thread waited for the
main thread to updated the graphics, now the main thread updates the
graphics in every iteration while the child thread sorts the array.
A few keybindings where added, such as:
- SPACE BAR: play/pause the sort
- R: restart the sorting (only if the previos sort ends)
Diffstat:
| M | array.c | | | 3 | +++ |
| M | drw.c | | | 97 | ++++++++++++++++++++++--------------------------------------------------------- |
| M | drw.h | | | 10 | +++------- |
| M | main.c | | | 61 | +++++++++++++++++++++++++++++++------------------------------ |
| M | sav.c | | | 7 | ++++--- |
| M | sav.h | | | 6 | +++--- |
| M | sdl_extra.c | | | 12 | ++++++------ |
| M | sdl_extra.h | | | 2 | +- |
| M | sort.c | | | 99 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------------------ |
| M | status.h | | | 1 | + |
| M | util.c | | | 4 | ++-- |
11 files changed, 158 insertions(+), 144 deletions(-)
diff --git a/array.c b/array.c
@@ -1,5 +1,6 @@
#include "array.h"
+#include <stdio.h>
#include <time.h>
void
@@ -7,4 +8,6 @@ shuffle(Arr *arr) {
srand((unsigned int)time(NULL));
for(size_t i = 0; i < arr->len; i++)
while(!(arr->v[i] = rand() % ARR_MAX));
+
+ printf("ARRAY: Shuffling array done\n");
}
diff --git a/drw.c b/drw.c
@@ -38,7 +38,7 @@ drw_array_graph(Drw *drw, SAV *sav) {
else if(i == sav->cmp) drw_element_color(drw, x, h, sav->arr->v[i], CMP_COLOR);
else drw_element_color(drw, x, h, sav->arr->v[i], NORM_COLOR);
}
- /* drw_status_bar(drw, sav); */
+ drw_status_bar(drw, sav);
}
void
@@ -57,21 +57,31 @@ drw_status_bar(Drw *drw, SAV *sav) {
SDL_SetRenderDrawColor(drw->rend, 0, 0, 0, 0); /* RGBA */
SDL_RenderFillRect(drw->rend, &rect);
- if(sav->status == UPDATE) {
- /* sprintf(drw->bar_text, "Press SPACE to start sorting the array or ESC/q to quit"); */
- snprintf(drw->bar_text, drw->bar_text_len - 2,
- "SORTING (%s sort) L: %ld, C: %ld, S: %ld",
- algo_strings[sav->sel_algo], sav->arr->len, sav->cmps,
- sav->swps);
-
- drw_text(drw, drw->bar_text, 0, drw->h - drw->font_size - 5);
- } else if(sav->status == SORTED) {
- snprintf(drw->bar_text, drw->bar_text_len - 2,
- "SORTED (%s sort) done in %.2fs, L: %ld, C: %ld, S: %ld, extra storage used: %ld Bytes",
- algo_strings[sav->sel_algo],
- (double)(sav->tf - sav->ti) / CLOCKS_PER_SEC,
- sav->arr->len, sav->cmps, sav->swps, sav->B_used);
-
+ if((sav->status == RUN) || (sav->status == UPDATE) || (sav->status == START)) {
+ if(sav->sort_status == SORTED) {
+ snprintf(drw->bar_text, drw->bar_text_len - 2,
+ "SORTED (%s sort) done in %.2fs, L: %ld, C: %ld, S: %ld, extra storage used: %ld Bytes",
+ algo_strings[sav->sort_algo],
+ (double)(sav->tf - sav->ti) / CLOCKS_PER_SEC,
+ sav->arr->len, sav->cmps, sav->swps, sav->B_used);
+ } else if(sav->sort_status == PAUSE) {
+ if(sav->status == START) {
+ snprintf(drw->bar_text, drw->bar_text_len - 2,
+ "Welcome to sorting algorithms visualized - (%s sort selected) press SPACE to start sorting",
+ algo_strings[sav->sort_algo], sav->arr->len, sav->cmps,
+ sav->swps);
+ } else {
+ snprintf(drw->bar_text, drw->bar_text_len - 2,
+ "PAUSED (%s sort) press SPACE to resume",
+ algo_strings[sav->sort_algo], sav->arr->len, sav->cmps,
+ sav->swps);
+ }
+ } else {
+ snprintf(drw->bar_text, drw->bar_text_len - 2,
+ "SORTING (%s sort) L: %ld, C: %ld, S: %ld",
+ algo_strings[sav->sort_algo], sav->arr->len, sav->cmps,
+ sav->swps);
+ }
drw_text(drw, drw->bar_text, 0, drw->h - drw->font_size - 5);
}
memset(drw->bar_text, 0, sizeof(char) * drw->bar_text_len);
@@ -159,61 +169,8 @@ void
Drw_destroy(Drw *drw) {
if(drw == NULL) return;
- SDL_cleanup(drw->win, drw->rend);
TTF_CloseFont(drw->font);
+ SDL_cleanup(drw->win, drw->rend);
free(drw->bar_text);
free(drw);
}
-
-void drw_array_graph_sav_free(Drw *drw, Arr *arr) {
- int x, w, h;
-
- SDL_GetWindowSize(drw->win, &w, &h);
-
- SDL_SetRenderDrawColor(drw->rend, 29, 28, 28, 0);
- SDL_RenderClear(drw->rend);
-
- size_t i;
- for(i = x = 0; i < arr->len; i++, x += RECT_WIDTH) {
- if(i == sav->sel) drw_element_color(drw, x, h, arr->v[i], SEL_COLOR);
- else if(i == sav->cmp) drw_element_color(drw, x, h, arr->v[i], CMP_COLOR);
- else drw_element_color(drw, x, h, arr->v[i], NORM_COLOR);
- }
- /* drw_status_bar(drw, sav); */
-}
-
-void
-void drw_status_bar_sav_free(Drw *drw, SAV *sav) {
- SDL_Rect rect;
- int bar_border = 2;
-
- rect.x = bar_border; /* top left + x */
- rect.y = drw->h - bar_border; /* top left + y, (y < 0) */
- rect.w = drw->w - (2 * bar_border); /* fixed width */
- rect.h = -BAR_HEIGHT;
-
- SDL_RenderDrawRect(drw->rend, &rect);
-
- /* TODO: Make a variable to store statusbar background color */
- SDL_SetRenderDrawColor(drw->rend, 0, 0, 0, 0); /* RGBA */
- SDL_RenderFillRect(drw->rend, &rect);
-
- if(sav->status == UPDATE) {
- /* sprintf(drw->bar_text, "Press SPACE to start sorting the array or ESC/q to quit"); */
- snprintf(drw->bar_text, drw->bar_text_len - 2,
- "SORTING (%s sort) L: %ld, C: %ld, S: %ld",
- algo_strings[sav->sel_algo], sav->arr->len, sav->cmps,
- sav->swps);
-
- drw_text(drw, drw->bar_text, 0, drw->h - drw->font_size - 5);
- } else if(sav->status == SORTED) {
- snprintf(drw->bar_text, drw->bar_text_len - 2,
- "SORTED (%s sort) done in %.2fs, L: %ld, C: %ld, S: %ld, extra storage used: %ld Bytes",
- algo_strings[sav->sel_algo],
- (double)(sav->tf - sav->ti) / CLOCKS_PER_SEC,
- sav->arr->len, sav->cmps, sav->swps, sav->B_used);
-
- drw_text(drw, drw->bar_text, 0, drw->h - drw->font_size - 5);
- }
- memset(drw->bar_text, 0, sizeof(char) * drw->bar_text_len);
-}
diff --git a/drw.h b/drw.h
@@ -4,9 +4,8 @@
#include <SDL2/SDL.h>
#include <SDL2/SDL_ttf.h>
-/* #include "sav.h" */
+#include "sav.h"
#include "util.h"
-/* #include "sort.h" */
#include "sdl_extra.h"
#define SEL_COLOR 0x00FF0000 // RGBA (A not used rn)
@@ -47,10 +46,7 @@ void drw_element(SDL_Renderer *rend, int x, int y, int h);
void drw_element_color(Drw *drw, int x, int y, int h, unsigned int col);
void drw_text(Drw *drw, char *text, int x, int y);
-/* void drw_array_graph(Drw *drw, SAV *sav); */
-/* void drw_status_bar(Drw *drw, SAV *sav); */
-
-void drw_array_graph_sav_free(Drw *, Arr *);
-void drw_status_bar_sav_free(Drw *drw, SAV *sav);
+void drw_array_graph(Drw *drw, SAV *sav);
+void drw_status_bar(Drw *drw, SAV *sav);
#endif // __DRAW_H__
diff --git a/main.c b/main.c
@@ -14,13 +14,13 @@ void *
routine_wrapper(void *arg) {
SAV *sav = (SAV *)arg;
- switch(sav->sel_algo) {
+ switch(sav->sort_algo) {
case BUBBLE_SORT: bubble_sort(sav); break;
case INSERTION_SORT: insertion_sort(sav); break;
case MERGE_SORT: merge_sort_wrapper(sav); break;
case QUICK_SORT: quick_sort_wrapper(sav); break;
default: {
- fprintf(stderr, "\"sel_algo\" not set. exiting\n");
+ fprintf(stderr, "\"sort_algo\" not set. exiting\n");
sav->status = STOP;
break;
}
@@ -42,30 +42,29 @@ main (void) {
/* assigns random values to array */
shuffle(sav->arr);
+ /* selecting the sorting algorithms */
+ sav->sort_algo = BUBBLE_SORT;
+
/* start sorting thread */
pthread_create(&p1, NULL, &routine_wrapper, (void *)sav);
- /* selecting the sorting algorithms */
- sav->sel_algo = QUICK_SORT;
+
+ sav->status = START;
+ sav->sort_status = PAUSE;
/* main loop */
- sav->status = RUN;
while(sav->status != STOP) {
- /* check_events(drw, sav); */
- if(sav->status == UPDATE) {
- /* drw_array_graph(drw, sav); */
- sav->status = RUN;
- SDL_RenderPresent(drw->rend);
- }
- if(sav->status == SORTED) {
- /* p1 ended */
- /* drw_array_graph(drw, sav); */
- SDL_RenderPresent(drw->rend);
- }
- if(sav->status == RESTART) {
+ check_events(drw, sav);
+
+ drw_array_graph(drw, sav);
+ drw_status_bar(drw, sav);
+ SDL_RenderPresent(drw->rend);
+
+ if((sav->sort_status == SORTED) && (sav->status == RESTART)) {
/* this state can only be achived if p1 ended */
shuffle(sav->arr);
sav->status = RUN;
+ sav->sort_status = RUN;
/* let's call p1 again */
pthread_create(&p1, NULL, &routine_wrapper, (void *)sav);
@@ -85,22 +84,24 @@ check_events(Drw *drw, SAV *sav) {
SDL_Event event;
while (SDL_PollEvent(&event)) {
switch(event.type) {
- case SDL_QUIT: sav->status = STOP; break;
+ case SDL_QUIT:
+ sav->status = sav->sort_status = STOP;
+ break;
case SDL_KEYDOWN:
switch(event.key.keysym.scancode) {
- /* case SDL_SCANCODE_EQUALS: */
- /* if(speed > SPEED_MAX) speed -= SPEED_STEP; */
- /* break; */
- /* case SDL_SCANCODE_MINUS: */
- /* if(speed < SPEED_MIN) speed += SPEED_STEP; */
- /* break; */
- /* case SDL_SCANCODE_P: */
- /* if(status == PAUSE) *status = RUN; */
- /* else *status = PAUSE; */
- /* break; */
case SDL_SCANCODE_R:
- if(sav->status == SORTED) sav->status = RESTART;
- else break;
+ if(sav->sort_status == SORTED) sav->status = RESTART;
+ break;
+ /* case SDL_SCANCODE_S: */
+ /* shuffle(sav->arr); */
+ /* break; */
+ case SDL_SCANCODE_SPACE:
+ printf("status: %d, sort_status: %d\n", sav->status, sav->sort_status);
+ /* if(sav->status == START) sav->status = sav->sort_status = RUN; */
+ if(sav->sort_status == PAUSE) sav->status = sav->sort_status = RUN;
+ else if(sav->sort_status == RUN) sav->sort_status = PAUSE;
+
+ break;
default: break;
}
case SDL_WINDOWEVENT:
diff --git a/sav.c b/sav.c
@@ -12,10 +12,11 @@ SAV_new(SAV **sav) {
if((*sav = (SAV *)malloc(sizeof(SAV))) == NULL)
return ERROR_MEMORY_ALLOC;
- (*sav)->sel = (*sav)->cmps = (*sav)->swps = (*sav)->its = (*sav)->B_used = 0;
- (*sav)->cmp = ARR_MAX + 1;
+ (*sav)->sel = (*sav)->cmp = ARR_MAX + 1;
+ (*sav)->cmps = (*sav)->swps = (*sav)->its = (*sav)->B_used = 0;
(*sav)->status = RUN;
- (*sav)->sel_algo = SORT_MAX_ALGORITHMS;
+ (*sav)->sort_status = PAUSE;
+ (*sav)->sort_algo = SORT_MAX_ALGORITHMS;
if(((*sav)->arr = (Arr *)malloc(sizeof(Arr))) == NULL)
return ERROR_MEMORY_ALLOC;
diff --git a/sav.h b/sav.h
@@ -7,7 +7,6 @@
#include <time.h>
#include <SDL2/SDL.h>
-#include "drw.h"
#include "util.h"
#include "array.h"
@@ -24,8 +23,9 @@ typedef struct {
size_t sel, cmp, cmps, swps, its, B_used;
clock_t ti, tf;
status_t status;
- sort_t sel_algo;
-} SAV; // Sort?
+ status_t sort_status;
+ sort_t sort_algo;
+} SAV;
extern char *algo_strings[SORT_MAX_ALGORITHMS];
diff --git a/sdl_extra.c b/sdl_extra.c
@@ -12,15 +12,15 @@ SDL_setup(SDL_Window **win, SDL_Renderer **rend) {
SDL_WINDOWPOS_UNDEFINED,
0,
0,
- SDL_WINDOW_OPENGL | SDL_WINDOW_RESIZABLE | SDL_WINDOW_UTILITY
+ SDL_WINDOW_RESIZABLE | SDL_WINDOW_UTILITY
);
*rend = SDL_CreateRenderer(*win, -1, SDL_RENDERER_ACCELERATED | SDL_RENDERER_PRESENTVSYNC);
- /* TODO: return error codes */
- if (*win == NULL) return ERROR_NULL_POINTER;
- else if (*rend == NULL) return ERROR_NULL_POINTER;
- else if(TTF_Init() == -1) return ERROR_SDL_FONT_INIT;
+ if ((*win == NULL) || (rend == NULL))
+ return ERROR_NULL_POINTER;
+ else if(TTF_Init() == -1)
+ return ERROR_SDL_FONT_INIT;
SDL_SetRenderDrawColor(*rend, 32, 32, 32, 0);
SDL_RenderClear(*rend);
@@ -37,7 +37,7 @@ SDL_setup(SDL_Window **win, SDL_Renderer **rend) {
status_t
SDL_cleanup(SDL_Window *win, SDL_Renderer *rend) {
- if(win == NULL || rend == NULL)
+ if((win == NULL) || (rend == NULL))
return ERROR_NULL_POINTER;
SDL_DestroyRenderer(rend);
diff --git a/sdl_extra.h b/sdl_extra.h
@@ -14,7 +14,7 @@
#define TOP_BORDER 50
#define RECT_WIDTH 5
-#define WIN_TITLE "SAV - Sorting Algorithms Visualized"
+#define WIN_TITLE "SAV: Sorting Algorithms Visualized"
status_t SDL_setup(SDL_Window **win, SDL_Renderer **rend);
status_t SDL_cleanup(SDL_Window *win, SDL_Renderer *rend);
diff --git a/sort.c b/sort.c
@@ -4,11 +4,16 @@
#include "sort.h"
+#define DELAY 5
+
void
insertion_sort(SAV *sav) {
int key;
size_t i, j;
+ if((sav->sort_status == STOP) || (sav->status == STOP)) return;
+ while(sav->sort_status == PAUSE);
+
sav->ti = clock();
for(i = 1; i < sav->arr->len; i++, sav->its++) {
sav->cmps += 1;
@@ -23,29 +28,43 @@ insertion_sort(SAV *sav) {
sav->cmp = j;
sav->its++;
- /* wait 'til main thread updates graphics */
- wait_main_thread(&(sav->status));
- if(sav->status == STOP) break;
+ /* Delay */
+ for(size_t i = 0; i < DELAY; i++) {
+ if((sav->sort_status == STOP) || (sav->status == STOP))
+ goto end;
+
+ SDL_Delay(1);
+ }
+ while(sav->sort_status == PAUSE);
}
sav->arr->v[j + 1] = key;
sav->sel = i;
sav->cmp = j;
sav->swps += 1;
- /* wait 'til main thread updates graphics */
- wait_main_thread(&(sav->status));
- if(sav->status == STOP) break;
+ /* Delay */
+ for(size_t i = 0; i < DELAY; i++) {
+ if((sav->sort_status == STOP) || (sav->status == STOP))
+ goto end;
+
+ SDL_Delay(1);
+ }
+ while(sav->sort_status == PAUSE);
}
+ end:
sav->tf = clock();
- if(sav->status != STOP) sav->status = SORTED;
+ if(sav->status != STOP) sav->sort_status = SORTED;
}
void
bubble_sort(SAV *sav) {
size_t i, j;
+ if((sav->sort_status == STOP) || (sav->status == STOP)) return;
+ while(sav->sort_status == PAUSE);
+
sav->ti = clock();
for(i = 0; i < sav->arr->len - 1; i++, sav->its++) {
for(j = 0; j < (sav->arr->len - 1 - i); j++, sav->its++) {
@@ -57,21 +76,38 @@ bubble_sort(SAV *sav) {
sav->swps += 1;
}
- /* wait 'til main thread updates graphics */
- wait_main_thread(&(sav->status));
- if(sav->status == STOP) break;
+ /* Delay */
+ for(size_t i = 0; i < DELAY; i++) {
+ if((sav->sort_status == STOP) || (sav->status == STOP))
+ goto end;
+
+ SDL_Delay(1);
+ }
+ while(sav->sort_status == PAUSE);
}
- wait_main_thread(&(sav->status));
- if(sav->status == STOP) break;
+
+ /* Delay */
+ for(size_t i = 0; i < DELAY; i++) {
+ if((sav->sort_status == STOP) || (sav->status == STOP))
+ goto end;
+
+ SDL_Delay(1);
+ }
+ while(sav->sort_status == PAUSE);
}
+ end:
+
sav->tf = clock();
- if(sav->status != STOP) sav->status = SORTED;
+ if(sav->status != STOP) sav->sort_status = SORTED;
}
void
merge(SAV *sav, int low, int middle, int high) {
size_t n1, n2, i, j, k;
+ if((sav->sort_status == STOP) || (sav->status == STOP)) return;
+ while(sav->sort_status == PAUSE);
+
n1 = middle - low;
n2 = high - middle;
@@ -97,9 +133,17 @@ merge(SAV *sav, int low, int middle, int high) {
sav->cmps += 1;
sav->its += 1;
- wait_main_thread(&(sav->status));
- if(sav->status == STOP) return;
+ while(sav->sort_status == PAUSE);
+
+ /* Delay */
+ for(size_t i = 0; i < DELAY; i++) {
+ if((sav->sort_status == STOP) || (sav->status == STOP))
+ goto end;
+
+ SDL_Delay(1);
+ }
}
+ end:
while(i < n1)
sav->arr->v[k++] = B[i++];
@@ -112,6 +156,11 @@ void
merge_sort(SAV *sav, int low, int high) {
if(sav == NULL) return;
+ if((sav->sort_status == STOP) || (sav->status == STOP))
+ return;
+
+ while(sav->sort_status == PAUSE);
+
int middle;
middle = ((high + low) / 2);
@@ -134,7 +183,7 @@ void merge_sort_wrapper(SAV *sav) {
merge_sort(sav, 0, sav->arr->len);
sav->tf = clock();
sav->sel = sav->arr->len + 1;
- if(sav->status != STOP) sav->status = SORTED;
+ if(sav->status != STOP) sav->sort_status = SORTED;
}
void
@@ -143,7 +192,7 @@ quick_sort_partition(SAV *sav, int low, int *middle, int high) {
pivot = high;
sav->sel = pivot;
- printf("SORT: pivot: %d\n", pivot);
+ /* printf("SORT: pivot: %d\n", pivot); */
for(i = j = low; j < high; j++, sav->cmps += 1) {
if(sav->arr->v[j] < sav->arr->v[pivot]) {
@@ -151,9 +200,15 @@ quick_sort_partition(SAV *sav, int low, int *middle, int high) {
sav->swps += 1;
}
- wait_main_thread(&(sav->status));
- if(sav->status == STOP) return;
+ if(sav->status != STOP) sav->status = UPDATE;
+ while(sav->sort_status == PAUSE);
+
+ for(size_t i = 0; i < 5; i++) {
+ if(sav->sort_status == STOP) goto end;
+ SDL_Delay(1);
+ }
}
+ end:
swap(&(sav->arr->v[i]), &(sav->arr->v[pivot]));
sav->swps += 1;
@@ -165,8 +220,7 @@ quick_sort(SAV *sav, int low, int high) {
int pivot;
if(sav->status == STOP) return;
- else if(sav->status == PAUSE)
- wait_main_thread(&(sav->status));
+ while(sav->sort_status == PAUSE);
if ((high - low) > 0) {
quick_sort_partition(sav, low, &pivot, high);
@@ -179,6 +233,7 @@ void
quick_sort_wrapper(SAV *sav) {
sav->ti = clock();
quick_sort(sav, 0, sav->arr->len - 1);
- sav->status = SORTED;
+ printf("SORT: sorting array done\n");
+ if(sav->sort_status != STOP) sav->sort_status = SORTED;
sav->tf = clock();
}
diff --git a/status.h b/status.h
@@ -12,6 +12,7 @@ typedef enum {
ERROR_NULL_POINTER,
ERROR_DRW,
SORTED,
+ START,
RESTART,
STOP
} status_t;
diff --git a/util.c b/util.c
@@ -2,10 +2,10 @@
void
wait_main_thread(status_t *st) {
- if(*st != STOP) *st = UPDATE;
+ if((*st != STOP) && (*st != PAUSE)) *st = UPDATE;
/* wait 'til main thread changes st value to RUN */
- while(*st == UPDATE);
+ while((*st == UPDATE) || (*st == PAUSE));
}
void
