1 /*****************************************************************************\
3 * Name : state_machine *
4 * Author : Chris Koeritz *
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 \*****************************************************************************/
15 #include "state_machine.h"
17 #include <basis/array.h>
18 #include <basis/functions.h>
19 #include <basis/guards.h>
20 #include <basis/astring.h>
21 #include <loggers/program_wide_logger.h>
22 #include <timely/time_stamp.h>
24 using namespace basis;
25 using namespace loggers;
26 using namespace timely;
32 //#define DEBUG_STATE_MACHINE
33 // uncomment if you want the debugging version.
35 //hmmm: implement logging...
37 #ifndef DEBUG_STATE_MACHINE
38 #define LOG(to_print) CLASS_EMERGENCY_LOG(program_wide_logger::get(), to_print)
40 #define LOG(to_print) {}
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
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
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; \
66 // locates a state or returns.
67 #define FIND_STATE(state) \
68 int indy = state_index(state); \
69 if (negative(indy)) return
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) {}
78 struct transition_info {
79 enum transition_type { SIMPLE, RANGE, TIMED };
82 int low_trigger, high_trigger;
85 transition_info() {} // blank.
86 transition_info(int next) : type(SIMPLE), next_state(next) {}
87 transition_info(int next, int time) : type(TIMED), next_state(next),
89 transition_info(int next, int low, int high) : type(RANGE),
90 next_state(next), low_trigger(low), high_trigger(high) {}
94 int state_id; // id for this state.
95 array<transition_info> transitions;
97 state_info() : state_id(0) {} // blank.
98 state_info(int state_id_in) : state_id(state_id_in) {}
103 class state_machine_override_array : public array<override> {};
104 class state_machine_state_array : public array<state_info> {};
108 state_machine::state_machine()
113 _start(new time_stamp()),
114 _name(new astring()),
115 _overrides(new state_machine_override_array)
118 state_machine::state_machine(const state_machine &to_copy)
124 _start(new time_stamp()),
125 _name(new astring()),
126 _overrides(new state_machine_override_array)
129 state_machine::~state_machine()
136 int state_machine::update() { return 0; }
138 void state_machine::set_name(const astring &name) { *_name = name; }
140 astring state_machine::get_name() const { return *_name; }
142 state_machine &state_machine::operator = (const state_machine &to_copy)
144 if (&to_copy == this) return *this;
145 _current = to_copy._current;
146 _last = to_copy._last;
147 _trig = to_copy._trig;
148 _type = to_copy._type;
149 *_start = *to_copy._start;
150 *_name = *to_copy._name;
151 *_overrides = *to_copy._overrides;
152 //careful when overrides becomes hidden internal type.
156 int state_machine::duration_index(int current, int next) const
158 for (int i = 0; i < _overrides->length(); i++)
159 if ( ((*_overrides)[i].current == current)
160 && ((*_overrides)[i].next == next) )
162 return common::NOT_FOUND;
165 void state_machine::set_state(int new_current, int new_last, int trigger,
166 transition_types type)
168 _current = new_current;
175 void state_machine::override_timing(int current, int next, int duration)
177 int indy = duration_index(current, next);
178 if (non_negative(indy)) {
179 // found an existing record for this current/next pair.
181 // zero duration means removal.
182 _overrides->zap(indy, indy);
185 // reset the duration.
186 (*_overrides)[indy].duration = duration;
189 // no existing record, so add one.
190 *_overrides += override(current, next, duration);
193 int state_machine::duration_override(int current, int next) const
195 int indy = duration_index(current, next);
196 if (negative(indy)) return 0;
197 return (*_overrides)[indy].duration;
200 time_stamp state_machine::start() const { return *_start; }
204 transition_map::transition_map()
207 _state_list(new state_machine_state_array)
210 transition_map::~transition_map()
216 // informational functions:
218 int transition_map::states() const { return _state_list->length(); }
220 int transition_map::state_index(int state_id) const
222 for (int i = 0; i < states(); i++)
223 if ((*_state_list)[i].state_id == state_id) return i;
224 return common::NOT_FOUND;
227 int transition_map::transition_index(int state_index, int next, int &start)
229 bounds_return(state_index, 0, states() - 1, common::BAD_INPUT);
230 state_info &state = (*_state_list)[state_index];
231 bounds_return(start, 0, state.transitions.length() - 1, common::BAD_INPUT);
232 // loop over the transitions by using our external index.
233 for (start = start; start < state.transitions.length(); start++)
234 if (state.transitions[start].next_state == next) {
235 start++; // position it after this index.
236 return start - 1; // return this index.
238 return common::NOT_FOUND;
241 // configurational functions:
243 void transition_map::reconfigure() { _valid = false; }
245 outcome transition_map::validate(int &examine)
247 // check for a bad starting state...
248 examine = _start_state;
249 FIND_STATE(_start_state) BAD_START;
251 if (!check_reachability(examine)) return UNREACHABLE;
252 // a state is unreachable from the starting state.
253 if (!check_overlapping(examine)) return OVERLAPPING_RANGES;
254 // bad (overlapping) ranges were found in one state.
255 _valid = true; // set us to operational.
259 bool transition_map::add_state(int state_number)
261 if (valid()) return false; // this is operational; no more config!
262 if (!state_number) return false; // zero is disallowed.
263 if (non_negative(state_index(state_number))) return false; // already exists.
264 *_state_list += state_info(state_number);
268 bool transition_map::set_start(int starting_state)
270 if (valid()) return false; // this is operational; no more config!
271 if (!starting_state) return false;
273 FIND_STATE(starting_state) false; // doesn't exist.
275 _start_state = starting_state;
279 bool transition_map::add_simple_transition(int current, int next)
281 if (valid()) return false; // this is operational; no more config!
283 (*_state_list)[indy].transitions += transition_info(next);
287 bool transition_map::add_range_transition(int current, int next, int low, int high)
289 if (valid()) return false; // this is operational; no more config!
291 (*_state_list)[indy].transitions += transition_info(next, low, high);
295 bool transition_map::add_timed_transition(int current, int next, int length)
297 if (valid()) return false; // this is operational; no more config!
299 state_info &found = (*_state_list)[indy];
300 // locates any existing timed transition and re-uses its slot.
301 for (int i = 0; i < found.transitions.length(); i++)
302 if (found.transitions[i].type == transition_info::TIMED) {
303 found.transitions[i] = transition_info(next, length);
306 // no existing timed transition found, so add a new one.
307 (*_state_list)[indy].transitions += transition_info(next, length);
311 // operational functions:
313 bool transition_map::make_transition(state_machine &m, int next)
315 if (!valid()) return false; // this is not operational yet!
317 #ifdef DEBUG_STATE_MACHINE
318 if (negative(state_index(m._current)))
319 LOG(astring("(%s) transition_map::make_transition: bad logic error; machine's "
320 "state is missing.", m._name->s()));
321 if (negative(state_index(next)))
322 LOG(astring("(%s) transition_map::make_transition: next state parameter is invalid.",
325 FIND_STATE(m._current) false; // bad next state.
327 if (negative(transition_index(indy, next, start))) return false;
328 // no transition exists for that next state.
329 MOVE_STATE(m, next, state_machine::SIMPLE, 0);
330 int trig = m.update();
331 if (trig) return pulse(m, trig);
335 bool transition_map::pulse(state_machine &m, int trigger)
337 if (!valid()) return false; // this is not operational yet!
339 #ifdef DEBUG_STATE_MACHINE
340 if (negative(state_index(m._current)))
341 LOG(astring("(%s) transition_map::pulse: bad logic error; state is missing.", m._name->s()));
343 FIND_STATE(m._current) false; // logic error!
344 state_info &found = (*_state_list)[indy];
345 for (int i = 0; i < found.transitions.length(); i++) {
346 if (found.transitions[i].type == transition_info::RANGE) {
347 // found the right type of transition.
348 transition_info &tran = found.transitions[i];
349 if ( (tran.low_trigger <= trigger)
350 && (tran.high_trigger >= trigger) ) {
351 // found a transition with an acceptable range.
352 MOVE_STATE(m, tran.next_state, state_machine::RANGE, trigger);
353 int trig = m.update();
354 if (trig) return pulse(m, trig);
362 bool transition_map::time_slice(state_machine &m)
364 if (!valid()) return false; // this is not operational yet!
367 #ifdef DEBUG_STATE_MACHINE
368 if (negative(state_index(m._current)))
369 LOG(astring("(%s) transition_map::time_slice: bad logic error; state "
370 "is missing.", m._name->s()));
372 FIND_STATE(m._current) false; // logic error!
374 state_info &found = (*_state_list)[indy];
375 for (int i = 0; i < found.transitions.length(); i++) {
376 if (found.transitions[i].type == transition_info::TIMED) {
377 // found the right type of transition.
378 transition_info &tran = found.transitions[i];
379 int duration = tran.time_span;
380 int override = m.duration_override(m._current, tran.next_state);
381 if (override) duration = override;
382 if (*m._start < time_stamp(-duration)) {
383 // found a transition with an expired time.
384 MOVE_STATE(m, tran.next_state, state_machine::TIMED, 0);
385 int trig = m.update();
386 if (trig) return pulse(m, trig);
394 bool transition_map::reset(state_machine &m)
396 if (!valid()) return false; // this is not operational yet!
397 m._current = _start_state;
398 m._last = _start_state;
400 m._type = state_machine::SIMPLE;
405 bool transition_map::check_overlapping(int &examine)
407 FUNCDEF("check_overlapping");
409 for (int i = 0; i < states(); i++) {
411 for (int j = 0; j < (*_state_list)[i].transitions.length(); j++) {
412 transition_info &a = (*_state_list)[i].transitions[j];
413 if (a.type != transition_info::RANGE) continue;
414 for (int k = j + 1; k < (*_state_list)[i].transitions.length(); k++) {
415 transition_info &b = (*_state_list)[i].transitions[k];
416 if (b.type != transition_info::RANGE) continue;
417 if ( (b.low_trigger <= a.low_trigger)
418 && (b.high_trigger >= a.low_trigger) ) {
419 LOG(astring("intersecting range on low end!"));
422 if ( (b.low_trigger <= a.high_trigger)
423 && (b.high_trigger >= a.high_trigger) ) {
424 LOG(astring("intersecting range on high end!"));
433 bool transition_map::check_reachability(int &examine)
435 FUNCDEF("check_reachability");
438 // list_to_add: the list of states that are definitely reachable and that
439 // need to be considered.
440 int_array list_to_add;
441 list_to_add += _start_state;
443 // already_checked: those states that have already been completely considered
444 // as to their reachability.
445 array<bool> already_checked(states());
446 for (int i = 0; i < already_checked.length(); i++)
447 already_checked[i] = false;
449 while (list_to_add.length()) {
450 // the next state that IS reachable has all of the states reachable from
451 // it added to the list of states that are to be checked...
452 examine = list_to_add[0];
453 int indy = state_index(examine);
454 if (negative(indy)) {
455 LOG(a_sprintf("bad state index for state %d!", examine));
458 #ifdef DEBUG_STATE_MACHINE
459 LOG(a_sprintf("state to add is %d, list size=%d.", examine,
460 list_to_add.length()));
462 // delete the item that we are now checking.
463 list_to_add.zap(0, 0);
465 // check whether this item has already had its kids (those states reachable
466 // from it) added to the list to add. if so, skip it.
467 if (already_checked[indy]) continue;
469 // update the information for this state we are considering in the list of
470 // already checked states.
471 already_checked[indy] = true;
473 state_info &found = (*_state_list)[indy];
475 // all states this one can reach are added to the list to check.
476 for (int i = 0; i < found.transitions.length(); i++) {
477 #ifdef DEBUG_STATE_MACHINE
478 LOG(astring("checking transition %d: ", i));
480 int now_reachable = found.transitions[i].next_state;
481 #ifdef DEBUG_STATE_MACHINE
482 LOG(astring("now reaching %d.", now_reachable));
484 if (now_reachable == examine) continue;
486 int indy = state_index(now_reachable);
487 if (already_checked[indy]) continue;
489 list_to_add += now_reachable;
492 #ifdef DEBUG_STATE_MACHINE
493 LOG("done checking reachability.");
495 for (int j = 0; j < already_checked.length(); j++)
496 if (!already_checked.get(j)) {
497 examine = (*_state_list)[j].state_id;
498 LOG(a_sprintf("state %d is not reachable", examine));
501 return true; // all states are reachable.