source/network/FSM.h

   1 /* Copyright (C) 2024 Wildfire Games.
   2  * This file is part of 0 A.D.
   3  *
   4  * 0 A.D. is free software: you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation, either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * 0 A.D. is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with 0 A.D.  If not, see <http://www.gnu.org/licenses/>.
  16  */
  17
  18 #ifndef FSM_H
  19 #define FSM_H
  20
  21 #include <limits>
  22 #include <unordered_map>
  23
  24
  25 constexpr unsigned int FSM_INVALID_STATE{std::numeric_limits<unsigned int>::max()};
  26
  27 /**
  28  * Represents a signal in the state machine that a change has occurred.
  29  * The CFsmEvent objects are under the control of CFsm so
  30  * they are created and deleted via CFsm.
  31  */
  32 class CFsmEvent
  33 {
  34 public:
  35         CFsmEvent(unsigned int type, void* pParam) :
  36                 m_Type{type},
  37                 m_Param{pParam}
  38         {}
  39
  40         unsigned int GetType() const
  41         {
  42                 return m_Type;
  43         }
  44
  45         void* GetParamRef()
  46         {
  47                 return m_Param;
  48         }
  49
  50 private:
  51         unsigned int m_Type; // Event type
  52         void* m_Param; // Event paramater
  53 };
  54
  55 /**
  56  * Manages states, events, actions and transitions
  57  * between states. It provides an interface for advertising
  58  * events and track the current state. The implementation is
  59  * a Mealy state machine, so the system respond to events
  60  * and execute some action.
  61  *
  62  * A Mealy state machine has behaviour associated with state
  63  * transitions; Mealy machines are event driven where an
  64  * event triggers a state transition.
  65  */
  66 template <typename Context>
  67 class CFsm
  68 {
  69         using Action = bool(Context* pContext, CFsmEvent* pEvent);
  70
  71         struct CallbackFunction
  72         {
  73                 Action* pFunction{nullptr};
  74                 Context* pContext{nullptr};
  75
  76                 bool operator()(CFsmEvent& event) const
  77                 {
  78                         return !pFunction || pFunction(pContext, &event);
  79                 }
  80         };
  81 public:
  82         /**
  83          * Adds a new transistion to the state machine.
  84          */
  85         void AddTransition(unsigned int state, unsigned int eventType, unsigned int nextState,
  86                 Action* pAction = nullptr, Context* pContext = nullptr)
  87         {
  88                 m_Transitions.insert({TransitionKey{state, eventType},
  89                         Transition{{pAction, pContext}, nextState}});
  90         }
  91
  92         /**
  93          * Sets the initial state for FSM.
  94          */
  95         void SetFirstState(unsigned int firstState)
  96         {
  97                 m_FirstState = firstState;
  98         }
  99
 100         /**
 101          * Sets the current state and update the last state to the current state.
 102          */
 103         void SetCurrState(unsigned int state)
 104         {
 105                 m_CurrState = state;
 106         }
 107         unsigned int GetCurrState() const
 108         {
 109                 return m_CurrState;
 110         }
 111
 112         void SetNextState(unsigned int nextState)
 113         {
 114                 m_NextState = nextState;
 115         }
 116
 117         unsigned int GetNextState() const
 118         {
 119                 return m_NextState;
 120         }
 121
 122         /**
 123          * Updates the FSM and retrieves next state.
 124          * @return whether the state was changed.
 125          */
 126         bool Update(unsigned int eventType, void* pEventData)
 127         {
 128                 if (IsFirstTime())
 129                         m_CurrState = m_FirstState;
 130
 131                 // Lookup transition
 132                 auto transitionIterator = m_Transitions.find({m_CurrState, eventType});
 133                 if (transitionIterator == m_Transitions.end())
 134                         return false;
 135
 136                 CFsmEvent event{eventType, pEventData};
 137
 138                 // Save the default state transition (actions might call SetNextState
 139                 // to override this)
 140                 SetNextState(transitionIterator->second.nextState);
 141
 142                 if (!transitionIterator->second.action(event))
 143                         return false;
 144
 145                 SetCurrState(GetNextState());
 146
 147                 // Reset the next state since it's no longer valid
 148                 SetNextState(FSM_INVALID_STATE);
 149
 150                 return true;
 151         }
 152
 153         /**
 154          * Tests whether the state machine has finished its work.
 155          */
 156         bool IsDone() const
 157         {
 158                 return m_Done;
 159         }
 160
 161 private:
 162         struct TransitionKey
 163         {
 164                 using UnderlyingType = unsigned int;
 165                 UnderlyingType state;
 166                 UnderlyingType eventType;
 167
 168                 struct Hash
 169                 {
 170                         size_t operator()(const TransitionKey& key) const noexcept
 171                         {
 172                                 constexpr size_t count{std::numeric_limits<size_t>::digits / 2};
 173                                 const size_t wideState{static_cast<size_t>(key.state)};
 174                                 const size_t rotatedState{(wideState << count) | (wideState >> count)};
 175                                 return static_cast<size_t>(key.eventType) ^ rotatedState;
 176                         }
 177                 };
 178
 179                 friend bool operator==(const TransitionKey& lhs, const TransitionKey& rhs) noexcept
 180                 {
 181                         return lhs.state == rhs.state && lhs.eventType == rhs.eventType;
 182                 }
 183         };
 184
 185         struct Transition
 186         {
 187                 CallbackFunction action;
 188                 unsigned int nextState;
 189         };
 190
 191         using TransitionMap = std::unordered_map<TransitionKey, const Transition,
 192                 typename TransitionKey::Hash>;
 193
 194         /**
 195          * Verifies whether state machine has already been updated.
 196          */
 197         bool IsFirstTime() const
 198         {
 199                 return m_CurrState == FSM_INVALID_STATE;
 200         }
 201
 202         bool m_Done{false};
 203         unsigned int m_FirstState{FSM_INVALID_STATE};
 204         unsigned int m_CurrState{FSM_INVALID_STATE};
 205         unsigned int m_NextState{FSM_INVALID_STATE};
 206         TransitionMap m_Transitions;
 207 };
 208
 209 #endif // FSM_H