src/common/blistsort.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                             *
************************************************************
*       blistsort.cpp, version 1.0                         *
************************************************************
*                                                          *
*blist extension so to keep a list sorted                  *
*                                                          *
*25'05'04- first revision (1.0)                            *
*                                                          *
***********************************************************/

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

struct blist_s *blistsort_add(blist_t *list, void *data, size_t size, class blist_t *tree,
                int(*compar)(const void*,const void*)) {
        return blistsort_add(list,data,size,tree,compar,list->head);
        }

struct blist_s *blistsort_add(blist_t *list, void *data, size_t size, class blist_t *tree,
                int(*compar)(const void*,const void*), blist_s *head)
 {
blist_s *new_obj;
void *copied_data;
//copy the data
        copied_data=list->heap->malloc(size,NO_ALIGN,FAC_BLIST|list->facility,NULL);
        if (copied_data==NULL)
                { complain("out of memory"); return NULL; }
        memmove(copied_data,data,size);
//allocate a book keeping object
        new_obj=(blist_s*) list->heap->malloc(sizeof(blist_s),NO_ALIGN,FAC_BLIST_BK|list->facility,NULL);
        if (new_obj == NULL)
                { complain("out of memory"); list->heap->free(copied_data); return NULL; }
//initialise data
        new_obj->tree=tree;
        new_obj->size=size;
        new_obj->data=copied_data;
//ziom, return the value
        return blistsort_link(list,new_obj,compar,head);

 }

struct blist_s *blistsort_ptr(blist_t *list, void *data, class blist_t *tree, int(*compar)(const void*,const void*))
 {
blist_s *new_obj;
//allocate a book keeping object
        new_obj=(blist_s*) list->heap->malloc(sizeof(blist_s),NO_ALIGN,FAC_BLIST_PTR|list->facility,NULL);
        if (new_obj == NULL)
                { complain("out of memory"); return NULL; }
//initialise data
        new_obj->tree=tree;
        new_obj->size=0;
        new_obj->data=data;
//ziom, return the value
        return blistsort_link(list, new_obj, compar);
 }

struct blist_s *blistsort_link(blist_t *list, blist_s *item,
        int(*compar)(const void*,const void*)) {
                return blistsort_link(list,item,compar,list->head);
 }

struct blist_s *blistsort_link(blist_t *list, blist_s *item,
        int(*compar)(const void*,const void*), blist_s *head)
 {
        list->lock_blist.lock();
/* add as the first */
        if ((head == NULL) ||
                (compar(head,item) >= 0))
         {
                item->next=head;
                if (head)
                        item->prev=head->prev;
                else
                        item->prev=NULL;
                if (item->next)
                        item->next->prev=item;
                else
                        list->tail=item;
                if ((head == NULL) || (list->head == head))
                        list->head=item;
                list->lock_blist.ulock();
                return item;
         }

/* add as last */
        if (compar(list->tail, item) <= 0)
         {
                item->next=NULL;
                item->prev=list->tail;
                if (item->prev)
                        item->prev->next=item;
                else
                        list->head=item;
                list->tail=item;
                list->lock_blist.ulock();
                return item;
         }
/* or in the middle */
blist_s *obj;
        for (obj=head;obj;obj=obj->next)
         {
                if (compar(obj, item) < 0)
                        continue;
                item->next=obj;
                item->prev=obj->prev;
                if (item->prev)
                        item->prev->next=item;
                else
                        list->head=item;
                obj->prev=item;
                list->lock_blist.ulock();
                return item;
         }

        list->lock_blist.ulock();
        return NULL;
 }

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

---