RTS tidyup sweep, first phase

The first phase of this tidyup is focussed on the header files, and in
particular making sure we are exposinng publicly exactly what we need
to, and no more.

 - Rts.h now includes everything that the RTS exposes publicly,
   rather than a random subset of it.

 - Most of the public header files have moved into subdirectories, and
   many of them have been renamed.  But clients should not need to
   include any of the other headers directly, just #include the main
   public headers: Rts.h, HsFFI.h, RtsAPI.h.

 - All the headers needed for via-C compilation have moved into the
   stg subdirectory, which is self-contained.  Most of the headers for
   the rest of the RTS APIs have moved into the rts subdirectory.

 - I left MachDeps.h where it is, because it is so widely used in
   Haskell code.
 
 - I left a deprecated stub for RtsFlags.h in place.  The flag
   structures are now exposed by Rts.h.

 - Various internal APIs are no longer exposed by public header files.

 - Various bits of dead code and declarations have been removed

 - More gcc warnings are turned on, and the RTS code is more
   warning-clean.

 - More source files #include "PosixSource.h", and hence only use
   standard POSIX (1003.1c-1995) interfaces.

There is a lot more tidying up still to do, this is just the first
pass.  I also intend to standardise the names for external RTS APIs
(e.g use the rts_ prefix consistently), and declare the internal APIs
as hidden for shared libraries.

1 files changed, 126 insertions, 0 deletions

diff --git a/rts/WSDeque.h b/rts/WSDeque.h
new file mode 100644
index 0000000000..d85567c38a
--- /dev/null
+++ b/rts/WSDeque.h
@@ -0,0 +1,126 @@
+/* -----------------------------------------------------------------------------
+ *
+ * (c) The GHC Team, 2009
+ *
+ * Work-stealing Deque data structure
+ * 
+ * ---------------------------------------------------------------------------*/
+
+#ifndef WSDEQUE_H
+#define WSDEQUE_H
+
+typedef struct WSDeque_ {
+    // Size of elements array. Used for modulo calculation: we round up
+    // to powers of 2 and use the dyadic log (modulo == bitwise &) 
+    StgWord size; 
+    StgWord moduloSize; /* bitmask for modulo */
+
+    // top, index where multiple readers steal() (protected by a cas)
+    volatile StgWord top;
+
+    // bottom, index of next free place where one writer can push
+    // elements. This happens unsynchronised.
+    volatile StgWord bottom;
+
+    // both top and bottom are continuously incremented, and used as
+    // an index modulo the current array size.
+  
+    // lower bound on the current top value. This is an internal
+    // optimisation to avoid unnecessarily accessing the top field
+    // inside pushBottom
+    volatile StgWord topBound;
+
+    // The elements array
+    void ** elements;
+
+    //  Please note: the dataspace cannot follow the admin fields
+    //  immediately, as it should be possible to enlarge it without
+    //  disposing the old one automatically (as realloc would)!
+
+} WSDeque;
+
+/* INVARIANTS, in this order: reasonable size,
+   topBound consistent, space pointer, space accessible to us.
+   
+   NB. This is safe to use only (a) on a spark pool owned by the
+   current thread, or (b) when there's only one thread running, or no
+   stealing going on (e.g. during GC).
+*/
+#define ASSERT_WSDEQUE_INVARIANTS(p)         \
+  ASSERT((p)->size > 0);                        \
+  ASSERT((p)->topBound <= (p)->top);            \
+  ASSERT((p)->elements != NULL);                \
+  ASSERT(*((p)->elements) || 1);                \
+  ASSERT(*((p)->elements - 1  + ((p)->size)) || 1);
+
+// No: it is possible that top > bottom when using pop()
+//  ASSERT((p)->bottom >= (p)->top);           
+//  ASSERT((p)->size > (p)->bottom - (p)->top);
+
+/* -----------------------------------------------------------------------------
+ * Operations
+ *
+ * A WSDeque has an *owner* thread.  The owner can perform any operation;
+ * other threads are only allowed to call stealWSDeque_(),
+ * stealWSDeque(), looksEmptyWSDeque(), and dequeElements().
+ *
+ * -------------------------------------------------------------------------- */
+
+// Allocation, deallocation
+WSDeque * newWSDeque  (nat size);
+void      freeWSDeque (WSDeque *q);
+
+// Take an element from the "write" end of the pool.  Can be called
+// by the pool owner only.
+void* popWSDeque (WSDeque *q);
+
+// Push onto the "write" end of the pool.  Return true if the push
+// succeeded, or false if the deque is full.
+rtsBool pushWSDeque (WSDeque *q, void *elem);
+
+// Removes all elements from the deque
+INLINE_HEADER void discardElements (WSDeque *q);
+
+// Removes an element of the deque from the "read" end, or returns
+// NULL if the pool is empty, or if there was a collision with another
+// thief.
+void * stealWSDeque_ (WSDeque *q);
+
+// Removes an element of the deque from the "read" end, or returns
+// NULL if the pool is empty.
+void * stealWSDeque (WSDeque *q);
+
+// "guesses" whether a deque is empty. Can return false negatives in
+//  presence of concurrent steal() calls, and false positives in
+//  presence of a concurrent pushBottom().
+INLINE_HEADER rtsBool looksEmptyWSDeque (WSDeque* q);
+
+INLINE_HEADER long dequeElements   (WSDeque *q);
+
+/* -----------------------------------------------------------------------------
+ * PRIVATE below here
+ * -------------------------------------------------------------------------- */
+
+INLINE_HEADER long
+dequeElements (WSDeque *q)
+{
+    StgWord t = q->top;
+    StgWord b = q->bottom;
+    // try to prefer false negatives by reading top first
+    return ((long)b - (long)t);
+}
+
+INLINE_HEADER rtsBool
+looksEmptyWSDeque (WSDeque *q)
+{
+    return (dequeElements(q) <= 0);
+}
+
+INLINE_HEADER void
+discardElements (WSDeque *q)
+{
+    q->top = q->bottom;
+//    pool->topBound = pool->top;
+}
+
+#endif // WSDEQUE_H