Changes in / [50f4b95:0a79ad9] in mainline


Ignore:
Location:
kernel
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • kernel/genarch/src/acpi/madt.c

    r50f4b95 r0a79ad9  
    131131};
    132132
    133 static int madt_cmp(void *a, void *b, void *arg)
    134 {
    135         uint8_t typea = (*((struct madt_apic_header **) a))->type;
    136         uint8_t typeb = (*((struct madt_apic_header **) b))->type;
     133static int madt_cmp(void *a, void *b)
     134{
     135        uint8_t typea = ((struct madt_apic_header *) a)->type;
     136        uint8_t typeb = ((struct madt_apic_header *) b)->type;
    137137       
    138138        if (typea > typeb)
    … …  
    208208       
    209209        /* Sort MADT index structure */
    210         if (!gsort(madt_entries_index, madt_entries_index_cnt,
    211             sizeof(struct madt_apic_header *), madt_cmp, NULL))
    212                 panic("Sorting error.");
     210        qsort(madt_entries_index, madt_entries_index_cnt, sizeof(uintptr_t),
     211            &madt_cmp);
    213212       
    214213        /* Parse MADT entries */

  • kernel/generic/include/sort.h

    r50f4b95 r0a79ad9  
    3838#include <typedefs.h>
    3939
    40 typedef int (* sort_cmp_t)(void *, void *, void *);
     40/*
     41 * sorting routines
     42 */
     43extern void bubblesort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b));
     44extern void qsort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b));
    4145
    42 extern bool gsort(void *, size_t, size_t, sort_cmp_t, void *);
    43 extern bool qsort(void *, size_t, size_t, sort_cmp_t, void *);
     46/*
     47 * default sorting comparators
     48 */
     49extern int int_cmp(void * a, void * b);
     50extern int uint32_t_cmp(void * a, void * b);
     51extern int uint16_t_cmp(void * a, void * b);
     52extern int uint8_t_cmp(void * a, void * b);
    4453
    4554#endif

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

    r50f4b95 r0a79ad9  
    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 gnome sort).
    39  *
    40  */
    41 
     38 * algorithms (e.g. quick sort and bubble sort).
     39 */
     40 
    4241#include <mm/slab.h>
    4342#include <memstr.h>
    4443#include <sort.h>
    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  */
    73 static 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;
     44#include <panic.h>
     45
     46#define EBUFSIZE        32
     47
     48void _qsort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *tmp, void *pivot);
     49void _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 */
     64void 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);
     74        }
     75
     76        _qsort(data, n, e_size, cmp, tmp, pivot);
    7777       
    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++;
     78        if (e_size > EBUFSIZE) {
     79                free(tmp);
     80                free(pivot);
    9081        }
    9182}
    … …  
    9384/** Quicksort
    9485 *
    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  */
    109 static 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))
     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 */
     96void _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))
    120105                                i++;
    121                        
    122                         while ((cmp(INDEX(data, j, elem_size), pivot, arg) >= 0) && (j > 0))
     106                        while ((cmp(data + j * e_size, pivot) >= 0) && (j > 0))
    123107                                j--;
    124108                       
    125109                        if (i < j) {
    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
     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 {
    131114                                break;
     115                        }
    132116                }
    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  */
    158 bool 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;
     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);
     120        } else {
     121                _bubblesort(data, n, e_size, cmp, tmp);
     122        }
     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 */
     136void 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;
    162140       
    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;
     141        if (e_size > EBUFSIZE) {
     142                slot = (void *) malloc(e_size, 0);
     143        }
     144
     145        _bubblesort(data, n, e_size, cmp, slot);
    169146       
    170         _gsort(data, cnt, elem_size, cmp, arg, slot);
    171        
    172         if (elem_size > IBUF_SIZE)
     147        if (e_size > EBUFSIZE) {
    173148                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  */
    195 bool 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;
     149        }
     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 */
     163void _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                        }
    211177                }
    212         } else {
    213                 slot = (void *) ibuf_slot;
    214                 pivot = (void *) ibuf_pivot;
    215         }
    216        
    217         _qsort(data, cnt, elem_size, cmp, arg, slot, pivot);
    218        
    219         if (elem_size > IBUF_SIZE) {
    220                 free(pivot);
    221                 free(slot);
    222         }
    223        
    224         return true;
     178        }
     179
     180}
     181
     182/*
     183 * Comparator returns 1 if a > b, 0 if a == b, -1 if a < b
     184 */
     185int int_cmp(void * a, void * b)
     186{
     187        return (* (int *) a > * (int*)b) ? 1 : (*(int *)a < * (int *)b) ? -1 : 0;
     188}
     189
     190int 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
     195int 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
     200int 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;
    225203}
    226204
Note: See TracChangeset for help on using the changeset viewer.