lock_free_bool_array.hpp 3.83 KB
Newer Older
1
2
3
4
/******************************************************************************
*                                                                             *
*  Copyright 2019 Max Planck Institute for Dynamics and Self-Organization     *
*                                                                             *
Cristian Lalescu's avatar
Cristian Lalescu committed
5
*  This file is part of TurTLE.                                               *
6
*                                                                             *
Cristian Lalescu's avatar
Cristian Lalescu committed
7
*  TurTLE is free software: you can redistribute it and/or modify             *
8
9
10
11
*  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.                                     *
*                                                                             *
Cristian Lalescu's avatar
Cristian Lalescu committed
12
*  TurTLE is distributed in the hope that it will be useful,                  *
13
14
15
16
17
*  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          *
Cristian Lalescu's avatar
Cristian Lalescu committed
18
*  along with TurTLE.  If not, see <http://www.gnu.org/licenses/>             *
19
20
21
22
23
24
25
*                                                                             *
* Contact: Cristian.Lalescu@ds.mpg.de                                         *
*                                                                             *
******************************************************************************/



26
27
28
29
#ifndef LOCK_FREE_BOOL_ARRAY_HPP
#define LOCK_FREE_BOOL_ARRAY_HPP

#include <vector>
30
31
32
33
34
#include <atomic>
#include <unistd.h>
#include <cstdio>
#include <omp.h>

35
36

class lock_free_bool_array{
37
38
39
40
41
42
43
44
45
46
47
48
49
    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;

50
51

public:
52
    explicit lock_free_bool_array(const long int inNbKeys = 1024){
53
        keys.resize(inNbKeys);
54
55
        for(auto& k : keys){
            k.reset(new Locker());
56
57
        }
    }
58
59
60
61
62
63
64
65
#ifndef NDEBUG
    ~lock_free_bool_array(){
        for(auto& k : keys){
            assert(k->lock.load() == Available);
            assert(k->ownerId.load() == NoOwner);
        }
    }
#endif
66
    void lock(const long int inKey){
67
68
        Locker* k = keys[inKey%keys.size()].get();
        if(k->ownerId.load() != omp_get_thread_num()){
69
            int localBusy = Busy;// Intel complains if we pass a const as last param
70
            int expected = Available;
71
#ifdef __INTEL_COMPILER
72
            while(!__sync_val_compare_and_swap((int*)&k->lock, expected, localBusy)){
73
#else
74
            while(!std::atomic_compare_exchange_strong(&k->lock, &expected, localBusy)){
75
#endif
76
                usleep(1);
77
                expected = Available;
78
            }
79
            assert(k->ownerId.load() == NoOwner);
80
81
            k->ownerId.store(omp_get_thread_num());
            k->counter = 0; // must remain
82
        }
83
84
85
86
        k->counter += 1;
        assert(k->lock.load() == Busy);
        assert(k->counter >= 1);
        assert(k->ownerId.load() == omp_get_thread_num());
87
88
    }

89
    void unlock(const long int inKey){
90
91
92
93
94
95
96
97
98
        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);
        }
99
100
101
102
    }
};

#endif