commit d951479e7d3639e6bb49680b3ae2b475ae5fa690
parent 86e93e464823fba6d6137500cb14cfcc06e2b421
Author: klewer-martin <martin.cachari@gmail.com>
Date: Sun, 17 Apr 2022 00:12:19 -0300
Fixed high CPU usage
Fixed high CPU usage by creating two functions to delay and pause the
sorting algorithm being run, sort_delay() and sort_pause() respectively;
both of this functions use a small delay in between the loop used to
wait until a condition breaks it.
The drw_element_color() function had a small change too, the line drawn
around the rect was moved by one pixel to the top and it was in the
wrong, side; now is drawn correctly.
Diffstat:
| M | Makefile | | | 2 | +- |
| M | drw.c | | | 70 | ++++++++++++++++++++++++++++++++++++++++++++-------------------------- |
| M | drw.h | | | 6 | +++++- |
| M | main.c | | | 73 | +++++++++++++++++++++++++++++++++++++++++++++++++++++-------------------- |
| M | sav.c | | | 10 | ++++++++++ |
| M | sav.h | | | 9 | ++++++--- |
| M | sdl_extra.h | | | 2 | -- |
| M | sort.c | | | 92 | ++++++++++++++++++++++++++++++++++++++++++++----------------------------------- |
| M | sort.h | | | 19 | +++++-------------- |
| M | status.h | | | 5 | +++-- |
10 files changed, 178 insertions(+), 110 deletions(-)
diff --git a/Makefile b/Makefile
@@ -1,6 +1,6 @@
CC := gcc
CLIBS := `sdl2-config --libs` -lSDL2_ttf -lm
-CFLAGS := `sdl2-config --cflags` -Wall -Wshadow -pedantic -ansi -std=c99 -pthread
+CFLAGS := `sdl2-config --cflags` -Wall -Wshadow -pedantic -ansi -std=c99 -O3
SRCS := $(wildcard *.c)
OBJS := $(SRCS:.c=.o)
diff --git a/drw.c b/drw.c
@@ -1,6 +1,20 @@
#include "drw.h"
static SDL_Rect rect;
+static const char *algo_sel_str[ALGORITHMS_COUNT] = {
+ "bubble",
+ "insertion",
+ "merge",
+ "quick"
+};
+
+static const char *sort_status_str[STATUS_MAX] = {
+ "READY",
+ "SORTING",
+ "PAUSED",
+ "SORTED",
+ "STOPPED"
+};
void drw_element_color(Drw *drw, int x, int y, int h, unsigned int col) {
rect.x = x + drw->x_border; /* bottom left + x */
@@ -8,16 +22,16 @@ void drw_element_color(Drw *drw, int x, int y, int h, unsigned int col) {
rect.w = RECT_WIDTH; /* fixed width */
rect.h = -h;
- /* SDL_RenderDrawRect(drw->rend, &rect); */
SDL_SetRenderDrawColor(drw->rend, UNHEX(col));
SDL_RenderFillRect(drw->rend, &rect);
/* printf("INFO: color: #%02X%02X%02X%02X\n", UNHEX(col)); */
+ /* Simulate shadows around rectangles */
SDL_SetRenderDrawColor(drw->rend, UNHEX(0x000000FF));
SDL_RenderDrawLine(drw->rend,
- x + drw->x_border, y - drw->y_border,
- x + drw->x_border, y - drw->y_border - h);
+ x + drw->x_border + RECT_WIDTH - 1, y - drw->y_border - 1,
+ x + drw->x_border + RECT_WIDTH - 1, y - drw->y_border - h);
}
void drw_array_graph(Drw *drw, SAV *sav) {
@@ -39,43 +53,47 @@ void drw_status_bar(Drw *drw, SAV *sav) {
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, UNHEX(0x000000FF)); /* RGBA */
SDL_RenderFillRect(drw->rend, &rect);
/* TODO: create a function which fetchs the status text to be drawn based on the status */
- if(sav->sort_status == SORTED) {
+ if(sav->status == WELCOME) {
+ snprintf(drw->bar_text, drw->bar_text_len - 2,
+ " Welcome to sorting algorithms visualized [%s sort] press SPACE to start sorting",
+ algo_sel_str[sav->sort_algo]);
+ }
+ else if(sav->status == START) {
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) {
+ " %-9s [%s sort] press SPACE to start sorting", sort_status_str[OK],
+ algo_sel_str[sav->sort_algo]);
+ }
+ else if(sav->status == RUN) {
+ if(sav->sort_status == PAUSE)
snprintf(drw->bar_text, drw->bar_text_len - 2,
- "[%s sort selected] press SPACE to start sorting",
- algo_strings[sav->sort_algo]);
- } else if(sav->status == WELCOME) {
+ " %-9s [%s sort] press SPACE to resume",
+ sort_status_str[sav->sort_status],
+ algo_sel_str[sav->sort_algo]);
+ else if(sav->sort_status == SORTED)
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]);
- } else {
+ " %-9s [%s sort] done in %lds, L: %ld, C: %ld, S: %ld, extra storage used: %ld Bytes",
+ sort_status_str[sav->sort_status],
+ algo_sel_str[sav->sort_algo],
+ (sav->tf - sav->ti),
+ sav->arr->len, sav->cmps, sav->swps, sav->B_used);
+ else if(sav->sort_status == RUN)
snprintf(drw->bar_text, drw->bar_text_len - 2,
- "PAUSED [%s sort] press SPACE to resume", algo_strings[sav->sort_algo]);
- }
- } 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);
+ " %-9s [%s sort] L: %ld, C: %ld, S: %ld", sort_status_str[sav->sort_status],
+ algo_sel_str[sav->sort_algo], sav->arr->len, sav->cmps,
+ sav->swps);
}
+ else snprintf(drw->bar_text, drw->bar_text_len - 2, " Exiting ..... ");
+
drw_text(drw, drw->bar_text, 0, drw->h - drw->font_size - 5);
memset(drw->bar_text, 0, sizeof(char) * drw->bar_text_len);
}
-void drw_text(Drw *drw, char *text, int x, int y) {
+void drw_text(Drw *drw, const char *text, int x, int y) {
drw->text_surface = TTF_RenderText_Blended(drw->font, text, drw->text_color);
drw->text_texture = SDL_CreateTextureFromSurface(drw->rend, drw->text_surface);
diff --git a/drw.h b/drw.h
@@ -13,6 +13,10 @@
#define CMP_COLOR 0x00FFFF00
#define NORM_COLOR 0xFF000000
+/* #define SEL_COLOR 0xFF0000FF // RGBA (A not used rn) */
+/* #define CMP_COLOR 0x00FF00FF */
+/* #define NORM_COLOR 0xFFFFFFFF */
+
#define FONT_SIZE 12
#define FONT_NAME "/home/mk/.local/share/fonts/VictorMono-Bold.ttf"
#define FONT_COLOR 0xBBBBBB
@@ -45,7 +49,7 @@ void Drw_destroy(Drw *drw);
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_text(Drw *drw, const char *text, int x, int y);
void drw_array_graph(Drw *drw, SAV *sav);
void drw_status_bar(Drw *drw, SAV *sav);
diff --git a/main.c b/main.c
@@ -1,20 +1,27 @@
#include <stdio.h>
#include <pthread.h>
+#include "sav.h"
#include "drw.h"
#include "sort.h"
#include "util.h"
#include "sdl_extra.h"
#include "array.h"
-#define WELCOME_MSG_TIME 5
-
-/* TODO: sorting algorithms should only keep track of sav->sort_status and not sav->status */
-/* TODO: support restart even if the sorting algorithm didn't finish */
+#define WELCOME_MSG_TIME 3
void check_events(Drw *, SAV *);
+
+/* void *(*start_routine)(void *), pthread_create routine */
void *routine_wrapper(void *);
+static void (*sort_handler[ALGORITHMS_COUNT])(SAV *) = {
+ &bubble_sort,
+ &insertion_sort,
+ &merge_sort_wrapper,
+ &quick_sort_wrapper
+};
+
void *routine_wrapper(void *arg) {
SAV *sav = (SAV *)arg;
@@ -26,12 +33,16 @@ void *routine_wrapper(void *arg) {
return NULL;
}
+/* TODO: Support random, reversed, in_order arrays */
+/* TODO: Support command line arguments */
+/* TODO: Support sound */
+
int main (void) {
SAV *sav;
Drw *drw;
- clock_t ti, tc;
+ time_t tic, toc;
- pthread_t p1;
+ pthread_t p1 = 0;
status_t st;
if((st = SAV_new(&sav)) != OK) goto end;
@@ -41,15 +52,11 @@ int main (void) {
shuffle(sav->arr);
/* selecting the sorting algorithm */
- sav->sort_algo = QUICK_SORT;
-
- /* TODO: this thread should be called if the user wants to begin sorting the array */
- /* start sorting thread */
- pthread_create(&p1, NULL, &routine_wrapper, (void *)sav);
+ sav->sort_algo = INSERTION_SORT;
sav->status = WELCOME;
sav->sort_status = PAUSE;
- ti = clock();
+ tic = time(NULL);
/* main loop */
while(sav->status != STOP) {
@@ -63,22 +70,39 @@ int main (void) {
SDL_RenderPresent(drw->rend);
if(sav->status == WELCOME)
- if((((tc = clock()) - ti) / CLOCKS_PER_SEC) > WELCOME_MSG_TIME)
+ if(((toc = time(NULL)) - tic) > WELCOME_MSG_TIME)
sav->status = START;
- if((sav->sort_status == SORTED) && (sav->status == RESTART)) {
- /* this state can only be achived if p1 ended */
+ if((sav->status == START) || (sav->status == WELCOME)) {
+ if(sav->sort_status == RUN) {
+ sav->status = RUN;
+ /* start sorting thread */
+ pthread_create(&p1, NULL, &routine_wrapper, (void *)sav);
+ }
+ }
+
+ if(sav->status == RESTART) {
+ /* if sorting thread is runnning stop it */
+ sav->sort_status = STOP;
+ pthread_join(p1, NULL);
+
+ reset_sort_stats(sav);
+
shuffle(sav->arr);
+
sav->status = RUN;
- sav->sort_status = RUN;
+ sav->sort_status = PAUSE;
- /* let's call p1 again */
+ /* let's start the sorting thread */
pthread_create(&p1, NULL, &routine_wrapper, (void *)sav);
}
}
end:
- pthread_join(p1, NULL);
+
+ /* check if p1 has been initialized */
+ if(p1 != 0)
+ pthread_join(p1, NULL);
SAV_destroy(sav);
Drw_destroy(drw);
@@ -96,12 +120,21 @@ void check_events(Drw *drw, SAV *sav) {
case SDL_KEYDOWN:
switch(event.key.keysym.scancode) {
case SDL_SCANCODE_R:
- if(sav->sort_status == SORTED) sav->status = RESTART;
+ if(sav->status == RUN) sav->status = RESTART;
break;
case SDL_SCANCODE_SPACE:
- if(sav->sort_status == PAUSE) sav->status = sav->sort_status = RUN;
+ if(sav->sort_status == PAUSE) sav->sort_status = RUN;
else if(sav->sort_status == RUN) sav->sort_status = PAUSE;
break;
+ case SDL_SCANCODE_Q:
+ sav->status = sav->sort_status = STOP;
+ break;
+ case SDL_SCANCODE_EQUALS:
+ set_sort_speed(sav, sav->sort_delay - 1);
+ break;
+ case SDL_SCANCODE_MINUS:
+ set_sort_speed(sav, sav->sort_delay + 1);
+ break;
default: break;
}
break;
diff --git a/sav.c b/sav.c
@@ -1,4 +1,12 @@
#include "sav.h"
+#include "sort.h"
+
+void reset_sort_stats(SAV *sav) {
+ if(sav == NULL) return;
+
+ sav->sel = sav->cmp = ARR_MAX + 1;
+ sav->cmps = sav->swps = sav->B_used = 0;
+}
status_t SAV_new(SAV **sav) {
if((*sav = (SAV *)malloc(sizeof(SAV))) == NULL)
@@ -6,9 +14,11 @@ status_t SAV_new(SAV **sav) {
(*sav)->sel = (*sav)->cmp = ARR_MAX + 1;
(*sav)->cmps = (*sav)->swps = (*sav)->its = (*sav)->B_used = 0;
+
(*sav)->status = RUN;
(*sav)->sort_status = PAUSE;
(*sav)->sort_algo = ALGORITHMS_COUNT;
+ (*sav)->sort_delay = SORT_DELAY_DEFAULT;
if(((*sav)->arr = (Arr *)malloc(sizeof(Arr))) == NULL)
return ERROR_MEMORY_ALLOC;
diff --git a/sav.h b/sav.h
@@ -21,13 +21,16 @@ typedef enum {
typedef struct {
Arr *arr;
size_t sel, cmp, cmps, swps, its, B_used;
- clock_t ti, tf;
- status_t status;
- status_t sort_status;
+ /* clock_t ti, tf; */
+ time_t ti, tf;
+ status_t status, prev_status, sort_status;
sort_t sort_algo;
+ size_t sort_delay;
} SAV;
status_t SAV_new(SAV **sav);
void SAV_destroy(SAV *sav);
+void reset_sort_stats(SAV *sav);
+
#endif
diff --git a/sdl_extra.h b/sdl_extra.h
@@ -6,8 +6,6 @@
#include "array.h"
#include "status.h"
-#include "drw.h"
-#include "sav.h"
#define X_BORDER 40
#define Y_BORDER 40
diff --git a/sort.c b/sort.c
@@ -4,20 +4,31 @@
#include "sort.h"
-#define DELAY 5
+void set_sort_speed(SAV *sav, size_t new_value) {
+ if(sav == NULL) return;
+
+ if((new_value > 0) && (new_value < SORT_DELAY_MAX)) {
+ printf("INFO: Updating sort_delay to: %ld\n", new_value);
+ sav->sort_delay = new_value;
+ }
+}
-status_t sort_wait(SAV *sav) {
+status_t sort_delay(const SAV *sav) {
size_t i;
- /* Delay */
- for(i = 0; i < DELAY; i++) {
+ for(i = 0; i < sav->sort_delay; i++) {
if((sav->sort_status == STOP) || (sav->status == STOP))
return STOP;
SDL_Delay(1);
}
- while(sav->sort_status == PAUSE);
+ return OK;
+}
+
+status_t sort_pause(const SAV *sav) {
+ while(sav->sort_status == PAUSE)
+ if(sort_delay(sav) == STOP) return STOP;
return OK;
}
@@ -27,13 +38,14 @@ void insertion_sort(SAV *sav) {
size_t i, j;
if(sav == NULL) return;
+ if(sort_pause(sav) == STOP) return;
- if((sav->sort_status == STOP) || (sav->status == STOP)) return;
- while(sav->sort_status == PAUSE);
+ sav->ti = time(NULL);
- sav->ti = clock();
+ for(i = 1; (i < sav->arr->len) && (sav->sort_status != STOP); i++) {
+ if(sort_delay(sav) == STOP) break;
+ if(sort_pause(sav) == STOP) break;
- for(i = 1; i < sav->arr->len; i++, sav->its++) {
sav->cmps += 1;
key = sav->arr->v[i];
j = i - 1;
@@ -43,32 +55,34 @@ void insertion_sort(SAV *sav) {
j--;
sav->sel = i;
- sav->cmp = j;
+ sav->cmp = j + 1;
sav->its++;
+
+ if(sort_delay(sav) == STOP) break;
+ if(sort_pause(sav) == STOP) break;
}
sav->arr->v[j + 1] = key;
sav->sel = i;
- sav->cmp = j;
+ sav->cmp = j + 1;
sav->swps += 1;
-
- if(sort_wait(sav) == STOP) break;
}
- sav->tf = clock();
+ sav->tf = time(NULL);
- if(sav->status != STOP) sav->sort_status = SORTED;
+ if(sav->sort_status != STOP) sav->sort_status = SORTED;
+ sav->sel = sav->cmp = ARR_MAX + 1;
}
void bubble_sort(SAV *sav) {
size_t i, j;
if(sav == NULL) return;
+ if(sort_pause(sav) == STOP) return;
- 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++) {
+ sav->ti = time(NULL);
+ for(i = 0; (i < sav->arr->len - 1) && (sav->sort_status != STOP); i++) {
+ if(sort_delay(sav) == STOP) break;
+ if(sort_pause(sav) == STOP) break;
for(j = 0; j < (sav->arr->len - 1 - i); j++, sav->its++) {
sav->sel = j + 1;
sav->cmp = j;
@@ -77,21 +91,20 @@ void bubble_sort(SAV *sav) {
swap(sav->arr->v + j, sav->arr->v+j+1);
sav->swps += 1;
}
- if(sort_wait(sav) == STOP) goto end;
+ if(sort_delay(sav) == STOP) break;
+ if(sort_pause(sav) == STOP) break;
}
- if(sort_wait(sav) == STOP) goto end;
}
- end:
- sav->tf = clock();
+ sav->tf = time(NULL);
if(sav->status != STOP) sav->sort_status = SORTED;
+ sav->sel = sav->cmp = ARR_MAX + 1;
}
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);
+ if(sort_pause(sav) == STOP) return;
n1 = middle - low;
n2 = high - middle;
@@ -118,19 +131,16 @@ void merge(SAV *sav, int low, int middle, int high) {
sav->cmps += 1;
sav->its += 1;
- if(sort_wait(sav) == STOP) goto end;
+ if(sort_delay(sav) == STOP) return;
+ if(sort_pause(sav) == STOP) return;
}
- end:
while(i < n1) sav->arr->v[k++] = B[i++];
while(j < n2) sav->arr->v[k++] = C[j++];
}
void merge_sort(SAV *sav, int low, int high) {
- if((sav->sort_status == STOP) || (sav->status == STOP))
- return;
-
- while(sav->sort_status == PAUSE);
+ if(sort_pause(sav) == STOP) return;
int middle;
@@ -152,11 +162,12 @@ void merge_sort(SAV *sav, int low, int high) {
void merge_sort_wrapper(SAV *sav) {
if(sav == NULL) return;
- sav->ti = clock();
+ sav->ti = time(NULL);
merge_sort(sav, 0, sav->arr->len);
- sav->tf = clock();
+ sav->tf = time(NULL);
sav->sel = sav->arr->len + 1;
if(sav->status != STOP) sav->sort_status = SORTED;
+ sav->sel = sav->cmp = ARR_MAX + 1;
}
void quick_sort_partition(SAV *sav, int low, int *middle, int high) {
@@ -164,7 +175,6 @@ void quick_sort_partition(SAV *sav, int low, int *middle, int high) {
pivot = high;
sav->sel = 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]) {
@@ -172,9 +182,9 @@ void quick_sort_partition(SAV *sav, int low, int *middle, int high) {
sav->swps += 1;
}
- if(sort_wait(sav) == STOP) goto end;
+ if(sort_delay(sav) == STOP) return;
+ if(sort_pause(sav) == STOP) return;
}
- end:
swap(&(sav->arr->v[i]), &(sav->arr->v[pivot]));
sav->swps += 1;
@@ -184,8 +194,7 @@ void quick_sort_partition(SAV *sav, int low, int *middle, int high) {
void quick_sort(SAV *sav, int low, int high) {
int pivot;
- if(sav->status == STOP) return;
- while(sav->sort_status == PAUSE);
+ if(sort_pause(sav) == STOP) return;
if ((high - low) > 0) {
quick_sort_partition(sav, low, &pivot, high);
@@ -197,9 +206,10 @@ void quick_sort(SAV *sav, int low, int high) {
void quick_sort_wrapper(SAV *sav) {
if(sav == NULL) return;
- sav->ti = clock();
+ sav->ti = time(NULL);
quick_sort(sav, 0, sav->arr->len - 1);
printf("SORT: sorting array done\n");
if(sav->sort_status != STOP) sav->sort_status = SORTED;
- sav->tf = clock();
+ sav->sel = sav->cmp = ARR_MAX + 1;
+ sav->tf = time(NULL);
}
diff --git a/sort.h b/sort.h
@@ -6,6 +6,11 @@
#include "sav.h"
+#define SORT_DELAY_DEFAULT 5
+#define SORT_DELAY_MAX 250
+
+void set_sort_speed(SAV *sav, size_t new_value);
+
void bubble_sort(SAV *);
void insertion_sort(SAV *);
@@ -17,18 +22,4 @@ void quick_sort_wrapper(SAV *sav);
void quick_sort(SAV *sav, int low, int high);
void quick_sort_partition(SAV *sav, int low, int *middle, int high);
-static void (*sort_handler[ALGORITHMS_COUNT])(SAV *) = {
- &bubble_sort,
- &insertion_sort,
- &merge_sort_wrapper,
- &quick_sort_wrapper
-};
-
-static const char *algo_strings[ALGORITHMS_COUNT] = {
- "bubble",
- "insertion",
- "merge",
- "quick"
-};
-
#endif // __SORT_H__
diff --git a/status.h b/status.h
@@ -5,17 +5,18 @@ typedef enum {
OK = 0,
RUN,
PAUSE,
+ SORTED,
+ STOP,
UPDATE,
ERROR_MEMORY_ALLOC,
ERROR_OPENING_FONT,
ERROR_SDL_FONT_INIT,
ERROR_NULL_POINTER,
ERROR_DRW,
- SORTED,
START,
RESTART,
WELCOME,
- STOP
+ STATUS_MAX
} status_t;
#endif
