Subversion Repositories HelenOS-historic

Rev

Rev 336 | Rev 350 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
333 bondari 1 
/*
2 
 * Copyright (C) 2005 Sergey Bondari
3 
 * All rights reserved.
4 
 *
5 
 * Redistribution and use in source and binary forms, with or without
6 
 * modification, are permitted provided that the following conditions
7 
 * are met:
8 
 *
9 
 * - Redistributions of source code must retain the above copyright
10 
 *   notice, this list of conditions and the following disclaimer.
11 
 * - Redistributions in binary form must reproduce the above copyright
12 
 *   notice, this list of conditions and the following disclaimer in the
13 
 *   documentation and/or other materials provided with the distribution.
14 
 * - The name of the author may not be used to endorse or promote products
15 
 *   derived from this software without specific prior written permission.
16 
 *
17 
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 
 */
28 
 
331 bondari 29 
#include <mm/heap.h>
30 
#include <memstr.h>
31 
#include <sort.h>
335 bondari 32 
#include <panic.h>
331 bondari 33 
 
349 jermar 34 
#define EBUFSIZE    32
35 
 
335 bondari 36 
static void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void * pivot, void * tmp);
331 bondari 37 
 
335 bondari 38 
/*
39 
 * Wrapper method for quicksort algorithm to decrease amount of allocations
40 
 */
331 bondari 41 
void qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) {
349 jermar 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) {
48 
        pivot = (void *) malloc(e_size);
49 
        tmp = (void *) malloc(e_size);
335 bondari 50 
 
349 jermar 51 
        if (!tmp || !pivot) {
52 
            panic("Cannot allocate memory\n");
53 
        }
335 bondari 54 
    }
55 
 
56 
    _qsort(data, n, e_size, cmp, pivot, tmp);
57 
 
349 jermar 58 
    if (e_size > EBUFSIZE) {
59 
        free(tmp);
60 
        free(pivot);
61 
    }
335 bondari 62 
}
63 
 
64 
 
65 
void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) {
349 jermar 66 
    __u8 buf_slot[EBUFSIZE];
335 bondari 67 
    bool done = false;
68 
    void * p;
349 jermar 69 
    void * slot = buf_slot;
70 
 
71 
    if (e_size > EBUFSIZE) {
72 
        slot = (void *) malloc(e_size);
73 
 
74 
        if (!slot) {
75 
            panic("Cannot allocate memory\n");
76 
        }
77 
    }
335 bondari 78 
 
79 
    while (!done) {
80 
        done = true;
81 
        for (p = data; p < data + e_size * (n - 1); p = p + e_size) {
82 
            if (cmp(p, p + e_size) == 1) {
83 
                memcpy(slot, p, e_size);
84 
                memcpy(p, p + e_size, e_size);
85 
                memcpy(p + e_size, slot, e_size);
86 
                done = false;
87 
            }
88 
        }
89 
    }
90 
 
349 jermar 91 
    if (e_size > EBUFSIZE) {   
92 
        free(slot);
93 
    }
335 bondari 94 
}
95 
 
96 
static void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void * pivot, void * tmp) {
333 bondari 97 
    if (n > 4) {
98 
        int i = 0, j = n - 1;
331 bondari 99 
 
333 bondari 100 
        memcpy(pivot, data, e_size);
331 bondari 101 
 
333 bondari 102 
        while (1) {
103 
            while ((cmp(data + i * e_size, pivot) < 0) && i < n) i++;
104 
            while ((cmp(data + j * e_size, pivot) >=0) && j > 0) j--;
105 
            if (i<j) {
106 
                memcpy(tmp, data + i * e_size, e_size);
107 
                memcpy(data + i * e_size, data + j * e_size, e_size);
108 
                memcpy(data + j * e_size, tmp, e_size);
109 
            } else {
110 
                break;
111 
            }
112 
        }
331 bondari 113 
 
333 bondari 114 
        qsort(data, j + 1, e_size, cmp);
115 
        qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp);
116 
    } else {
117 
        bubblesort(data, n, e_size, cmp);
118 
    }
331 bondari 119 
}
120 
 
121 
 
122 
 
123 
/*
124 
 * Comparator returns 1 if a > b, 0 if a == b, -1 if a < b
125 
 */
126 
int int_cmp(void * a, void * b) {
333 bondari 127 
    return (* (int *) a > * (int*)b) ? 1 : (*(int *)a < * (int *)b) ? -1 : 0;
331 bondari 128 
}
129 
 
130 
int __u8_cmp(void * a, void * b) {
333 bondari 131 
    return (* (__u8 *) a > * (__u8 *)b) ? 1 : (*(__u8 *)a < * (__u8 *)b) ? -1 : 0;
331 bondari 132 
}
133 
 
134 
int __u16_cmp(void * a, void * b) {
333 bondari 135 
    return (* (__u16 *) a > * (__u16 *)b) ? 1 : (*(__u16 *)a < * (__u16 *)b) ? -1 : 0;
331 bondari 136 
}
137 
 
138 
int __u32_cmp(void * a, void * b) {
333 bondari 139 
    return (* (__u32 *) a > * (__u32 *)b) ? 1 : (*(__u32 *)a < * (__u32 *)b) ? -1 : 0;
331 bondari 140 
}
141