gsp.c

Go to the documentation of this file.

/*
 * Copyright (c) 2009 Jiri Svoboda
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <gsp.h>
#include <adt/hash_table.h>
#include <stdlib.h>
#include <stdio.h>

#define TRANS_TABLE_CHAINS 256

/*
 * Hash table operations for the transition function.
 */

static hash_index_t trans_op_hash(unsigned long key[]);
static int trans_op_compare(unsigned long key[], hash_count_t keys,
    link_t *item);
static void trans_op_remove_callback(link_t *item);

static hash_table_operations_t trans_ops = {
        .hash = trans_op_hash,
        .compare = trans_op_compare,
        .remove_callback = trans_op_remove_callback
};

static gsp_trans_t *trans_lookup(gsp_t *p, int state, int input);
static void trans_insert(gsp_t *p, gsp_trans_t *t);
static gsp_trans_t *trans_new(void);

void gsp_init(gsp_t *p)
{
        p->states = 1;
        hash_table_create(&p->trans, TRANS_TABLE_CHAINS, 2, &trans_ops);
}

int gsp_insert_defs(gsp_t *p, const int *defs)
{
        unsigned mods, key;
        const int *dp;
        int rc;

        dp = defs;

        while (1) {
                /* Read the output values. */
                mods = *dp++;
                key = *dp++;
                if (key == 0) break;

                /* Insert one sequence. */              
                rc = gsp_insert_seq(p, dp, mods, key);
                if (rc != 0)
                        return rc;

                /* Skip to the next definition. */
                while (*dp != GSP_END)
                        ++dp;
                ++dp;
        }

        return 0;
}

int gsp_insert_seq(gsp_t *p, const int *seq, unsigned mods, unsigned key)
{
        int state;
        gsp_trans_t *t;

        state = 0;
        t = NULL;

        /* Input sequence must be non-empty. */
        if (*seq == GSP_END)
                return -1;

        while (*(seq + 1) != GSP_END) {
                t = trans_lookup(p, state, *seq);
                if (t == NULL) {
                        /* Create new state. */
                        t = trans_new();
                        t->old_state = state;
                        t->input = *seq;
                        t->new_state = p->states++;

                        t->out_mods = 0;
                        t->out_key = 0;

                        trans_insert(p, t);
                }
                state = t->new_state;
                ++seq;
        }

        /* Process the last transition. */
        t = trans_lookup(p, state, *seq);
        if (t != NULL) {
                exit(1);
                return -1;      /* Conflicting definition. */
        }

        t = trans_new();
        t->old_state = state;
        t->input = *seq;
        t->new_state = 0;

        t->out_mods = mods;
        t->out_key = key;

        trans_insert(p, t);

        return 0;
}

int gsp_step(gsp_t *p, int state, int input, unsigned *mods, unsigned *key)
{
        gsp_trans_t *t;

        t = trans_lookup(p, state, input);
        if (t == NULL) {
                t = trans_lookup(p, state, GSP_DEFAULT);
        }

        if (t == NULL) {
                printf("gsp_step: not found\n");
                *mods = 0;
                *key = 0;
                return 0;
        }

        *mods = t->out_mods;
        *key = t->out_key;
        return t->new_state;
}

static gsp_trans_t *trans_lookup(gsp_t *p, int state, int input)
{
        link_t *item;
        unsigned long key[2];

        key[0] = state;
        key[1] = input;

        item = hash_table_find(&p->trans, key);
        if (item == NULL) return NULL;

        return hash_table_get_instance(item, gsp_trans_t, link);
}

static void trans_insert(gsp_t *p, gsp_trans_t *t)
{
        unsigned long key[2];

        key[0] = t->old_state;
        key[1] = t->input;

        hash_table_insert(&p->trans, key, &t->link);
}

static gsp_trans_t *trans_new(void)
{
        gsp_trans_t *t;

        t = malloc(sizeof(gsp_trans_t));
        if (t == NULL) {
                printf("Memory allocation failed.\n");
                exit(1);
        }

        return t;
}

/*
 * Transition function hash table operations.
 */

static hash_index_t trans_op_hash(unsigned long key[])
{
        return (key[0] * 17 + key[1]) % TRANS_TABLE_CHAINS;
}

static int trans_op_compare(unsigned long key[], hash_count_t keys,
    link_t *item)
{
        gsp_trans_t *t;

        t = hash_table_get_instance(item, gsp_trans_t, link);
        return ((key[0] == (unsigned long) t->old_state)
            && (key[1] == (unsigned long) t->input));
}

static void trans_op_remove_callback(link_t *item)
{
}

---