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


Ignore:
Timestamp:
2010-06-30T20:36:48Z (14 years ago)
Author:
Martin Decky <martin@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
99718a2e
Parents:
0a79ad9 (diff), e9f4b59 (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 (hopefully) final fix for ia32/amd64 SMP issues.

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r0a79ad9 r50f4b95  
    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                        printf("exch: %u %u\n", i - 1, i);
     87                        i--;
     88                } else
     89                        i++;
    7490        }
    75 
    76         _qsort(data, n, e_size, cmp, tmp, pivot);
    77        
    78         if (e_size > EBUFSIZE) {
    79                 free(tmp);
    80                 free(pivot);
    81         }
    8291}
    8392
    8493/** Quicksort
    8594 *
    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))
     95 * Apply generic quicksort algorithm on supplied data,
     96 * using pre-allocated buffers.
     97 *
     98 * @param data      Pointer to data to be sorted.
     99 * @param cnt       Number of elements to be sorted.
     100 * @param elem_size Size of one element.
     101 * @param cmp       Comparator function.
     102 * @param arg       3rd argument passed to cmp.
     103 * @param slot      Pointer to scratch memory buffer
     104 *                  elem_size bytes long.
     105 * @param pivot     Pointer to scratch memory buffer
     106 *                  elem_size bytes long.
     107 *
     108 */
     109static void _qsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp,
     110    void *arg, void *slot, void *pivot)
     111{
     112        if (cnt > 4) {
     113                size_t i = 0;
     114                size_t j = cnt - 1;
     115               
     116                memcpy(pivot, data, elem_size);
     117               
     118                while (true) {
     119                        while ((cmp(INDEX(data, i, elem_size), pivot, arg) < 0) && (i < cnt))
    105120                                i++;
    106                         while ((cmp(data + j * e_size, pivot) >= 0) && (j > 0))
     121                       
     122                        while ((cmp(INDEX(data, j, elem_size), pivot, arg) >= 0) && (j > 0))
    107123                                j--;
    108124                       
    109125                        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 {
     126                                memcpy(slot, INDEX(data, i, elem_size), elem_size);
     127                                memcpy(INDEX(data, i, elem_size), INDEX(data, j, elem_size),
     128                                    elem_size);
     129                                memcpy(INDEX(data, j, elem_size), slot, elem_size);
     130                        } else
    114131                                break;
    115                         }
    116132                }
    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);
     133               
     134                _qsort(data, j + 1, elem_size, cmp, arg, slot, pivot);
     135                _qsort(INDEX(data, j + 1, elem_size), cnt - j - 1, elem_size,
     136                    cmp, arg, slot, pivot);
     137        } else
     138                _gsort(data, cnt, elem_size, cmp, arg, slot);
     139}
     140
     141/** Gnome sort wrapper
     142 *
     143 * This is only a wrapper that takes care of memory
     144 * allocations for storing the slot element for generic
     145 * gnome sort algorithm.
     146 *
     147 * This function can sleep.
     148 *
     149 * @param data      Pointer to data to be sorted.
     150 * @param cnt       Number of elements to be sorted.
     151 * @param elem_size Size of one element.
     152 * @param cmp       Comparator function.
     153 * @param arg       3rd argument passed to cmp.
     154 *
     155 * @return True if sorting succeeded.
     156 *
     157 */
     158bool gsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, void *arg)
     159{
     160        uint8_t ibuf_slot[IBUF_SIZE];
     161        void *slot;
     162       
     163        if (elem_size > IBUF_SIZE) {
     164                slot = (void *) malloc(elem_size, 0);
     165                if (!slot)
     166                        return false;
     167        } else
     168                slot = (void *) ibuf_slot;
     169       
     170        _gsort(data, cnt, elem_size, cmp, arg, slot);
     171       
     172        if (elem_size > IBUF_SIZE)
     173                free(slot);
     174       
     175        return true;
     176}
     177
     178/** Quicksort wrapper
     179 *
     180 * This is only a wrapper that takes care of memory
     181 * allocations for storing the pivot and temporary elements
     182 * for generic quicksort algorithm.
     183 *
     184 * This function can sleep.
     185 *
     186 * @param data      Pointer to data to be sorted.
     187 * @param cnt       Number of elements to be sorted.
     188 * @param elem_size Size of one element.
     189 * @param cmp       Comparator function.
     190 * @param arg       3rd argument passed to cmp.
     191 *
     192 * @return True if sorting succeeded.
     193 *
     194 */
     195bool qsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, void *arg)
     196{
     197        uint8_t ibuf_slot[IBUF_SIZE];
     198        uint8_t ibuf_pivot[IBUF_SIZE];
     199        void *slot;
     200        void *pivot;
     201       
     202        if (elem_size > IBUF_SIZE) {
     203                slot = (void *) malloc(elem_size, 0);
     204                if (!slot)
     205                        return false;
     206               
     207                pivot = (void *) malloc(elem_size, 0);
     208                if (!pivot) {
     209                        free(slot);
     210                        return false;
     211                }
    120212        } else {
    121                 _bubblesort(data, n, e_size, cmp, tmp);
     213                slot = (void *) ibuf_slot;
     214                pivot = (void *) ibuf_pivot;
    122215        }
    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) {
     216       
     217        _qsort(data, cnt, elem_size, cmp, arg, slot, pivot);
     218       
     219        if (elem_size > IBUF_SIZE) {
     220                free(pivot);
    148221                free(slot);
    149222        }
    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;
     223       
     224        return true;
    203225}
    204226
Note: See TracChangeset for help on using the changeset viewer.