commit e2906963e3d9eab289c9862128a6f1d33bccc5fa
parent 2a48566bef7af181a2e6e5cd735e07f4a76e6370
Author: Martin J. Klöckner <64109770+klewer-martin@users.noreply.github.com>
Date: Mon, 4 Jul 2022 21:29:46 -0300
Merge pull request #14 from klewer-martin/insertion_sort_leak
General code refactorization and bug fixes
Diffstat:
14 files changed, 175 insertions(+), 126 deletions(-)
diff --git a/README.md b/README.md
@@ -4,13 +4,20 @@ The idea is to develop a visual program that shows how an array is being sorted
Written using C and SDL2 library for graphics
-
+
-# Quick start
+## Quick start
```console
$ make
$ ./sav
+
```
-You can change the sorting algorithm by setting the varible "sel\_algo" in the main function
-(in a future this will be done by parsing command line arguments)
+## Keybindings
+
+- `space` - start/stop.
+- `tab` - change sorting algorithm.
+- `R` - restart.
+
+## License
+[MIT](./LICENSE)
diff --git a/array.c b/array.c
@@ -9,10 +9,37 @@ static void (*shuffle_handler[MAX_SHUFFLE])(Arr *arr) = {
&arr_random
};
+status_t Arr_create(Arr **arr) {
+ if(((*arr) = (Arr *)malloc(sizeof(Arr))) == NULL)
+ return ERROR_MEMORY_ALLOC;
+
+ if(((*arr)->v = malloc(sizeof(int) * (ARR_LEN + 4))) == NULL)
+ return ERROR_MEMORY_ALLOC;
+
+ if(((*arr)->bk = malloc(sizeof(int) * (ARR_LEN + 4))) == NULL)
+ return ERROR_MEMORY_ALLOC;
+
+ (*arr)->len = ARR_LEN;
+ (*arr)->shuffle = NULL;
+
+ return OK;
+}
+
+void Arr_destroy(Arr *arr) {
+ free(arr->bk);
+ free(arr->v);
+ free(arr);
+}
+
+void arr_restore_from_bk(Arr *arr) {
+ for(size_t i = 0; i < arr->len; i++)
+ arr->v[i] = arr->bk[i];
+}
+
void arr_random(Arr *arr) {
srand((unsigned int)time(NULL));
for(size_t i = 0; i < arr->len; i++)
- while(!(arr->v[i] = rand() % ARR_MAX));
+ while(!(arr->v[i] = arr->bk[i] = rand() % ARR_MAX));
printf("ARRAY: Shuffling array done\n");
}
diff --git a/array.h b/array.h
@@ -2,6 +2,7 @@
#define __ARRAY_H__
#include <stdlib.h>
+#include "status.h"
#define ARR_LEN 128
#define ARR_MAX 512
@@ -15,6 +16,7 @@ typedef enum {
typedef struct _Arr {
int *v;
+ int *bk;
size_t len;
shuffle_t shuffle_sel;
void (*shuffle)(struct _Arr *arr);
@@ -26,10 +28,14 @@ static char *const shuffle_t_str[MAX_SHUFFLE] = {
"random",
};
+status_t Arr_create(Arr **arr);
+void Arr_destroy(Arr *arr);
+
void arr_random(Arr *arr);
void arr_reversed(Arr *arr);
void arr_in_order(Arr *arr);
+void arr_restore_from_bk(Arr *arr);
void arr_shuffle(Arr *arr);
void arr_shuffle_next(Arr *arr);
diff --git a/drw.c b/drw.c
@@ -1,10 +1,11 @@
#include "drw.h"
-#include <assert.h>
-
-static SDL_Rect rect;
+static status_t drw_status_bar_fetch_text(Drw *, SAV *);
+static void drw_text(Drw *drw, const char *text, int x, int y);
void drw_element_color(Drw *drw, int x, int y, int h, unsigned int col) {
+ SDL_Rect rect;
+
rect.x = x + drw->x_border; /* bottom left + x */
rect.y = y - drw->y_border; /* bottom */
rect.w = RECT_WIDTH; /* fixed width */
@@ -32,87 +33,98 @@ void drw_array_graph(Drw *drw, SAV *sav) {
}
}
-void drw_status_bar(Drw *drw, SAV *sav) {
- 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;
-
- /* TODO: Make a variable to store statusbar background color */
- SDL_SetRenderDrawColor(drw->rend, UNHEX(0x000000FF)); /* RGBA */
- SDL_RenderFillRect(drw->rend, &rect);
+static status_t drw_status_bar_fetch_text(Drw *drw, SAV *sav) {
+ if(drw->bar_text == NULL) return ERROR_NULL_POINTER;
- /* TODO: create a function which fetchs the status text to be drawn based on the status */
if(sav->status == WELCOME) {
snprintf(drw->bar_text, drw->bar_text_len - 2,
- " Welcome to sorting algorithms visualized [%s] [%s] press SPACE to start sorting",
- algo_sel_str[sav->sort_algo], shuffle_t_str[sav->arr->shuffle_sel]);
+ " Welcome to sorting algorithms visualized [%s] [%-25s press SPACE to start sorting",
+ shuffle_t_str[sav->arr->shuffle_sel], algo_sel_str[sav->sort_algo]);
}
else if(sav->status == START) {
snprintf(drw->bar_text, drw->bar_text_len - 2,
- " %-8s [%s] [%s] press SPACE to start sorting", sort_status_str[OK],
- algo_sel_str[sav->sort_algo], shuffle_t_str[sav->arr->shuffle_sel]);
+ " %-8s [%s] [%-25s press SPACE to start sorting", sort_status_str[OK],
+ shuffle_t_str[sav->arr->shuffle_sel], 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,
- " %-8s [%s] [%s] L: %ld, C: %ld, S: %ld Press SPACE to resume",
+ " %-8s [%s] [%-25s L: %ld, C: %ld, S: %ld Press SPACE to resume",
sort_status_str[sav->sort_status],
- algo_sel_str[sav->sort_algo], shuffle_t_str[sav->arr->shuffle_sel],
+ shuffle_t_str[sav->arr->shuffle_sel], algo_sel_str[sav->sort_algo],
sav->arr->len, sav->cmps, sav->swps);
else if(sav->sort_status == SORTED)
snprintf(drw->bar_text, drw->bar_text_len - 2,
- " %-8s [%s] [%s] L: %ld, C: %ld, S: %ld, done in %lds, extra storage used: %ld Bytes",
+ " %-8s [%s] [%-25s L: %ld, C: %ld, S: %ld, done in %lds, extra storage used: %ld Bytes",
sort_status_str[sav->sort_status],
- algo_sel_str[sav->sort_algo], shuffle_t_str[sav->arr->shuffle_sel],
+ shuffle_t_str[sav->arr->shuffle_sel], algo_sel_str[sav->sort_algo],
sav->arr->len, sav->cmps, sav->swps, (sav->tf - sav->ti), sav->B_used);
else if(sav->sort_status == RUN)
snprintf(drw->bar_text, drw->bar_text_len - 2,
- " %-8s [%s] [%s] L: %ld, C: %ld, S: %ld", sort_status_str[sav->sort_status],
- algo_sel_str[sav->sort_algo], shuffle_t_str[sav->arr->shuffle_sel],
+ " %-8s [%s] [%-25s L: %ld, C: %ld, S: %ld", sort_status_str[sav->sort_status],
+ shuffle_t_str[sav->arr->shuffle_sel], 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);
+ return OK;
}
-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);
+static void drw_text(Drw *drw, const char *text, int x, int y) {
+ SDL_Surface *text_surface;
+ SDL_Texture *text_texture;
+
+ /* TODO: UNICODE support? */
+ /* drw->text_surface = TTF_RenderText_Blended(drw->font, text, drw->text_color); */
+ /* drw->text_surface = TTF_RenderUNICODE_Blended(drw->font, text, drw->text_color); */
+ text_surface = TTF_RenderUTF8_Blended(drw->font, text, drw->text_color);
+ text_texture = SDL_CreateTextureFromSurface(drw->rend, text_surface);
drw->bar_text_rect.x = 10 + x;
drw->bar_text_rect.y = drw->h - drw->font_size - 5;
- drw->bar_text_rect.w = drw->text_surface->w;
- drw->bar_text_rect.h = drw->text_surface->h;
+ drw->bar_text_rect.w = text_surface->w;
+ drw->bar_text_rect.h = 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);
+ SDL_RenderCopy(drw->rend, text_texture, NULL, &drw->bar_text_rect);
+ SDL_DestroyTexture(text_texture);
+ SDL_FreeSurface(text_surface);
}
-status_t Drw_create(Drw **drw) {
- SDL_Renderer *rend;
- SDL_Window *win;
- TTF_Font *font;
+status_t drw_status_bar(Drw *drw, SAV *sav) {
+ status_t st;
+ 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;
- if((*drw = (Drw *)malloc(sizeof(Drw))) == NULL)
- return ERROR_MEMORY_ALLOC;
+ /* TODO: Make a variable to store statusbar background color */
+ SDL_SetRenderDrawColor(drw->rend, UNHEX(0x000000FF)); /* RGBA */
+ SDL_RenderFillRect(drw->rend, &rect);
- SDL_setup(&win, &rend);
+ if((st = drw_status_bar_fetch_text(drw, sav)) != OK) return st;
- (*drw)->rend = rend;
- (*drw)->win = win;
+ drw_text(drw, drw->bar_text, 0, drw->h - drw->font_size - 5);
+ memset(drw->bar_text, 0, sizeof(char) * drw->bar_text_len);
- font = TTF_OpenFont(FONT_NAME, FONT_SIZE);
+ return OK;
+}
- if(font == NULL) {
- fprintf(stderr, "TTF_OpenFont: %s\n", TTF_GetError());
- return ERROR_OPENING_FONT;
- }
+status_t Drw_create(Drw **drw) {
+ SDL_Renderer *rend = NULL;
+ SDL_Window *win = NULL;
+ TTF_Font *font = NULL;
+ status_t st;
+
+ if(((*drw) = (Drw *)malloc(sizeof(Drw))) == NULL) return ERROR_MEMORY_ALLOC;
+ memset(*drw, 0, sizeof(Drw));
+
+ if((st = SDL_setup(&win, &rend)) != OK) return st;
+
+ font = TTF_OpenFont(FONT_NAME, FONT_SIZE);
+ if(font == NULL) return ERROR_TTF_OPENING_FONT;
(*drw)->rend = rend;
(*drw)->win = win;
@@ -153,9 +165,6 @@ status_t Drw_create(Drw **drw) {
(*drw)->bar_text = (char *)malloc(sizeof(char) * (*drw)->bar_text_len);
if((*drw)->bar_text == NULL) return ERROR_MEMORY_ALLOC;
- (*drw)->text_surface = NULL;
- (*drw)->text_texture = NULL;
-
return OK;
}
diff --git a/drw.h b/drw.h
@@ -30,8 +30,6 @@
typedef struct {
SDL_Renderer *rend;
SDL_Window *win;
- SDL_Surface *text_surface;
- SDL_Texture *text_texture;
SDL_Color text_color;
SDL_Rect bar_rect, bar_text_rect;
TTF_Font *font;
@@ -40,18 +38,6 @@ typedef struct {
char *bar_text;
} Drw;
-static char * const algo_sel_str[ALGORITHMS_COUNT + 1] = {
- "bubble sort",
- "improved bubble sort",
- "insertion sort",
- "merge sort",
- "quick sort",
- "shell sort",
- "selection sort",
- "heap sort",
- "sort not set"
-};
-
static char * const sort_status_str[STATUS_MAX] = {
"READY",
"SORTING",
@@ -65,9 +51,8 @@ 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, const char *text, int x, int y);
void drw_array_graph(Drw *drw, SAV *sav);
-void drw_status_bar(Drw *drw, SAV *sav);
+status_t drw_status_bar(Drw *drw, SAV *sav);
#endif
diff --git a/main.c b/main.c
@@ -13,7 +13,7 @@
void check_events(Drw *, SAV *);
-/* void *(*start_routine)(void *), pthread_create routine */
+/* pthread_create compliant start routine */
void *routine_wrapper(void *);
static void (*sort_handler[ALGORITHMS_COUNT])(SAV *) = {
@@ -27,7 +27,8 @@ static void (*sort_handler[ALGORITHMS_COUNT])(SAV *) = {
&heap_sort
};
-void *routine_wrapper(void *arg) {
+void *routine_wrapper(void *arg)
+{
SAV *sav = (SAV *)arg;
assert((sav->sort_algo != ALGORITHMS_COUNT) && "Default sorting algorithm not set");
@@ -40,8 +41,10 @@ void *routine_wrapper(void *arg) {
/* TODO: Random, reversed, in_order arrays selector from GUI */
/* TODO: Support command line arguments */
/* TODO: Support sound */
+/* TODO: More sorting algorithms */
-int main (void) {
+int main (void)
+{
SAV *sav = NULL;
Drw *drw = NULL;
time_t tic, toc;
@@ -52,18 +55,15 @@ int main (void) {
if((st = SAV_create(&sav)) != OK) goto end;
if((st = Drw_create(&drw)) != OK) goto end;
- /* default sorting algorithm */
- sav->sort_algo = SELECTION_SORT;
-
- /* default array shuffle mode */
- sav->arr->shuffle_sel = IN_ORDER;
-
- arr_shuffle(sav->arr);
-
+ /* defaults */
+ sav->sort_algo = INSERTION_SORT;
+ sav->arr->shuffle_sel = RANDOM;
sav->status = WELCOME;
sav->sort_status = PAUSE;
tic = time(NULL);
+ arr_shuffle(sav->arr);
+
/* main loop */
while(sav->status != STOP) {
check_events(drw, sav);
@@ -76,12 +76,11 @@ int main (void) {
SDL_RenderPresent(drw->rend);
- /* Print welcome message only on startup */
- if(sav->status == WELCOME)
+ if((sav->status == START) || (sav->status == WELCOME)) {
+ /* Print welcome message during the first WELCOME_MSG_TIME seconds */
if(((toc = time(NULL)) - tic) > WELCOME_MSG_TIME)
sav->status = START;
- if((sav->status == START) || (sav->status == WELCOME)) {
if(sav->sort_status == RUN) {
sav->status = RUN;
@@ -91,7 +90,7 @@ int main (void) {
}
if(sav->status == RESTART) {
- /* if sorting thread is runnning stop it */
+ /* if sorting thread is running stop it */
sav->sort_status = STOP;
pthread_join(p1, NULL);
@@ -102,12 +101,13 @@ int main (void) {
sav->sort_status = PAUSE;
}
- if(sav->sort_status == SORTED)
+ if(sav->sort_status == SORTED) {
+ pthread_join(p1, NULL);
sav->sel = sav->cmp = ARR_LEN + 1;
+ }
}
- end:
-
+end:
/* check if p1 has been initialized */
if(p1 != 0) pthread_join(p1, NULL);
@@ -116,7 +116,8 @@ int main (void) {
return 0;
}
-void check_events(Drw *drw, SAV *sav) {
+void check_events(Drw *drw, SAV *sav)
+{
SDL_Event event;
while (SDL_PollEvent(&event)) {
@@ -130,8 +131,16 @@ void check_events(Drw *drw, SAV *sav) {
if(sav->status == RUN) sav->status = RESTART;
break;
case SDL_SCANCODE_SPACE:
- if(sav->sort_status == PAUSE) sav->sort_status = RUN;
- else if(sav->sort_status == RUN) sav->sort_status = PAUSE;
+ if(sav->sort_status == PAUSE)
+ sav->sort_status = RUN;
+ else if(sav->sort_status == RUN)
+ sav->sort_status = PAUSE;
+ else if(sav->sort_status == SORTED) {
+ sort_reset_stats(sav);
+ arr_restore_from_bk(sav->arr);
+ sav->status = START;
+ sav->sort_status = RUN;
+ }
break;
case SDL_SCANCODE_Q:
sav->status = sav->sort_status = STOP;
@@ -147,6 +156,10 @@ void check_events(Drw *drw, SAV *sav) {
break;
case SDL_SCANCODE_S:
arr_shuffle_next(sav->arr);
+ if(sav->sort_status == PAUSE) {
+ if(sav->status == RUN) sav->status = RESTART;
+ else arr_shuffle(sav->arr);
+ }
break;
default: break;
}
@@ -154,7 +167,7 @@ void check_events(Drw *drw, SAV *sav) {
case SDL_WINDOWEVENT:
switch(event.window.event) {
case SDL_WINDOWEVENT_RESIZED:
- SDL_Log("Window resized to %dx%d", event.window.data1, event.window.data2);
+ /* SDL_Log("Window resized to %dx%d", event.window.data1, event.window.data2); */
drw->w = event.window.data1;
drw->h = event.window.data2;
diff --git a/sav.c b/sav.c
@@ -9,6 +9,8 @@ void sort_reset_stats(SAV *sav) {
}
status_t SAV_create(SAV **sav) {
+ status_t st;
+
if((*sav = (SAV *)malloc(sizeof(SAV))) == NULL)
return ERROR_MEMORY_ALLOC;
@@ -20,18 +22,8 @@ status_t SAV_create(SAV **sav) {
(*sav)->sort_algo = ALGORITHMS_COUNT;
(*sav)->sort_delay = SORT_DELAY_DEFAULT;
- if(((*sav)->arr = (Arr *)malloc(sizeof(Arr))) == NULL)
- return ERROR_MEMORY_ALLOC;
-
- if(((*sav)->arr->v = (int *)malloc(sizeof(int) * ARR_LEN)) == NULL)
- return ERROR_MEMORY_ALLOC;
-
- (*sav)->arr->len = ARR_LEN;
- (*sav)->arr->shuffle = NULL;
-
- if((*sav)->arr == NULL) {
- return ERROR_MEMORY_ALLOC;
- }
+ if((st = Arr_create(&(*sav)->arr)) != OK)
+ return st;
return OK;
}
@@ -39,8 +31,7 @@ status_t SAV_create(SAV **sav) {
void SAV_destroy(SAV *sav) {
if(sav == NULL) return;
- free(sav->arr->v);
- free(sav->arr);
+ Arr_destroy(sav->arr);
free(sav);
}
diff --git a/sav.h b/sav.h
@@ -1,11 +1,8 @@
#ifndef __SAV_H__
#define __SAV_H__
-#include <stdlib.h>
-#include <unistd.h>
-#include <stdbool.h>
#include <time.h>
-#include <SDL2/SDL.h>
+#include <stdbool.h>
#include "util.h"
#include "array.h"
@@ -29,6 +26,7 @@ typedef struct {
status_t status, prev_status, sort_status;
sort_t sort_algo;
size_t sort_delay;
+ bool quit;
} SAV;
status_t SAV_create(SAV **sav);
diff --git a/sdl_extra.c b/sdl_extra.c
@@ -3,7 +3,8 @@
status_t SDL_setup(SDL_Window **win, SDL_Renderer **rend) {
int min_w, min_h;
- SDL_Init(SDL_INIT_VIDEO);
+ if (SDL_Init(SDL_INIT_VIDEO) != 0)
+ return ERROR_SDL_INIT;
*win = SDL_CreateWindow(
WIN_TITLE,
@@ -14,7 +15,7 @@ status_t SDL_setup(SDL_Window **win, SDL_Renderer **rend) {
SDL_WINDOW_RESIZABLE
);
- *rend = SDL_CreateRenderer(*win, -1, SDL_RENDERER_ACCELERATED | SDL_RENDERER_PRESENTVSYNC);
+ *rend = SDL_CreateRenderer(*win, -1, SDL_RENDERER_ACCELERATED);
if ((*win == NULL) || (rend == NULL))
return ERROR_NULL_POINTER;
diff --git a/sort.c b/sort.c
@@ -1,6 +1,7 @@
#include <stdio.h>
#include <stdbool.h>
#include <time.h>
+#include <SDL2/SDL.h>
#include "sort.h"
@@ -32,7 +33,7 @@ status_t sort_pause(const SAV *sav) {
void insertion_sort(SAV *sav) {
int key;
- size_t i, j;
+ int i, j;
if(sav == NULL) return;
if(sort_pause(sav) == STOP) return;
diff --git a/sort.h b/sort.h
@@ -1,19 +1,27 @@
#ifndef __SORT_H__
#define __SORT_H__
-#include <stdio.h>
-#include <stdbool.h>
-
#include "sav.h"
#define SORT_DELAY_DEFAULT 5
#define SORT_DELAY_MAX 250
+static char * const algo_sel_str[ALGORITHMS_COUNT + 1] = {
+ "bubble sort]",
+ "improved bubble sort]",
+ "insertion sort]",
+ "merge sort]",
+ "quick sort]",
+ "shell sort]",
+ "selection sort]",
+ "heap sort]",
+ "sort not set]"
+};
+
void set_sort_speed(SAV *sav, size_t new_value);
void bubble_sort(SAV *);
void bubble_sort_improved(SAV *);
-void insertion_sort(SAV *);
void merge(SAV *, int, int, int);
void merge_sort(SAV *, int, int);
@@ -23,10 +31,11 @@ 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);
+void insertion_sort(SAV *);
void shell_sort(SAV *sav);
void selection_sort(SAV *sav);
void heap_sort(SAV *sav);
-void heapify(SAV *sav, int len, int i);
+/* void heapify(SAV *sav, int len, int i); */
#endif // __SORT_H__
diff --git a/status.h b/status.h
@@ -9,8 +9,9 @@ typedef enum {
STOP,
UPDATE,
ERROR_MEMORY_ALLOC,
- ERROR_OPENING_FONT,
+ ERROR_TTF_OPENING_FONT,
ERROR_SDL_FONT_INIT,
+ ERROR_SDL_INIT,
ERROR_NULL_POINTER,
ERROR_DRW,
START,
@@ -27,8 +28,9 @@ static char * const status_string[STATUS_MAX] = {
"STOP",
"UPDATE",
"ERROR_MEMORY_ALLOC",
- "ERROR_OPENING_FONT",
+ "ERROR_TTF_OPENING_FONT",
"ERROR_SDL_FONT_INIT",
+ "ERROR_SDL_INIT",
"ERROR_NULL_POINTER",
"ERROR_DRW",
"START",
diff --git a/util.c b/util.c
@@ -1,5 +1,8 @@
#include "util.h"
+#include <stdio.h>
+#include <stdlib.h>
+
void end(const char *msg) {
fprintf(stderr, "%s\n", msg);
exit(1);
diff --git a/util.h b/util.h
@@ -1,9 +1,6 @@
#ifndef __UTIL_H__
#define __UTIL_H__
-#include <stdio.h>
-#include <stdlib.h>
-
#include "status.h"
#define UNHEX(color) \
