src/base/state_machine.c

/*
 * Copyright 2015 Google Inc.
 *
 * See file CREDITS for list of people who contributed to this
 * project.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of
 * the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * 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
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston,
 * MA 02111-1307 USA
 *
 */

#include <assert.h>
#include <libpayload.h>

#include "base/state_machine.h"

/*
 * Each state is represented by:
 * a. Unique id provided by caller
 * b. Whether this is final state
 * c. List of all valid transitions from this state
 */
struct sm_state {
	int id;
	int is_final;
	ListNode transitions;
};

/*
 * Each transition is represented by:
 * a. Input that it takes
 * b. Dest state because of this transition
 * c. Pointer to next valid transition at source state
 */
struct sm_transition {
	int input;
	struct sm_state *next;
	ListNode list_node;
};

/*
 * State machine is represented by:
 * a. Start state
 * b. Current state of the machine
 * c. Array containing pointers to each state machine structure(arr)
 * d. Used slots in state machine arr
 * e. Max slots available in state machine arr
 */
struct sm_data {
	struct sm_state *start_state;
	struct sm_state *curr_state;
	size_t used;
	size_t max;
	struct sm_state *arr[0];
};

/* Allocates memory for arr based on the value of n states */
struct sm_data *sm_init(size_t n)
{
	struct sm_data *sm = xzalloc(sizeof(*sm) +
				     n * sizeof(struct sm_state *));

	sm->max = n;

	return sm;
}

/* Returns pointer to a state given its id. */
static struct sm_state *sm_find_state(struct sm_data *sm, int id)
{
	int i = 0;

	for(; i < sm->used; i++) {
		if (sm->arr[i]->id == id)
			return sm->arr[i];
	}

	return NULL;
}

/* Resets curr_state to start_state. */
void sm_reset_state(struct sm_data *sm)
{
	sm->curr_state = sm->start_state;
}

/* Sets start_state given id of the state. */
static void sm_set_start_state(struct sm_data *sm, int id)
{
	struct sm_state *state = sm_find_state(sm, id);
	sm->start_state = state;
	sm_reset_state(sm);
}

/* Allocates memory for new state and adds to arr in state machine. */
static void sm_add_state(struct sm_data *sm, int id, int is_final)
{
	assert(sm->used < sm->max);

	/* State already exists in state machine table */
	if (sm_find_state(sm, id))
		return;

	struct sm_state *state = xzalloc(sizeof(*state));
	state->id = id;
	state->is_final = is_final;

	sm->arr[sm->used] = state;
	sm->used++;
}

void sm_add_nonfinal_state(struct sm_data *sm, int id)
{
	sm_add_state(sm, id, STATE_NOT_FINAL);
}

void sm_add_final_state(struct sm_data *sm, int id)
{
	sm_add_state(sm, id, STATE_FINAL);
}

void sm_add_start_state(struct sm_data *sm, int id)
{
	sm_add_state(sm, id, STATE_NOT_FINAL);
	sm_set_start_state(sm, id);
}

/*
 * Given src and dst ids, it finds the corr state structures and adds curr
 * transition to list of valid transitions in the src structure
 */
void sm_add_transition(struct sm_data *sm, int src_id, int input, int dst_id)
{
	struct sm_state *src = sm_find_state(sm, src_id);
	struct sm_state *dst = sm_find_state(sm, dst_id);

	assert (src && dst);

	struct sm_transition *tran = xzalloc(sizeof(*tran));
	tran->input = input;
	tran->next = dst;

	list_insert_after(&tran->list_node, &src->transitions);
}

/*
 * Given an input, it checks current state for valid transition with that
 * input.
 * If a transition is found, it updates output with the value of next state id.
 * Then, it updates curr state to next state.
 * If next state is final, it returns STATE_FINAL and resets state machine.
 * Else it returns STATE_NOT_FINAL.
 * If no valid transition is found, it returns STATE_NO_TRANSITION
 */
int sm_run(struct sm_data *sm, int input, int *output)
{
	assert(sm->curr_state && sm->start_state);

	struct sm_state *curr = sm->curr_state;

	struct sm_transition *tran;

	list_for_each(tran, curr->transitions, list_node) {
		if (tran->input != input)
			continue;

		sm->curr_state = tran->next;
		*output = sm->curr_state->id;
		if (sm->curr_state->is_final == STATE_FINAL) {
			sm_reset_state(sm);
			return STATE_FINAL;
		} else
			return STATE_NOT_FINAL;
	}

	return STATE_NO_TRANSITION;
}