import
        tango.core.Memory,
        tango.core.Atomic;
        
extern (C)  void * memcpy (void *dst, void *src, uint);

class FreeList(MSG){
        
        private{
                struct Node{
                        MSG*            msg;
                }
                struct  NodeList{
                        Node*   node;
                        uint    count;
                }
                Atomic!(NodeList*)      ver;
        }
        
        this(){
                ver.store(&NodeList.init);
        }
        
        uint count(){
                NodeList* now   = ver.load();
                return  now.count;
        }
        
        void unshift(in MSG* p){
                NodeList* ol, nl;
                nl      = new NodeList;
                uint    size;
                Node*   n;
                do{
                        ol              = ver.load();
                        nl.count        = ol.count + 1;
                        n               = cast(Node*) GC.malloc( Node.sizeof *  
nl.count );
                        if( ol.count > 0 ){
                                memcpy(cast(void*)n + Node.sizeof , 
cast(void*)ol.node, Node.sizeof *  ol.count );
                        }
                        nl.node = n;
                        n.msg   = p;
                }while( !ver.storeIf(nl, ol) );
        }
                
        void push(in MSG* p){
                NodeList* ol, nl;
                nl      = new NodeList;
                uint    size;
                Node*   n;
                do{
                        ol              = ver.load();
                        nl.count        = ol.count + 1;
                        n               = cast(Node*) GC.malloc( Node.sizeof *  
nl.count );
                        if( ol.count > 0 ){
                                memcpy(cast(void*)n, cast(void*)ol.node, 
Node.sizeof *  ol.count );
                        }
                        nl.node                 = n;
                        (n+ol.count).msg        = p;
                }while( !ver.storeIf(nl, ol) );
        }
        
        bool pop(out MSG* p){
                NodeList* ol, nl;
                nl      = new NodeList;
                uint    size;
                Node*   n;
                do{
                        ol      = ver.load();
                        if( ol.count is 0 ){
                                return false;
                        }
                        nl.count        = ol.count - 1;
                        p               = ( ol.node + nl.count ).msg;
                        if( nl.count > 0 ){
                                n       = cast(Node*) GC.malloc( Node.sizeof *  
nl.count );
                                memcpy(cast(void*)n , cast(void*)ol.node  , 
Node.sizeof *  nl.count );
                                nl.node         = n;
                        }else{
                                nl      = &NodeList.init;
                        }
                }while( !ver.storeIf(nl, ol) );
                return true;
        }
        
        bool shift(out MSG* p){
                NodeList* ol, nl;
                nl      = new NodeList;
                uint    size;
                Node*   n;
                do{
                        ol      = ver.load();
                        if( ol.count is 0 ){
                                return false;
                        }
                        nl.count        = ol.count - 1;
                        p               = ol.node.msg;
                        if( nl.count > 0 ){
                                n       = cast(Node*) GC.malloc( Node.sizeof *  
nl.count );
                                memcpy(cast(void*)n , cast(void*)ol.node + 
Node.sizeof , Node.sizeof *  nl.count );
                                nl.node         = n;
                        }else{
                                nl      = &NodeList.init;
                        }
                }while( !ver.storeIf(nl, ol) );
                return true;
        }
        
}



// -------------------------

import

        tango.util.log.Trace,
        tango.core.Thread,
        tango.time.Clock,
        tango.core.sync.Semaphore;

void main(){
        struct Msg{
                int     i;
                Time    now;
                
        };
        auto li = new FreeList!(Msg);
        
        Msg* p;
        for( int i = 0 ; i < 500 ; i++){
                p       = new Msg;
                p.i     = i;
                p.now   = Clock.now;
                li.unshift(p);
        }
        
        Trace.formatln("msg.count = {} ", li.count).flush;
        
        GC.collect;
        
        while( li.shift(p) ){
                if( p.i % 100 is 0 )
                        Trace.format ("{} {}ms \n", p.i, ( Clock.now - 
p.now).millis );
        }
        
        Trace.formatln("Done").flush;
}



Reply via email to