Sealed Macro

2009/07/05 06:50
모던 C++ 디자인이라는 책은 봐도봐도 새로운 내용이 나온다.
그책에서 건진내용중에 하나인데, 클래스가 상속을 받을때 virtual table이 그냥 생기는것이 아니라 virtual 함수가 있을때만 생긴다는것 - '단위전략'은 CRTP를 쓰기위해 다중상속을 활용하는데, 부모클래스에 virtual 함수가 있으면 부모마다 vtable이 생겨 오버헤드라는 이야기 - 이다.

나는 소멸자를 virtual로 만들지 않고 상속받을때의 무시무시함을 겪은적이 있다. 그래서 소멸자는 항상 virtual - 이것이 상속받을이유가 없는 클래스라도 - 로 하곤 했었는데, 그럴때마다 vtable을 만들거라 생각하니 찝찝했다. 그렇다고 상속을 허용하면서 소멸자를 virtual로 안하는것은 정말 귀신피하려다 호랑이 만나는꼴 당할수 있는일이라, 상속을 못받게 하는방법을 찾아보았다.

몇가지 좋은정보들을 찾았는데, 전부 비얀할아버지가 작성한것을 기반으로 하고 있고 응용버전으로 birdkr님의 템플렛버전이 있었다. 그런데 gcc에서는 friend T는 안된다. - 사실, friend T는 표준 C++  문법이 아니다.

좀더 찾아보니 Boost Mailing List 에도 비슷한 주제가 올라왔었고 friend T 문제를 어느정도 해결한 방법을사용한 최종버전도 있더라 - 저것이 표준 Boost Library로 승인되었는지는 잘 모르겠다.

하늘은 뒤지는자의 편이라 했던가. (음?)
써먹기에는 영 마음에 들지 않아서 더 뒤져보니 그럭저럭 마음에 드는 버전을 찾을수 있었다. 옮겨보면,

(Language : cpp)
#define SEALED(className) \
    className ## Sealer \
        { \
            private: className ## Sealer(){}; \
            friend class className; \
        }; \
        class className : virtual private className ## Sealer \

class SEALED(MyClass) {};

무엇보다 비록 매크로지만 - 아니, 매크로라서 - 사용에 있어서 훨씬 직관적인 장점이 있다.

프로그래밍 C++, 프로그래밍

재컴파일 속도 올리기

2009/03/25 22:45
사실 나는 컴파일이 느려서 불만이었던적은 거의 없는데 make 파일을 작성하다가 (재)컴파일 속도를 올리는 방법을 컴파일러 입장에서 생각해보게 되었다.

컴파일을 할때 .o를 새로 만들필요가 없으면 컴파일 안하는게 가장 빠른 방법일것이다. 그래서 make는 target과 src의 업데이트를 비교해 src 파일이 업데이트가 없으면 컴파일을 수행하지 않는다.(make와 그 친구들 참조)

근데 이 작업에 의외의 난관이 있는게, c에서 include 하고 있는 헤더가 변경되면 어떻게 될것인가 여부다. 즉, c파일이 변경되었는지 아닌지를 판별하기 위해서는 .c파일과 .o 파일의 시간확인만으로는 안되고 .c파일이 의존하고 있는 .h파일들과 .o 파일의 시간확인이 필요하다.

.c파일이 include하고 있는 헤더를 확인하기위해 많이 쓰는방법이 makedep같은 의존성 확인툴을 사용하는것이다. 또 다른방법으로는 gcc -M 옵션으로 include되는 의존성을 확인하는 방법이 있다. 의존성을 확인할때는 #ifdef 같은것으로 include가 제한될수 있으므로 플래그 옵션까지 넣어서 확인하는게 일반적이다.

만일 헤더가 다른 헤더를 include하고 있다면 다시 그 include하고 있는 파일까지 일일이 .o파일과 비교해봐야 할것이다. 만일 그렇게 하지 않으려면 의존성 확인은 .c파일의 헤더만 확인하고 대신에 .c파일에서는 모든 헤더를 다 써주겠다는 프로젝트 고유의 룰을 만들고 그것을 바탕으로 make 파일을 작성해 주어야 할것이다.(gcc를 사용하면 소스파일만 적어넣어주면 .c파일과 .o 파일에 관련된 모든 종속파일들을 다 보여준다. 만일 gcc -MM 옵션을 주면 시스템 헤더등은 제외한다.)

비주얼 스튜디오를 사용하면 이런 세세한 설정을 할 수는 없지만 이녀석도 사람이 만든이상 비슷한 일을 할 것이다. 잘 알려진 좀더 나은 방법으로 삼바 프로젝트에서 한것처럼 변경사항관리같은것을 해슁해서 캐싱하고 있다가 그것을 토대로 변경사항을 확인하는 방법등이 있으니 그것을 사용하고 있을지도 모르겠다.(모르긴 몰라도 이런식의 방법이 아니면 비주얼 스튜디오가 F5를 눌렀을때 번개같이 실행하는것은 납득할수 없다. 일단 변경된지를 체크해야 하는데 그것이 위에서 말한것처럼 쉽지 않기 때문이다.)

어쨌거나 이렇게 복잡하게 얽긴 헤더는 확실히 컴파일 속도를 느리게 하는 원인이다. 복잡하게 얽힌 의존성을 확인하는데 걸린 시간이 그냥 컴파일을 하는데 걸린 시간과 비슷해질지도 모를일이다. 그래서 우선 컴파일 속도를 빠르게 하려면 헤더 종속성 문제를 코딩단계에서 고려해야 한다.

만일 .o 파일이 아닌 .a 파일(즉, 라이브러리로) 만든다면, include 의존성을 확인할 필요가 없이 .a 파일과 관련된 모든 파일들과 .a 파일의 업데이트 시간만을 비교하는것으로 재컴파일을 할지를 결정할수 있다. 내가 이 방법을 써봤는데 확실한 속도 향상이 있었다.

그래서 라이브러리를 만들어내는 중간 프로젝트들을 많이 만들어 배치하는것이 전체적인 컴파일 속도를 올리는 또 다른 방법이 될 수 있다.

이런식의 테크닉들을 적용하려고 보면 makefile을 작성하는것이 정말 아스트랄해진다. 그래서 내가 선택한것은 rake였는데 굉장히 만족하면서 사용하고 있다.

아래는 앞에서 말한 로직을 만족하는 rakefile 내 함수의 일부이다.
(Language : perl)
i = 0
size = files_to_check.length
while i < size
    break unless uptodate?(target, files_to_check[i])
    i += 1
end

# do not need build
return if i == size

# need to compile
updated_objects = 0
srcs.each do | fullPath |
    #puts fullPath
    gcc_mm = "gcc -MM #{include_flags} #{fullPath}"
    result = `#{gcc_mm}`.split
    object_file = result[0].chomp(':')
    object_file.gsub!(/\.o$/, '_g.o') if @with_debug_symbol
    need_compile = uptodate?(object_file, fullPath) ? false : true
    unless need_compile
        2.upto(result.length-1) do | result_index |
            dependent_header = result[result_index]
            #puts dependent_file
            if ( dependent_header != "\\" ) \
                and ( dependent_header.include?("wxWidgets-2.8.9") == false ) \
                and ( dependent_header.include?("/usr/") == false ) \
                and ( uptodate?(object_file, dependent_header) == false )
                puts "#{object_file} will be recompiled because #{dependent_header} was changed"
                need_compile = true
            end
            break if need_compile
        end
    end
    #compile
    if need_compile
        compiler = ( fullPath.match(/.*\.cpp$/) != nil )? 'g++' : 'gcc'
        compiler << " -g -o #{object_file}" if @with_debug_symbol
        sh "#{compiler}#{include_flags} -O3 -c #{fullPath}"
    end

    lib_flags_head << ' ' + object_file
    updated_objects += 1 unless uptodate?(target, object_file)
end

전체 소스는 여기서 볼수 있다. .h와 .c 파일의 의존성은 는 gcc( -MM옵션)를 이용해 파악하고 있다. uptodate? 라는 함수가 파일간의 timestamp를 확인하는 함수이다. .a를 빌드해내는 프로젝트라면 앞에서 말한것처럼 files_to_check 라는 배열에 .a를 만드는데 관여하는 모든 파일을 넣고 그것들의 변경여부를 확인한다.

rake로 만들어 생기는 다른 장점으로는 Hudson에 연동하기가 매우 쉽다는 점이다. 내가 Hudson에 rake 작업들을 등록하고 맨 처음에 해본일이 과연 내가만든 빌드규칙과 MS의 빌드 규칙중 누가더 빠른지를 확인하는거였는데, 물론 clean상태의 컴파일 속도가 아니라 변경사항이 일부 있을때의 재컴파일 속도이다.

hudson_rake_build

위의 스샷처럼 루비 Rake를 통해 직접 작성한 gcc_debug 가 동일한 조건에서 msbuild를 이용하여 컴파일한 vc_debug 보다 6배 이상 빠르다! 흐흐.

-_- 세줄요약
1. 헤더 종속성을 고려하자
2. 라이브러리 프로젝트를 잘 활용하자.
3. rake 만세.

프로그래밍 Development, rake, 루비, 빌드

어차피 io는 느린걸

2009/02/08 17:02
C의 printf 계열보다 C++ 의 cout 등의 io 계열이 많이 느리다는건 익히 알려진 문제이다. 그런데 printf계열은 가변인자를 사용하여 printf와 비슷한 함수를 직접만드려면 어쩔수없이 va_list 계열의 매크로를 건드려야한다.

게다가 printf 계열은 버퍼오퍼플로를 막기위해 많은 변종들이 생겨나서 어떤게 표준인지 했갈리기도 한다. c99 표준이라고 알고 있는 snprintf는 Visual Studio 2008에서 조차 지원하지 않는다.

이런거 저런거 다 따져보면 차라리 C++ 계열의 io를 사용하는게 낫겠다는 생각이 들었다.
가변인자를 오버로딩으로 처리하면 formatting이 없는 경우에는 오히려 printf보다 빠르겠다는 생각도 들었다.

그래서 logger를 이런식으로 구현해봤다.
(Language : cpp)
static void log( const char* _pSzContents )
{
    onPreSetMessage_();
    pLogger_->strCurrentMessage_ = _pSzContents;
    onPostSetMessage_();
}

template< typename T0, typename T1 >
static void log( const char* _pSzContents, T0 _t0, T1 _t1 )
{
    onPreSetMessage_();
    EStringUtils::formatStr(pLogger_->strCurrentMessage_, _pSzContents, _t0, _t1);
    onPostSetMessage_();
}

template< typename T0, typename T1, typename T2 >
static void log( const char* _pSzContents, T0 _t0, T1 _t1, T2 _t2 )
{
    onPreSetMessage_();
    EStringUtils::formatStr(pLogger_->strCurrentMessage_, _pSzContents, _t0, _t1, _t2);
    onPostSetMessage_();
}
...


물론 formatStr로 비슷하게 구현되어 있다.
(Language : cpp)
template< typename T0 >
static void formatStr(std::string& _rString, const char* _pSzContents, T0 _t0 )
{
    formatStr(_rString, _pSzContents, _t0, FORMAT_INDEX_ERROR);
}

template< typename T0, typename T1 >
static void formatStr(std::string& _rString, const char* _pSzContents, T0 _t0, T1 _t1 )
{
    formatStr(_rString, _pSzContents, _t0, _t1, FORMAT_INDEX_ERROR);
}

...

static void formatStr(std::string& _rString, const char* _pSzContents, T0 _t0, T1 _t1, T2 _t2, T3 _t3, T4 _t4, T5 _t5, T6 _t6, T7 _t7 )
{
    assert(_rString.empty());
    std::vector< std::string > vBuffers;
    splitFormat_(_pSzContents, vBuffers);

    std::ostringstream oss;
    ...
   
}

뭐, 어차피 io는 느린걸...

관련 자료들
 - printf vs. cout
 - ELogger.h
 - EStringUtils.h

프로그래밍 C++, 프로그래밍

T-Rex : 작은 C++ 정규표현식 라이브러리

2009/02/07 21:25
C++에서 C# 형태의 스트링 포메팅을 지원하는 로거를 만들다보니 정규표현식을 지원하는 라이브러리가 필요하게 되었다. 유명한 boost 에 정규표현식 지원 라이브러리가 있었지만 여러프로젝트의 기반이 되는 프로젝트에 포함시킬 생각이어서 코드상태로 프로젝트에 포함될정도 작아야했다.

sf에서 뒤지다가 딱 필요한 정도의 기능만 구현되어 있는 t-rex라는 라이브러리를 발견했다. zlib 라이센스에 파일도 헤더파일, cpp파일 2개만 있으면 쓸수 있을정도로 작았고 사용방법도 아주 간단했다.

세미콜론에 비교적 안정적인 path splitter(앞뒤로 세미콜론이 있을수 있고, 세미콜론사이에 여러개의 세미콜론이 들어가도 분리가능하고 맨 끝은 세미콜론이 없어도 나누어줄수 있는) 를 요 라이브러리로 구현하면 다음과 같다.

(Language : cpp)
std::vector< std::string > vecSplittedPath;

const char* pSzContents = ";;/usr;;/opt/lib;/sbin;;/etc";
const char* pSzError = 0;
const char* pSzPattern = "[^;]+";
TRex* pRex = trex_compile(pSzPattern, &pSzError);
if(pRex)
{
    const char *pSzBegin,*pSzEnd;
    while(trex_search(pRex, pSzContents, &pSzBegin, &pSzEnd) )
    {
        TRexMatch match;
        trex_getsubexp(pRex,0,&match);
        vecSplittedPath.push_back( std::string(match.begin, match.len) );

        pSzContents = pSzEnd;
    }
}
trex_free(pRex);

프로그래밍 C++, 프로그래밍

슈퍼개발자의 길

2008/09/02 21:37
왠 낚시제목 같은 RSS피드가 떡하니 날아와서 내 썬더버드의 목록을 채우고 있길래, 파닥파닥 한번 해주는셈 치고 글을 읽어보았는데, 왠걸, 글 내용이 무척 좋다.

뭔 글이고 하니 요새 zdnet에서 하고 있는 슈퍼개발자의 길이라는 연재 기사다.

개발 2년이 갓 넘은 피덩어리인데, 찔끔찔끔 지칠때가 있다. 특히 요새같이 개강을 한다든지 해서 환경이 바뀌면 부쩍 우울해지고 꿀꿀해지는데 연재에 나오는 슈퍼개발자들 이야기를 들어보면 재미있다.

특히 좋았던글 몇개를 소개하자면,

나눔과 교육으로 날아라 : ... 그들(슈퍼개발자들)은 잘 안 풀리는 문제를 만나도, 씨익 웃어주는 여유와 함께 쉬는 시간에 사람들과 커피 한잔 하면서 최신 개그라도 하나쯤 흉내 내어 보는 그런 긍정적인 자세와 사고를 가지고 일을 한다.

기본기 없는 고수는 없다, 코드 리뷰 (Code Review)를 통해서 널리 알려라

프로그래밍을 즐기는법 : ... 이미 진행 중인 프로젝트가 있다면, 거기에 약간의 새로움을 가미해보길 바란다. 그렇다면 더 즐겁게 일할 수 있을 것이다. 물론 그 새로움이란, 자기계발과 프로젝트에 모두 도움이 되는 것으로 선택하는 것이 좋다. 그리고 작은 목표(기왕이면 측정 가능한 것)도 도움이 된다. 예를 들면 코드 품질을 나타낼 수 있는 몇 가지 방법(Code Metrics)을 적용할 수 있을 것이다.

본디, 프로그래밍은 재미있는것이다. 그런것이다.

프로그래밍 슈퍼개발자, 주저리

Inner Class의 완전(명시적) 특화

2008/09/02 20:36
C++ 템플릿 특화중에 특이한 사실중에 하나는, Inner Class의 완전특화가 C++표준이 아니라는것이다. 그래서 Inner Class를 완전특화에서 사용하면 gcc에서는 컴파일이 안된다.

회사에서 매주 월요일 점심시간 짜투리에 CodeDojo 라는 이름으로 Programming Challenges 책의 문제를 푼다.(하긴, 이것도 월요일날 학교를 가게되어서 앞으로는 하지 못할것 같다.) 문제들은 전형적인 ACM 문제유형으로 인풋이 주어지면 문제를 해결한 적절한 아웃풋을 만들어내야하는 식이다.

참여횟수가 늘어나면 인풋을 적절히 일반화를 해보고자 하여 템플릿을 사용하게 되었는데, 이를테면 인풋의 값을 string 형태로 보관한다거나 혹은 int 형태로 보관할수 있게 만들고자했다. 여기에 보통 '0 0'를 입력하면 입력을 종료한다는 조건이 붙는데 stirng형이면 zero가 char형의 '0'가 될 것이고 int 형이면 zero가 int형의 0이 되도록 하기 위해 템플릿 완전(명시적) 특화를 사용하려 하였다.

그런데 VS에서 멀쩡히 컴파일되던 녀석이 테스트 봇 - gcc를 사용한다 - 에서 컴파일이 안되어서 여기저기 알아보니 클래스 내의 Inner Class는 템플릿의 명시적 특화가 '확장이 아닌 표준을 따르면' 지원되지 않는덴다. 그래서 꼼수로 생각한게 부분특화를 사용하고 템플릿 인자에 기본인자를 사용하였더니 gcc나 VS에서 문제없이 컴파일이 되었다.

아래는 이렇게 작성된 부분특화용 Inner Class.

(Language : cpp)
//////////////////////////////////////////////////////////////////////
//
// Input Processor Interface
//
//////////////////////////////////////////////////////////////////////

class InputProcessor
{
public:

    //  break type
    enum BREAK_CONDITION
    {
        BREAK_EOF = 0,
        BREAK_ENTER,
        BREAK_ZERO,

        BREAK_TOTAL
    };

    // 생성자 / 소멸자
    InputProcessor(BREAK_CONDITION _eBreak) { eBreakCondition_ = _eBreak; }
    virtual ~InputProcessor(){}

    // 인터페이스
    virtual void  process()              = 0;
    virtual int   getDataIndexCount()    = 0;
    virtual const std::vector<int>* getDigits(int _nIndex)   = 0;
    virtual const std::vector<std::string>* getChars(int _nIndex)   = 0;

    // Test를 위한 함수
    virtual void addTestInput(const char* pSzTestData) = 0;

protected:

    // break condition
    BREAK_CONDITION  eBreakCondition_;

    // data manipulator
    // 로컬 템플릿 클래스는 명시적 특화가 허용되지 않고 부분특화만 허용됨. 그에 대한 꽁수
    // cf. 비주얼스튜디오 확장으로 로컬클래스의 명시적 특화가 허용된다.
    template< typename T, typename PartialSpecialization = bool >
    struct SDataManipulator{};
    template< typename PartialSpecialization >
    struct SDataManipulator< int, PartialSpecialization >
    {
        static int convertData(char* _pSzData){ return atoi( _pSzData ); }
        static const int getZero(){return 0;}
        static const std::vector<int>* getDigits(
                std::vector< std::vector<int>* >& _refVecData,
                int _nIndex)
        {
            return _refVecData[ _nIndex ];
        }
        static const std::vector<std::string>*  getChars(
                std::vector< std::vector<int>* >& _refVecData,
                int _nIndex)
        {
            return 0;
        }
    };
    template< typename PartialSpecialization >
    struct SDataManipulator< std::string, PartialSpecialization >
    {
        static char* convertData(char* _pSzData){ return _pSzData; }
        static const char* getZero(){ return "0";}
        static const std::vector<int>* getDigits(
                std::vector< std::vector<std::string>* >& _refVecData,
                int _nIndex)
        {
            return 0;
        }
        static const std::vector<std::string>*  getChars(
                std::vector< std::vector<std::string>* >& _refVecData,
                int _nIndex)
        {
            return _refVecData[ _nIndex ];
        }
    };

    // multiline data
    template< typename T >
    struct SInputData
    {
        // data container
        std::vector< std::vector<T>* > aVecVecData;

        // get data
        void processData(BREAK_CONDITION _eBreak, const char* _pSzManualData )
        {
            char buf[512];
            bool bLoop = true;
            while( bLoop )
            {
                if( _pSzManualData == 0 )
                {
                    // 라인으로 입력받기
                    if( gets( buf ) == 0 )
                        return;
                }
                else
                {
                    strcpy(buf, _pSzManualData);
                    bLoop = false;
                }

                std::vector<T>*  pVector = new std::vector<T>;
                char* pSzEach = strtok(buf, " ");
                while (pSzEach!= 0)
                {
                    pVector->push_back(
                                SDataManipulator<T>::convertData( pSzEach )
                    );
                    pSzEach = strtok(0, " ");
                }

                // Zero Break
                if( _eBreak == BREAK_ZERO && pVector->size() == 2 )
                {
                    if( (*pVector)[0] == SDataManipulator<T>::getZero() &&
                        (*pVector)[1] == SDataManipulator<T>::getZero() )
                    {
                        delete pVector;
                        return;
                    }
                }

                aVecVecData.push_back( pVector );

                // Enter Break
                if( _eBreak == BREAK_ENTER )
                    return;
            }
        }

        // clear data
        void clearData()
        {
            int nSize = (int)aVecVecData.size();
            for( int i = 0; i < nSize; ++i)
            {
                delete aVecVecData[i];
            }
            aVecVecData.clear();
        }
    };

};


//////////////////////////////////////////////////////////////////////
//
// Input Processor Implimentation
//
//////////////////////////////////////////////////////////////////////

template< typename T >
class InputProcessorImpl : public InputProcessor
{
public:
    InputProcessorImpl(BREAK_CONDITION _eBreak) : InputProcessor(_eBreak) {}
    virtual ~InputProcessorImpl(){ aData_.clearData(); }

    virtual void process()
    {
        if( aData_.aVecVecData.empty() == false )
                aData_.clearData();
        aData_.processData( eBreakCondition_, 0);
    }

    virtual const std::vector<int>* getDigits(int _nIndex)
    {
        if( _nIndex < 0 ||
            aData_.aVecVecData.empty() ||
            _nIndex >= getDataIndexCount() )
            return 0;

        return InputProcessor::SDataManipulator<T>::getDigits(aData_.aVecVecData, _nIndex);
    }

    virtual const std::vector<std::string>* getChars(int _nIndex)
    {
        if( _nIndex < 0 ||
             aData_.aVecVecData.empty() ||
              _nIndex >= getDataIndexCount() )
            return 0;

        return InputProcessor::SDataManipulator<T>::getChars(aData_.aVecVecData, _nIndex);
    }

    virtual int getDataIndexCount()
    {
        return (int)aData_.aVecVecData.size();
    }

    virtual void addTestInput(const char* pSzTestData)
    {
        aData_.processData(InputProcessor::BREAK_EOF, pSzTestData );
    }

private:
    InputProcessor::SInputData< T > aData_;
};

아래는 보너스로, 위의 인풋프로세스를 이용하여 푼 LCD문제. (물론 봇테스트도 통과, 최적화는 되어있지 않다)
http://www.programming-challenges.com/pg.php?page=viewsubmission&subid=211071

아래는 위의 일반화된 인풋이전에 인풋을 나누어 사용했을때 풀었던 문제 MineSweeper.
http://www.programming-challenges.com/pg.php?page=viewsubmission&subid=200889

프로그래밍 C++, 메타프로그래밍

타입리스트와 재귀적 상속

2008/07/24 22:28
(회사에서 삽질하며 만든코드인데, 쓸일이 없어져서 폐기해버려서 슬쩍 포스팅 해본다.)
그러니까, 이런걸 만들고 싶은거였다.

타입리스트에 있는 항목들을 하나씩 인스턴스로 자동으로 생성하게 하기

어떤 오브젝트가 있고 이것은 다수의 모듈들의 상호작용으로 기능을 수행한다.
그런데 모듈들을 하나하나 enum화 하는것은 귀찮은 일이다.

그래서 모듈들을 타입리스트의 묶고 이 모듈 타입리스트에 있는 항목에 대해 하나씩 인스턴스를 생성하게 하고 싶다. 문제는, 타입리스트의 메타함수 결과값들은 컴파일 시점에 만들어지므로 for문을 돌며 인스턴스를 생성하는것이 불가능하다는것.

(Language : cpp)
// 아래의 코드는 컴파일 되지 않는다.
for(int i = 0; i < TL::Length<T_TypeList>::value; ++i)
{
    m_Modules[ i ] = new TL::TypeAt< T_TypeList, i>
}


이때 예전에 봐두었던 재미난 코드가 생각이 났다.
Template Non-Type Parameter 밑에 있는, 재귀적 상속.

그렇다! N계층으로 재귀적으로 상속이 컴파일 인스턴스 되면,  생성자가 N번 불리므로, 원하는 작업을 할수 있다!

(Language : cpp)
void InitContext()
{
    // ...

    m_pMockModuleGen = new T_MockModuleGen;

    MakeUsingModule<
        T_TypeList, TL::Length<T_TypeList>::value> makeIt(m_pMockModuleGen);

    // ...
}

(Language : cpp)
template<typename T_TypeList, int i>
struct MakeUsingModule : public MakeUsingModule<T_TypeList, i-1>
{
    MakeUsingModule( MockModuleGenerator* pModuleGen)
        : MakeUsingModule<T_TypeList, i-1>(pModuleGen)
    {
        pModuleGen->CreateUsingModule< TL::TypeAt<T_TypeList, i-1>::Result >();
    }
};

template<typename T_TypeList>
struct MakeUsingModule<T_TypeList, 0>
{
    MakeUsingModule(MockModuleGenerator* pModuleGen)
    {
    }
};

타입리스트에 대응하는 for문을 발견한 위대한(!) 순간이었다.

프로그래밍 C++, 메타프로그래밍, 타입리스트

CRTP와 멤버함수포인터

2008/05/20 21:13
회사에서 네트워크 관련 라이브러리에서 CRTP를 활용할 수 있는 예가 있어서 만들어봤던 코드인데, 회사내의 정책이 바뀌어서 쓸모가 없어진 비운의 코드이다. 자랑할겸(-_-) 소스정리 해보았다. CRTP에 대해서는 예전글 참조

네트워크나 스크립트 엔진등에서 함수를 문자열을 통해 호출하는 경우가 많다. 예를들면

(Language : cpp)
CHelloPok aTestPok("Test pok on hello world 'key'...");
aTestPok.callFunc("key");
aTestPok.callFunc("id");

이런식으로 callFunc라는 메쏘드를 통해 "key"와 연결된 함수를 호출한다. 이렇게 하기 위해 일반적으로 두가지 방법을 사용한다. "key"에 연결된것이 static member 함수여서 map 자료형에 함수포인터를 담아놓거나 혹은 callFunc자체를 virtual로 두고 자식클래스 단에서 그것을 구현하는 경우다. 전자의 경우는 널리 사용되는 방법인데 멤버에 대한 접근성이 많이 부족하고 후자의 경우는 자식클래스단에서의 구현 알고리즘이 똑같은데 - 문자열에 대응하는 멤버함수를 연결 - 멤버함수마다 자료형이 달라서 어쩔수 없이 자식클래스 마다 따로 구현해야되는 문제때문에 많이 쓰이지는 않는다.

후자의 문제를 해결하기 위해 접근했던 방법이, 부모가 알고리즘을 가지고 자식의 자료형을 부모가 알고 있게 하면 어떻게 할수 있지 않을까 였고, 부모가 자식의 자료형을 알고 있게 하기 위해 CRTP를 사용하였다.

구현 소스를 보면 일단 호출 인터페이스가 있고

(Language : cpp)
class CrtpInterface
{
public:
    virtual ~CrtpInterface(){}
    virtual void callFunc(const char* _pSzFuncId) = 0;
};

그것을 상속받은 CRTP의 중간객체가 존재한다.

(Language : cpp)
template <typename T>
class CrtpImpl : public CrtpInterface
{
public:
    virtual void callFunc(const char* _pSzFuncKey)
    {
        FuncMap::iterator itr = funcMap_.find(_pSzFuncKey);
        if( itr == funcMap_.end() )
        {
            printf("Not Found '%s!'\n", _pSzFuncKey);
            return;
        }

        // call func
        (static_cast<T*>(this)->*(itr->second))();
    }

protected:
    typedef void (T::*Func)(void);
    void registerFunc(const char* _pSzFuncKey, Func _pFunc)
    {
        funcMap_[ _pSzFuncKey ] = _pFunc;
    }

private:
    typedef std::map< std::string, Func > FuncMap;
    FuncMap funcMap_;
};

몇가지 신기한 자료형이 나오는데, 메범함수 포인터 자료형은( (static_cast<T*>(this)->*(itr->second))(); ) C++의 재미있는 자료형중 하나이다. 뭐랄까.. 좀 심오한 자료형인데, 알렉산더레스쿠(-_- 맞나..)의 Modern C++ Design에 그에 대한 자세한 설명이 있다.(일반화된 Command Functor 설명부분에 있었던듯 하다.)

그리고 본격적으로 상속받아 기능을 구현하는 클래스들이 있고 그 클래스들을 활용하는 메인루프가 있을것이다.

(Language : cpp)
class CHelloWorld : public CrtpImpl< CHelloWorld >
{
public:
    CHelloWorld()
    {
        // key 라는 문자열에 CHelloWorld::helloWorld 멤버함수 연결
        registerFunc("key", &CHelloWorld::helloWorld );
    }

    void helloWorld()
    {
        printf("Hello World!\n");
    }
};

class CHelloPok : public CrtpImpl< CHelloPok >
{
public:
    CHelloPok(const char* _pSzContents) : strToSay_( _pSzContents )
    {
        // key 라는 문자열에 CHelloPok::helloPok 멤버함수 연결
        registerFunc("key", &CHelloPok::helloPok );

        // id 라는 문자열에 CHelloPok::whoAmI 멤버함수 연결
        registerFunc("id", &CHelloPok::whoAmI );
    }

    void helloPok()
    {
        printf("%s\n", strToSay_.c_str() );
    }

    void whoAmI()
    {
        printf("Hey, it's me. pok.\n\n");
    }

private:
    std::string strToSay_;
};

(Language : cpp)

int _tmain(int argc, _TCHAR* argv[])
{
    // 함수호출 테스트
    CHelloPok aTestPok("Test pok on hello world 'key'...");
    aTestPok.callFunc("key");
    aTestPok.callFunc("id");

    // 다형성 테스트
    CHelloWorld aHelloWorld;
    CHelloPok aHelloPok("Hello pok!");

    std::vector< CrtpInterface* > vecFunc;
    vecFunc.push_back(&aHelloWorld);
    vecFunc.push_back(&aHelloPok);

    for(std::vector< CrtpInterface* >::iterator itr = vecFunc.begin();
        itr != vecFunc.end(); ++itr )
    {
        (*itr)->callFunc("key");
    }
    return 0;
}

프로그래밍 C++, 프로그래밍

비트연산자를 통한 프로퍼티 구현

2008/02/29 22:53
자주 확인하지 않는 프로퍼티들이 bool 값으로 들어있는것은 아깝다. 이때는 비트연산자를 이용해서 프로퍼티들 관리하는것이 좋다.

(Language : cpp)
enum PROP
{
    PROP_1 = 1 << 1,
    PROP_2 = 1 << 2
};

int g_prop = 0;

void AddProperty(PROP _eProp)
{
    g_prop |= _eProp;
}

void RemoveProperty(PROP _eProp)
{
    g_prop &= ~_eProp;
}

bool QueryProperty(PROP _eProp)
{
    if( (g_prop & _eProp) == _eProp )
        return true;
    return false;
    // 혹은
    // return (g_prop & _eProp) ? true : false;
}

프로그래밍 C/C++, 프로그래밍

그래프 : 깊이우선 탐색

2007/12/01 20:30
그래프의 깊이우선 탐색은 트리의 순회와 비슷하다.(그러나, 그만큼 우아하지는 않은것 같다.)
트리순회와 가장 큰 차이는 "방문여부"를 판별할 수 있는 방법이 제공되어야 하는것 뿐이다.

트리와 다르게 그래프는 여러 연결 경로가 있기 때문에 들어온곳을 다시 들어올수 있다.(-_- 이게 내가 그래프 탐색이 '우아'하지 않다고 생각하는 이유다) 예전에 방문했던곳을 탐색의 거점에서 제외하는게 그래프 탐색과 트리 순회의 핵심적인 차이이고, 그 때문에 "방문여부"를 알 필요가 있다.

방문여부는 Vertex가 방문여부를 알수 있도록 멤버로 가지고 있거나, Vertex의 ID를 인덱스로 가지는 배열이나 해쉬등을 이용해 방문여부를 표시함으로써 알수 있다. Vertex가 방문여부를 가지고 있다면, 방문전(혹은 후)에 Vertex의 방문여부를 초기화 해주어야 할 뿐만이 아니라, 하나의 그래프를 여러 Thread에서 탐색할 경우 Thread Safe하지 않으므로 그리 좋은 방법은 아니라고 생각한다.

그래프 탐색에는 깊이우선 탐색과 너비우선 탐색이 있는데 깊이우선 탐색이란, 연결된 Edge중 하나를 잡아 Vertex를 방문하고, 다시 그 Vertex에 연결된 Edge를 하나잡고 (마치, 아래로 타고 내려가듯이) 다음 Vertex를 방문하는 하다가, 더이상 연결된 Edge가 없으면 위로 올라가서 다음 Edge를 방문하는 방식(물론, 다음 Edge가 없으면 다시 위로 올라간다.)이다.

깊이우선 탐색은 다시, Vertex가 다음 방문을 위해 연결된 Edge가 없을때 위로 올라가는(예전 Vertex로 돌아가는) 방식에 따라 크게 스택을 사용하는 방식과 재귀를 사용하는 방식으로 나뉜다. - 물론 재귀를 사용하는 방식이 더 우아하다고 생각한다.

다음은 깊이우선 탐색 - 스택 버전을 Ruby로 구현한 경우다. (전체소스는 여기에 있다.)
살펴볼만한 부분이, 방문여부의 판별을 위해 루비의 Hash를 이용한 부분이다. 방문여부를 셀이 가지고 있지 않기 때문에 이 깊이우선 탐색은 Thread Safe하다.

(Language : perl)
def dfsWithStack( _rStartCell )
    aCurrentCell = @aCellContainer[_rStartCell.cell_id]
    return if aCurrentCell == nil

    aMarkedCells = Hash.new
    aDepthStack = Pok::Stack.new

    #start dfs
    aDepthStack.push_back( aCurrentCell )
    print "DFS init With Cell id : " + aCurrentCell.cell_id.to_s + "\n"

    #stack loop
    while aDepthStack.empty? == false
        aCurrentCell = aDepthStack.pop_back
        next if aMarkedCells[ aCurrentCell.cell_id ] == true

        # marking
        aMarkedCells[aCurrentCell.cell_id] = true
        print "Cell id : " + aCurrentCell.cell_id.to_s + " is now visited\n"

        #Test 확인을 쉽게 하기 위해 거꾸로 push 하도록 해서 pop할때는 작은수부터 나오게
        aConnectedCells = aCurrentCell.edge_container.sort
        aConnectedCells.reverse!
        aConnectedCells.each do | id_value_array |
            #연결된 셀을 선택
            aCandidateCell = @aCellContainer[ id_value_array[0] ]
            if aMarkedCells[aCandidateCell.cell_id] == nil
                #셀이 예전에 탐색되지 않은 셀이라면, 스택에 넣어준다.
                aDepthStack.push_back(aCandidateCell)
            end
        end
    end
end


깊이우선 탐색 - 재귀버전은 방문여부를 알기위한 장치(역시, 여기서도 Hash를 사용했다)나 기타 초기화를 하는initial condition과 Base Case과 Recursive Case를 가지고 실제 재귀를 하는 Core 부분으로 나누었다.

(Language : perl)
def dfsRecursive( _rStartCell )
    aCurrentCell = @aCellContainer[_rStartCell.cell_id]
    return if aCurrentCell == nil

    aMarkedCellsContainer = Hash.new
    print "DFS(Recursive version) init With Cell id : " + aCurrentCell.cell_id.to_s + "\n"
    dfsRecursiveCore( aCurrentCell, aMarkedCellsContainer )
end

(Language : perl)
def dfsRecursiveCore( _rCell , _rMarkedCells)
    _rMarkedCells[ _rCell.cell_id ] = true
    print "Cell id : " + _rCell.cell_id.to_s + " is just now visited\n"

    #테스트 확인을 쉽게 하기 위해 셀 번호순서대로 소팅하기
    aConnectedCellsContainer = _rCell.edge_container.sort
    aConnectedCellsContainer.each do | vertex_id_weight |
        nCell_id = vertex_id_weight[0]
        if _rMarkedCells[ nCell_id ] == nil
            dfsRecursiveCore( @aCellContainer[nCell_id], _rMarkedCells )
        end
    end
end

깊이우선 탐색의 알고리듬 수행시간은 Adjacency List의 경우에 O(|v|+|E|)로 알려져 있으나 이게 뭔말인지는 모르겠고(-_-) Fundamentals of Data Structures in C 에서는 O(e)라고 소개하고 있는것과 내가 열심히 생각해본 결과(-_-)로 보아, Undirected Graph일 경우 Edge 갯수 * 2 번만큼 순회하므로 O(2E)이다. (...-_- 일것이다.)

프로그래밍 그래프, 루비, 자료구조