src/common/qsort.cpp

Idź do dokumentacji tego pliku.

/***********************************************************
*PANALIX 0.06, (c) Adrian Panasiuk 2002-4                  *
*adek336[at]o2.pl, panalix.prv.pl                          *
*under GPLv3 license                                       *
*                                                          *
*panalix - small osdev project                             *
************************************************************
*       qsort.cpp, version 1.0                             *
************************************************************
*                                                          *
*damn good quick sort algorithm, compliant with info       *
*'qsort'
*                                                          *
*25'04'04- first revision (1.0)                            *
*                                                          *
***********************************************************/

#include "src/common/shared.hpp"
#include "src/memory/memset.hpp"
#include "src/memory/align.hpp"
#include "src/memory/heap.hpp"
#include "src/common/qsort.hpp"

// #define malloc(ignore) ;
// #define free(ignore) ;

/*swap two elements*/
void element_swap(void *l1, void *l2, void *temp_buf, size_t size)
 {
        memmove(temp_buf,l1,size);
        memmove(l1,l2,size);
        memmove(l2,temp_buf,size);
 }

/*tha ziom quick sort algorithm*/
void qsort(void *base, size_t nmemb, size_t size, int(*compar)(const void*,const void*), void *temp_buf)
 {
void *pivot, *less, *more, *last;
void *buf;
        if (nmemb < 2) return;
/*get a tempbuf*/
        if (temp_buf == NULL)
                buf=Memory::Heap::heap0.malloc(size, NO_ALIGN, FAC_OTHER|FAC_QSORTBUF, NULL);
        else
                buf=temp_buf;
/*find a pivot*/
        less=pivot=base;
        more=last=(void*)((uint32)base+(nmemb-1)*size);
/*partition*/
        while (less < more)
         {
                while (compar(pivot,less) >= 0) {
                        if (less == last) break;
                        less=(void*)((uint32)less+size); }
                while (compar(pivot,more) < 0)
                        more=(void*)((uint32)more-size);
                if (less < more)
                        element_swap(less,more,buf,size);
         }
                if (less < more)
                {element_swap(pivot,less,buf,size); pivot=less;}
                else
                {element_swap(pivot,more,buf,size); pivot=more;}
/*recursive*/
        qsort(base,((uint32)pivot-(uint32)base)/size,size,compar, buf);
        qsort((void*)((uint32)pivot+size),nmemb-1-(((uint32)pivot-(uint32)base)/size),size,compar, buf);
/*get ridof the buffer*/
        if (temp_buf==NULL)
                Memory::Heap::heap0.free(buf);
 }

/*compare function for ints*/
int intcompar(const void *v1, const void *v2) {
        if (*(int*)v1 > *(int*)v2)
                return 1;
        if (*(int*)v1 < *(int*)v2)
                return -1;
        return 0;
 }


/***********************************************************
*                                                          *
*panalix 0.06 (c) Adrian Panasiuk 2002-4                   *
*adek336[at]o2.pl, panalix.prv.pl                          *
*                                                          *
***********************************************************/

---