Regular Expressions with Finite State Machines

Let's make a "Finite State Machine" which is used to check "a*b" regular expression.
At first we must design the FSM.

class State {
protected:
 State * const nextState;
 bool isFinal;
public:
 State( State & next, bool _isFinal ) : nextState( &next ) { isFinal = _isFinal; }
 virtual State * transition( char in ) = 0;
 bool isFinalState( ) { return isFinal; }
 ~State( ) { isFinal = false; }
};

class State1 : public State {
public:
 State1( State & nextState, bool _isFinal ) : State( nextState, _isFinal ) { }
 State * transition( char in );
};

State * State1::transition( char in ) {
 if( in >= '0' && in <= '9' ) return this->nextState;
 else return NULL;
}

class State2 : public State {
public:
 State2( State & nextState, bool _isFinal ) : State( nextState, _isFinal ) { }
 State * transition( char in );
};

State * State2::transition( char in ) {
 if( in == '*' ) return this->nextState;
 else return NULL;
}

class FSM {
 State1 state1;
 State2 state2;
 State1 state3;
 State2 final;
 State * current;
public:
 FSM( ) : state1( state2, false ), state2( state3, false ), state3( final, false ), final( final,true ), current( &state1 ) { }
 bool run( const char *s );
};

bool FSM::run(const char *s) {
 int len = strlen( s );
 int i = 0;
 do {
  current = current->transition( s[i] );
  if( current && current->isFinalState( ) )
   return true;
  i++;
 } while( NULL != current && i < len );
 
 return false;
}

int main() {
 char s[ ] = "3*4";
 FSM fsm;

 if( fsm.run( s ) ) {
  cout << s << " is a regular expression like \"a*b\" " << endl;
 }

 return 0;
}

malloc, free & realloc with buddy algorithm

struct m_list {
   void *address;
   unsigned int size;
   unsigned int in_use:1;
   m_list *next;
   m_list( void *_address, long _size) { size = _size; address = _address; next = NULL; in_use = 0; }
};

//1 KB buffer
char buffer[1024];

unsigned int get_next_two_power( unsigned int n ) {
   unsigned int num = 1;
   while( num < n ) {
       num <<= 1;
   }
   return num;
}

void * my_malloc( unsigned int size, m_list **memlist ) {
   if ( NULL == memlist || NULL == *memlist ) return NULL;
   int alloc_size = get_next_two_power( size );

   m_list *p = *memlist;
   while( p ) {
       if( p->in_use == 0 ) {
           if( alloc_size == p->size ) {
               p->in_use = 1;
               return p->address;
           }
           if ( alloc_size < p->size ) {
               m_list *node = new m_list(NULL, p->size >> 1);
               node->address = (void *)((int)(p->address) + (p->size >> 1));
               node->next = p->next;
               p->next = node;
               p->size = p->size >> 1;
               return my_malloc( alloc_size, memlist );
           }
       }
       p = p->next;
   }

   return NULL;
}

void merge_buddies( m_list **memlist ) {
   m_list *curr = *memlist, *next = curr;
   bool is_merge = false;
   while( curr ) {
       if( curr->in_use == 0 ) {
           if( NULL != curr->next ) {
               next = curr->next;
               if( 0 == next->in_use && (next->size == curr->size) ) {
                   curr->size += next->size;
                   curr->next = next->next;
                   is_merge = true;
                   free(next);
               }
           }
       }
       curr = curr->next;
   }
   if ( is_merge ) {
       merge_buddies( memlist );
   }
}

void my_free( void * address, m_list **memlist ) {
   if( NULL == address || NULL == memlist || NULL == *memlist ) return;
   m_list *curr = *memlist, *back, *next;

   while( curr ) {
       if( curr->address == address ) {
           curr->in_use = 0;
           merge_buddies( memlist );
           return;
       }
       curr = curr->next;
   }
}

void * my_realloc( void * address, unsigned int size, m_list **memlist ) {
 my_free(address, memlist);
 void *adr = my_malloc(size, memlist);
 memcpy(adr, address, size );

 return adr;
}

int main() {
 m_list *memlist = new m_list((void *)buffer, 1024);
 printf("buffer address:: %p\n", buffer);
 printf("memlist address:: %p\n", memlist->address);

 int *p1 = (int *)my_malloc(sizeof(int)*100, &memlist);
 for( int i = 0; i < 100; i++ ) {
  p1[i] = i;
 }

 p1 = (int *)my_realloc(p1, sizeof(int)*256, &memlist);
 for( int i = 0; i < 100; i++ ) {
  cout << p1[i] << " * ";
 }
 cout << endl;

 my_free( p1, &memlist );

 char *p2 = (char *)my_malloc(sizeof(char)*240, &memlist);
 *p2 = '\0';
 strcpy( p2, "Mustafa Veysi Soyvural\0" );
 cout << p2 << endl;
 my_free( p2, &memlist );

 return 0;
}