dynlist.c

Go to the documentation of this file.

#include <string.h>
#include "dynlist.h"

dynlist createlist(int itemsize) {
        dynlist newlist;
        newlist.itemsize=itemsize;
        newlist.lasti=0;
        newlist.endi=-1;
        newlist.end=0;
        newlist.last=0;
        newlist.start=0;
        
        #ifdef THREADSAFE
        sem_init(&(newlist.lock), 0, 0);
        sem_post(&(newlist.lock));
        #endif

        return newlist;
}

void *newitem(dynlist *list) {
        dynlistitem *temp;

        #ifdef THREADSAFE
        sem_wait(&(list->lock));
        #endif

        temp=(void*)malloc(sizeof(dynlistitem));
        if(!temp) {
                #ifdef THREADSAFE
                sem_post(&(list->lock));
                #endif
                return NULL;
        }
        temp->prev=list->end;
        temp->next=0;
        temp->refer=(void*)malloc(list->itemsize);
        memset(temp->refer, 0, list->itemsize);
        
        if(!list->start)
                list->start=temp;

        list->end=temp;
        if(temp->prev)
                temp->prev->next=temp;
        
        list->endi++;

        if(!list->last)
                list->last=temp;

        
        #ifdef THREADSAFE
        sem_post(&(list->lock));
        #endif

        return temp->refer;
}

void additem(dynlist *list, void *item, int i) {
        dynlistitem *temp, *prev, *next;

        #ifdef THREADSAFE
        sem_wait(&(list->lock));
        #endif

        prev=getdl(list, i-1);
        if(i==0)
                prev=NULL;

        next=getdl(list, i);
        if(list->endi<0)
                next=NULL;
        
        temp=malloc(sizeof(dynlistitem));
        temp->prev=prev;
        temp->next=next;
        temp->refer=(void*)malloc(list->itemsize);
        memcpy(temp->refer, item, list->itemsize);
        
        if(!prev)
                list->start=temp;
        else
                prev->next=temp;

        if(next)
                next->prev=temp;
        else
                list->end=temp;
        
        list->endi++;
        list->last=temp;

        #ifdef THREADSAFE
        sem_post(&(list->lock));
        #endif
}

void appenditem(dynlist *list, void *item) {
        void *target;
        #ifdef THREADSAFE
        sem_wait(&(list->lock));
        #endif

        target=newitem(list);
        memcpy(target, item, list->itemsize);

        #ifdef THREADSAFE
        sem_post(&(list->lock));
        #endif
}

void catlists(dynlist *list1, dynlist *list2) {
        dynlistitem *temp;
        int i;

        #ifdef THREADSAFE
        sem_wait(&(list1->lock));
        sem_wait(&(list2->lock));
        #endif
        
        if(list1->itemsize!=list2->itemsize)
                return; /*TODO: return val?*/

        for(i=0;i<getlen(*list2);++i) {
                temp=getdl(list2, i);
                if(temp)
                        appenditem(list1, temp->refer);
        }

        #ifdef THREADSAFE
        sem_post(&(list1->lock));
        sem_post(&(list2->lock));
        #endif
}

dynlist splitlist(dynlist *list, int i) {
        dynlist temp;
        void *item;
        int loopi, len=getlen(*list);

        #ifdef THREADSAFE
        sem_wait(&(list->lock));
        #endif

        /*TODO:test*/
        temp=createlist(list->itemsize);

        for(loopi=i; loopi<len; ++loopi) {
                item=getitem(list, i);
                if(item) {
                        appenditem(&temp, item);
                        eraseitem(list, i);
                }
        }

        #ifdef THREADSAFE
        sem_post(&(list->lock));
        #endif

        list->last=list->start;
        list->lasti=0;

        return temp;
}

void reverse(dynlist *list) {
        dynlistitem *temp, *refpt;
        
        #ifdef THREADSAFE
        sem_wait(&(list->lock));
        #endif
        temp=list->start;
        list->start=list->end;
        list->end=temp;

        for(temp=list->start; temp; temp=temp->next) {
                refpt=temp->prev;
                temp->prev=temp->next;
                temp->next=refpt;
        }       
        list->lasti = list->endi - list->lasti;

        #ifdef THREADSAFE
        sem_post(&(list->lock));
        #endif
}

void swap(dynlist *list, int i, int j) {
        dynlistitem *itemp, *jtemp;
        void *btemp;

        #ifdef THREADSAFE
        sem_wait(&(list->lock));
        #endif

        itemp=getdl(list, i);
        jtemp=getdl(list, j);
        
        btemp=itemp->refer;
        itemp->refer=jtemp->refer;
        jtemp->refer=btemp;

        #ifdef THREADSAFE
        sem_post(&(list->lock));
        #endif
}

dynlistitem *getdl(dynlist *list, int i) {
        int idx, idxinit, count, difflast;
        dynlistitem *current;
        
        /*experimental: add support for python-style negative indexing
         *-1 equals len-1*/
        if(i<0) {
                i = list->endi + i + 1;
                if(i<0)
                        return NULL;
        }

        if(i>list->endi)
                return NULL;

        if(i==0)
                return list->start;
        
        if(i==list->endi)
                return list->end;

        if(i==list->lasti)
                return list->last;

        if( (difflast=i-list->lasti) < 0) {
                difflast*=-1;
                count=-1;
        }

        else 
                count=1;
        
        if(i > (list->endi/2)) { /*i is over half*/
                if((list->endi - i) < difflast) {/*i is closest to endi*/
                        current=list->end;
                        idxinit=list->endi;
                        count=-1;
                }
        
                else {
                        current=list->last;
                        idxinit=list->lasti;
                }
        }
        
        else if(i<difflast) {
                current=list->start;
                idxinit=0;
                count=1;
        }
        
        else {
                if(list->last)
                        current=list->last;

                else
                        current=list->start;

                idxinit=list->lasti;
        }

        for(idx=idxinit;current;) {
                if(idx==i) {
                        list->lasti=i;
                        list->last=current; 
                        return current;
                }

                switch(count) {
                        case 1:
                                current=current->next;
                                ++idx;
                                break;

                        case -1:
                                current=current->prev;
                                --idx;
                                break;

                        default:
                                return 0;
                }
        }

        return 0;
}

void *getitem(dynlist *list, int i) {
        dynlistitem *manage;

        #ifdef THREADSAFE
        sem_wait(&(list->lock));
        #endif

        manage=getdl(list, i);

        if(manage) {
                #ifdef THREADSAFE
                sem_post(&(list->lock));
                #endif
                
                return manage->refer;
        }

        else {
                #ifdef THREADSAFE
                sem_post(&(list->lock));
                #endif

                return 0;
        }
}

void eraseitem(dynlist *list, int i) {
        dynlistitem *manage;

        #ifdef THREADSAFE
        sem_wait(&(list->lock));
        #endif

        manage=getdl(list, i);
        
        if(!manage) {
                #ifdef THREADSAFE
                sem_post(&(list->lock));
                #endif

                return;
        }

        if(manage->prev)
                manage->prev->next=manage->next;
        else
                list->start=manage->next;
        
        if(manage->next)
                manage->next->prev=manage->prev;
        else
                list->end=manage->prev;
        
        list->endi--;
        
        if(manage->refer)
                free(manage->refer);
        if(manage)
                free(manage);

        list->lasti=0;
        list->last=NULL;
        
        #ifdef THREADSAFE
        sem_post(&(list->lock));
        #endif
}

void clearlist(dynlist *list) {
        dynlistitem *current, *temp;
        #ifdef THREADSAFE
        sem_wait(&(list->lock));
        #endif

        for(current=list->start; current; ) {
                temp=current->next;
                if(current->refer) { 
                        free(current->refer);
                        current->refer=0;
                }
                
                if(current) 
                        free(current);
                        
                current=temp;
        }
        #ifdef THREADSAFE
        sem_post(&(list->lock));
        sem_destroy(&(list->lock));
        #endif
}

long getsize(dynlist list) {
        long temp;

        #ifdef THREADSAFE
        sem_wait(&(list.lock));
        #endif

        temp = (list.endi+1) * (sizeof(dynlistitem) + list.itemsize) + sizeof(dynlist);

        #ifdef THREADSAFE
        sem_post(&(list.lock));
        #endif

        return temp;
}

long getlen(dynlist list) {
        long temp;

        #ifdef THREADSAFE
        sem_wait(&(list.lock));
        #endif

        temp = list.endi+1;

        #ifdef THREADSAFE
        sem_post(&(list.lock));
        #endif

        return temp;
}

void *compile(dynlist list) {
        long total_size, itemnr;
        void *array;
        char *arrayptr;
        dynlistitem *item;
        #ifdef THREADSAFE
        sem_wait(&(list.lock));
        #endif

        total_size=0;


        total_size = (list.endi + 1) * list.itemsize;

        array=arrayptr=(char*)malloc(total_size);

        for(itemnr=0; itemnr<=list.endi; ++itemnr) {
                item = getdl(&list, itemnr);
                memcpy(arrayptr, item->refer, list.itemsize);
                arrayptr+=list.itemsize;
        }

        #ifdef THREADSAFE
        sem_post(&(list.lock));
        #endif
        return array;
}

dynlist decompile(void *data, int itemsize, int num) {
        dynlist list;
        void *temp;
        int i;

        char *override=data;
        
        list=createlist(itemsize);

        for(i=0;i<num;++i) {
                temp=newitem(&list);
                memcpy(temp, override, itemsize);
                override+=itemsize;
        }

        return list;
}

void sortlist(dynlist *list, int (*func)(void*, void*)) {
        int i, len;
        void *first, *second;
        int changed;

        if((len=getlen(*list)) <= 1)
                return;

        do {
                changed=0;

                for(i=0; i<len-1; ++i) {
                        first=getitem(list, i);
                        second=getitem(list, i+1);

                        if( (*func)(first, second)) {
                                swap(list, i, i+1);
                                changed=1;
                        }
                }
        }while(changed);
}

---