feisty meow concerns codebase  2.140
state_machine.cpp
Go to the documentation of this file.
1 /*****************************************************************************\
2 * *
3 * Name : state_machine *
4 * Author : Chris Koeritz *
5 * *
6 *******************************************************************************
7 * Copyright (c) 1992-$now By Author. This program is free software; you can *
8 * redistribute it and/or modify it under the terms of the GNU General Public *
9 * License as published by the Free Software Foundation; either version 2 of *
10 * the License or (at your option) any later version. This is online at: *
11 * http://www.fsf.org/copyleft/gpl.html *
12 * Please send any updates to: fred@gruntose.com *
13 \*****************************************************************************/
14 
15 #include "state_machine.h"
16 
17 #include <basis/array.h>
18 #include <basis/functions.h>
19 #include <basis/guards.h>
20 #include <basis/astring.h>
22 #include <timely/time_stamp.h>
23 
24 using namespace basis;
25 using namespace loggers;
26 using namespace timely;
27 
28 namespace processes {
29 
31 
32 //#define DEBUG_STATE_MACHINE
33  // uncomment if you want the debugging version.
34 
35 //hmmm: implement logging...
36 #undef LOG
37 #ifndef DEBUG_STATE_MACHINE
38  #define LOG(to_print) CLASS_EMERGENCY_LOG(program_wide_logger::get(), to_print)
39 #else
40  #define LOG(to_print) {}
41 #endif
42 
44 
45 // checks whether the machine passed in is valid or not.
46 #define CHECK_VALID(m) \
47  if (!m._current) return false; \
48  if (!m._last) return false
49 
50 // checks whether the current and next states exist or not.
51 #define CHECK_STATES \
52  if (!current) return false; \
53  if (!next) return false; \
54  int indy = state_index(current); \
55  if (negative(indy)) return false; \
56  if (negative(state_index(next))) return false
57 
58 // moves to a new state and resets the new state's timestamp.
59 #define MOVE_STATE(m, next, type, trigger) \
60  m._last = m._current; \
61  m._current = next; \
62  m._type = type; \
63  m._trig = trigger; \
64  m._start->reset()
65 
66 // locates a state or returns.
67 #define FIND_STATE(state) \
68  int indy = state_index(state); \
69  if (negative(indy)) return
70 
72 
73 struct override { int current; int next; int duration;
74  override(int _current = 0, int _next = 0, int _duration = 0)
75  : current(_current), next(_next), duration(_duration) {}
76 };
77 
78  struct transition_info
79  {
80  enum transition_type
81  {
82  SIMPLE, RANGE, TIMED
83  };
84  transition_type type;
85  int next_state;
86  int low_trigger, high_trigger;
87  int time_span;
88 
89  // blank constructor.
90  transition_info()
91  : type(RANGE), next_state(0), low_trigger(0), high_trigger(0), time_span(0)
92  {
93  }
94 
95  transition_info(int next)
96  : type(SIMPLE), next_state(next),
97  low_trigger(0), high_trigger(0), time_span(0)
98  {
99  }
100 
101  transition_info(int next, int time)
102  : type(TIMED), next_state(next), time_span(time), low_trigger(0), high_trigger(0)
103  {
104  }
105 
106  transition_info(int next, int low, int high)
107  : type(RANGE), next_state(next), low_trigger(low), high_trigger(high), time_span(0)
108  {
109  }
110  };
111 
112 struct state_info {
113  int state_id; // id for this state.
114  array<transition_info> transitions;
115 
116  state_info() : state_id(0) {} // blank.
117  state_info(int state_id_in) : state_id(state_id_in) {}
118 };
119 
121 
122 class state_machine_override_array : public array<override> {};
123 class state_machine_state_array : public array<state_info> {};
124 
126 
127 state_machine::state_machine()
128 : _current(0),
129  _last(0),
130  _trig(0),
131  _type(SIMPLE),
132  _start(new time_stamp()),
133  _name(new astring()),
134  _overrides(new state_machine_override_array)
135 {}
136 
138 : root_object(),
139  _current(0),
140  _last(0),
141  _trig(0),
142  _type(SIMPLE),
143  _start(new time_stamp()),
144  _name(new astring()),
145  _overrides(new state_machine_override_array)
146 { *this = to_copy; }
147 
149 {
150  WHACK(_start);
151  WHACK(_name);
152  WHACK(_overrides);
153 }
154 
155 int state_machine::update() { return 0; }
156 
157 void state_machine::set_name(const astring &name) { *_name = name; }
158 
159 astring state_machine::get_name() const { return *_name; }
160 
162 {
163  if (&to_copy == this) return *this;
164  _current = to_copy._current;
165  _last = to_copy._last;
166  _trig = to_copy._trig;
167  _type = to_copy._type;
168  *_start = *to_copy._start;
169  *_name = *to_copy._name;
170  *_overrides = *to_copy._overrides;
171 //careful when overrides becomes hidden internal type.
172  return *this;
173 }
174 
175 int state_machine::duration_index(int current, int next) const
176 {
177  for (int i = 0; i < _overrides->length(); i++)
178  if ( ((*_overrides)[i].current == current)
179  && ((*_overrides)[i].next == next) )
180  return i;
181  return common::NOT_FOUND;
182 }
183 
184 void state_machine::set_state(int new_current, int new_last, int trigger,
185  transition_types type)
186 {
187  _current = new_current;
188  _last = new_last;
189  _trig = trigger;
190  _type = type;
191  _start->reset();
192 }
193 
194 void state_machine::override_timing(int current, int next, int duration)
195 {
196  int indy = duration_index(current, next);
197  if (non_negative(indy)) {
198  // found an existing record for this current/next pair.
199  if (!duration) {
200  // zero duration means removal.
201  _overrides->zap(indy, indy);
202  return;
203  }
204  // reset the duration.
205  (*_overrides)[indy].duration = duration;
206  return;
207  }
208  // no existing record, so add one.
209  *_overrides += override(current, next, duration);
210 }
211 
212 int state_machine::duration_override(int current, int next) const
213 {
214  int indy = duration_index(current, next);
215  if (negative(indy)) return 0;
216  return (*_overrides)[indy].duration;
217 }
218 
219 time_stamp state_machine::start() const { return *_start; }
220 
222 
224 : _valid(false),
225  _start_state(0),
226  _state_list(new state_machine_state_array)
227 {}
228 
230 {
231  _valid = false;
232  WHACK(_state_list);
233 }
234 
235 // informational functions:
236 
237 int transition_map::states() const { return _state_list->length(); }
238 
239 int transition_map::state_index(int state_id) const
240 {
241  for (int i = 0; i < states(); i++)
242  if ((*_state_list)[i].state_id == state_id) return i;
243  return common::NOT_FOUND;
244 }
245 
246 int transition_map::transition_index(int state_index, int next, int &start)
247 {
248  bounds_return(state_index, 0, states() - 1, common::BAD_INPUT);
249  state_info &state = (*_state_list)[state_index];
250  bounds_return(start, 0, state.transitions.length() - 1, common::BAD_INPUT);
251  // loop over the transitions by using our external index.
252  for (; start < state.transitions.length(); start++)
253  if (state.transitions[start].next_state == next) {
254  start++; // position it after this index.
255  return start - 1; // return this index.
256  }
257  return common::NOT_FOUND;
258 }
259 
260 // configurational functions:
261 
262 void transition_map::reconfigure() { _valid = false; }
263 
265 {
266  // check for a bad starting state...
267  examine = _start_state;
268  FIND_STATE(_start_state) BAD_START;
269 
270  if (!check_reachability(examine)) return UNREACHABLE;
271  // a state is unreachable from the starting state.
272  if (!check_overlapping(examine)) return OVERLAPPING_RANGES;
273  // bad (overlapping) ranges were found in one state.
274  _valid = true; // set us to operational.
275  return OKAY;
276 }
277 
278 bool transition_map::add_state(int state_number)
279 {
280  if (valid()) return false; // this is operational; no more config!
281  if (!state_number) return false; // zero is disallowed.
282  if (non_negative(state_index(state_number))) return false; // already exists.
283  *_state_list += state_info(state_number);
284  return true;
285 }
286 
287 bool transition_map::set_start(int starting_state)
288 {
289  if (valid()) return false; // this is operational; no more config!
290  if (!starting_state) return false;
291 
292  FIND_STATE(starting_state) false; // doesn't exist.
293 
294  _start_state = starting_state;
295  return true;
296 }
297 
298 bool transition_map::add_simple_transition(int current, int next)
299 {
300  if (valid()) return false; // this is operational; no more config!
301  CHECK_STATES;
302  (*_state_list)[indy].transitions += transition_info(next);
303  return true;
304 }
305 
306 bool transition_map::add_range_transition(int current, int next, int low, int high)
307 {
308  if (valid()) return false; // this is operational; no more config!
309  CHECK_STATES;
310  (*_state_list)[indy].transitions += transition_info(next, low, high);
311  return true;
312 }
313 
314 bool transition_map::add_timed_transition(int current, int next, int length)
315 {
316  if (valid()) return false; // this is operational; no more config!
317  CHECK_STATES;
318  state_info &found = (*_state_list)[indy];
319  // locates any existing timed transition and re-uses its slot.
320  for (int i = 0; i < found.transitions.length(); i++)
321  if (found.transitions[i].type == transition_info::TIMED) {
322  found.transitions[i] = transition_info(next, length);
323  return true;
324  }
325  // no existing timed transition found, so add a new one.
326  (*_state_list)[indy].transitions += transition_info(next, length);
327  return true;
328 }
329 
330 // operational functions:
331 
333 {
334  if (!valid()) return false; // this is not operational yet!
335  CHECK_VALID(m);
336 #ifdef DEBUG_STATE_MACHINE
337  if (negative(state_index(m._current)))
338  LOG(astring("(%s) transition_map::make_transition: bad logic error; machine's "
339  "state is missing.", m._name->s()));
340  if (negative(state_index(next)))
341  LOG(astring("(%s) transition_map::make_transition: next state parameter is invalid.",
342  m._name->s()));
343 #endif
344  FIND_STATE(m._current) false; // bad next state.
345  int start = 0;
346  if (negative(transition_index(indy, next, start))) return false;
347  // no transition exists for that next state.
348  MOVE_STATE(m, next, state_machine::SIMPLE, 0);
349  int trig = m.update();
350  if (trig) return pulse(m, trig);
351  return true;
352 }
353 
355 {
356  if (!valid()) return false; // this is not operational yet!
357  CHECK_VALID(m);
358 #ifdef DEBUG_STATE_MACHINE
359  if (negative(state_index(m._current)))
360  LOG(astring("(%s) transition_map::pulse: bad logic error; state is missing.", m._name->s()));
361 #endif
362  FIND_STATE(m._current) false; // logic error!
363  state_info &found = (*_state_list)[indy];
364  for (int i = 0; i < found.transitions.length(); i++) {
365  if (found.transitions[i].type == transition_info::RANGE) {
366  // found the right type of transition.
367  transition_info &tran = found.transitions[i];
368  if ( (tran.low_trigger <= trigger)
369  && (tran.high_trigger >= trigger) ) {
370  // found a transition with an acceptable range.
371  MOVE_STATE(m, tran.next_state, state_machine::RANGE, trigger);
372  int trig = m.update();
373  if (trig) return pulse(m, trig);
374  return true;
375  }
376  }
377  }
378  return false;
379 }
380 
382 {
383  if (!valid()) return false; // this is not operational yet!
384  CHECK_VALID(m);
385 
386 #ifdef DEBUG_STATE_MACHINE
387  if (negative(state_index(m._current)))
388  LOG(astring("(%s) transition_map::time_slice: bad logic error; state "
389  "is missing.", m._name->s()));
390 #endif
391  FIND_STATE(m._current) false; // logic error!
392 
393  state_info &found = (*_state_list)[indy];
394  for (int i = 0; i < found.transitions.length(); i++) {
395  if (found.transitions[i].type == transition_info::TIMED) {
396  // found the right type of transition.
397  transition_info &tran = found.transitions[i];
398  int duration = tran.time_span;
399  int override = m.duration_override(m._current, tran.next_state);
400  if (override) duration = override;
401  if (*m._start < time_stamp(-duration)) {
402  // found a transition with an expired time.
403  MOVE_STATE(m, tran.next_state, state_machine::TIMED, 0);
404  int trig = m.update();
405  if (trig) return pulse(m, trig);
406  return true;
407  }
408  }
409  }
410  return false;
411 }
412 
414 {
415  if (!valid()) return false; // this is not operational yet!
416  m._current = _start_state;
417  m._last = _start_state;
418  m._trig = 0;
419  m._type = state_machine::SIMPLE;
420  m._start->reset();
421  return true;
422 }
423 
424 bool transition_map::check_overlapping(int &examine)
425 {
426  FUNCDEF("check_overlapping");
427  examine = 0;
428  for (int i = 0; i < states(); i++) {
429  examine = i;
430  for (int j = 0; j < (*_state_list)[i].transitions.length(); j++) {
431  transition_info &a = (*_state_list)[i].transitions[j];
432  if (a.type != transition_info::RANGE) continue;
433  for (int k = j + 1; k < (*_state_list)[i].transitions.length(); k++) {
434  transition_info &b = (*_state_list)[i].transitions[k];
435  if (b.type != transition_info::RANGE) continue;
436  if ( (b.low_trigger <= a.low_trigger)
437  && (b.high_trigger >= a.low_trigger) ) {
438  LOG(astring("intersecting range on low end!"));
439  return false;
440  }
441  if ( (b.low_trigger <= a.high_trigger)
442  && (b.high_trigger >= a.high_trigger) ) {
443  LOG(astring("intersecting range on high end!"));
444  return false;
445  }
446  }
447  }
448  }
449  return true;
450 }
451 
452 bool transition_map::check_reachability(int &examine)
453 {
454  FUNCDEF("check_reachability");
455  examine = 0;
456 
457  // list_to_add: the list of states that are definitely reachable and that
458  // need to be considered.
459  int_array list_to_add;
460  list_to_add += _start_state;
461 
462  // already_checked: those states that have already been completely considered
463  // as to their reachability.
464  array<bool> already_checked(states());
465  for (int i = 0; i < already_checked.length(); i++)
466  already_checked[i] = false;
467 
468  while (list_to_add.length()) {
469  // the next state that IS reachable has all of the states reachable from
470  // it added to the list of states that are to be checked...
471  examine = list_to_add[0];
472  int indy = state_index(examine);
473  if (negative(indy)) {
474  LOG(a_sprintf("bad state index for state %d!", examine));
475  return false;
476  }
477 #ifdef DEBUG_STATE_MACHINE
478  LOG(a_sprintf("state to add is %d, list size=%d.", examine,
479  list_to_add.length()));
480 #endif
481  // delete the item that we are now checking.
482  list_to_add.zap(0, 0);
483 
484  // check whether this item has already had its kids (those states reachable
485  // from it) added to the list to add. if so, skip it.
486  if (already_checked[indy]) continue;
487 
488  // update the information for this state we are considering in the list of
489  // already checked states.
490  already_checked[indy] = true;
491 
492  state_info &found = (*_state_list)[indy];
493 
494  // all states this one can reach are added to the list to check.
495  for (int i = 0; i < found.transitions.length(); i++) {
496 #ifdef DEBUG_STATE_MACHINE
497  LOG(astring("checking transition %d: ", i));
498 #endif
499  int now_reachable = found.transitions[i].next_state;
500 #ifdef DEBUG_STATE_MACHINE
501  LOG(astring("now reaching %d.", now_reachable));
502 #endif
503  if (now_reachable == examine) continue;
504  else {
505  int indy = state_index(now_reachable);
506  if (already_checked[indy]) continue;
507  }
508  list_to_add += now_reachable;
509  }
510  }
511 #ifdef DEBUG_STATE_MACHINE
512  LOG("done checking reachability.");
513 #endif
514  for (int j = 0; j < already_checked.length(); j++)
515  if (!already_checked.get(j)) {
516  examine = (*_state_list)[j].state_id;
517  LOG(a_sprintf("state %d is not reachable", examine));
518  return false;
519  }
520  return true; // all states are reachable.
521 }
522 
523 } //namespace.
524 
a_sprintf is a specialization of astring that provides printf style support.
Definition: astring.h:440
int length() const
Returns the current reported length of the allocated C array.
Definition: array.h:115
outcome zap(int start, int end)
Deletes from "this" the objects inclusively between "start" and "end".
Definition: array.h:769
Provides a dynamically resizable ASCII character string.
Definition: astring.h:35
const char * s() const
synonym for observe. the 's' stands for "string", if that helps.
Definition: astring.h:113
A simple object that wraps a templated array of ints.
Definition: array.h:275
Outcomes describe the state of completion for an operation.
Definition: outcome.h:31
Monitors objects with multiple states and the transitions between states.
Definition: state_machine.h:45
void override_timing(int current, int next, int duration)
modifies the recorded timing for timed transitions.
virtual int update()
this is the main implementation function provided by derived classes.
int trigger() const
returns the trigger that caused this state.
Definition: state_machine.h:85
basis::astring get_name() const
retrieves the object's current name.
int current() const
returns the current state.
Definition: state_machine.h:79
void set_state(int new_current, int new_last, int trigger, transition_types type)
sets the current state to "new_current" and the previous state to "new_last".
timely::time_stamp start() const
start time for the current state.
state_machine()
sets up the machine in a blank state.
int duration_override(int current, int next) const
reports if there's a duration override for a timed transition.
void set_name(const basis::astring &name)
sets the name to be printed in any debugging information for "this".
state_machine & operator=(const state_machine &to_copy)
assigns this to a copy of the machine provided in "to_copy".
bool add_range_transition(int current, int next, int low, int high)
adds a transition that listens to triggers in the pulse() method.
bool time_slice(state_machine &m)
bool set_start(int starting_state)
assigns a state as the first state.
bool add_simple_transition(int current, int next)
adds a transition between "current" and "next".
bool make_transition(state_machine &m, int next)
changes the state to the "next" listed for "m" given the current state.
bool pulse(state_machine &m, int trigger)
applies a "trigger" to possibly cause a range transition.
bool valid() const
returns true if the transition_map is valid and ready for operation.
bool reset(state_machine &m)
void reconfigure()
puts the transition_map back into an unvalidated state.
int states() const
returns the current number of states.
bool add_state(int state_number)
registers a legal state in the transition_map.
basis::outcome validate(int &examine)
checks to that all required transition conditions are satisfied.
bool add_timed_transition(int current, int next, int duration)
adds a transition that occurs after a timeout with no other activity.
Represents a point in time relative to the operating system startup time.
Definition: time_stamp.h:38
void reset()
sets the stamp time back to now.
Definition: time_stamp.cpp:59
#define FUNCDEF(func_in)
FUNCDEF sets the name of a function (and plugs it into the callstack).
Definition: enhance_cpp.h:57
#define bounds_return(value, low, high, to_return)
Verifies that "value" is between "low" and "high", inclusive.
Definition: guards.h:48
The guards collection helps in testing preconditions and reporting errors.
Definition: array.h:30
void WHACK(contents *&ptr)
deletion with clearing of the pointer.
Definition: functions.h:121
bool non_negative(const type &a)
non_negative returns true if "a" is greater than or equal to zero.
Definition: functions.h:45
bool negative(const type &a)
negative returns true if "a" is less than zero.
Definition: functions.h:43
A logger that sends to the console screen using the standard output device.
#include <time.h>
Definition: earth_time.cpp:37
#define FIND_STATE(state)
#define MOVE_STATE(m, next, type, trigger)
#define CHECK_STATES
#define LOG(to_print)
#define CHECK_VALID(m)