commit 86e93e464823fba6d6137500cb14cfcc06e2b421
parent 36a84f0c5aa1e083c042c507ad52f82c65462e03
Author: Martin J. Klöckner <64109770+klewer-martin@users.noreply.github.com>
Date: Sat, 16 Apr 2022 01:19:34 -0300
Merge pull request #7 from klewer-martin/modules-reorganization
Fixed high memory usage
Diffstat:
| M | Makefile | | | 11 | +++++------ |
| M | drw.c | | | 95 | +++++++++++++++++++++++++++++++++++-------------------------------------------- |
| M | main.c | | | 18 | +++++++++++++----- |
| M | sort.c | | | 91 | ++++++++++++++++++++++++++++--------------------------------------------------- |
| M | sort.h | | | 1 | - |
| M | util.c | | | 7 | ------- |
| M | util.h | | | 6 | ++++++ |
7 files changed, 98 insertions(+), 131 deletions(-)
diff --git a/Makefile b/Makefile
@@ -1,9 +1,8 @@
-CC := cc
-CLIBS := `sdl2-config --libs --cflags`
-CFLAGS := -lSDL2_ttf -lm -Werror -pedantic -ansi -std=c99 -pthread
-SRCS := main.c sav.c util.c sort.c drw.c sdl_extra.c array.c
+CC := gcc
+CLIBS := `sdl2-config --libs` -lSDL2_ttf -lm
+CFLAGS := `sdl2-config --cflags` -Wall -Wshadow -pedantic -ansi -std=c99 -pthread
+SRCS := $(wildcard *.c)
OBJS := $(SRCS:.c=.o)
-LIBS := array.h status.h
TARGET := sav
@@ -11,7 +10,7 @@ TARGET := sav
all: $(TARGET) clean
-$(TARGET): $(OBJS) $(HEADERS) $(LIBS)
+$(TARGET): $(OBJS) $(HEADERS)
$(CC) $(CLIBS) $(CFLAGS) -o $@ $^
%.o: %.c
diff --git a/drw.c b/drw.c
@@ -1,46 +1,37 @@
#include "drw.h"
-void drw_element_color(Drw *drw, int x, int y, int h, unsigned int col) {
- SDL_Rect rect;
- unsigned char r, g, b, a;
+static SDL_Rect rect;
+void drw_element_color(Drw *drw, int x, int y, int h, unsigned int col) {
rect.x = x + drw->x_border; /* bottom left + x */
rect.y = y - drw->y_border; /* bottom */
rect.w = RECT_WIDTH; /* fixed width */
rect.h = -h;
- r = (char)(col >> 24) & 0xFF;
- g = (char)(col >> 16) & 0xFF;
- b = (char)(col >> 8) & 0xFF;
- a = (char)(col) & 0xFF;
-
- SDL_RenderDrawRect(drw->rend, &rect);
- SDL_SetRenderDrawColor(drw->rend, r, g, b, a);
+ /* SDL_RenderDrawRect(drw->rend, &rect); */
+ SDL_SetRenderDrawColor(drw->rend, UNHEX(col));
SDL_RenderFillRect(drw->rend, &rect);
- SDL_SetRenderDrawColor(drw->rend, 0, 0, 0, 0);
- SDL_RenderDrawLine(drw->rend, x + drw->x_border, y - drw->y_border, x + drw->x_border, y - drw->y_border - h);
+ /* printf("INFO: color: #%02X%02X%02X%02X\n", UNHEX(col)); */
+
+ 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);
}
void drw_array_graph(Drw *drw, SAV *sav) {
- int x, w, h;
-
- SDL_GetWindowSize(drw->win, &w, &h);
-
- SDL_SetRenderDrawColor(drw->rend, 29, 28, 28, 0);
- SDL_RenderClear(drw->rend);
+ int x;
size_t i;
for(i = x = 0; i < sav->arr->len; i++, x += RECT_WIDTH) {
- if(i == sav->sel) drw_element_color(drw, x, h, sav->arr->v[i], SEL_COLOR);
- 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);
+ if(i == sav->sel) drw_element_color(drw, x, drw->h, sav->arr->v[i], SEL_COLOR);
+ else if(i == sav->cmp) drw_element_color(drw, x, drw->h, sav->arr->v[i], CMP_COLOR);
+ else drw_element_color(drw, x, drw->h, sav->arr->v[i], NORM_COLOR);
}
- drw_status_bar(drw, sav);
}
void drw_status_bar(Drw *drw, SAV *sav) {
- SDL_Rect rect;
int bar_border = 2;
rect.x = bar_border; /* top left + x */
@@ -48,44 +39,39 @@ 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);
+ /* SDL_RenderDrawRect(drw->rend, &rect); */
/* TODO: Make a variable to store statusbar background color */
- SDL_SetRenderDrawColor(drw->rend, 0, 0, 0, 0); /* RGBA */
+ SDL_SetRenderDrawColor(drw->rend, UNHEX(0x000000FF)); /* RGBA */
SDL_RenderFillRect(drw->rend, &rect);
- if((sav->status == RUN) || (sav->status == UPDATE) || (sav->status == START) || sav->status == WELCOME) {
- if(sav->sort_status == SORTED) {
+ /* TODO: create a function which fetchs the status text to be drawn based on the status */
+ 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,
- "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,
- "(%s sort selected) press SPACE to start sorting",
- algo_strings[sav->sort_algo], sav->arr->len, sav->cmps,
- sav->swps);
- } else if(sav->status == WELCOME) {
- 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);
- }
+ "[%s sort selected] press SPACE to start sorting",
+ algo_strings[sav->sort_algo]);
+ } else if(sav->status == WELCOME) {
+ 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 {
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);
+ "PAUSED [%s sort] press SPACE to resume", algo_strings[sav->sort_algo]);
}
- drw_text(drw, drw->bar_text, 0, drw->h - drw->font_size - 5);
+ } 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);
}
@@ -99,6 +85,8 @@ void drw_text(Drw *drw, char *text, int x, int y) {
drw->bar_text_rect.h = drw->text_surface->h;
SDL_RenderCopy(drw->rend, drw->text_texture, NULL, &drw->bar_text_rect);
+ SDL_DestroyTexture(drw->text_texture);
+ SDL_FreeSurface(drw->text_surface);
}
status_t Drw_new(Drw **drw) {
@@ -110,6 +98,7 @@ status_t Drw_new(Drw **drw) {
return ERROR_MEMORY_ALLOC;
SDL_setup(&win, &rend);
+
(*drw)->rend = rend;
(*drw)->win = win;
@@ -148,7 +137,7 @@ status_t Drw_new(Drw **drw) {
{
int w_text, h_text;
TTF_SizeText(font,
- "SORTED (XXXXXXXXXXs sort) done in XXX.Xs, L: XXXXX,\
+ "SORTED [XXXXXXXXXXs sort] done in XXX.Xs, L: XXXXX,\
C: XXXXXX, S: XXXXXX, I: XXXXXX, storage used: XXXXXX Bytes",
&w_text, &h_text);
diff --git a/main.c b/main.c
@@ -9,6 +9,9 @@
#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 */
+
void check_events(Drw *, SAV *);
void *routine_wrapper(void *);
@@ -37,9 +40,10 @@ int main (void) {
/* assigns random values to array */
shuffle(sav->arr);
- /* selecting the sorting algorithms */
+ /* 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);
@@ -51,14 +55,17 @@ int main (void) {
while(sav->status != STOP) {
check_events(drw, sav);
- if(sav->status == WELCOME)
- if((((tc = clock()) - ti) / CLOCKS_PER_SEC) > WELCOME_MSG_TIME)
- sav->status = START;
+ SDL_SetRenderDrawColor(drw->rend, 29, 28, 28, 0);
+ SDL_RenderClear(drw->rend);
drw_array_graph(drw, sav);
drw_status_bar(drw, sav);
SDL_RenderPresent(drw->rend);
+ if(sav->status == WELCOME)
+ if((((tc = clock()) - ti) / CLOCKS_PER_SEC) > WELCOME_MSG_TIME)
+ sav->status = START;
+
if((sav->sort_status == SORTED) && (sav->status == RESTART)) {
/* this state can only be achived if p1 ended */
shuffle(sav->arr);
@@ -69,6 +76,7 @@ int main (void) {
pthread_create(&p1, NULL, &routine_wrapper, (void *)sav);
}
}
+
end:
pthread_join(p1, NULL);
@@ -79,6 +87,7 @@ int main (void) {
void check_events(Drw *drw, SAV *sav) {
SDL_Event event;
+
while (SDL_PollEvent(&event)) {
switch(event.type) {
case SDL_QUIT:
@@ -114,4 +123,3 @@ void check_events(Drw *drw, SAV *sav) {
}
}
}
-
diff --git a/sort.c b/sort.c
@@ -6,14 +6,33 @@
#define DELAY 5
+status_t sort_wait(SAV *sav) {
+ size_t i;
+
+ /* Delay */
+ for(i = 0; i < DELAY; i++) {
+ if((sav->sort_status == STOP) || (sav->status == STOP))
+ return STOP;
+
+ SDL_Delay(1);
+ }
+
+ while(sav->sort_status == PAUSE);
+
+ return OK;
+}
+
void insertion_sort(SAV *sav) {
int key;
size_t i, j;
+ if(sav == NULL) return;
+
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;
key = sav->arr->v[i];
@@ -26,31 +45,14 @@ void insertion_sort(SAV *sav) {
sav->sel = i;
sav->cmp = j;
sav->its++;
-
- /* 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;
- /* 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);
+ if(sort_wait(sav) == STOP) break;
}
- end:
sav->tf = clock();
@@ -60,6 +62,8 @@ void insertion_sort(SAV *sav) {
void bubble_sort(SAV *sav) {
size_t i, j;
+ if(sav == NULL) return;
+
if((sav->sort_status == STOP) || (sav->status == STOP)) return;
while(sav->sort_status == PAUSE);
@@ -73,25 +77,9 @@ void bubble_sort(SAV *sav) {
swap(sav->arr->v + j, sav->arr->v+j+1);
sav->swps += 1;
}
-
- /* 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);
+ if(sort_wait(sav) == STOP) goto end;
}
-
- /* 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);
+ if(sort_wait(sav) == STOP) goto end;
}
end:
@@ -130,28 +118,15 @@ void merge(SAV *sav, int low, int middle, int high) {
sav->cmps += 1;
sav->its += 1;
- 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);
- }
+ if(sort_wait(sav) == STOP) goto end;
}
end:
- while(i < n1)
- sav->arr->v[k++] = B[i++];
-
- while (j < n2)
- sav->arr->v[k++] = C[j++];
+ 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 == NULL) return;
-
if((sav->sort_status == STOP) || (sav->status == STOP))
return;
@@ -175,6 +150,8 @@ void merge_sort(SAV *sav, int low, int high) {
}
void merge_sort_wrapper(SAV *sav) {
+ if(sav == NULL) return;
+
sav->ti = clock();
merge_sort(sav, 0, sav->arr->len);
sav->tf = clock();
@@ -195,13 +172,7 @@ void quick_sort_partition(SAV *sav, int low, int *middle, int high) {
sav->swps += 1;
}
- 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);
- }
+ if(sort_wait(sav) == STOP) goto end;
}
end:
@@ -224,6 +195,8 @@ void quick_sort(SAV *sav, int low, int high) {
}
void quick_sort_wrapper(SAV *sav) {
+ if(sav == NULL) return;
+
sav->ti = clock();
quick_sort(sav, 0, sav->arr->len - 1);
printf("SORT: sorting array done\n");
diff --git a/sort.h b/sort.h
@@ -24,7 +24,6 @@ static void (*sort_handler[ALGORITHMS_COUNT])(SAV *) = {
&quick_sort_wrapper
};
-/* static const char *algo_strings[ALGORITHMS_COUNT]; */
static const char *algo_strings[ALGORITHMS_COUNT] = {
"bubble",
"insertion",
diff --git a/util.c b/util.c
@@ -1,12 +1,5 @@
#include "util.h"
-void wait_main_thread(status_t *st) {
- if((*st != STOP) && (*st != PAUSE)) *st = UPDATE;
-
- /* wait 'til main thread changes st value to RUN */
- while((*st == UPDATE) || (*st == PAUSE));
-}
-
void end(const char *msg) {
fprintf(stderr, "%s\n", msg);
exit(1);
diff --git a/util.h b/util.h
@@ -6,6 +6,12 @@
#include "status.h"
+#define UNHEX(color) \
+ ((color) >> (8 * 3)) & 0xFF, \
+ ((color) >> (8 * 2)) & 0xFF, \
+ ((color) >> (8 * 1)) & 0xFF, \
+ ((color) >> (8 * 0)) & 0xFF
+
void end(const char *msg);
void swap(int *a, int *b);
void wait_main_thread(status_t *st);
