aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorNebuleon Fumika2013-01-27 00:45:59 -0500
committerNebuleon Fumika2013-01-27 00:45:59 -0500
commitcfa1c811c65f1b8a10d9034a5974d617cda92ec6 (patch)
treebf9686f73faed39ef7c3c49c05d92d597d9143de
parent362b28e9372d124ac6602bfc49e9775e510ba929 (diff)
downloadsnes9x2005-cfa1c811c65f1b8a10d9034a5974d617cda92ec6.tar.gz
snes9x2005-cfa1c811c65f1b8a10d9034a5974d617cda92ec6.tar.bz2
snes9x2005-cfa1c811c65f1b8a10d9034a5974d617cda92ec6.zip
Reimplement Quicksort correctly for file selection screens. Before this commit, the emulator could sometimes give a file out of its order, for example an O* file between two S* files.
-rw-r--r--source/nds/gui.c69
1 files changed, 34 insertions, 35 deletions
diff --git a/source/nds/gui.c b/source/nds/gui.c
index ece310c..c57c660 100644
--- a/source/nds/gui.c
+++ b/source/nds/gui.c
@@ -435,53 +435,52 @@ void change_ext(char *src, char *buffer, char *extension)
--------------------------------------------------------*/
static int sort_function(const void *dest_str_ptr, const void *src_str_ptr)
{
- char *dest_str = *((char **)dest_str_ptr);
- char *src_str = *((char **)src_str_ptr);
+ char *dest_str = ((char *)dest_str_ptr);
+ char *src_str = ((char *)src_str_ptr);
// For files and directories, . and .. sort first.
- if(src_str[0] == '.')
+ if(src_str[0] == '.' && dest_str[0] != '.')
return 1;
- if(dest_str[0] == '.')
+ if(dest_str[0] == '.' && src_str[0] != '.')
return -1;
return strcasecmp(dest_str, src_str);
}
-static int my_array_partion(void *array, int left, int right)
+static int my_array_partion(void **array, int left, int right)
{
- unsigned int pivot= *((unsigned int*)array + left);
-
- while(left < right)
- {
- while(sort_function((void*)((unsigned int*)array+left), (void*)((unsigned int *)array+right)) < 0) {
- right--;
- }
-
- if(right== left) break;
- *((unsigned int*)array + left) = *((unsigned int*)array + right);
- *((unsigned int*)array + right) = pivot;
-
- if(left < right)
- {
- left++;
- if(right== left) break;
- }
-
- while(sort_function((void*)((unsigned int*)array+right), (void*)((unsigned int *)array+left)) > 0) {
- left++;
- }
+ // Choose a pivot, left <= pivot <= right
+ unsigned int pivotIndex = left + (right - left) / 2;
+
+ // Move pivot value to the end
+ void *temp = array[pivotIndex];
+ array[pivotIndex] = array[right];
+ array[right] = temp;
+
+ // Move values that sort before the pivot value to before the new
+ // pivot's location
+ unsigned int storeIndex = left, i;
+ for (i = left; i <= right - 1; i++)
+ {
+ if (sort_function(array[i], array[right]) < 0)
+ {
+ temp = array[i];
+ array[i] = array[storeIndex];
+ array[storeIndex] = temp;
+ storeIndex++;
+ }
+ }
- if(left== right) break;
- *((unsigned int*)array + right) = *((unsigned int*)array + left);
- *((unsigned int*)array + left) = pivot;
- right--;
- }
+ // Move the pivot value to its correct location
+ temp = array[storeIndex];
+ array[storeIndex] = array[right];
+ array[right] = temp;
- return left;
+ return storeIndex;
}
-static void my_qsort(void *array, int left, int right)
+static void my_qsort(void **array, int left, int right)
{
if(left < right)
{
@@ -748,9 +747,9 @@ static int load_file_list(struct FILE_LIST_INFO *filelist_infop)
#if 0
my_qsort((void *)file_list, 0, num_files-1);
#else //to support ".." directory, but take it as file
- my_qsort((void *)file_list, 1, num_files-1);
+ my_qsort((void **)file_list, 1, num_files-1);
#endif
- my_qsort((void *)dir_list, 0, num_dirs-1);
+ my_qsort((void **)dir_list, 0, num_dirs-1);
return 0;
}