Changeset f2460a50 in mainline


Ignore:
Timestamp:
2017-05-30T06:16:25Z (8 years ago)
Author:
Jiri Svoboda <jiri@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
c726209
Parents:
719a208
Message:

qsort() compliant with C standard.

Files:
3 added
11 edited
4 moved

Legend:

Unmodified
Added
Removed

  • kernel/Makefile

    r719a208 rf2460a50  
    242242        generic/src/lib/memstr.c \
    243243        generic/src/lib/memfnc.c \
    244         generic/src/lib/sort.c \
     244        generic/src/lib/gsort.c \
    245245        generic/src/lib/str.c \
    246246        generic/src/lib/elf.c \

  • kernel/genarch/src/acpi/madt.c

    r719a208 rf2460a50  
    4646#include <mm/slab.h>
    4747#include <memstr.h>
    48 #include <sort.h>
     48#include <gsort.h>
    4949
    5050struct acpi_madt *acpi_madt = NULL;

  • kernel/generic/include/gsort.h

    r719a208 rf2460a50  
    3333 */
    3434
    35 #ifndef KERN_SORT_H_
    36 #define KERN_SORT_H_
     35#ifndef KERN_GSORT_H_
     36#define KERN_GSORT_H_
    3737
    3838#include <typedefs.h>
    … …  
    4141
    4242extern bool gsort(void *, size_t, size_t, sort_cmp_t, void *);
    43 extern bool qsort(void *, size_t, size_t, sort_cmp_t, void *);
    4443
    4544#endif

  • kernel/generic/src/lib/gsort.c

    r719a208 rf2460a50  
    2727 */
    2828
    29 /** @addtogroup generic
     29/** @addtogroup libc
    3030 * @{
    3131 */
    … …  
    4040 */
    4141
     42#include <gsort.h>
     43#include <memstr.h>
    4244#include <mm/slab.h>
    43 #include <memstr.h>
    44 #include <sort.h>
    4545
    4646/** Immediate buffer size.
    … …  
    7777       
    7878        while (i < cnt) {
    79                 if ((i > 0) &&
     79                if ((i != 0) &&
    8080                    (cmp(INDEX(data, i, elem_size),
    8181                    INDEX(data, i - 1, elem_size), arg) == -1)) {
    … …  
    9090}
    9191
    92 /** Quicksort
    93  *
    94  * Apply generic quicksort algorithm on supplied data,
    95  * using pre-allocated buffers.
    96  *
    97  * @param data      Pointer to data to be sorted.
    98  * @param cnt       Number of elements to be sorted.
    99  * @param elem_size Size of one element.
    100  * @param cmp       Comparator function.
    101  * @param arg       3rd argument passed to cmp.
    102  * @param slot      Pointer to scratch memory buffer
    103  *                  elem_size bytes long.
    104  * @param pivot     Pointer to scratch memory buffer
    105  *                  elem_size bytes long.
    106  *
    107  */
    108 static void _qsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp,
    109     void *arg, void *slot, void *pivot)
    110 {
    111         if (cnt > 4) {
    112                 size_t i = 0;
    113                 size_t j = cnt - 1;
    114                
    115                 memcpy(pivot, data, elem_size);
    116                
    117                 while (true) {
    118                         while ((cmp(INDEX(data, i, elem_size), pivot, arg) < 0) && (i < cnt))
    119                                 i++;
    120                        
    121                         while ((cmp(INDEX(data, j, elem_size), pivot, arg) >= 0) && (j > 0))
    122                                 j--;
    123                        
    124                         if (i < j) {
    125                                 memcpy(slot, INDEX(data, i, elem_size), elem_size);
    126                                 memcpy(INDEX(data, i, elem_size), INDEX(data, j, elem_size),
    127                                     elem_size);
    128                                 memcpy(INDEX(data, j, elem_size), slot, elem_size);
    129                         } else
    130                                 break;
    131                 }
    132                
    133                 _qsort(data, j + 1, elem_size, cmp, arg, slot, pivot);
    134                 _qsort(INDEX(data, j + 1, elem_size), cnt - j - 1, elem_size,
    135                     cmp, arg, slot, pivot);
    136         } else
    137                 _gsort(data, cnt, elem_size, cmp, arg, slot);
    138 }
    139 
    14092/** Gnome sort wrapper
    14193 *
    … …  
    14395 * allocations for storing the slot element for generic
    14496 * gnome sort algorithm.
    145  *
    146  * This function can sleep.
    14797 *
    14898 * @param data      Pointer to data to be sorted.
    … …  
    175125}
    176126
    177 /** Quicksort wrapper
    178  *
    179  * This is only a wrapper that takes care of memory
    180  * allocations for storing the pivot and temporary elements
    181  * for generic quicksort algorithm.
    182  *
    183  * This function can sleep.
    184  *
    185  * @param data      Pointer to data to be sorted.
    186  * @param cnt       Number of elements to be sorted.
    187  * @param elem_size Size of one element.
    188  * @param cmp       Comparator function.
    189  * @param arg       3rd argument passed to cmp.
    190  *
    191  * @return True if sorting succeeded.
    192  *
    193  */
    194 bool qsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, void *arg)
    195 {
    196         uint8_t ibuf_slot[IBUF_SIZE];
    197         uint8_t ibuf_pivot[IBUF_SIZE];
    198         void *slot;
    199         void *pivot;
    200        
    201         if (elem_size > IBUF_SIZE) {
    202                 slot = (void *) malloc(elem_size, 0);
    203                 if (!slot)
    204                         return false;
    205                
    206                 pivot = (void *) malloc(elem_size, 0);
    207                 if (!pivot) {
    208                         free(slot);
    209                         return false;
    210                 }
    211         } else {
    212                 slot = (void *) ibuf_slot;
    213                 pivot = (void *) ibuf_pivot;
    214         }
    215        
    216         _qsort(data, cnt, elem_size, cmp, arg, slot, pivot);
    217        
    218         if (elem_size > IBUF_SIZE) {
    219                 free(pivot);
    220                 free(slot);
    221         }
    222        
    223         return true;
    224 }
    225 
    226127/** @}
    227128 */

  • uspace/app/bdsh/cmds/modules/ls/ls.c

    r719a208 rf2460a50  
    3939#include <vfs/vfs.h>
    4040#include <str.h>
    41 #include <sort.h>
    4241
    4342#include "ls.h"
    … …  
    6261static unsigned int ls_start(ls_job_t *);
    6362static void ls_print(struct dir_elem_t *);
    64 static int ls_cmp(void *, void *, void *);
     63static int ls_cmp(const void *, const void *);
    6564static signed int ls_scan_dir(const char *, DIR *, struct dir_elem_t **);
    6665static unsigned int ls_recursive(const char *, DIR *);
    … …  
    104103 * @param a             Pointer to the structure of the first element.
    105104 * @param b             Pointer to the structure of the second element.
    106  * @param arg           Pointer for an other and optionnal argument.
    107105 *
    108106 * @return              -1 if a < b, 1 otherwise.
    109107 */
    110 static int ls_cmp(void *a, void *b, void *arg)
    111 {
    112         struct dir_elem_t *da = a;
    113         struct dir_elem_t *db = b;
     108static int ls_cmp(const void *a, const void *b)
     109{
     110        struct dir_elem_t const *da = a;
     111        struct dir_elem_t const *db = b;
    114112       
    115113        if ((da->s.is_directory && db->s.is_file) ||
    … …  
    191189        }
    192190       
    193         if (ls.sort) {
    194                 if (!qsort(&tosort[0], nbdirs, sizeof(struct dir_elem_t),
    195                     ls_cmp, NULL)) {
    196                         printf("Sorting error.\n");
    197                 }
    198         }
     191        if (ls.sort)
     192                qsort(&tosort[0], nbdirs, sizeof(struct dir_elem_t), ls_cmp);
    199193       
    200194        for (i = 0; i < nbdirs; i++)

  • uspace/app/top/top.c

    r719a208 rf2460a50  
    4242#include <sys/time.h>
    4343#include <errno.h>
    44 #include <sort.h>
     44#include <gsort.h>
    4545#include "screen.h"
    4646#include "top.h"

  • uspace/dist/src/c/demos/top/top.c

    r719a208 rf2460a50  
    4242#include <sys/time.h>
    4343#include <errno.h>
    44 #include <sort.h>
     44#include <gsort.h>
    4545#include "screen.h"
    4646#include "top.h"

  • uspace/lib/c/Makefile

    r719a208 rf2460a50  
    8181        generic/event.c \
    8282        generic/errno.c \
     83        generic/gsort.c \
    8384        generic/loc.c \
    8485        generic/mem.c \
    … …  
    158159        generic/stacktrace.c \
    159160        generic/arg_parse.c \
    160         generic/sort.c \
    161161        generic/stats.c \
    162162        generic/assert.c \
    163163        generic/pio_trace.c \
     164        generic/qsort.c \
    164165        generic/uuid.c \
    165166        generic/vbd.c \
    … …  
    181182        test/main.c \
    182183        test/odict.c \
     184        test/qsort.c \
    183185        test/sprintf.c \
    184186        test/str.c

  • uspace/lib/c/generic/gsort.c

    r719a208 rf2460a50  
    4040 */
    4141
    42 #include <sort.h>
     42#include <gsort.h>
    4343#include <mem.h>
    4444#include <malloc.h>
    … …  
    9090}
    9191
    92 /** Quicksort
    93  *
    94  * Apply generic quicksort algorithm on supplied data,
    95  * using pre-allocated buffers.
    96  *
    97  * @param data      Pointer to data to be sorted.
    98  * @param cnt       Number of elements to be sorted.
    99  * @param elem_size Size of one element.
    100  * @param cmp       Comparator function.
    101  * @param arg       3rd argument passed to cmp.
    102  * @param slot      Pointer to scratch memory buffer
    103  *                  elem_size bytes long.
    104  * @param pivot     Pointer to scratch memory buffer
    105  *                  elem_size bytes long.
    106  *
    107  */
    108 static void _qsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp,
    109     void *arg, void *slot, void *pivot)
    110 {
    111         if (cnt > 4) {
    112                 size_t i = 0;
    113                 size_t j = cnt - 1;
    114                
    115                 memcpy(pivot, data, elem_size);
    116                
    117                 while (true) {
    118                         while ((cmp(INDEX(data, i, elem_size), pivot, arg) < 0) && (i < cnt))
    119                                 i++;
    120                        
    121                         while ((cmp(INDEX(data, j, elem_size), pivot, arg) >= 0) && (j > 0))
    122                                 j--;
    123                        
    124                         if (i < j) {
    125                                 memcpy(slot, INDEX(data, i, elem_size), elem_size);
    126                                 memcpy(INDEX(data, i, elem_size), INDEX(data, j, elem_size),
    127                                     elem_size);
    128                                 memcpy(INDEX(data, j, elem_size), slot, elem_size);
    129                         } else
    130                                 break;
    131                 }
    132                
    133                 _qsort(data, j + 1, elem_size, cmp, arg, slot, pivot);
    134                 _qsort(INDEX(data, j + 1, elem_size), cnt - j - 1, elem_size,
    135                     cmp, arg, slot, pivot);
    136         } else
    137                 _gsort(data, cnt, elem_size, cmp, arg, slot);
    138 }
    139 
    14092/** Gnome sort wrapper
    14193 *
    … …  
    173125}
    174126
    175 /** Quicksort wrapper
    176  *
    177  * This is only a wrapper that takes care of memory
    178  * allocations for storing the pivot and temporary elements
    179  * for generic quicksort algorithm.
    180  *
    181  * @param data      Pointer to data to be sorted.
    182  * @param cnt       Number of elements to be sorted.
    183  * @param elem_size Size of one element.
    184  * @param cmp       Comparator function.
    185  * @param arg       3rd argument passed to cmp.
    186  *
    187  * @return True if sorting succeeded.
    188  *
    189  */
    190 bool qsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, void *arg)
    191 {
    192         uint8_t ibuf_slot[IBUF_SIZE];
    193         uint8_t ibuf_pivot[IBUF_SIZE];
    194         void *slot;
    195         void *pivot;
    196        
    197         if (elem_size > IBUF_SIZE) {
    198                 slot = (void *) malloc(elem_size);
    199                 if (!slot)
    200                         return false;
    201                
    202                 pivot = (void *) malloc(elem_size);
    203                 if (!pivot) {
    204                         free(slot);
    205                         return false;
    206                 }
    207         } else {
    208                 slot = (void *) ibuf_slot;
    209                 pivot = (void *) ibuf_pivot;
    210         }
    211        
    212         _qsort(data, cnt, elem_size, cmp, arg, slot, pivot);
    213        
    214         if (elem_size > IBUF_SIZE) {
    215                 free(pivot);
    216                 free(slot);
    217         }
    218        
    219         return true;
    220 }
    221 
    222127/** @}
    223128 */

  • uspace/lib/c/include/gsort.h

    r719a208 rf2460a50  
    4242
    4343extern bool gsort(void *, size_t, size_t, sort_cmp_t, void *);
    44 extern bool qsort(void *, size_t, size_t, sort_cmp_t, void *);
    4544
    4645#endif

  • uspace/lib/c/include/stdlib.h

    r719a208 rf2460a50  
    3737
    3838#include <malloc.h>
     39#include <qsort.h>
    3940#include <stacktrace.h>
    4041

  • uspace/lib/c/test/main.c

    r719a208 rf2460a50  
    3333
    3434PCUT_IMPORT(odict);
     35PCUT_IMPORT(qsort);
    3536PCUT_IMPORT(sprintf);
    3637PCUT_IMPORT(str);

  • uspace/lib/clui/tinput.c

    r719a208 rf2460a50  
    2727 */
    2828
    29 #include <sort.h>
    3029#include <stdio.h>
    3130#include <stdlib.h>
    … …  
    583582
    584583/** Compare two entries in array of completions. */
    585 static int compl_cmp(void *va, void *vb, void *arg)
     584static int compl_cmp(const void *va, const void *vb)
    586585{
    587586        const char *a = *(const char **) va;
    … …  
    741740                        /* No common prefix. Sort and display all entries. */
    742741
    743                         qsort(compl, cnum, sizeof(char *), compl_cmp, NULL);
     742                        qsort(compl, cnum, sizeof(char *), compl_cmp);
    744743
    745744                        tinput_jump_after(ti);

  • uspace/lib/ext4/src/directory_index.c

    r719a208 rf2460a50  
    3838#include <errno.h>
    3939#include <mem.h>
    40 #include <sort.h>
    4140#include <stdlib.h>
    4241#include <str.h>
    … …  
    668667 * @param arg1  First entry
    669668 * @param arg2  Second entry
    670  * @param dummy Unused parameter, can be NULL
    671669 *
    672670 * @return Classic compare result
    … …  
    674672 *
    675673 */
    676 static int ext4_directory_dx_entry_comparator(void *arg1, void *arg2, void *dummy)
    677 {
    678         ext4_dx_sort_entry_t *entry1 = arg1;
    679         ext4_dx_sort_entry_t *entry2 = arg2;
     674static int ext4_directory_dx_entry_comparator(const void *arg1,
     675    const void *arg2)
     676{
     677        ext4_dx_sort_entry_t const *entry1 = arg1;
     678        ext4_dx_sort_entry_t const *entry2 = arg2;
    680679       
    681680        if (entry1->hash == entry2->hash)
    … …  
    793792        /* Sort all entries */
    794793        qsort(sort_array, idx, sizeof(ext4_dx_sort_entry_t),
    795             ext4_directory_dx_entry_comparator, NULL);
     794            ext4_directory_dx_entry_comparator);
    796795       
    797796        /* Allocate new block for store the second part of entries */

  • uspace/lib/posix/source/stdlib.c

    r719a208 rf2460a50  
    4747#include "posix/unistd.h"
    4848
    49 #include "libc/sort.h"
     49#include "libc/qsort.h"
    5050#include "libc/str.h"
    5151#include "libc/vfs/vfs.h"
    … …  
    136136
    137137/**
    138  * Private helper function that serves as a compare function for qsort().
    139  *
    140  * @param elem1 First element to compare.
    141  * @param elem2 Second element to compare.
    142  * @param compare Comparison function without userdata parameter.
    143  * @return Relative ordering of the elements.
    144  */
    145 static int sort_compare_wrapper(void *elem1, void *elem2, void *userdata)
    146 {
    147         int (*compare)(const void *, const void *) = userdata;
    148         int ret = compare(elem1, elem2);
    149        
    150         /* Native qsort internals expect this. */
    151         if (ret < 0) {
    152                 return -1;
    153         } else if (ret > 0) {
    154                 return 1;
    155         } else {
    156                 return 0;
    157         }
    158 }
    159 
    160 /**
    161138 * Array sorting utilizing the quicksort algorithm.
    162139 *
    … …  
    169146    int (*compare)(const void *, const void *))
    170147{
    171         /* Implemented in libc with one extra argument. */
    172         qsort(array, count, size, sort_compare_wrapper, compare);
     148        qsort(array, count, size, compare);
    173149}
    174150
Note: See TracChangeset for help on using the changeset viewer.