lock_free_bool_array.hpp

/******************************************************************************
*                                                                             *
*  Copyright 2019 Max Planck Institute for Dynamics and Self-Organization     *
*                                                                             *
*  This file is part of TurTLE.                                               *
*                                                                             *
*  TurTLE is free software: you can redistribute it and/or modify             *
*  it under the terms of the GNU General Public License as published          *
*  by the Free Software Foundation, either version 3 of the License,          *
*  or (at your option) any later version.                                     *
*                                                                             *
*  TurTLE is distributed in the hope that it will be useful,                  *
*  but WITHOUT ANY WARRANTY; without even the implied warranty of             *
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the              *
*  GNU General Public License for more details.                               *
*                                                                             *
*  You should have received a copy of the GNU General Public License          *
*  along with TurTLE.  If not, see <http://www.gnu.org/licenses/>             *
*                                                                             *
* Contact: Cristian.Lalescu@ds.mpg.de                                         *
*                                                                             *
******************************************************************************/



#ifndef LOCK_FREE_BOOL_ARRAY_HPP
#define LOCK_FREE_BOOL_ARRAY_HPP

#include <vector>
#include <atomic>
#include <unistd.h>
#include <cstdio>
#include <omp.h>


class lock_free_bool_array{
    static const int Available = 0;
    static const int Busy = 1;
    static const int NoOwner = -1;

    struct Locker {
        Locker() : lock(Available), ownerId(NoOwner), counter(0) {}
        std::atomic_int lock;
        std::atomic_int ownerId;
        int counter;
    };

    std::vector<std::unique_ptr<Locker>> keys;


public:
    explicit lock_free_bool_array(const long int inNbKeys = 1024){
        keys.resize(inNbKeys);
        for(auto& k : keys){
            k.reset(new Locker());
        }
    }
#ifndef NDEBUG
    ~lock_free_bool_array(){
        for(auto& k : keys){
            assert(k->lock.load() == Available);
            assert(k->ownerId.load() == NoOwner);
        }
    }
#endif
    void lock(const long int inKey){
        Locker* k = keys[inKey%keys.size()].get();
        if(k->ownerId.load() != omp_get_thread_num()){
            int localBusy = Busy;// Intel complains if we pass a const as last param
            int expected = Available;
#ifdef __INTEL_COMPILER
            while(!__sync_val_compare_and_swap((int*)&k->lock, expected, localBusy)){
#else
            while(!std::atomic_compare_exchange_strong(&k->lock, &expected, localBusy)){
#endif
                usleep(1);
                expected = Available;
            }
            assert(k->ownerId.load() == NoOwner);
            k->ownerId.store(omp_get_thread_num());
            k->counter = 0; // must remain
        }
        k->counter += 1;
        assert(k->lock.load() == Busy);
        assert(k->counter >= 1);
        assert(k->ownerId.load() == omp_get_thread_num());
    }

    void unlock(const long int inKey){
        Locker* k = keys[inKey%keys.size()].get();
        assert(k->lock.load() == Busy);
        assert(k->counter >= 1);
        assert(k->ownerId.load() == omp_get_thread_num());
        k->counter -= 1;
        if(k->counter == 0){
            k->ownerId.store(NoOwner);
            k->lock.store(Available);
        }
    }
};

#endif