void** (double void pointer) 고찰

많은 API 에서 void ** 가 쓰인다.
이 void **를 한번 분석해보자

1. 다차원 포인터

int * * pI

int * * pI 포인터 변수이다

int * * pI int* 의 주소를 담는 (int**) 형의 타입이다.

2. void 포인터

보이드 포인터 타입은 모든 포인터를 대입할수 있다.
(malloc 는 void*를 리턴한다.)
단 역참조와 정수와의 주소 offset 연산이 불가능하며 같은 void 포인터 타입과 비교연산(==)가 가능하다

void * vP;

int * nP;

....

*nP <--- O 가능 int포인터로써 역참조가 가능하다.

*vP <--- X 불가능 대체 무슨타입으로 역참조를 해야한단 말인가? 컴파일러는 판단할수 없다.

*nP 는 직접적으로int의 정수에 접근이 가능하지만

위의 두 포인터 변수의 차이는 void는 형을 알수없음으로 역참조를 할수 없는데 있다.

3.void **
앞에 두 개념을 숙지하고 아래의 개념을 다시 한번 생각해보았다.

왜 void**를 쓰는가?

char* 자체를 void*로 바꿔서 생각해 보자.
void** 는 void* 의 포인터 이므로 유연하게 모든 포인터를 void*로 받을수 있다.

const char* funcMsg = "hello World";
void func(void **something)
{
    *something= (void *)funcMsg;
}
char * msg;
func((void**)&msg);
printf(msg);

KMP 알고리즘

문자열이 아닌 바이너리 모드에서 기존 STL의 문자열 탐색 라이브리는 정상 작동되지
않는다.

바이너리 속에서 특정 바이너리 패턴을 찾을 일이 있을때, 문자열 알고리즘 중에 KMP 알고리즘이 가장 효율적이다.

1.기본 개요

위 그림의 문자열 비교 처럼 문자열이 일치하지 않을때, 이미 비교한 부분의 정보를 가지고 불필요한 비교를 피하는것이 KMP알고리즘의 원리의 전부이다.

이 알고리즘을 적용하려면 패턴이 어디까지 일치하였을때, 얼마만큼 패턴을 스킵해야 할지 계산할 필요가 있다.

일치 텍스트와 패턴을 비교하지 않고 미리 패턴의 접두사와 접미사를 이용해 패턴의 접두 접미 일치표를 만들어놓고 실제 텍스트와 패턴 비교시 사용하는것이 접두 접미 일치표이다

패턴     ababaca

텍스트 bacbababaabacbab

아래의 코드를 첨부한다

#include 
#include 
#include "Kmp_Header.h"

KmpSearch::~KmpSearch()
{
 if (!m_pMatchTable)
  free(m_pMatchTable);
}
int KmpSearch::SearchKmp(Byte* text, Byte* pattern, int textLen, int patternLen)
{
 m_textLen = textLen;
 m_patternLen = patternLen;
 m_text = text;
 m_pattern = pattern;

 PrefixPI();
 Matching();
 return 1;
}
int KmpSearch::PrefixPI()
{
 m_pMatchTable = (int*)malloc(sizeof(int)*m_patternLen);

 int i = 1; //접미사 
 int j = 0; //접두사

 m_pMatchTable[0] = 0;

 while (i < m_patternLen)
 {
  if (m_text[i] == m_pattern[j])
  {
   m_pMatchTable[i] = j;
   i++;
   j++;
  }
  else if (j > 0)
  {
   j = m_pMatchTable[j - 1];
  }
  else
  {
   m_pMatchTable[i] = 0;
   i++;
  }

 }//while
 return 1;
}

int KmpSearch::Matching()
{
 int i = 0; //text index
 int j = 0; //pattern index
 while (i < m_textLen)
 {
  if (m_text[i] == m_pattern[j])
  {
   if (j + 1 == m_patternLen)
    return  i - j;
   i++;
   j++;
   
  }
  else if (j>0) //i는 고정 전 j값으로 비교 다르기 전까지 접두사 비교 일치
  {
   j = m_pMatchTable[j-1];
  }
  else
  {
   i++;
  }
   
 }
 return -1;
}

사용 방법

 PrefixPI((unsigned char*)pattern, _mbstrlen(pattern));
 int result = Matching((unsigned char*)text, _mbstrlen(text), (unsigned char*)pattern, _mbstrlen(pattern));

-참고 서적-

1. 다양한 예제로 배우는 알고리즘

(나라심하 카루만치 저 전계도, 전형일 역 인사이트 2014.02.22.)

http://book.naver.com/bookdb/book_detail.nhn?bid=7430898


2. Introduction to Algorithms.

const iterator 를 리턴하는 stl 자료구조에서 const를 푸는법

map 류의 힙형 자료구조는 정렬된 상태를 유지하기에 iterator가 const값만을 리턴한다
따라서 부득이하게 iteraotr 값을 바꿔야할 경우
템플릿 함수를 하나 만들고 아래처럼 활용한다.

template  T & unconst(const T & x)
{
   return const_cast(x);
};
 multimap myMap;
 multimap::iteraotr it;
.
.
.
unconst(*it);