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

// sequential equivalent swap
void swap( uint victim_idx, uint my_idx  ) {
    // Step 0:
    work_queue * my_queue = request_queues[my_idx];
    work_queue * vic_queue = request_queues[victim_idx];
    // Step 2:
    request_queues[my_idx] = 0p;
    // Step 3:
    request_queues[victim_idx] = my_queue;
    // Step 4:
    request_queues[my_idx] = vic_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) {
    // Step 0:
    // request_queues is the shared array of all sharded queues
    work_queue * my_queue = request_queues[my_idx];
    work_queue * vic_queue = request_queues[victim_idx];

    // Step 1:
    // 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 ) return false;

    // Step 2:
    // Try to set thief's queue ptr to be 0p.
    // If this CAS fails someone stole thief's queue so return false
    if ( !CAS( &request_queues[my_idx], &my_queue, 0p ) )
        return false;
    
    // Step 3:
    // Try to set victim queue ptr to be thief's queue ptr.
    // If it fails someone stole 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;
    }

    // Step 4:
    // Successfully swapped.
    // Thief's ptr is 0p so no one will touch it
    // Write back without CAS is safe
    request_queues[my_idx] = vic_queue;
    return true;
}