dstate.cpp

我的一个利用有限状态机的正则表达式的实现。

#include "DState.h"
#include "MyHash.h"

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// macros
#define DEFAULT_DTRAN_SIZE 16

HASH_TABLE* initialize_dstate_hash_table() {
	return new_hash_table();	
}

HASH_TABLE* DSTATE_HASH_TABLE = initialize_dstate_hash_table();

inline size_t get_address_hash_value( void* address ) {

	return (HASH_TABLE_SIZE - 1)&( (size_t) address );

}

HASH_TABLE::LLNode* insert_dstate( HASH_TABLE* hash_table, DSTATE* ds ) {
	
	size_t hash = get_address_hash_value( ds->node_set );

	HASH_TABLE::LLNode* prev = &hash_table->table[hash];
	HASH_TABLE::LLNode* n = prev->next;

	HASH_TABLE::LLNode* new_n = NULL;

	DSTATE* ns = NULL;

	while( n ) {

		ns = (DSTATE*)n->v;

		if( ns->node_set == ds->node_set ) {
			// there is an existing ds, return it
			new_n = n;
			goto END;
		} 

		if( ns->node_set > ds->node_set ) {
			// no same node, insert one
			goto INSERT;			
		}
		
		// goto next
		prev = n;
		n = n->next;
	}

INSERT:
	new_n = (HASH_TABLE::LLNode*) malloc( sizeof(HASH_TABLE::LLNode) );
	new_n->v = ds;
	new_n->next = n;
	prev->next = new_n;
END:
	return new_n;
}

DSTATE* find_dstate( HASH_TABLE* hash_table, SET* s ) {
	size_t hash = get_address_hash_value( s );
	HASH_TABLE::LLNode* n = hash_table->table[hash].next;

	DSTATE* ns = NULL;

	while( n ) {

		ns = (DSTATE*) n->v;

		if ( ns->node_set == s ) {
			return ns;
		}

		if ( ns->node_set > s ) {
			break;
		}
		
		// goto next
		n = n->next;
	}

	return NULL;
}

DSTATE* new_dstate( SET* s ) {
	// create new dstate
	DSTATE* ds = (DSTATE*) malloc(sizeof(DSTATE));
	ds->node_set = s;
	ds->dtrans_count = 0;
	ds->dtrans_size = DEFAULT_DTRAN_SIZE;
	ds->marked = 0;
	ds->end = 0;
	ds->dtrans = (DTRAN**)malloc( sizeof(DTRAN*)*ds->dtrans_size );

	return ds;
}

void release_dstate( void* v ) {
	DSTATE* d = (DSTATE*) v;
	for( size_t i = 0; i < d->dtrans_count; i++ ) {
		free( d->dtrans[i] );	
	}
	free( d );
}

DTRAN* new_dtran( DSTATE* src, DSTATE* tar, char c ) {

	DTRAN* dt = NULL;
	int i = 0, j = src->dtrans_count -1;
	for( ; i <src->dtrans_count; i++ ) {
		dt = src->dtrans[i];
		if ( dt->c == c ) {
			if ( dt->tar == tar ) { return dt; } // found same, return
			if ( dt->tar > tar ) { break; } // insert here
		}
		if ( dt->c > c ) { break; } // insert here		
	}
	
	// null end, max count = size -1
	if( src->dtrans_count == src->dtrans_size ) {
		// enlarge the dtran table
		src->dtrans_size *= 2;
		src->dtrans = (DTRAN**)realloc( src->dtrans, sizeof(DTRAN*)*src->dtrans_size );
	}

	// if insert point is not at end, move tail
	for( ; j >= i; j-- ) {
		src->dtrans[j+1] = src->dtrans[j];
	}

	// insert the dtran
	dt = (DTRAN*) malloc( sizeof(DTRAN) );
	dt->c = c;
	dt->src = src;
	dt->tar = tar;
	src->dtrans[i] = dt;
	src->dtrans_count++;
	
	return dt;
}

DTRAN* find_dtran( DSTATE* ds, char c ) {
	DTRAN* dt = NULL;
	int i = 0;
	for( ; i <ds->dtrans_count; i++ ) {
		dt = ds->dtrans[i];
		if ( dt->c == c ) {
			return dt;
		}
		if ( dt->c > c ) { break; } // there is no dtran for input c
	}
	return NULL;
}

void PrintDTran( DTRAN* dt ) {
	printf("DTRAN: %d\n", dt);
	printf("ACCEPT: %c\n", dt->c );
	printf("FROM %d TO %d\n", dt->src, dt->tar );
	printf("=== DTRAN %d ENDS ===\n", dt );
}

void PrintDState( DSTATE* ds ) {
	printf("DSTATE: %d\n", ds );
	printf("ENDABLE: %s\n", ( ds->end ? "TRUE" : "FALSE" ) );
	printf("Dtran Count: %d\n", ds->dtrans_count );
	for( int i =0; i < ds->dtrans_count; i++ ) {
		printf ("%d\n", ds->dtrans[i]);
	}
}