myset.cpp

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

#include "myreg.h"

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

#define MIN_TEMP_SET_SPACE_SIZE 256

inline size_t get_set_hash_value( void** set, size_t count ) {
	return ( HASH_TABLE_SIZE -1 ) & 
	  ( ( (size_t)(set[0]) & 0x000000FF ) | 
		( (size_t)(set[count-1]) & 0xFF000000 ) |
		( (size_t)(set[ count/2 ]) & 0x00FFFF00 ) );
}

HASH_TABLE::LLNode* insert_set_obj( HASH_TABLE* hash_table, SET* s ) {

	size_t hash = get_set_hash_value( s->set, s->count );
	HASH_TABLE::LLNode* n = hash_table->table[hash].next;
	HASH_TABLE::LLNode* prev = &hash_table->table[hash];

	SET* ns = NULL;
	HASH_TABLE::LLNode* new_n = NULL;
	int cmp = 0;
	
	while( n ) {
		ns = (SET*) n->v;
		// sort according to the set::count
		
		if( ns->count > s->count ) {
			goto ADD_NEW_NODE;
			break;
		}
		// when count equal, sort according to set::set
		if( ns->count == s->count ) {
			cmp = memcmp( ns->set, s->set, sizeof(void*)*ns->count );
			// found a same node
			if ( cmp == 0 ) {
				new_n = n;
				goto END;			
			}
			if ( cmp > 0 ) {
				goto ADD_NEW_NODE;
			}
		}

		prev = n;
		n = n->next;
	}

ADD_NEW_NODE:

	new_n = (HASH_TABLE::LLNode*) malloc( sizeof( HASH_TABLE::LLNode ) );
	new_n->v = (void*) s;
	prev->next = new_n;
	new_n->next = n;

END:

	return new_n;
}

SET* find_set_obj( HASH_TABLE* hash_table, void** set, size_t count ) {

	size_t hash = get_set_hash_value( set, count );
	HASH_TABLE::LLNode* n = hash_table->table[hash].next;
	SET* ns = NULL;
	int cmp = 0;

	while( n ) {
		// compare the set
		ns = (SET*) n->v;
		if ( ns->count == count ) {
			cmp = memcmp( ns->set, set, sizeof(void*)*count );
			if ( cmp == 0 ) {
				// found
				return ns;
			}
			if ( cmp > 0 ) {
				return NULL;
			}
		}
		if ( ns->count > count ) {
			return NULL;
		}
		// next 
		n = n->next;
	}

	return NULL;
}


SET_FACTORY* initialize_set_factory() {

	SET_FACTORY* f = (SET_FACTORY*) malloc( sizeof(SET_FACTORY) );
	
	f->temp_set_space_size = MIN_TEMP_SET_SPACE_SIZE;
	f->temp_set_space = (void**) malloc( f->temp_set_space_size*sizeof( void* ) );

	f->set_hash_table = new_hash_table();

	return f;
}

void release_set( void* v ) {
	SET* s = (SET*) v;
	free( s->set );
}

void release_set_factory( SET_FACTORY* f ) {
	free( f->temp_set_space );
	release_hash_table( f->set_hash_table, release_set );	
}

SET_FACTORY* FACTORY = initialize_set_factory();

// new set which contains one element
SET* new_set( SET_FACTORY* factory,  void* n1 ) {
	void* list[] = { n1, NULL };
	return new_set( factory, list, 1 );
}

// new set which contains two element
SET* new_set( SET_FACTORY* factory,  void* n1, void* n2 ) {

	void* list[] = { NULL, NULL, NULL };
	if ( n1 > n2 ) {
		list[0] = n2;
		list[1] = n1;
	} else {
		list[0] = n1;
		list[1] = n2;
	}

	return new_set( factory, list, 2 );
}

// new set
SET* new_set( SET_FACTORY* factory, void** set, size_t count ) {

	if ( set == NULL ||  count == 0 ) {
		return NULL;
	}

	SET* s = find_set( factory, set, count );
	if ( s ) { return s; } // there is an existing set
	// create new set
	s = (SET*) malloc( sizeof(SET) );
	s->size = sizeof(void*)*count;
	s->count = count;
	s->set = (void**) malloc( sizeof(void*)*s->size );
	memcpy( s->set, set, count*sizeof(void*));
	// end by NULL
	s->set[s->count] = NULL;

	insert_set_obj( factory->set_hash_table, s );

	// PrintSet( s );
	return s;
}


// union two set
SET* union_set( SET_FACTORY* factory, SET* s1, SET* s2 ) {
	
	if( s2 == NULL ) { 
		// s2 is empty while s1 is not
		return s1; 
	}
	return union_set( factory, s1, s2->set, s2->count );	
}

// union a set and a sorted list
SET* union_set( SET_FACTORY* factory, SET* s1, void** set, size_t count ) {

	if ( s1 == NULL && ( set == NULL || count ==0 ) ) {
		// union two empty set
		return NULL;
	}

	if ( s1 == NULL ) {
		// s1 is empty while set is not
		return new_set( factory, set, count );
	}

	if ( set == NULL || count == 0 ) { 
		// set is empty whie s1 is not
		return s1; 
	}

	if ( factory->temp_set_space_size < s1->count + count ) { 
		// there might be over flowder
		factory->temp_set_space_size *= 2;
		factory->temp_set_space = (void**)realloc( factory->temp_set_space, sizeof(void*)*factory->temp_set_space_size );
	}

	void** w = factory->temp_set_space;
	int w_count = 0;
	void** r1 = s1->set;
	void** r2 = set;
	 
	// merge two set
	while( *r1 && *r2 ) {
		if ( *r1 <= *r2 ) {
			// write r1
			*w = *r1++;			
			// skip r2
			if ( *w == *r2 ) { r2 ++; }
		} else {
			// write r2
			*w = *r2;
			r2++;
		}
		w++;
	}

	while( *r1 ) {
		*w++ = *r1++;		
	}

	while( *r2 ) {
		*w++ = *r2++;		
	}

	w_count = w - factory->temp_set_space;

	return new_set( factory, factory->temp_set_space, w_count );

}

// find a set handler
SET* find_set( SET_FACTORY* factory, void** set, size_t count ) {
	return find_set_obj( factory->set_hash_table, set, count );
}

// print set to stdout
void PrintSet ( SET* s ) {
	if ( s ) {
		printf( "Set %x\nSize:%d\nCount:%d\n", s, s->size, s->count );
		REG_NODE** n = (REG_NODE**)s->set;
		while( *n ) {
			printf( "%x\n", *n++ );			
		}
	} else {
		printf( "Empty Set\n" );
	}
}