Changeset f2460a50 in mainline for kernel/generic/src/lib/gsort.c


Ignore:
Timestamp:
2017-05-30T06:16:25Z (7 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.

File:
1 moved

Legend:

Unmodified
Added
Removed

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