Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Fetching contributors…

Octocat-spinner-32-eaf2f5

Cannot retrieve contributors at this time

file 127 lines (100 sloc) 4.112 kb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 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
EXTERN_INLINE 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().
EXTERN_INLINE rtsBool looksEmptyWSDeque (WSDeque* q);

EXTERN_INLINE long dequeElements (WSDeque *q);

/* -----------------------------------------------------------------------------
* PRIVATE below here
* -------------------------------------------------------------------------- */

EXTERN_INLINE 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);
}

EXTERN_INLINE rtsBool
looksEmptyWSDeque (WSDeque *q)
{
    return (dequeElements(q) <= 0);
}

EXTERN_INLINE void
discardElements (WSDeque *q)
{
    q->top = q->bottom;
// pool->topBound = pool->top;
}

#endif // WSDEQUE_H
Something went wrong with that request. Please try again.