- fixed typos and 64-bit compatibility

- conform to idle callback functionality in devel_0_38
new lock-free lifo and fifo

svn path=/trunk/; revision=2582

4 files changed, 354 insertions, 103 deletions

diff --git a/externals/grill/flext/flext.vcproj b/externals/grill/flext/flext.vcproj
index 8c043589..b948179c 100644
--- a/externals/grill/flext/flext.vcproj
+++ b/externals/grill/flext/flext.vcproj
@@ -3311,6 +3311,9 @@ copy F:\prog\max\flext\max-msvc\flext.max.dll f:\prog\dll
 				</FileConfiguration>
 			</File>
 			<File
+				RelativePath=".\source\flcontainers.h">
+			</File>
+			<File
 				RelativePath=".\source\flmap.h">
 			</File>
 			<File
diff --git a/externals/grill/flext/source/flcontainers.h b/externals/grill/flext/source/flcontainers.h
new file mode 100644
index 00000000..562bbf64
--- /dev/null
+++ b/externals/grill/flext/source/flcontainers.h
@@ -0,0 +1,315 @@
+/* 

+

+flext - C++ layer for Max/MSP and pd (pure data) externals

+

+Copyright (c) 2001-2005 Thomas Grill (gr@grrrr.org)

+For information on usage and redistribution, and for a DISCLAIMER OF ALL

+WARRANTIES, see the file, "license.txt," in this distribution.  

+

+*/

+

+/*! \file flcontainers.h

+	\brief Lock-free container classes

+   

+	This code has been adapted from the MidiShare project (c)Grame

+*/

+

+#ifndef __FLCONTAINERS_H

+#define __FLCONTAINERS_H

+

+

+#include "flprefix.h"

+

+

+class Cell 

+{

+	friend class Lifo;

+	friend class Fifo;

+private:

+	Cell *link;

+};

+

+

+#if 1 //def __Pentium__

+#define VTYPE volatile

+#else

+#define VTYPE

+#endif

+

+#define __SMP__

+

+

+class FLEXT_SHARE Lifo 

+{

+public:

+    inline Lifo() { Init(); }

+

+    inline void Init() { ic = oc = 0; top = NULL; }

+

+    inline Cell *Avail() { return (Cell *)top; }

+

+#if defined(_WIN32) && defined(_MSC_VER)

+    #ifdef __SMP__

+    #define LOCK lock

+    #else

+    #define LOCK

+    #endif

+

+    inline void Push(Cell *cell) 

+    {

+	    __asm 

+	    {

+		    push	eax

+		    push	ebx

+		    push	ecx

+		    push	edx

+		    push	esi

+		    mov		esi, this

+		    mov		eax, dword ptr [esi]

+		    mov		ecx, cell

+		    mov		edx, dword ptr [esi+4]

+	    _loop:

+		    mov		ebx, eax

+		    inc		ebx

+		    mov		[ecx], edx

+		    LOCK cmpxchg8b qword ptr [esi]

+		    jnz		_loop

+		    pop		esi

+		    pop		edx

+		    pop		ecx

+		    pop		ebx

+		    pop		eax

+	    }

+    }

+

+    inline Cell *Pop() 

+    {

+	    __asm 

+	    {

+		    push	ebx

+		    push	ecx

+		    push	edx

+		    push	esi

+		    mov		esi, this

+		    add		esi, 4 /* point to top */

+		    mov 	edx, dword ptr [esi+4]

+		    mov  	eax, dword ptr [esi]	

+		    test	eax, eax

+		    jz		_end

+	    _loop:

+		    mov		ebx, dword ptr [eax]

+		    mov		ecx, edx

+		    inc		ecx

+		    LOCK cmpxchg8b qword ptr [esi]

+		    jz		_end

+		    test	eax, eax

+		    jnz		_loop

+	    _end:

+		    pop		esi

+		    pop		edx

+		    pop		ecx

+		    pop		ebx

+	    }

+    }

+

+    inline size_t Size() const { return ic-oc; }

+#elif defined(__GNUC__) && defined(__)

+    #ifndef SMPLOCK

+    # ifdef __SMP__

+    #  define SMPLOCK "lock ; "

+    # else

+    #  define SMPLOCK ""

+    # endif

+    #endif

+

+    inline void Push(Cell *cl) 

+    {

+	    __asm__ __volatile__ (

+		    "# LFPUSH					\n\t"

+		    "pushl	%%ebx				\n\t"

+		    "pushl	%%ecx				\n\t"

+		    "movl 0(%%esi), %%eax		\n\t"

+		    "movl 4(%%esi), %%edx		\n"	

+		    "1:                         \t"

+		    "movl %%eax, %%ebx			\n\t"

+		    "incl %%ebx					\n\t"

+		    "movl %%edx, (%%ecx)		\n\t"

+		    SMPLOCK "cmpxchg8b (%%esi)	\n\t"

+		    "jnz	1b					\n\t"

+		    "popl	%%ecx				\n\t"

+		    "popl	%%ebx				\n\t"

+		    :/* no output */

+		    :"S" (this), "c" (cl)

+		    :"memory", "eax", "edx");

+    }

+

+    inline Cell *Pop() 

+    {

+	    cell*	v=0;

+	    __asm__ __volatile__ (

+		    "# LFPOP 					\n\t"

+		    "pushl	%%ebx				\n\t"

+		    "pushl	%%ecx				\n\t"

+		    "movl 	4(%%esi), %%edx		\n\t"

+		    "movl  	(%%esi), %%eax		\n\t"	

+		    "testl	%%eax, %%eax		\n\t"

+		    "jz		20f					\n"

+		    "10:                        \t"

+		    "movl 	(%%eax), %%ebx		\n\t"

+		    "movl	%%edx, %%ecx		\n\t"

+		    "incl	%%ecx				\n\t"

+		    SMPLOCK "cmpxchg8b (%%esi)	\n\t"

+		    "jz		20f					\n\t"

+		    "testl	%%eax, %%eax		\n\t"

+		    "jnz	10b					\n"

+		    "20:                        \t"

+		    "popl	%%ecx				\n\t"

+		    "popl	%%ebx				\n\t"

+		    :"=a" (v)

+		    :"S" (&this->top)

+		    :"memory", "edx");

+	    return v;

+    }

+

+    inline size_t Size() 

+    {

+	    size_t n;

+	    __asm__ __volatile__ (

+		    "# LFSIZE					\n\t"

+		    "movl 	8(%%esi), %%edx		\n\t"

+		    "movl  	(%%esi), %%eax		\n\t"	

+		    "subl 	%%edx, %%eax		\n\t"

+		    :"=a" (n)

+		    :"S" (this)

+		    :"memory", "edx");

+	    return n;

+    }

+#elif defined(__GNUC__) && defined(__POWERPC__)

+    inline void Push(register Cell *cl) 

+    {

+        register volatile long t1;

+        register long t2=0;

+        asm volatile (

+	        "# LFPUSH \n"

+	        "0: 				      \n"

+	        "   lwarx   %0, %3, %1  \n"		

+	        "   stw	  %0, 0(%2)   \n"	

+	        "   sync  			  \n"	

+	        "   stwcx.  %2, %3, %1  \n"						   

+	        "   bne-    0b	      \n"  

+	        "0:				      \n"

+	        "   lwarx   %0, %3, %4  \n"		

+	        "   addi    %0, %0, 1	  \n"  

+	        "   sync  			  \n"  

+	        "   stwcx.  %0, %3, %4  \n"

+	        "   bne-    0b		  \n"

+	        : "=r" (t1)

+	        : "r" (&this->top), "r" (cl), "r" (t2), "r" (&this->oc), "0" (t1)

+	        : "r0" 		/* prevents using r0 because of the ambiguity of 'addi' coding: */

+	  				        /* gcc version 2.95.3 20010315 (release - Linux-Mandrake 8.0 for PPC) */

+					        /* compiles the instruction "addi 0, 0, n" as li 0, n */

+        );

+    }

+

+    inline Cell *Pop() 

+    {

+	    register Cell *result;

+	    register volatile long a, b;

+	    register long c=0;

+	    asm volatile (

+        "# LFPOP					\n"

+            "0:						\n"

+		    "	lwarx	%4, %1, %2	\n"         /* creates a reservation on lf    */

+		    "	cmpwi	%4, 0		\n"         /* test if the lifo is empty      */

+		    "	beq-	1f		\n"

+		    "	lwz		%5, 0(%4)	\n"         /* next cell in b                */

+            "	sync            	\n"         /* synchronize instructions       */

+		    "	stwcx.	%5, %1, %2	\n"         /* if the reservation is not altered */

+                                                /* modify lifo top                */

+		    "	bne-	0b  		\n"         /* otherwise: loop and try again  */

+            "0:						\n"

+		    "	lwarx	%5, %1, %3	\n"         /* creates a reservation on lf->count */

+            "	addi	%5, %5, -1	\n"         /* dec count                      */

+		    "	sync            	\n"         /* synchronize instructions       */

+		    "	stwcx.	%5, %1, %3	\n"         /* conditionnal store             */

+		    "	bne-	0b			\n"

+            "1:						\n"

+		    "	mr		%0, %4		\n"

+        :"=r" (result), "=r" (c)

+	    : "r" (&this->top), "r" (&this->oc), "r" (a), "r" (b), "1" (c)

+	    : "r0" 		/* prevents using r0 because of the ambiguity of 'addi' coding: */

+	  				    /* gcc version 2.95.3 20010315 (release - Linux-Mandrake 8.0 for PPC) */

+					    /* compiles the instruction "addi 0, 0, n" as li 0, n */

+	    );

+	    return result;

+    }

+

+    inline size_t Size() const { return oc; }

+#endif

+

+private:

+    // don't change order!

+    VTYPE size_t ic;		// input (push) count

+	VTYPE Cell *top;	    // top of the stack

+	VTYPE size_t oc;		// output (pop) count

+#ifdef __POWERPC__

+	size_t unused[5];		// lifo size must be at least 32 bytes

+							// to avoid livelock in multiprocessor

+#endif

+};

+

+

+class FLEXT_SHARE Fifo 

+{

+public:

+    void Init() { in.Init(); out.Init(); }

+

+    inline size_t Size() const { return in.Size()+out.Size(); }

+

+    inline void Put(Cell *cl) { in.Push(cl); }

+

+    Cell *Get() 

+    {

+        Cell *v1 = out.Pop();

+        if(!v1) {

+            v1 = in.Pop();

+            if(v1)

+                for(Cell *v2; (v2 = in.Pop()) != NULL; v1 = v2) 

+                    out.Push(v1);

+        }

+        return v1;

+    }

+

+    Cell *Avail()

+    {

+        Cell *v1 = out.Avail();

+        if(v1)

+            return v1;

+        else {

+            for(Cell *v2; (v2 = in.Pop()) != NULL; ) 

+                out.Push(v2);

+            return out.Avail();

+        }

+    }

+

+    Cell *Clear()

+    {

+        Cell *first = Get();

+        if(!first) return NULL;

+

+        Cell *next,*cur = first;

+        while((next = Get()) != NULL) {

+            cur->link = next;

+            cur = next;

+        }

+        cur->link = NULL;

+

+        Init();

+        return first;

+    }

+

+	Lifo in,out;

+};

+

+

+#endif

diff --git a/externals/grill/flext/source/flqueue.cpp b/externals/grill/flext/source/flqueue.cpp
index f629379b..62a8b35a 100755
--- a/externals/grill/flext/source/flqueue.cpp
+++ b/externals/grill/flext/source/flqueue.cpp
@@ -18,6 +18,7 @@ WARRANTIES, see the file, "license.txt," in this distribution.
 
 #include "flext.h"
 #include "flinternal.h"
+#include "flcontainers.h"
 #include <string.h> // for memcpy
 
 #ifdef FLEXT_THREADS
@@ -25,84 +26,64 @@ WARRANTIES, see the file, "license.txt," in this distribution.
 flext::thrid_t flext::thrmsgid = 0;
 #endif
 
-#define QUEUE_LENGTH 2048
-#define QUEUE_ATOMS 8192
 
-class qmsg
+class qmsg:
+    public flext,
+    public Cell
 {
 public:
-    void Set(flext_base *t,int o,const t_symbol *s,int ac,const t_atom *av) 
-    { 
-        th = t; out = o;
-        sym = s,argc = ac,argv = av; 
-    }
+    qmsg(flext_base *t,int o,const t_symbol *s,int ac,const t_atom *av)
+        : msg(s,ac,av)
+        , th(t),out(o)
+    {}
 
     // \note PD sys lock must already be held by caller
     void Send() const
     {
         if(out < 0)
             // message to self
-            th->m_methodmain(-1-out,sym,argc,argv); 
+            th->m_methodmain(-1-out,msg.Header(),msg.Count(),msg.Atoms()); 
         else
             // message to outlet
-            th->ToSysAnything(out,sym,argc,argv);
+            th->ToSysAnything(out,msg.Header(),msg.Count(),msg.Atoms());
     }
 
-    int Args() const { return argc; }
-
 private:
     flext_base *th;
     int out;
-    const t_symbol *sym; 
-    int argc; 
-    const t_atom *argv;
+    AtomAnything msg;
 };
 
 /* \TODO This is only thread-safe if called from one thread which need NOT be the case.
          Reimplement in a thread-safe manner!!!
 */
 class Queue:
-    public flext
+    public flext,
+    public Fifo
 {
 public:
-    Queue()
-    {
-        qhead = qtail = 0;
-        ahead = atail = 0;
-    }
-
-    bool Empty() const { return qhead == qtail; }
-
-    int Count() const 
-    { 
-        int c = qtail-qhead;
-        return c >= 0?c:c+QUEUE_LENGTH; 
-    }
+    inline bool Empty() const { return Size() == 0; }
 
-    const qmsg &Head() { return lst[qhead]; }
+    inline void Push(qmsg *q) { Fifo::Put(q); }
 
-    void Pop() 
-    { 
-        PopAtoms(Head().Args());
-        qhead = (qhead+1)%QUEUE_LENGTH;
-    }
+    inline qmsg *Pop() { return static_cast<qmsg *>(Fifo::Get()); }
 
     void Push(flext_base *th,int o) // bang
     { 
-        Set(th,o,sym_bang,0,NULL); 
+        Put(new qmsg(th,o,sym_bang,0,NULL));
     }
 
     void Push(flext_base *th,int o,float dt) 
     { 
-        t_atom *at = GetAtoms(1); 
-        SetFloat(*at,dt);
-        Set(th,o,sym_float,1,at); 
+        t_atom at; 
+        SetFloat(at,dt);
+        Put(new qmsg(th,o,sym_float,1,&at));
     }
 
     void Push(flext_base *th,int o,int dt) 
     { 
-        t_atom *at = GetAtoms(1); 
-        SetInt(*at,dt);
+        t_atom at; 
+        SetInt(at,dt);
         const t_symbol *sym;
 #if FLEXT_SYS == FLEXT_SYS_PD
         sym = sym_float;
@@ -111,20 +92,18 @@ public:
 #else
 #error Not implemented!
 #endif
-        Set(th,o,sym,1,at); 
+        Put(new qmsg(th,o,sym,1,&at));
     }
 
     void Push(flext_base *th,int o,const t_symbol *dt) 
     { 
-        t_atom *at = GetAtoms(1); 
-        SetSymbol(*at,dt);
-        Set(th,o,sym_symbol,1,at); 
+        t_atom at; 
+        SetSymbol(at,dt);
+        Put(new qmsg(th,o,sym_symbol,1,&at));
     }
 
     void Push(flext_base *th,int o,const t_atom &a) 
     { 
-        t_atom *at = GetAtoms(1); 
-        *at = a;
         const t_symbol *sym;
         if(IsSymbol(a))
             sym = sym_symbol;
@@ -142,64 +121,18 @@ public:
             error("atom type not supported");
             return;
         }
-        Set(th,o,sym,1,at); 
+        Put(new qmsg(th,o,sym,1,&a));
     }
 
     void Push(flext_base *th,int o,int argc,const t_atom *argv) 
     {
-        t_atom *at = GetAtoms(argc);
-        memcpy(at,argv,argc*sizeof(t_atom));
-        Set(th,o,sym_list,argc,at); 
+        Put(new qmsg(th,o,sym_list,argc,argv));
     }
 
     void Push(flext_base *th,int o,const t_symbol *sym,int argc,const t_atom *argv) 
     { 
-        t_atom *at = GetAtoms(argc);
-        memcpy(at,argv,argc*sizeof(t_atom));
-        Set(th,o,sym,argc,at); 
-    }
-
-protected:
-    void Set(flext_base *th,int o,const t_symbol *sym,int argc,const t_atom *argv)
-    {
-        FLEXT_ASSERT(Count() < QUEUE_LENGTH-1);
-        lst[qtail].Set(th,o,sym,argc,argv);
-        qtail = (qtail+1)%QUEUE_LENGTH;
-    }
-
-    int CntAtoms() const 
-    { 
-        int c = atail-ahead;
-        return c >= 0?c:c+QUEUE_ATOMS;
-    }
-
-    // must return contiguous region
-    t_atom *GetAtoms(int argc)
-    {
-        t_atom *ret;
-        if(atail+argc >= QUEUE_ATOMS) {
-            FLEXT_ASSERT(ahead > argc);
-            ret = atoms;
-            atail = argc;
-        }
-        else {
-            FLEXT_ASSERT(ahead <= atail || ahead > atail+argc);
-            ret = atoms+atail;
-            atail += argc;
-        }
-        return ret;
+        Put(new qmsg(th,o,sym,argc,argv)); 
     }
-
-    void PopAtoms(int argc) 
-    {
-        const int p = ahead+argc;
-        ahead = p >= QUEUE_ATOMS?argc:p;
-    }
-
-    volatile int qhead,qtail;
-    qmsg lst[QUEUE_LENGTH];
-    volatile int ahead,atail;
-    t_atom atoms[QUEUE_ATOMS];
 };
 
 static Queue queue;
@@ -222,18 +155,18 @@ static void QWork(bool syslock)
         // qc will be a minimum guaranteed number of present queue elements.
         // On the other hand, if new queue elements are added by the methods called
         // in the loop, these will be sent in the next tick to avoid recursion overflow.
-        int qc = queue.Count();
+        size_t qc = queue.Size();
         if(!qc) break;
 
     #if FLEXT_QMODE == 2
         if(syslock) flext::Lock();
     #endif
 
-        // once more, because flushing in destructors could have reduced the count
-        for(qc = queue.Count(); qc--; ) {
-            queue.Head().Send();
-            queue.Pop();
-        } // inner loop
+        qmsg *q;
+        while((q = queue.Pop()) != NULL) {
+            q->Send();
+            delete q;
+        }
 
     #if FLEXT_QMODE == 2
         if(syslock) flext::Unlock();
diff --git a/externals/grill/flext/source/flsupport.h b/externals/grill/flext/source/flsupport.h
index 9377b021..123f956a 100644
--- a/externals/grill/flext/source/flsupport.h
+++ b/externals/grill/flext/source/flsupport.h
@@ -138,7 +138,7 @@ public:
     static int Version();    
 
     //! Flext version string
-    static const char *VersionStr();    
+    static const char *VersionStr();
 
 // --- buffer/array stuff -----------------------------------------