Subversion Repositories HelenOS-historic

Rev

Rev 336 | Rev 350 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 336 Rev 349
Line 29... Line 29...
29 
#include <mm/heap.h>
 29 
#include <mm/heap.h>
30 
#include <memstr.h>
 30 
#include <memstr.h>
31 
#include <sort.h>
 31 
#include <sort.h>
32 
#include <panic.h>
 32 
#include <panic.h>
33 
 
 33 
 
- 
 
 34 
#define EBUFSIZE    32
- 
 
 35 
 
34 
static void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void * pivot, void * tmp);
 36 
static void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void * pivot, void * tmp);
35 
 
 37 
 
36 
/*
 38 
/*
37 
 * Wrapper method for quicksort algorithm to decrease amount of allocations
 39 
 * Wrapper method for quicksort algorithm to decrease amount of allocations
38 
 */
 40 
 */
39 
void qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) {
 41 
void qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) {
- 
 
 42 
    __u8 buf_tmp[EBUFSIZE];
- 
 
 43 
    __u8 buf_pivot[EBUFSIZE];
- 
 
 44 
    void * tmp = buf_tmp;
- 
 
 45 
    void * pivot = buf_pivot;
- 
 
 46 
 
- 
 
 47 
    if (e_size > EBUFSIZE) {
40 
    void * tmp = (void *) malloc(e_size);
 48 
        pivot = (void *) malloc(e_size);
41 
    void * pivot = (void *) malloc(e_size);
 49 
        tmp = (void *) malloc(e_size);
42 
   
 50 
   
43 
    if (!tmp || !pivot) {
 51 
        if (!tmp || !pivot) {
44 
        panic("Cannot allocate memory\n");
 52 
            panic("Cannot allocate memory\n");
- 
 
 53 
        }
45 
    }
 54 
    }
46 
 
 55 
 
47 
    _qsort(data, n, e_size, cmp, pivot, tmp);
 56 
    _qsort(data, n, e_size, cmp, pivot, tmp);
48 
   
 57 
   
- 
 
 58 
    if (e_size > EBUFSIZE) {
49 
    free(tmp);
 59 
        free(tmp);
50 
    free(pivot);
 60 
        free(pivot);
- 
 
 61 
    }
51 
}
 62 
}
52 
 
 63 
 
53 
 
 64 
 
54 
void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) {
 65 
void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) {
- 
 
 66 
    __u8 buf_slot[EBUFSIZE];
55 
    bool done = false;
 67 
    bool done = false;
56 
    void * p;
 68 
    void * p;
- 
 
 69 
    void * slot = buf_slot;
- 
 
 70 
   
- 
 
 71 
    if (e_size > EBUFSIZE) {
57 
    void * slot = (void *) malloc(e_size);
 72 
        slot = (void *) malloc(e_size);
- 
 
 73 
       
- 
 
 74 
        if (!slot) {
- 
 
 75 
            panic("Cannot allocate memory\n");
- 
 
 76 
        }
- 
 
 77 
    }
58 
 
 78 
 
59 
    while (!done) {
 79 
    while (!done) {
60 
        done = true;
 80 
        done = true;
61 
        for (p = data; p < data + e_size * (n - 1); p = p + e_size) {
 81 
        for (p = data; p < data + e_size * (n - 1); p = p + e_size) {
62 
            if (cmp(p, p + e_size) == 1) {
 82 
            if (cmp(p, p + e_size) == 1) {
Line 66... Line 86...
66 
                done = false;
 86 
                done = false;
67 
            }
 87 
            }
68 
        }
 88 
        }
69 
    }
 89 
    }
70 
   
 90 
   
- 
 
 91 
    if (e_size > EBUFSIZE) {   
71 
    free(slot);
 92 
        free(slot);
- 
 
 93 
    }
72 
}
 94 
}
73 
 
 95 
 
74 
static void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void * pivot, void * tmp) {
 96 
static void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void * pivot, void * tmp) {
75 
    if (n > 4) {
 97 
    if (n > 4) {
76 
        int i = 0, j = n - 1;
 98 
        int i = 0, j = n - 1;