Changeset f2460a50 in mainline for uspace/lib/c


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.

Location:
uspace/lib/c
Files:
3 added
3 edited
2 moved

Legend:

Unmodified
Added
Removed

  • 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);
Note: See TracChangeset for help on using the changeset viewer.