source: doc/theses/colby_parsons_MMAth/code/swap_queues.cfa @ efdd18c

// this is a code stub and will not compile

// tries to atomically swap two queues and returns 0p if the swap failed
// returns ptr to newly owned queue if swap succeeds
static inline work_queue * try_swap_queues( worker & this, unsigned int victim_idx, unsigned int my_idx ) with(this) {
    work_queue * my_queue = request_queues[my_idx];
    work_queue * other_queue = request_queues[victim_idx];

    // if either queue is 0p then they are in the process of being stolen
    if ( other_queue == 0p || my_queue == 0p ) return 0p;

    // try to set our queue ptr to be 0p. If it fails someone moved our queue so return false
    if ( !__atomic_compare_exchange_n( &request_queues[my_idx], &my_queue, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) )
        return 0p;

    // try to set other queue ptr to be our queue ptr. If it fails someone moved the other queue so fix up then return false
    if ( !__atomic_compare_exchange_n( &request_queues[victim_idx], &other_queue, my_queue, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ) {
        /* paranoid */ verify( request_queues[my_idx] == 0p );
        request_queues[my_idx] = my_queue; // reset my queue ptr back to appropriate val
        return 0p;
    }

    // we have successfully swapped and since our queue is 0p no one will touch it so write back new queue ptr non atomically
    request_queues[my_idx] = other_queue; // last write does not need to be atomic
    return other_queue;
}

// This routine is atomic
bool CAS( work_queue ** ptr, work_queue ** old, work_queue * new ) {
    if ( *ptr != *old )
        return false;
    *ptr = new;
    return true;
}

bool try_swap_queues( worker & this, uint victim_idx, uint my_idx ) with(this) {
    work_queue * my_queue = request_queues[my_idx];
    work_queue * vic_queue = request_queues[victim_idx];

    // If either queue is 0p then they are in the process of being stolen
    // 0p is CForAll's equivalent of C++'s nullptr
    if ( vic_queue == 0p || my_queue == 0p ) return false;

    // Try to set our queue ptr to be 0p.
    // If this CAS fails someone moved our queue so return false
    if ( !CAS( &request_queues[my_idx], &my_queue, 0p ) )
        return false;

    // Try to set other queue ptr to be our queue ptr.
    // If it fails someone moved the other queue, so fix up then return false
    if ( !CAS( &request_queues[victim_idx], &vic_queue, my_queue ) ) {
        request_queues[my_idx] = my_queue; // reset queue ptr back to prev val
        return false;
    }

    // Successfully swapped.
    // Our queue is 0p so no one will touch it so write back without CAS is safe
    request_queues[my_idx] = vic_queue;
    return true;
}