WebSVN – HelenOS – Diff – //branches/dd/kernel/generic/src/lib/sort.c



#include <sort.h>
#include <panic.h>
 
#define EBUFSIZE    32
 
void _qsort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *tmp, void *pivot);
void _bubblesort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot);
 
/** Quicksort wrapper
 *
 * This is only a wrapper that takes care of memory allocations for storing
 * the pivot and temporary elements for generic quicksort algorithm.

 * @param n Number of elements to be sorted.
 * @param e_size Size of one element.
 * @param cmp Comparator function.
 *
 */
void qsort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b))
{
    uint8_t buf_tmp[EBUFSIZE];
    uint8_t buf_pivot[EBUFSIZE];
    void * tmp = buf_tmp;
    void * pivot = buf_pivot;

 * @param cmp Comparator function.
 * @param tmp Pointer to scratch memory buffer e_size bytes long.
 * @param pivot Pointer to scratch memory buffer e_size bytes long.
 *
 */
void _qsort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *tmp, void *pivot)
{
    if (n > 4) {
        unsigned int i = 0, j = n - 1;
 
        memcpy(pivot, data, e_size);

 * @param n Number of elements to be sorted.
 * @param e_size Size of one element.
 * @param cmp Comparator function.
 *
 */
void bubblesort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b))
{
    uint8_t buf_slot[EBUFSIZE];
    void * slot = buf_slot;
   
    if (e_size > EBUFSIZE) {

 * @param e_size Size of one element.
 * @param cmp Comparator function.
 * @param slot Pointer to scratch memory buffer e_size bytes long.
 *
 */
void _bubblesort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot)
{
    bool done = false;
    void * p;
 
    while (!done) {

Rev 3022	Rev 4537
Line 43...	Line 43...
43	#include <sort.h>	43	#include <sort.h>
44	#include <panic.h>	44	#include <panic.h>
45		45
46	#define EBUFSIZE 32	46	#define EBUFSIZE 32
47		47
48	void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void tmp, void pivot);	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, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot);	49	void _bubblesort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot);
50		50
51	/** Quicksort wrapper	51	/** Quicksort wrapper
52	*	52	*
53	* This is only a wrapper that takes care of memory allocations for storing	53	* This is only a wrapper that takes care of memory allocations for storing
54	* the pivot and temporary elements for generic quicksort algorithm.	54	* the pivot and temporary elements for generic quicksort algorithm.
Line 59...	Line 59...
59	* @param n Number of elements to be sorted.	59	* @param n Number of elements to be sorted.
60	* @param e_size Size of one element.	60	* @param e_size Size of one element.
61	* @param cmp Comparator function.	61	* @param cmp Comparator function.
62	*	62	*
63	*/	63	*/
64	void qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b))	64	void qsort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b))
65	{	65	{
66	uint8_t buf_tmp[EBUFSIZE];	66	uint8_t buf_tmp[EBUFSIZE];
67	uint8_t buf_pivot[EBUFSIZE];	67	uint8_t buf_pivot[EBUFSIZE];
68	void * tmp = buf_tmp;	68	void * tmp = buf_tmp;
69	void * pivot = buf_pivot;	69	void * pivot = buf_pivot;
Line 91...	Line 91...
91	* @param cmp Comparator function.	91	* @param cmp Comparator function.
92	* @param tmp Pointer to scratch memory buffer e_size bytes long.	92	* @param tmp Pointer to scratch memory buffer e_size bytes long.
93	* @param pivot Pointer to scratch memory buffer e_size bytes long.	93	* @param pivot Pointer to scratch memory buffer e_size bytes long.
94	*	94	*
95	*/	95	*/
96	void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void tmp, void pivot)	96	void _qsort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void tmp, void pivot)
97	{	97	{
98	if (n > 4) {	98	if (n > 4) {
99	unsigned int i = 0, j = n - 1;	99	unsigned int i = 0, j = n - 1;
100		100
101	memcpy(pivot, data, e_size);	101	memcpy(pivot, data, e_size);
Line 131...	Line 131...
131	* @param n Number of elements to be sorted.	131	* @param n Number of elements to be sorted.
132	* @param e_size Size of one element.	132	* @param e_size Size of one element.
133	* @param cmp Comparator function.	133	* @param cmp Comparator function.
134	*	134	*
135	*/	135	*/
136	void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b))	136	void bubblesort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b))
137	{	137	{
138	uint8_t buf_slot[EBUFSIZE];	138	uint8_t buf_slot[EBUFSIZE];
139	void * slot = buf_slot;	139	void * slot = buf_slot;
140		140
141	if (e_size > EBUFSIZE) {	141	if (e_size > EBUFSIZE) {
Line 158...	Line 158...
158	* @param e_size Size of one element.	158	* @param e_size Size of one element.
159	* @param cmp Comparator function.	159	* @param cmp Comparator function.
160	* @param slot Pointer to scratch memory buffer e_size bytes long.	160	* @param slot Pointer to scratch memory buffer e_size bytes long.
161	*	161	*
162	*/	162	*/
163	void _bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot)	163	void _bubblesort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot)
164	{	164	{
165	bool done = false;	165	bool done = false;
166	void * p;	166	void * p;
167		167
168	while (!done) {	168	while (!done) {

Subversion Repositories HelenOS

(root)//branches/dd/kernel/generic/src/lib/sort.c – Rev 3022 → 4537