SingleStateQueue.h revision 9b82924cbd203f1678c2f78aa73b15909efa3e81 
1/*
2 * Copyright (C) 2012 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#ifndef SINGLE_STATE_QUEUE_H
18#define SINGLE_STATE_QUEUE_H
19
20// Non-blocking single element state queue, or
21// Non-blocking single-reader / single-writer multi-word atomic load / store
22
23#include <stdint.h>
24#include <cutils/atomic.h>
25
26namespace android {
27
28template<typename T> class SingleStateQueue {
29
30public:
31
32    class Mutator;
33    class Observer;
34
35    struct Shared {
36        // needs to be part of a union so don't define constructor or destructor
37
38        friend class Mutator;
39        friend class Observer;
40
41private:
42        void                init() { mAck = 0; mSequence = 0; }
43
44        volatile int32_t    mAck;
45        volatile int32_t    mSequence;
46        T                   mValue;
47    };
48
49    class Mutator {
50    public:
51        Mutator(Shared *shared)
52            : mSequence(0), mShared(shared)
53        {
54            // exactly one of Mutator and Observer must initialize, currently it is Observer
55            // shared->init();
56        }
57
58        // push new value onto state queue, overwriting previous value;
59        // returns a sequence number which can be used with ack()
60        int32_t push(const T& value)
61        {
62            Shared *shared = mShared;
63            int32_t sequence = mSequence;
64            sequence++;
65            android_atomic_acquire_store(sequence, &shared->mSequence);
66            shared->mValue = value;
67            sequence++;
68            android_atomic_release_store(sequence, &shared->mSequence);
69            mSequence = sequence;
70            // consider signalling a futex here, if we know that observer is waiting
71            return sequence;
72        }
73
74        // return true if most recent push has been observed
75        bool ack() const
76        {
77            return mShared->mAck - mSequence == 0;
78        }
79
80        // return true if a push with specified sequence number or later has been observed
81        bool ack(int32_t sequence) const
82        {
83            // this relies on 2's complement rollover to detect an ancient sequence number
84            return mShared->mAck - sequence >= 0;
85        }
86
87    private:
88        int32_t     mSequence;
89        Shared * const mShared;
90    };
91
92    class Observer {
93    public:
94        Observer(Shared *shared)
95            : mSequence(0), mSeed(1), mShared(shared)
96        {
97            // exactly one of Mutator and Observer must initialize, currently it is Observer
98            shared->init();
99        }
100
101        // return true if value has changed
102        bool poll(T& value)
103        {
104            Shared *shared = mShared;
105            int32_t before = shared->mSequence;
106            if (before == mSequence) {
107                return false;
108            }
109            for (int tries = 0; ; ) {
110                const int MAX_TRIES = 5;
111                if (before & 1) {
112                    if (++tries >= MAX_TRIES) {
113                        return false;
114                    }
115                    before = shared->mSequence;
116                } else {
117                    android_memory_barrier();
118                    T temp = shared->mValue;
119                    int32_t after = android_atomic_release_load(&shared->mSequence);
120                    if (after == before) {
121                        value = temp;
122                        shared->mAck = before;
123                        mSequence = before;
124                        return true;
125                    }
126                    if (++tries >= MAX_TRIES) {
127                        return false;
128                    }
129                    before = after;
130                }
131            }
132        }
133
134    private:
135        int32_t     mSequence;
136        int         mSeed;  // for PRNG
137        Shared * const mShared;
138    };
139
140#if 0
141    SingleStateQueue(void /*Shared*/ *shared);
142    /*virtual*/ ~SingleStateQueue() { }
143
144    static size_t size() { return sizeof(Shared); }
145#endif
146
147};
148
149}   // namespace android
150
151#endif  // SINGLE_STATE_QUEUE_H
152