?? 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]);
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -