Is this thread safe?

[Koroskin Denis]

On Sat, 12 Jul 2008 04:52:15 +0400, dsimcha <dsimcha at yahoo.com> wrote:

> Never mind, I see at least one reason why my last post would be  
> incorrect.  The
> length variable could be set out-of-order before all of the factorials  
> up to
> length are calculated.  Is there any simple way to write this function  
> so it's
> thread-safe without using synchronized just to access cached results?

The following approach would be easier, I think:

1) Have an array that reallocates without invalidating old data, so that
all the pointers and iterators remain valid after array resize took place

2) When need to access Nth element do the following:
    a) if size > N, return array[N]
    b) increase the capacity (atomically)
    c) set the array[N] to the calculated value
    d) use compareAndSwap (atomicStoreIf in Tango) to increase array.length
    e) return value

Using my SafeGrowingArray from here -  
http://www.everfall.com/paste/id.php?tmjp3qzeo622
your code could be simplified to the following:

// Important invariant assumption:
// if the size is N, then values 0..N-1 are evaluated and correct.
//
// The steps are taken in the following order:
// 1) increase capacity
// 2) calculate and set the value
// 3) increase size
//
// As a result, if another thread changes the array size to some K then it  
means that it is guarantied that values 0..K-1 are correct

class FactorialTable : SafeGrowingArray!(real,  
ThreadSafetyPolicy.ThreadSafe)
{
     real opIndex(size_t index)
     {
         size_t size = _size;
         if (size > index) {
             return super.opIndex(index);
         }

         reserve(index + 1); // step 1, ensure the capacity

         for (size_t i = size; i <= index; ++i) {
             real value = calcFactorialValue(i);   // step 2 a, calculate  
the value
             this.opIndexAssign(index, value);     // step 2 b, set the  
value. It is safe
                                                   // because capacity is  
large and faction is deterministic
         }

         while (true) {
             if (atomicStoreIf(_size, size, index + 1)) { // step 3, the  
most important one
                 break; // succeeded                      // if succeeded,  
the size is updated
             }

             // failed                                    // if failed ->  
size is changed in another thread
             size = _size;
             if (size > index) {                          // check whether  
the size is large enough
                 break;
             }

             // try again
         }

         return super.opIndex(index);
     }
}

FactorialTable factorialTable;

static this() {
     factorialTable = new FactorialTable();
}

real logFactorial(uint n) {
    return factorialTable[n];
}

Use anything at your will.
NOTE: not tested