Index: kernel/Makefile =================================================================== --- kernel/Makefile (revision 719a208dbe29f92f5690472a3500c890db8f3f1f) +++ kernel/Makefile (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) @@ -242,5 +242,5 @@ generic/src/lib/memstr.c \ generic/src/lib/memfnc.c \ - generic/src/lib/sort.c \ + generic/src/lib/gsort.c \ generic/src/lib/str.c \ generic/src/lib/elf.c \ Index: kernel/genarch/src/acpi/madt.c =================================================================== --- kernel/genarch/src/acpi/madt.c (revision 719a208dbe29f92f5690472a3500c890db8f3f1f) +++ kernel/genarch/src/acpi/madt.c (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) @@ -46,5 +46,5 @@ #include #include -#include +#include struct acpi_madt *acpi_madt = NULL; Index: kernel/generic/include/gsort.h =================================================================== --- kernel/generic/include/gsort.h (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) +++ kernel/generic/include/gsort.h (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) @@ -0,0 +1,47 @@ +/* + * Copyright (c) 2005 Sergey Bondari + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup generic + * @{ + */ +/** @file + */ + +#ifndef KERN_GSORT_H_ +#define KERN_GSORT_H_ + +#include + +typedef int (* sort_cmp_t)(void *, void *, void *); + +extern bool gsort(void *, size_t, size_t, sort_cmp_t, void *); + +#endif + +/** @} + */ Index: rnel/generic/include/sort.h =================================================================== --- kernel/generic/include/sort.h (revision 719a208dbe29f92f5690472a3500c890db8f3f1f) +++ (revision ) @@ -1,48 +1,0 @@ -/* - * Copyright (c) 2005 Sergey Bondari - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * - Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - The name of the author may not be used to endorse or promote products - * derived from this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR - * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. - * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -/** @addtogroup generic - * @{ - */ -/** @file - */ - -#ifndef KERN_SORT_H_ -#define KERN_SORT_H_ - -#include - -typedef int (* sort_cmp_t)(void *, void *, void *); - -extern bool gsort(void *, size_t, size_t, sort_cmp_t, void *); -extern bool qsort(void *, size_t, size_t, sort_cmp_t, void *); - -#endif - -/** @} - */ Index: kernel/generic/src/lib/gsort.c =================================================================== --- kernel/generic/src/lib/gsort.c (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) +++ kernel/generic/src/lib/gsort.c (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) @@ -0,0 +1,128 @@ +/* + * Copyright (c) 2005 Sergey Bondari + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup libc + * @{ + */ + +/** + * @file + * @brief Sorting functions. + * + * This files contains functions implementing several sorting + * algorithms (e.g. quick sort and gnome sort). + * + */ + +#include +#include +#include + +/** Immediate buffer size. + * + * For small buffer sizes avoid doing malloc() + * and use the stack. + * + */ +#define IBUF_SIZE 32 + +/** Array accessor. + * + */ +#define INDEX(buf, i, elem_size) ((buf) + (i) * (elem_size)) + +/** Gnome sort + * + * Apply generic gnome sort algorithm on supplied data, + * using pre-allocated buffer. + * + * @param data Pointer to data to be sorted. + * @param cnt Number of elements to be sorted. + * @param elem_size Size of one element. + * @param cmp Comparator function. + * @param arg 3rd argument passed to cmp. + * @param slot Pointer to scratch memory buffer + * elem_size bytes long. + * + */ +static void _gsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, + void *arg, void *slot) +{ + size_t i = 0; + + while (i < cnt) { + if ((i != 0) && + (cmp(INDEX(data, i, elem_size), + INDEX(data, i - 1, elem_size), arg) == -1)) { + memcpy(slot, INDEX(data, i, elem_size), elem_size); + memcpy(INDEX(data, i, elem_size), INDEX(data, i - 1, elem_size), + elem_size); + memcpy(INDEX(data, i - 1, elem_size), slot, elem_size); + i--; + } else + i++; + } +} + +/** Gnome sort wrapper + * + * This is only a wrapper that takes care of memory + * allocations for storing the slot element for generic + * gnome sort algorithm. + * + * @param data Pointer to data to be sorted. + * @param cnt Number of elements to be sorted. + * @param elem_size Size of one element. + * @param cmp Comparator function. + * @param arg 3rd argument passed to cmp. + * + * @return True if sorting succeeded. + * + */ +bool gsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, void *arg) +{ + uint8_t ibuf_slot[IBUF_SIZE]; + void *slot; + + if (elem_size > IBUF_SIZE) { + slot = (void *) malloc(elem_size, 0); + if (!slot) + return false; + } else + slot = (void *) ibuf_slot; + + _gsort(data, cnt, elem_size, cmp, arg, slot); + + if (elem_size > IBUF_SIZE) + free(slot); + + return true; +} + +/** @} + */ Index: rnel/generic/src/lib/sort.c =================================================================== --- kernel/generic/src/lib/sort.c (revision 719a208dbe29f92f5690472a3500c890db8f3f1f) +++ (revision ) @@ -1,227 +1,0 @@ -/* - * Copyright (c) 2005 Sergey Bondari - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * - Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - The name of the author may not be used to endorse or promote products - * derived from this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR - * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. - * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -/** @addtogroup generic - * @{ - */ - -/** - * @file - * @brief Sorting functions. - * - * This files contains functions implementing several sorting - * algorithms (e.g. quick sort and gnome sort). - * - */ - -#include -#include -#include - -/** Immediate buffer size. - * - * For small buffer sizes avoid doing malloc() - * and use the stack. - * - */ -#define IBUF_SIZE 32 - -/** Array accessor. - * - */ -#define INDEX(buf, i, elem_size) ((buf) + (i) * (elem_size)) - -/** Gnome sort - * - * Apply generic gnome sort algorithm on supplied data, - * using pre-allocated buffer. - * - * @param data Pointer to data to be sorted. - * @param cnt Number of elements to be sorted. - * @param elem_size Size of one element. - * @param cmp Comparator function. - * @param arg 3rd argument passed to cmp. - * @param slot Pointer to scratch memory buffer - * elem_size bytes long. - * - */ -static void _gsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, - void *arg, void *slot) -{ - size_t i = 0; - - while (i < cnt) { - if ((i > 0) && - (cmp(INDEX(data, i, elem_size), - INDEX(data, i - 1, elem_size), arg) == -1)) { - memcpy(slot, INDEX(data, i, elem_size), elem_size); - memcpy(INDEX(data, i, elem_size), INDEX(data, i - 1, elem_size), - elem_size); - memcpy(INDEX(data, i - 1, elem_size), slot, elem_size); - i--; - } else - i++; - } -} - -/** Quicksort - * - * Apply generic quicksort algorithm on supplied data, - * using pre-allocated buffers. - * - * @param data Pointer to data to be sorted. - * @param cnt Number of elements to be sorted. - * @param elem_size Size of one element. - * @param cmp Comparator function. - * @param arg 3rd argument passed to cmp. - * @param slot Pointer to scratch memory buffer - * elem_size bytes long. - * @param pivot Pointer to scratch memory buffer - * elem_size bytes long. - * - */ -static void _qsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, - void *arg, void *slot, void *pivot) -{ - if (cnt > 4) { - size_t i = 0; - size_t j = cnt - 1; - - memcpy(pivot, data, elem_size); - - while (true) { - while ((cmp(INDEX(data, i, elem_size), pivot, arg) < 0) && (i < cnt)) - i++; - - while ((cmp(INDEX(data, j, elem_size), pivot, arg) >= 0) && (j > 0)) - j--; - - if (i < j) { - memcpy(slot, INDEX(data, i, elem_size), elem_size); - memcpy(INDEX(data, i, elem_size), INDEX(data, j, elem_size), - elem_size); - memcpy(INDEX(data, j, elem_size), slot, elem_size); - } else - break; - } - - _qsort(data, j + 1, elem_size, cmp, arg, slot, pivot); - _qsort(INDEX(data, j + 1, elem_size), cnt - j - 1, elem_size, - cmp, arg, slot, pivot); - } else - _gsort(data, cnt, elem_size, cmp, arg, slot); -} - -/** Gnome sort wrapper - * - * This is only a wrapper that takes care of memory - * allocations for storing the slot element for generic - * gnome sort algorithm. - * - * This function can sleep. - * - * @param data Pointer to data to be sorted. - * @param cnt Number of elements to be sorted. - * @param elem_size Size of one element. - * @param cmp Comparator function. - * @param arg 3rd argument passed to cmp. - * - * @return True if sorting succeeded. - * - */ -bool gsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, void *arg) -{ - uint8_t ibuf_slot[IBUF_SIZE]; - void *slot; - - if (elem_size > IBUF_SIZE) { - slot = (void *) malloc(elem_size, 0); - if (!slot) - return false; - } else - slot = (void *) ibuf_slot; - - _gsort(data, cnt, elem_size, cmp, arg, slot); - - if (elem_size > IBUF_SIZE) - free(slot); - - return true; -} - -/** Quicksort wrapper - * - * This is only a wrapper that takes care of memory - * allocations for storing the pivot and temporary elements - * for generic quicksort algorithm. - * - * This function can sleep. - * - * @param data Pointer to data to be sorted. - * @param cnt Number of elements to be sorted. - * @param elem_size Size of one element. - * @param cmp Comparator function. - * @param arg 3rd argument passed to cmp. - * - * @return True if sorting succeeded. - * - */ -bool qsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, void *arg) -{ - uint8_t ibuf_slot[IBUF_SIZE]; - uint8_t ibuf_pivot[IBUF_SIZE]; - void *slot; - void *pivot; - - if (elem_size > IBUF_SIZE) { - slot = (void *) malloc(elem_size, 0); - if (!slot) - return false; - - pivot = (void *) malloc(elem_size, 0); - if (!pivot) { - free(slot); - return false; - } - } else { - slot = (void *) ibuf_slot; - pivot = (void *) ibuf_pivot; - } - - _qsort(data, cnt, elem_size, cmp, arg, slot, pivot); - - if (elem_size > IBUF_SIZE) { - free(pivot); - free(slot); - } - - return true; -} - -/** @} - */ Index: uspace/app/bdsh/cmds/modules/ls/ls.c =================================================================== --- uspace/app/bdsh/cmds/modules/ls/ls.c (revision 719a208dbe29f92f5690472a3500c890db8f3f1f) +++ uspace/app/bdsh/cmds/modules/ls/ls.c (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) @@ -39,5 +39,4 @@ #include #include -#include #include "ls.h" @@ -62,5 +61,5 @@ static unsigned int ls_start(ls_job_t *); static void ls_print(struct dir_elem_t *); -static int ls_cmp(void *, void *, void *); +static int ls_cmp(const void *, const void *); static signed int ls_scan_dir(const char *, DIR *, struct dir_elem_t **); static unsigned int ls_recursive(const char *, DIR *); @@ -104,12 +103,11 @@ * @param a Pointer to the structure of the first element. * @param b Pointer to the structure of the second element. - * @param arg Pointer for an other and optionnal argument. * * @return -1 if a < b, 1 otherwise. */ -static int ls_cmp(void *a, void *b, void *arg) -{ - struct dir_elem_t *da = a; - struct dir_elem_t *db = b; +static int ls_cmp(const void *a, const void *b) +{ + struct dir_elem_t const *da = a; + struct dir_elem_t const *db = b; if ((da->s.is_directory && db->s.is_file) || @@ -191,10 +189,6 @@ } - if (ls.sort) { - if (!qsort(&tosort[0], nbdirs, sizeof(struct dir_elem_t), - ls_cmp, NULL)) { - printf("Sorting error.\n"); - } - } + if (ls.sort) + qsort(&tosort[0], nbdirs, sizeof(struct dir_elem_t), ls_cmp); for (i = 0; i < nbdirs; i++) Index: uspace/app/top/top.c =================================================================== --- uspace/app/top/top.c (revision 719a208dbe29f92f5690472a3500c890db8f3f1f) +++ uspace/app/top/top.c (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) @@ -42,5 +42,5 @@ #include #include -#include +#include #include "screen.h" #include "top.h" Index: uspace/dist/src/c/demos/top/top.c =================================================================== --- uspace/dist/src/c/demos/top/top.c (revision 719a208dbe29f92f5690472a3500c890db8f3f1f) +++ uspace/dist/src/c/demos/top/top.c (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) @@ -42,5 +42,5 @@ #include #include -#include +#include #include "screen.h" #include "top.h" Index: uspace/lib/c/Makefile =================================================================== --- uspace/lib/c/Makefile (revision 719a208dbe29f92f5690472a3500c890db8f3f1f) +++ uspace/lib/c/Makefile (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) @@ -81,4 +81,5 @@ generic/event.c \ generic/errno.c \ + generic/gsort.c \ generic/loc.c \ generic/mem.c \ @@ -158,8 +159,8 @@ generic/stacktrace.c \ generic/arg_parse.c \ - generic/sort.c \ generic/stats.c \ generic/assert.c \ generic/pio_trace.c \ + generic/qsort.c \ generic/uuid.c \ generic/vbd.c \ @@ -181,4 +182,5 @@ test/main.c \ test/odict.c \ + test/qsort.c \ test/sprintf.c \ test/str.c Index: uspace/lib/c/generic/gsort.c =================================================================== --- uspace/lib/c/generic/gsort.c (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) +++ uspace/lib/c/generic/gsort.c (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) @@ -0,0 +1,128 @@ +/* + * Copyright (c) 2005 Sergey Bondari + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup libc + * @{ + */ + +/** + * @file + * @brief Sorting functions. + * + * This files contains functions implementing several sorting + * algorithms (e.g. quick sort and gnome sort). + * + */ + +#include +#include +#include + +/** Immediate buffer size. + * + * For small buffer sizes avoid doing malloc() + * and use the stack. + * + */ +#define IBUF_SIZE 32 + +/** Array accessor. + * + */ +#define INDEX(buf, i, elem_size) ((buf) + (i) * (elem_size)) + +/** Gnome sort + * + * Apply generic gnome sort algorithm on supplied data, + * using pre-allocated buffer. + * + * @param data Pointer to data to be sorted. + * @param cnt Number of elements to be sorted. + * @param elem_size Size of one element. + * @param cmp Comparator function. + * @param arg 3rd argument passed to cmp. + * @param slot Pointer to scratch memory buffer + * elem_size bytes long. + * + */ +static void _gsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, + void *arg, void *slot) +{ + size_t i = 0; + + while (i < cnt) { + if ((i != 0) && + (cmp(INDEX(data, i, elem_size), + INDEX(data, i - 1, elem_size), arg) == -1)) { + memcpy(slot, INDEX(data, i, elem_size), elem_size); + memcpy(INDEX(data, i, elem_size), INDEX(data, i - 1, elem_size), + elem_size); + memcpy(INDEX(data, i - 1, elem_size), slot, elem_size); + i--; + } else + i++; + } +} + +/** Gnome sort wrapper + * + * This is only a wrapper that takes care of memory + * allocations for storing the slot element for generic + * gnome sort algorithm. + * + * @param data Pointer to data to be sorted. + * @param cnt Number of elements to be sorted. + * @param elem_size Size of one element. + * @param cmp Comparator function. + * @param arg 3rd argument passed to cmp. + * + * @return True if sorting succeeded. + * + */ +bool gsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, void *arg) +{ + uint8_t ibuf_slot[IBUF_SIZE]; + void *slot; + + if (elem_size > IBUF_SIZE) { + slot = (void *) malloc(elem_size); + if (!slot) + return false; + } else + slot = (void *) ibuf_slot; + + _gsort(data, cnt, elem_size, cmp, arg, slot); + + if (elem_size > IBUF_SIZE) + free(slot); + + return true; +} + +/** @} + */ Index: uspace/lib/c/generic/qsort.c =================================================================== --- uspace/lib/c/generic/qsort.c (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) +++ uspace/lib/c/generic/qsort.c (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) @@ -0,0 +1,214 @@ +/* + * Copyright (c) 2017 Jiri Svoboda + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup libc + * @{ + */ + +/** + * @file + * @brief Quicksort. + */ + +#include +#include +#include + +/** Quicksort spec */ +typedef struct { + void *base; + size_t nmemb; + size_t size; + int (*compar)(const void *, const void *, void *); + void *arg; +} qs_spec_t; + +/** Comparison function wrapper. + * + * Performs qsort_r comparison using qsort comparison function + * + * @param a First element + * @param b Second element + * @param arg qsort comparison function + */ +static int compar_wrap(const void *a, const void *b, void *arg) +{ + int (*compar)(const void *, const void *) = + (int (*)(const void *, const void *))arg; + + return compar(a, b); +} + +/** Determine if one element is less-than another element. + * + * @param qs Quicksort spec + * @param i First element index + * @param j Second element index + */ +static bool elem_lt(qs_spec_t *qs, size_t i, size_t j) +{ + const void *a; + const void *b; + int r; + + a = qs->base + i * qs->size; + b = qs->base + j * qs->size; + + r = qs->compar(a, b, qs->arg); + + return r < 0; +} + +/** Swap two elements. + * + * @param qs Quicksort spec + * @param i First element index + * @param j Second element index + */ +static void elem_swap(qs_spec_t *qs, size_t i, size_t j) +{ + char *a; + char *b; + char t; + size_t k; + + a = qs->base + i * qs->size; + b = qs->base + j * qs->size; + + for (k = 0; k < qs->size; k++) { + t = a[k]; + a[k] = b[k]; + b[k] = t; + } +} + +/** Partition a range of indices. + * + * @param qs Quicksort spec + * @param lo Lower bound (inclusive) + * @param hi Upper bound (inclusive) + * @return Pivot index + */ +static size_t partition(qs_spec_t *qs, size_t lo, size_t hi) +{ + size_t pivot; + size_t i, j; + + pivot = lo + (hi - lo) / 2; + i = lo; + j = hi; + while (true) { + while (elem_lt(qs, i, pivot)) + ++i; + while (elem_lt(qs, pivot, j)) + --j; + + if (i >= j) + return j; + + elem_swap(qs, i, j); + + /* Need to follow pivot movement */ + if (i == pivot) + pivot = j; + else if (j == pivot) + pivot = i; + + i++; + j--; + } +} + +/** Sort a range of indices. + * + * @param qs Quicksort spec + * @param lo Lower bound (inclusive) + * @param hi Upper bound (inclusive) + */ +static void quicksort(qs_spec_t *qs, size_t lo, size_t hi) +{ + size_t p; + + if (lo < hi) { + p = partition(qs, lo, hi); + quicksort(qs, lo, p); + quicksort(qs, p + 1, hi); + } +} + +/** Quicksort. + * + * @param base Array to sort + * @param nmemb Number of array members + * @param size Size of member in bytes + * @param compar Comparison function + */ +void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, + const void *)) +{ + qs_spec_t qs; + + if (nmemb == 0) + return; + + qs.base = base; + qs.nmemb = nmemb; + qs.size = size; + qs.compar = compar_wrap; + qs.arg = compar; + + quicksort(&qs, 0, nmemb - 1); +} + +/** Quicksort with extra argument to comparison function. + * + * @param base Array to sort + * @param nmemb Number of array members + * @param size Size of member in bytes + * @param compar Comparison function + * @param arg Argument to comparison function + */ +void qsort_r(void *base, size_t nmemb, size_t size, int (*compar)(const void *, + const void *, void *), void *arg) +{ + qs_spec_t qs; + + if (nmemb == 0) + return; + + qs.base = base; + qs.nmemb = nmemb; + qs.size = size; + qs.compar = compar; + qs.arg = arg; + + quicksort(&qs, 0, nmemb - 1); +} + +/** @} + */ Index: pace/lib/c/generic/sort.c =================================================================== --- uspace/lib/c/generic/sort.c (revision 719a208dbe29f92f5690472a3500c890db8f3f1f) +++ (revision ) @@ -1,223 +1,0 @@ -/* - * Copyright (c) 2005 Sergey Bondari - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * - Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - The name of the author may not be used to endorse or promote products - * derived from this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR - * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. - * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -/** @addtogroup libc - * @{ - */ - -/** - * @file - * @brief Sorting functions. - * - * This files contains functions implementing several sorting - * algorithms (e.g. quick sort and gnome sort). - * - */ - -#include -#include -#include - -/** Immediate buffer size. - * - * For small buffer sizes avoid doing malloc() - * and use the stack. - * - */ -#define IBUF_SIZE 32 - -/** Array accessor. - * - */ -#define INDEX(buf, i, elem_size) ((buf) + (i) * (elem_size)) - -/** Gnome sort - * - * Apply generic gnome sort algorithm on supplied data, - * using pre-allocated buffer. - * - * @param data Pointer to data to be sorted. - * @param cnt Number of elements to be sorted. - * @param elem_size Size of one element. - * @param cmp Comparator function. - * @param arg 3rd argument passed to cmp. - * @param slot Pointer to scratch memory buffer - * elem_size bytes long. - * - */ -static void _gsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, - void *arg, void *slot) -{ - size_t i = 0; - - while (i < cnt) { - if ((i != 0) && - (cmp(INDEX(data, i, elem_size), - INDEX(data, i - 1, elem_size), arg) == -1)) { - memcpy(slot, INDEX(data, i, elem_size), elem_size); - memcpy(INDEX(data, i, elem_size), INDEX(data, i - 1, elem_size), - elem_size); - memcpy(INDEX(data, i - 1, elem_size), slot, elem_size); - i--; - } else - i++; - } -} - -/** Quicksort - * - * Apply generic quicksort algorithm on supplied data, - * using pre-allocated buffers. - * - * @param data Pointer to data to be sorted. - * @param cnt Number of elements to be sorted. - * @param elem_size Size of one element. - * @param cmp Comparator function. - * @param arg 3rd argument passed to cmp. - * @param slot Pointer to scratch memory buffer - * elem_size bytes long. - * @param pivot Pointer to scratch memory buffer - * elem_size bytes long. - * - */ -static void _qsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, - void *arg, void *slot, void *pivot) -{ - if (cnt > 4) { - size_t i = 0; - size_t j = cnt - 1; - - memcpy(pivot, data, elem_size); - - while (true) { - while ((cmp(INDEX(data, i, elem_size), pivot, arg) < 0) && (i < cnt)) - i++; - - while ((cmp(INDEX(data, j, elem_size), pivot, arg) >= 0) && (j > 0)) - j--; - - if (i < j) { - memcpy(slot, INDEX(data, i, elem_size), elem_size); - memcpy(INDEX(data, i, elem_size), INDEX(data, j, elem_size), - elem_size); - memcpy(INDEX(data, j, elem_size), slot, elem_size); - } else - break; - } - - _qsort(data, j + 1, elem_size, cmp, arg, slot, pivot); - _qsort(INDEX(data, j + 1, elem_size), cnt - j - 1, elem_size, - cmp, arg, slot, pivot); - } else - _gsort(data, cnt, elem_size, cmp, arg, slot); -} - -/** Gnome sort wrapper - * - * This is only a wrapper that takes care of memory - * allocations for storing the slot element for generic - * gnome sort algorithm. - * - * @param data Pointer to data to be sorted. - * @param cnt Number of elements to be sorted. - * @param elem_size Size of one element. - * @param cmp Comparator function. - * @param arg 3rd argument passed to cmp. - * - * @return True if sorting succeeded. - * - */ -bool gsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, void *arg) -{ - uint8_t ibuf_slot[IBUF_SIZE]; - void *slot; - - if (elem_size > IBUF_SIZE) { - slot = (void *) malloc(elem_size); - if (!slot) - return false; - } else - slot = (void *) ibuf_slot; - - _gsort(data, cnt, elem_size, cmp, arg, slot); - - if (elem_size > IBUF_SIZE) - free(slot); - - return true; -} - -/** Quicksort wrapper - * - * This is only a wrapper that takes care of memory - * allocations for storing the pivot and temporary elements - * for generic quicksort algorithm. - * - * @param data Pointer to data to be sorted. - * @param cnt Number of elements to be sorted. - * @param elem_size Size of one element. - * @param cmp Comparator function. - * @param arg 3rd argument passed to cmp. - * - * @return True if sorting succeeded. - * - */ -bool qsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, void *arg) -{ - uint8_t ibuf_slot[IBUF_SIZE]; - uint8_t ibuf_pivot[IBUF_SIZE]; - void *slot; - void *pivot; - - if (elem_size > IBUF_SIZE) { - slot = (void *) malloc(elem_size); - if (!slot) - return false; - - pivot = (void *) malloc(elem_size); - if (!pivot) { - free(slot); - return false; - } - } else { - slot = (void *) ibuf_slot; - pivot = (void *) ibuf_pivot; - } - - _qsort(data, cnt, elem_size, cmp, arg, slot, pivot); - - if (elem_size > IBUF_SIZE) { - free(pivot); - free(slot); - } - - return true; -} - -/** @} - */ Index: uspace/lib/c/include/gsort.h =================================================================== --- uspace/lib/c/include/gsort.h (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) +++ uspace/lib/c/include/gsort.h (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) @@ -0,0 +1,48 @@ +/* + * Copyright (c) 2005 Sergey Bondari + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup libc + * @{ + */ +/** @file + */ + +#ifndef LIBC_SORT_H_ +#define LIBC_SORT_H_ + +#include +#include + +typedef int (* sort_cmp_t)(void *, void *, void *); + +extern bool gsort(void *, size_t, size_t, sort_cmp_t, void *); + +#endif + +/** @} + */ Index: uspace/lib/c/include/qsort.h =================================================================== --- uspace/lib/c/include/qsort.h (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) +++ uspace/lib/c/include/qsort.h (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) @@ -0,0 +1,48 @@ +/* + * Copyright (c) 2017 Jiri Svoboda + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup libc + * @{ + */ +/** @file + */ + +#ifndef LIBC_QSORT_H_ +#define LIBC_QSORT_H_ + +#include + +extern void qsort(void *, size_t, size_t, int (*)(const void *, + const void *)); +extern void qsort_r(void *, size_t, size_t, int (*)(const void *, + const void *, void *), void *); + +#endif + +/** @} + */ Index: pace/lib/c/include/sort.h =================================================================== --- uspace/lib/c/include/sort.h (revision 719a208dbe29f92f5690472a3500c890db8f3f1f) +++ (revision ) @@ -1,49 +1,0 @@ -/* - * Copyright (c) 2005 Sergey Bondari - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * - Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - The name of the author may not be used to endorse or promote products - * derived from this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR - * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. - * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -/** @addtogroup libc - * @{ - */ -/** @file - */ - -#ifndef LIBC_SORT_H_ -#define LIBC_SORT_H_ - -#include -#include - -typedef int (* sort_cmp_t)(void *, void *, void *); - -extern bool gsort(void *, size_t, size_t, sort_cmp_t, void *); -extern bool qsort(void *, size_t, size_t, sort_cmp_t, void *); - -#endif - -/** @} - */ Index: uspace/lib/c/include/stdlib.h =================================================================== --- uspace/lib/c/include/stdlib.h (revision 719a208dbe29f92f5690472a3500c890db8f3f1f) +++ uspace/lib/c/include/stdlib.h (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) @@ -37,4 +37,5 @@ #include +#include #include Index: uspace/lib/c/test/main.c =================================================================== --- uspace/lib/c/test/main.c (revision 719a208dbe29f92f5690472a3500c890db8f3f1f) +++ uspace/lib/c/test/main.c (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) @@ -33,4 +33,5 @@ PCUT_IMPORT(odict); +PCUT_IMPORT(qsort); PCUT_IMPORT(sprintf); PCUT_IMPORT(str); Index: uspace/lib/c/test/qsort.c =================================================================== --- uspace/lib/c/test/qsort.c (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) +++ uspace/lib/c/test/qsort.c (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) @@ -0,0 +1,174 @@ +/* + * Copyright (c) 2017 Jiri Svoboda + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include +#include +#include +#include + +enum { + /** Length of test number sequences */ + test_seq_len = 5 +}; + +/** Test compare function. + * + * @param a First key + * @param b Second key + * @return <0, 0, >0 if @a a is less than, equal or greater than @a b + */ +static int test_cmp(const void *a, const void *b) +{ + int *ia = (int *)a; + int *ib = (int *)b; + + return *ia - *ib; +} + +static void bubble_sort(int *seq, size_t nmemb) +{ + size_t i; + size_t j; + int t; + + for (i = 0; i < nmemb - 1; i++) + for (j = 0; j < nmemb - 1; j++) { + if (seq[j] > seq[j + 1]) { + t = seq[j]; + seq[j] = seq[j + 1]; + seq[j + 1] = t; + } + } +} + +PCUT_INIT + +PCUT_TEST_SUITE(qsort); + +/** Test sorting already sorted increasing sequence */ +PCUT_TEST(incr_seq) +{ + int *seq; + int i; + + seq = calloc(test_seq_len, sizeof(int)); + PCUT_ASSERT_NOT_NULL(seq); + + for (i = 0; i < test_seq_len; i++) + seq[i] = i; + + qsort(seq, test_seq_len, sizeof(int), test_cmp); + + for (i = 0; i < test_seq_len; i++) { + PCUT_ASSERT_INT_EQUALS(i, seq[i]); + } + + free(seq); +} + +/** Test sorting reverse-sorted decreasing sequence. */ +PCUT_TEST(decr_seq) +{ + int *seq; + int i; + + seq = calloc(test_seq_len, sizeof(int)); + PCUT_ASSERT_NOT_NULL(seq); + + for (i = 0; i < test_seq_len; i++) + seq[i] = test_seq_len - 1 - i; + + qsort(seq, test_seq_len, sizeof(int), test_cmp); + + for (i = 0; i < test_seq_len; i++) { + PCUT_ASSERT_INT_EQUALS(i, seq[i]); + } + + free(seq); +} + +/** Test sorting reverse-sorted decreasing sequence where each member repeats twice. */ +PCUT_TEST(decr2_seq) +{ + int *seq; + int i; + + seq = calloc(test_seq_len, sizeof(int)); + PCUT_ASSERT_NOT_NULL(seq); + + for (i = 0; i < test_seq_len; i++) { + seq[i] = (test_seq_len - 1 - i) / 2; + } + + qsort(seq, test_seq_len, sizeof(int), test_cmp); + + for (i = 0; i < test_seq_len; i++) { + PCUT_ASSERT_INT_EQUALS(i / 2, seq[i]); + } + + free(seq); +} + +/** Generate pseudorandom sequence. */ +static int seq_next(int cur) +{ + return (cur * 1951) % 1000000; +} + +/** Test sorting pseudorandom sequence. */ +PCUT_TEST(pseudorandom_seq) +{ + int *seq, *seq2; + int i; + int v; + + seq = calloc(test_seq_len, sizeof(int)); + PCUT_ASSERT_NOT_NULL(seq); + + seq2 = calloc(test_seq_len, sizeof(int)); + PCUT_ASSERT_NOT_NULL(seq); + + v = 1; + for (i = 0; i < test_seq_len; i++) { + seq[i] = v; + seq2[i] = v; + v = seq_next(v); + } + + qsort(seq, test_seq_len, sizeof(int), test_cmp); + bubble_sort(seq2, test_seq_len); + + for (i = 0; i < test_seq_len; i++) { + PCUT_ASSERT_INT_EQUALS(seq2[i], seq[i]); + } + + free(seq); + free(seq2); +} + +PCUT_EXPORT(qsort); Index: uspace/lib/clui/tinput.c =================================================================== --- uspace/lib/clui/tinput.c (revision 719a208dbe29f92f5690472a3500c890db8f3f1f) +++ uspace/lib/clui/tinput.c (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) @@ -27,5 +27,4 @@ */ -#include #include #include @@ -583,5 +582,5 @@ /** Compare two entries in array of completions. */ -static int compl_cmp(void *va, void *vb, void *arg) +static int compl_cmp(const void *va, const void *vb) { const char *a = *(const char **) va; @@ -741,5 +740,5 @@ /* No common prefix. Sort and display all entries. */ - qsort(compl, cnum, sizeof(char *), compl_cmp, NULL); + qsort(compl, cnum, sizeof(char *), compl_cmp); tinput_jump_after(ti); Index: uspace/lib/ext4/src/directory_index.c =================================================================== --- uspace/lib/ext4/src/directory_index.c (revision 719a208dbe29f92f5690472a3500c890db8f3f1f) +++ uspace/lib/ext4/src/directory_index.c (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) @@ -38,5 +38,4 @@ #include #include -#include #include #include @@ -668,5 +667,4 @@ * @param arg1 First entry * @param arg2 Second entry - * @param dummy Unused parameter, can be NULL * * @return Classic compare result @@ -674,8 +672,9 @@ * */ -static int ext4_directory_dx_entry_comparator(void *arg1, void *arg2, void *dummy) -{ - ext4_dx_sort_entry_t *entry1 = arg1; - ext4_dx_sort_entry_t *entry2 = arg2; +static int ext4_directory_dx_entry_comparator(const void *arg1, + const void *arg2) +{ + ext4_dx_sort_entry_t const *entry1 = arg1; + ext4_dx_sort_entry_t const *entry2 = arg2; if (entry1->hash == entry2->hash) @@ -793,5 +792,5 @@ /* Sort all entries */ qsort(sort_array, idx, sizeof(ext4_dx_sort_entry_t), - ext4_directory_dx_entry_comparator, NULL); + ext4_directory_dx_entry_comparator); /* Allocate new block for store the second part of entries */ Index: uspace/lib/posix/source/stdlib.c =================================================================== --- uspace/lib/posix/source/stdlib.c (revision 719a208dbe29f92f5690472a3500c890db8f3f1f) +++ uspace/lib/posix/source/stdlib.c (revision f2460a50f76f92f3a70ead8969f2bffd83b3a7a4) @@ -47,5 +47,5 @@ #include "posix/unistd.h" -#include "libc/sort.h" +#include "libc/qsort.h" #include "libc/str.h" #include "libc/vfs/vfs.h" @@ -136,27 +136,4 @@ /** - * Private helper function that serves as a compare function for qsort(). - * - * @param elem1 First element to compare. - * @param elem2 Second element to compare. - * @param compare Comparison function without userdata parameter. - * @return Relative ordering of the elements. - */ -static int sort_compare_wrapper(void *elem1, void *elem2, void *userdata) -{ - int (*compare)(const void *, const void *) = userdata; - int ret = compare(elem1, elem2); - - /* Native qsort internals expect this. */ - if (ret < 0) { - return -1; - } else if (ret > 0) { - return 1; - } else { - return 0; - } -} - -/** * Array sorting utilizing the quicksort algorithm. * @@ -169,6 +146,5 @@ int (*compare)(const void *, const void *)) { - /* Implemented in libc with one extra argument. */ - qsort(array, count, size, sort_compare_wrapper, compare); + qsort(array, count, size, compare); }