dtlist.c

Go to the documentation of this file.

#include        <cdt/dthdr.h>
#include        <stdlib.h>
 
/*      List, Deque, Stack, Queue.
**
**      Written by Kiem-Phong Vo (05/25/96)
*/
 
static void* dtlist(Dt_t* dt, void* obj, int type)
{
        int             lk, sz, ky;
        Dtcompar_f      cmpf;
        Dtdisc_t*       disc;
        Dtlink_t        *r, *t;
        void    *key, *k;
 
        UNFLATTEN(dt);
        disc = dt->disc; _DTDSC(disc,ky,sz,lk,cmpf);
 
        if(!obj)
        {       if(type&(DT_LAST|DT_FIRST) )
                {       if((r = dt->data->head) )
                        {       if(type&DT_LAST)
                                        r = r->left;
                                dt->data->here = r;
                        }
                        return r ? _DTOBJ(r,lk) : NULL;
                }
                else if(type&(DT_DELETE|DT_DETACH))
                {       if(!(r = dt->data->head))
                                return NULL;
                        else    goto dt_delete;
                }
                else if(type&DT_CLEAR)
                {       if(disc->freef || disc->link < 0)
                        {       for(r = dt->data->head; r; r = t)
                                {       t = r->right;
                                        if(disc->freef)
                                                disc->freef(_DTOBJ(r, lk));
                                        if(disc->link < 0)
                                                free(r);
                                }
                        }
                        dt->data->head = dt->data->here = NULL;
                        dt->data->size = 0;
                        return NULL;
                }
                else    return NULL;
        }
 
        if(type&DT_INSERT)
        {       if (disc->makef && (type&DT_INSERT) && !(obj = disc->makef(obj, disc)))
                        return NULL;
                if(lk >= 0)
                        r = _DTLNK(obj,lk);
                else
                {       r = malloc(sizeof(Dthold_t));
                        if(r)
                                ((Dthold_t*)r)->obj = obj;
                        else
                        {       if(disc->makef && disc->freef && (type&DT_INSERT))
                                        disc->freef(obj);
                                return NULL;
                        }
                }
 
                /* if(dt->data->type&DT_QUEUE) */
                if((t = dt->data->head) )
                {       t->left->right = r;
                        r->left = t->left;
                        t->left = r;
                }
                else
                {       dt->data->head = r;
                        r->left = r;
                }
                r->right = NULL;
 
                if(dt->data->size >= 0)
                        dt->data->size += 1;
 
                dt->data->here = r;
                return _DTOBJ(r,lk);
        }
 
        if((type&DT_MATCH) || !(r = dt->data->here) || _DTOBJ(r,lk) != obj)
        {       key = (type&DT_MATCH) ? obj : _DTKEY(obj,ky,sz);
                for(r = dt->data->head; r; r = r->right)
                {       k = _DTOBJ(r,lk); k = _DTKEY(k,ky,sz);
                        if(_DTCMP(key, k, cmpf, sz) == 0)
                                break;
                }
        }
 
        if(!r)
                return NULL;
 
        if(type&(DT_DELETE|DT_DETACH))
        { dt_delete:
                if(r->right)
                        r->right->left = r->left;
                if(r == (t = dt->data->head) )
                {       dt->data->head = r->right;
                        if(dt->data->head)
                                dt->data->head->left = t->left;
                }
                else
                {       r->left->right = r->right;
                        if(r == t->left)
                                t->left = r->left;
                }
 
                dt->data->here = r == dt->data->here ? r->right : NULL;
                dt->data->size -= 1;
 
                obj = _DTOBJ(r,lk);
                if(disc->freef && (type&DT_DELETE))
                        disc->freef(obj);
                if(disc->link < 0)
                        free(r);
                return obj;
        }
        else if(type&DT_NEXT)
                r = r->right;
        else if(type&DT_PREV)
                r = r == dt->data->head ? NULL : r->left;
 
        dt->data->here = r;
        return r ? _DTOBJ(r,lk) : NULL;
}
 
Dtmethod_t _Dtqueue = { dtlist, DT_QUEUE };
 
Dtmethod_t* Dtqueue = &_Dtqueue;