Changeset cefb126 in mainline for kernel/generic/src/lib/sort.c


Ignore:
Timestamp:
2010-07-02T14:19:30Z (14 years ago)
Author:
Jakub Jermar <jakub@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
89c57b6
Parents:
fe7abd0 (diff), e3ee9b9 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge mainline changes.

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    rfe7abd0 rcefb126  
    2727 */
    2828
    29 /** @addtogroup generic 
     29/** @addtogroup generic
    3030 * @{
    3131 */
    … …  
    3333/**
    3434 * @file
    35  * @brief       Sorting functions.
     35 * @brief Sorting functions.
    3636 *
    3737 * This files contains functions implementing several sorting
    38  * algorithms (e.g. quick sort and bubble sort).
    39  */
    40  
     38 * algorithms (e.g. quick sort and gnome sort).
     39 *
     40 */
     41
    4142#include <mm/slab.h>
    4243#include <memstr.h>
    4344#include <sort.h>
    44 #include <panic.h>
    45 
    46 #define EBUFSIZE        32
    47 
    48 void _qsort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *tmp, void *pivot);
    49 void _bubblesort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot);
    50 
    51 /** Quicksort wrapper
    52  *
    53  * This is only a wrapper that takes care of memory allocations for storing
    54  * the pivot and temporary elements for generic quicksort algorithm.
    55  *
    56  * This function _can_ sleep
    57  *
    58  * @param data Pointer to data to be sorted.
    59  * @param n Number of elements to be sorted.
    60  * @param e_size Size of one element.
    61  * @param cmp Comparator function.
    62  *
    63  */
    64 void qsort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b))
    65 {
    66         uint8_t buf_tmp[EBUFSIZE];
    67         uint8_t buf_pivot[EBUFSIZE];
    68         void * tmp = buf_tmp;
    69         void * pivot = buf_pivot;
    70 
    71         if (e_size > EBUFSIZE) {
    72                 pivot = (void *) malloc(e_size, 0);
    73                 tmp = (void *) malloc(e_size, 0);
     45
     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,
     62 * using pre-allocated buffer.
     63 *
     64 * @param data      Pointer to data to be sorted.
     65 * @param cnt       Number of elements to be sorted.
     66 * @param elem_size Size of one element.
     67 * @param cmp       Comparator function.
     68 * @param arg       3rd argument passed to cmp.
     69 * @param slot      Pointer to scratch memory buffer
     70 *                  elem_size bytes long.
     71 *
     72 */
     73static void _gsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp,
     74    void *arg, void *slot)
     75{
     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++;
    7489        }
    75 
    76         _qsort(data, n, e_size, cmp, tmp, pivot);
    77        
    78         if (e_size > EBUFSIZE) {
    79                 free(tmp);
    80                 free(pivot);
    81         }
    8290}
    8391
    8492/** Quicksort
    8593 *
    86  * Apply generic quicksort algorithm on supplied data, using pre-allocated buffers.
    87  *
    88  * @param data Pointer to data to be sorted.
    89  * @param n Number of elements to be sorted.
    90  * @param e_size Size of one element.
    91  * @param cmp Comparator function.
    92  * @param tmp Pointer to scratch memory buffer e_size bytes long.
    93  * @param pivot Pointer to scratch memory buffer e_size bytes long.
    94  *
    95  */
    96 void _qsort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *tmp, void *pivot)
    97 {
    98         if (n > 4) {
    99                 unsigned int i = 0, j = n - 1;
    100 
    101                 memcpy(pivot, data, e_size);
    102 
    103                 while (1) {
    104                         while ((cmp(data + i * e_size, pivot) < 0) && (i < n))
     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 */
     108static 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))
    105119                                i++;
    106                         while ((cmp(data + j * e_size, pivot) >= 0) && (j > 0))
     120                       
     121                        while ((cmp(INDEX(data, j, elem_size), pivot, arg) >= 0) && (j > 0))
    107122                                j--;
    108123                       
    109124                        if (i < j) {
    110                                 memcpy(tmp, data + i * e_size, e_size);
    111                                 memcpy(data + i * e_size, data + j * e_size, e_size);
    112                                 memcpy(data + j * e_size, tmp, e_size);
    113                         } else {
     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
    114130                                break;
    115                         }
    116131                }
    117 
    118                 _qsort(data, j + 1, e_size, cmp, tmp, pivot);
    119                 _qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp, tmp, pivot);
     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
     140/** Gnome sort wrapper
     141 *
     142 * This is only a wrapper that takes care of memory
     143 * allocations for storing the slot element for generic
     144 * gnome sort algorithm.
     145 *
     146 * This function can sleep.
     147 *
     148 * @param data      Pointer to data to be sorted.
     149 * @param cnt       Number of elements to be sorted.
     150 * @param elem_size Size of one element.
     151 * @param cmp       Comparator function.
     152 * @param arg       3rd argument passed to cmp.
     153 *
     154 * @return True if sorting succeeded.
     155 *
     156 */
     157bool gsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, void *arg)
     158{
     159        uint8_t ibuf_slot[IBUF_SIZE];
     160        void *slot;
     161       
     162        if (elem_size > IBUF_SIZE) {
     163                slot = (void *) malloc(elem_size, 0);
     164                if (!slot)
     165                        return false;
     166        } else
     167                slot = (void *) ibuf_slot;
     168       
     169        _gsort(data, cnt, elem_size, cmp, arg, slot);
     170       
     171        if (elem_size > IBUF_SIZE)
     172                free(slot);
     173       
     174        return true;
     175}
     176
     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 */
     194bool 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                }
    120211        } else {
    121                 _bubblesort(data, n, e_size, cmp, tmp);
     212                slot = (void *) ibuf_slot;
     213                pivot = (void *) ibuf_pivot;
    122214        }
    123 }
    124 
    125 /** Bubblesort wrapper
    126  *
    127  * This is only a wrapper that takes care of memory allocation for storing
    128  * the slot element for generic bubblesort algorithm.
    129  *
    130  * @param data Pointer to data to be sorted.
    131  * @param n Number of elements to be sorted.
    132  * @param e_size Size of one element.
    133  * @param cmp Comparator function.
    134  *
    135  */
    136 void bubblesort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b))
    137 {
    138         uint8_t buf_slot[EBUFSIZE];
    139         void * slot = buf_slot;
    140        
    141         if (e_size > EBUFSIZE) {
    142                 slot = (void *) malloc(e_size, 0);
    143         }
    144 
    145         _bubblesort(data, n, e_size, cmp, slot);
    146        
    147         if (e_size > EBUFSIZE) {
     215       
     216        _qsort(data, cnt, elem_size, cmp, arg, slot, pivot);
     217       
     218        if (elem_size > IBUF_SIZE) {
     219                free(pivot);
    148220                free(slot);
    149221        }
    150 }
    151 
    152 /** Bubblesort
    153  *
    154  * Apply generic bubblesort algorithm on supplied data, using pre-allocated buffer.
    155  *
    156  * @param data Pointer to data to be sorted.
    157  * @param n Number of elements to be sorted.
    158  * @param e_size Size of one element.
    159  * @param cmp Comparator function.
    160  * @param slot Pointer to scratch memory buffer e_size bytes long.
    161  *
    162  */
    163 void _bubblesort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot)
    164 {
    165         bool done = false;
    166         void * p;
    167 
    168         while (!done) {
    169                 done = true;
    170                 for (p = data; p < data + e_size * (n - 1); p = p + e_size) {
    171                         if (cmp(p, p + e_size) == 1) {
    172                                 memcpy(slot, p, e_size);
    173                                 memcpy(p, p + e_size, e_size);
    174                                 memcpy(p + e_size, slot, e_size);
    175                                 done = false;
    176                         }
    177                 }
    178         }
    179 
    180 }
    181 
    182 /*
    183  * Comparator returns 1 if a > b, 0 if a == b, -1 if a < b
    184  */
    185 int int_cmp(void * a, void * b)
    186 {
    187         return (* (int *) a > * (int*)b) ? 1 : (*(int *)a < * (int *)b) ? -1 : 0;
    188 }
    189 
    190 int uint8_t_cmp(void * a, void * b)
    191 {
    192         return (* (uint8_t *) a > * (uint8_t *)b) ? 1 : (*(uint8_t *)a < * (uint8_t *)b) ? -1 : 0;
    193 }
    194 
    195 int uint16_t_cmp(void * a, void * b)
    196 {
    197         return (* (uint16_t *) a > * (uint16_t *)b) ? 1 : (*(uint16_t *)a < * (uint16_t *)b) ? -1 : 0;
    198 }
    199 
    200 int uint32_t_cmp(void * a, void * b)
    201 {
    202         return (* (uint32_t *) a > * (uint32_t *)b) ? 1 : (*(uint32_t *)a < * (uint32_t *)b) ? -1 : 0;
     222       
     223        return true;
    203224}
    204225
Note: See TracChangeset for help on using the changeset viewer.