Changeset c6c49de in mainline for uspace/lib/c/generic/sort.c


Ignore:
Timestamp:
2010-06-30T20:17:27Z (14 years ago)
Author:
Martin Decky <martin@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
0c3e63f
Parents:
4edd57fd
Message:

replace bubble sort with gnome sort
improve quicksort readability
use stack space for small temporary buffers

File:
1 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/c/generic/sort.c

    r4edd57fd rc6c49de  
    3636 *
    3737 * This files contains functions implementing several sorting
    38  * algorithms (e.g. quick sort and bubble sort).
     38 * algorithms (e.g. quick sort and gnome sort).
    3939 *
    4040 */
    … …  
    4444#include <malloc.h>
    4545
    46 /** Bubble sort
    47  *
    48  * Apply generic bubble sort algorithm on supplied data,
     46/** Immediate buffer size.
     47 *
     48 * For small buffer sizes avoid doing malloc()
     49 * and use the stack.
     50 *
     51 */
     52#define IBUF_SIZE  32
     53
     54/** Array accessor.
     55 *
     56 */
     57#define INDEX(buf, i, elem_size)  ((buf) + (i) * (elem_size))
     58
     59/** Gnome sort
     60 *
     61 * Apply generic gnome sort algorithm on supplied data,
    4962 * using pre-allocated buffer.
    5063 *
    … …  
    5871 *
    5972 */
    60 static void _bsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp,
     73static void _gsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp,
    6174    void *arg, void *slot)
    6275{
    63         bool done = false;
    64         void *tmp;
    65        
    66         while (!done) {
    67                 done = true;
    68                
    69                 for (tmp = data; tmp < data + elem_size * (cnt - 1);
    70                     tmp = tmp + elem_size) {
    71                         if (cmp(tmp, tmp + elem_size, arg) == 1) {
    72                                 memcpy(slot, tmp, elem_size);
    73                                 memcpy(tmp, tmp + elem_size, elem_size);
    74                                 memcpy(tmp + elem_size, slot, elem_size);
    75                                 done = false;
    76                         }
    77                 }
     76        size_t i = 0;
     77       
     78        while (i < cnt) {
     79                if ((i != 0) &&
     80                    (cmp(INDEX(data, i, elem_size),
     81                    INDEX(data, i - 1, elem_size), arg) == -1)) {
     82                        memcpy(slot, INDEX(data, i, elem_size), elem_size);
     83                        memcpy(INDEX(data, i, elem_size), INDEX(data, i - 1, elem_size),
     84                            elem_size);
     85                        memcpy(INDEX(data, i - 1, elem_size), slot, elem_size);
     86                        i--;
     87                } else
     88                        i++;
    7889        }
    7990}
    … …  
    89100 * @param cmp       Comparator function.
    90101 * @param arg       3rd argument passed to cmp.
    91  * @param tmp       Pointer to scratch memory buffer
     102 * @param slot      Pointer to scratch memory buffer
    92103 *                  elem_size bytes long.
    93104 * @param pivot     Pointer to scratch memory buffer
    … …  
    96107 */
    97108static void _qsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp,
    98     void *arg, void *tmp, void *pivot)
     109    void *arg, void *slot, void *pivot)
    99110{
    100111        if (cnt > 4) {
    … …  
    105116               
    106117                while (true) {
    107                         while ((cmp(data + i * elem_size, pivot, arg) < 0) && (i < cnt))
     118                        while ((cmp(INDEX(data, i, elem_size), pivot, arg) < 0) && (i < cnt))
    108119                                i++;
    109120                       
    110                         while ((cmp(data + j * elem_size, pivot, arg) >= 0) && (j > 0))
     121                        while ((cmp(INDEX(data, j, elem_size), pivot, arg) >= 0) && (j > 0))
    111122                                j--;
    112123                       
    113124                        if (i < j) {
    114                                 memcpy(tmp, data + i * elem_size, elem_size);
    115                                 memcpy(data + i * elem_size, data + j * elem_size,
     125                                memcpy(slot, INDEX(data, i, elem_size), elem_size);
     126                                memcpy(INDEX(data, i, elem_size), INDEX(data, j, elem_size),
    116127                                    elem_size);
    117                                 memcpy(data + j * elem_size, tmp, elem_size);
     128                                memcpy(INDEX(data, j, elem_size), slot, elem_size);
    118129                        } else
    119130                                break;
    120131                }
    121132               
    122                 _qsort(data, j + 1, elem_size, cmp, arg, tmp, pivot);
    123                 _qsort(data + (j + 1) * elem_size, cnt - j - 1, elem_size,
    124                     cmp, arg, tmp, pivot);
     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);
    125136        } else
    126                 _bsort(data, cnt, elem_size, cmp, arg, tmp);
    127 }
    128 
    129 /** Bubble sort wrapper
     137                _gsort(data, cnt, elem_size, cmp, arg, slot);
     138}
     139
     140/** Gnome sort wrapper
    130141 *
    131142 * This is only a wrapper that takes care of memory
    132143 * allocations for storing the slot element for generic
    133  * bubble sort algorithm.
     144 * gnome sort algorithm.
    134145 *
    135146 * @param data      Pointer to data to be sorted.
    … …  
    142153 *
    143154 */
    144 bool bsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, void *arg)
    145 {
    146         void *slot = (void *) malloc(elem_size);
    147         if (!slot)
    148                 return false;
    149        
    150         _bsort(data, cnt, elem_size, cmp, arg, slot);
    151        
    152         free(slot);
     155bool gsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, void *arg)
     156{
     157        uint8_t ibuf_slot[IBUF_SIZE];
     158        void *slot;
     159       
     160        if (elem_size > IBUF_SIZE) {
     161                slot = (void *) malloc(elem_size);
     162                if (!slot)
     163                        return false;
     164        } else
     165                slot = (void *) ibuf_slot;
     166       
     167        _gsort(data, cnt, elem_size, cmp, arg, slot);
     168       
     169        if (elem_size > IBUF_SIZE)
     170                free(slot);
    153171       
    154172        return true;
    … …  
    172190bool qsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, void *arg)
    173191{
    174         void *tmp = (void *) malloc(elem_size);
    175         if (!tmp)
    176                 return false;
    177        
    178         void *pivot = (void *) malloc(elem_size);
    179         if (!pivot) {
    180                 free(tmp);
    181                 return false;
     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;
    182210        }
    183211       
    184         _qsort(data, cnt, elem_size, cmp, arg, tmp, pivot);
    185        
    186         free(pivot);
    187         free(tmp);
     212        _qsort(data, cnt, elem_size, cmp, arg, slot, pivot);
     213       
     214        if (elem_size > IBUF_SIZE) {
     215                free(pivot);
     216                free(slot);
     217        }
    188218       
    189219        return true;
Note: See TracChangeset for help on using the changeset viewer.