/// from glibc:ostream
typedef basic_streambuf<_CharT, _Traits> __streambuf_type;
/**
 *  @brief  Base constructor.
 *
 *  This ctor is almost never called by the user directly, rather from 
 *  derived classes' initialization lists, which pass a pointer to
 *  their own stream buffer.
 */
explicit basic_ostream(__streambuf_type* __sb) { this->init(__sb); }

streambuf에 대한 기본적인 작동 방식은 cppreference를 통해 이해할 수 있다. (해당 링크의 사진을 꼭 보는 것을 추천한다.) 기본적으로 가상 함수를 통해 다형성을 지원한다. 링크에 나와있듯이, 6개의 포인터를 사용해 입출력을 관리한다. 우리가 흔히 C언어에서 (혹은 메모리를 직접 관리하는 경우에) 동적 배열을 관리하기 위해서는 3개의 포인터 값을 통해 유지할 수 있다. 첫 번째로 필요한 것은 배열의 시작점이다. 두 번째 포인터는 배열의 길이를 나타낸다. 마지막 포인터는 배열의 실제 허용하는 메모리 공간의 끝 지점을 나타낸다. 시작 점을 제외한 나머지 두 개의 값은 포인터가 아니라 정수를 사용해 표현하는 경우가 더 일반적일 것이다. 실제로 glibc의 std::vector의 구현을 살펴보아도3개의 포인터를 사용하여 공간을 표현하고 있다.

///from glibc:stl_vector.h
struct _Vector_impl_data {
    pointer _M_start;
    pointer _M_finish;
    pointer _M_end_of_storage;
}

streambuf는 입력에 해당하는 영역과 출력에 해당하는 영역을 둘 다 표기해야 하므로 두 배인 6개의 포인터를 사용한다. 입력에 해당하는 영역은 get 영역이라고 부르고 출력에 해당하는 영역은 put 영역이라고 부른다. 이러한 6개의 포인터를 관리하면서 인터페이스(streambuf)에 맞는 함수를 오버라이드해서 구현하면 ostream/istream에서 사용할 입출력 처리 로직을 자요롭게 사용할 수 있다. 이 글에선 std::stringstream에서 사용하고 있는 std::stringbuf의 glibc 구현체를 살펴봄으로써 streambuf를 이해하는 것이 목표이다.

소스 코드는 gcc-mirror github의 release/gcc-11.1.0 태그에서 수집된 결과물이며, raw.githubusercontent.com을 임베드 하였다.

std::stringstream and std::stringbuf

ostream이 basic_ostream<char>의 aliasing 이듯이 std::stringbuf도 std::basic_streambuf<char>의 aliasing이다. std::stringbuf는 이름 그대로 내부에 유지하고 있는 입출력 영역은 std::string으로 관리하고 있다. std::string에 6개의 포인터를 어떻게 설정하는지 보기 전에 먼저 overflow에 대한 함수를 보고 가려고 한다. overflow는 이름 그대로 버퍼가 꽉 찬 경우 출력을 하기 위해 호출되는 함수이다. 정확히는 pptr이 nullptr이거나 pptr이 epptr보다 크거나 같을 때 출력된다. 후자가 버퍼가 꽉찼다고 인지하는 경우이다. 상위 클래스인 std::streambuf가 put 영역의 3개의 포인터를 임의로 사용하여 출력을 하다가 끝 지점에 도달했을 경우 이 virtual 함수를 호출하여 처리한다. overflow의 구현체는 sstream.tcc에 존재한다. (CXX11_ABI는 꺼져있는 것으로 간주한다.)

먼저 현재 스트림의 모드가 out이거나 입력으로 준 값이 EOF(end of file) 값일 경우는 스펙에 맞는 값을 즉시 리턴한다. __testput 변수는 스트림의 pptr값과 epptr값을 비교한다. pptr 값은 put area 배열의 현재 끝 점을 나타내고, epptr은 put area의 capacity 관점에서 끝을 나타낸다. pptr이 epptr 미만이라면, 즉 __testput이 true 라는 것은 capacity를 늘리지 않아도 입력 값 c 를 put area에 넣을 수 있다는 것이다. 따라서 함수 하단 부의 else 영역을 보면 단순히 현재 pptr에 입력 값을 넣고 있다. 만약, false라면 capacity를 늘릴 필요가 있다. 일반적으로 배열을 늘리는 경우와 유사하게 새로운 배열 영역의 길이를 계산하고 그 길이의 string객체를 __tmp 로생성한다. 그 후 assign을 통해 pbase부터 pptr까지 다시말해 기존 버퍼에 있던 내용을 복사한다. 그 다음 새로운 버퍼에 입력 값 c 를 넣고 _M_sync함수를 통해 pbase, pptr, 그리고 epptr 같은 값을 동기화를 시킨다. 위 두 경우에 대해 출력을 처리한 후에는 pbump를 통해 epptr 값을 한 칸 전진시킨다.

다음으로 확인할 것은 overflow와 반대 개념인 underflow 함수이다. 마찬가지로입력 버퍼가 비어있을 경우 호출된다. 여기서도 정확히는 gptr 값이 nullptr이거나 gptr이 egptr보다 크거나 같을 때 호출되고 후자의 경우가 입력 버퍼가 비어있을 경우이다. underflow 구현체 역시 sstream.tcc에 존재한다.

underflow 자체는 단순하다. 현재 스트림의 모드가 in일 경우 진짜로 string의 끝에도달하였는지 확인한다. _M_update_egptr 함수를 통해 string의 내부 배열 구간과 get area를 동기화 시킨 뒤 get area에 내용이 더 있으면 해당 값을 반환한다.

지금까지 입출력에서 중요한 역할을 하는 두 함수를 살펴보았다. 여기서 더 나아가 두 함수에서 사용하고 있는 내부 함수들에 대해서도 볼 가치가 있다. 먼저 _M_sync 이다. 이 함수는 overflow에서 기존 string객체의 공간이 부족해 새로운 string 객체를 만들어 그 것을 내부 버퍼로 사용할 때 불린 함수이다. 또한 setbuf 함수나 객체의 생성자에서 초기화 할 때 불리는 함수이기도 하다. 한마디로 하자면 6개의 포인터를 내부 버퍼에 맞추는 작업을 하는 함수이다. _M_sync 구현체는 다음과 같다.

overflow에서는 첫 번째 인자로 버퍼 string의 data를, 두 번째 인자로 gptr - eback 값을, 세 번째 인자로 pptr - pbase 값을 인자로 넣었다. 두 번째 인자 __i 는 get area의 현재 위치와 버퍼 시작 지점의 차이의 길이를 나타내고 세 번째 인자 __o 는 put area의 길이를 나타낸다. 따라서 get area의 세 포인터 eback, gptr, egptr을 각각 string의 data, 입력으로 준 기존 gtpr - eback 값 그리고 string의 size 값으로 설정한다. put area의 경우 세 포인터 pbase, pptr, epptr을 각각 string의 data, string의 capacity 그리고 string의 size 값으로 설정한다.  setg와 달리 setp의 경우 pbase와 pptr만 지정할 수 있고 pptr은 pbump를 통해서 전진해야하는데 basic_streambuf의 pbump의 인자가 int 여서 발생하는 문제를 해결하기 위한 또다른 내부 함수가 _M_pbump 는 __size_type이다.

두 번째로 볼 내부 함수는 underflow에서 사용했던 _M_update_egptr 이다. 이 함수는 sstream에 직접 들어있다.

pptr이 egptr보다 크다면, 즉 get area의 버퍼의 끝 지점이 put area의 길이의 끝 지점보다 작다면 get area에서 고려하지 못한 내용이 string에 더 있다는 것이다. 그렇다면 egptr 값을 pptr 값으로 바꿔 더 읽을 내용이 있다는 것을 나타낸다. stream의 시작 시점의 내부 string 버퍼의 길이가 10이라고 가정해서 egptr을 그 당시의 string 길이의 끝 지점으로 설정 한 뒤 출력을 진행하여 실제 string 버퍼에추가 내용을 넣을 때 egptr 값을 바로 바꾸는 것이 아니라, egptr은 여전히 길이가 10인 시점의 값으로 유지하고 있다가 필요할 때 확인하여 본래 값으로 맞춰 주는 작업을 하는 것이다.

std::istream and std::ostream

std::stringstream은 std::string을 std::streambuf로 사용하는 부분에 대한 추가적인 로직을 담당하고 실제로 입출력을 사용할 때 호출하는 함수 operator<<와 operator>>는 각각 std::basic_ostream과 std::basic_istream에 선언 및 정의되어 있다. 여러가지 에러 처리나 동기화 등을 위한 추가 함수가 많은데, 먼저 ostream에 문자열을 출력하는 함수를 보자.

__ostream_insert 는 bits/ostream_insert.h에 정의되어 있고 내용은 다음과 같다.

여러 에러 케이스를 처리하는 코드를 제외하면 실졸 사용하는 함수는 __ostream_write 이고, 해당 함수는 단순히 rdbuf()->sputn(str, legnth) 를 호출할 뿐이다. 해당 함수는 basic_streambuf에 정의되어 있고, xputn에 대한 NVI(non-virtual interface)이다. basic_streambuf는 xputn을 따로 구현하지 않았으므로 basic_streambuf의 xputn을 살펴보면 다음과 같다.

여기서 부터는 위에서 다루었던 개념을 사용하여 출력을 처리한다. epptr과 pptr을 통해 남아있는 버퍼의 영역을 확인하고, 버퍼의 영역에 가능한 만큼 출력한다. 그 후 양이 남아있다면 overflow함수를 사용한다. 더이상 출력할 수 없다면 출력한 만큼의 길이를 반환하고, 그 위의 함수에서 badbit 설정하는 등 출력에 실패한 경우에 대해 처리한다.

버퍼로 부터 문자열을 입력받는 경우는 약간 더 복잡하니 코드는 생략하고 핵심이 되는 함수만 살펴보자. 실제로 입력을 얻어오는 함수는 snextc 이다.  snextc는 여러가지 경우에 따라 작동한다. 먼저 sbumpc의 반환값이 EOF가 아닐 경우 sgetc를 호출한다. sgetc 함수는 gptr이 egptr보다 작다면 get area에 더 읽을 내용이 남아 있다는 뜻이므로 gptr을 접근하여 그 값을 반환한다. 만약 아니라면 위에서 설명한 underflow를 호출하고 그 값을 반환한다. sbumpc는 마찬가지로 gptr이 egptr보다 작다면 gptr를 읽고 그 값을 반환하고, gbump를 통해 gptr값을 1만큼 증가시킨다. 만약 아니라면 uflow 함수를 호출한다. uflow함수는 underflow를 호출하여 그 값이 EOF가 아니라면 gptr에서 값을 읽고 반환한 뒤 gptr값을 1만큼 증가시킨다. 위 함수들이 비슷하다는 사실을 알아 차렸을 것이다. uflow는 underflow를 호출한 뒤 gptr을 증가시키는 차이가 있고, sbumpc는 sgetc와 달리 gptr을 접근 한 뒤 gptr 값을 증가시키는 차이가 역시 존재한다.

실제로 stream들은 단순히 데이터를 읽고 출력하는 것이 아니라 포맷에 맞춰 출력을 하거나 문자열이 아닌 정수 등을 출력하는 역할도 한다. 근본적으로 해당 기능들은 가장 기본적인 데이터를 읽고 쓰는 과정을 포함하기 때문에 일반적으로 상상하는 과정들이 있을 것이라 추측할 수 있다. 위에서 코드를 보여주지 않고 넘어간 버퍼로 부터문자열을 입력받는 경우를 예시로 살펴보면, 동기화에 관련된 코드나 width에 관한 코드 등이 있다. locale 기능의 std::num_get 같은 클래스를 살펴봐도 좋다. 실제로 stream의 모든 문자열 처리를 locale을 바탕으로 하고 있기 때문에 이를 사실 지나칠 수 없다.

결론

이 글에서 C++의 기본 입출력 컨셉인 stream에서 어떻게 실제로 데이터 값을 읽고 쓰는지 살펴보았다. boost의 iostreams 역시 overflow와 underflow를 포함한 내용을 구현하여 std::iostream의 테두리 안에서 작동하고 있다. boost는 더 나아가 컨셉을 새로 만들어 그 컨셉을 사용한 adpater를 바탕으로 커스텀한 streambuf가 구현되어 있다. 이 개념들을 활용하여 커스텀한 streambuf를 사용하여 나만의 입출력 처리 방법을 구현할 수 있을 것이다.

MBR(Minimum Bounding Rectangle)은 geometry 정보를 간략하게 표현하기 위한 방법 중 하나이다. 어떤 geoemtry의 MBR은 각 차원 별 geometry에 속한 좌표들의 최솟값(min)과 최댓값(max) 정보를 유지하게 되므로, n차원 geometry의 경우 2 * n개의 정보를 유지하게 된다. 일반적으로 2차원을 사용하는 경우가 많으므로 2차원 MBR을 아래 글에서 서술할 때 사용한다. 임의의 2차원 MBR \( m \) 에 대해 최솟값과 최댓값 정보를 나타낼 때 \( m = \{m^x_{min}, m^x_{max}, m^y_{min}, m^y_{max}\} \)와 같은 기호를 사용할 것이다.

R-Tree의 leaf node는 복수의 어떤 geometry의 MBR과 주소 (또는 개체의 ref 값)를 갖는다. Branch node는 다른 트리 구조처럼 여러 children node들을 유지하고 있다. 이 때 한 child node를 나타내기 위해 leaf node처럼 그 child node의 MBR 값과 주소를 갖는다. 한 node의 MBR이란 그 node (와 그 이하의 subtree)가 가지고 있는 모든 객체들의 MBR을 의미한다.

R-Tree는 높이 균형(height balanced) 트리이므로 삽입 도중에서 어떤 노드의 분할(split)이 일어날 수 있다. R-Tree 탐색은 B-Tree와 달리 multipath로 이루어지기 때문에 노드의 분할이 효율적이지 않는다면 탐색 속도의 결과가 좋지 않을 것이라고 확인할 수 있다. 따라서 여러 node splitting 알고리즘이 제안되었고, ^{[2] [3] [4]} 본 글에서는 최근 A. Korotkov가 제시한 새로운 splitting 알고리즘을 제시한다. ^[5] 해당 알고리즘은 현재 PostGIS에서 사용하고 있는 알고리즘 이다.

알고리즘 소개

R-Tree node splitting 문제를 다르게 서술하면 다음과 같다. MBR의 집합 I가 주어질 때, I의 모든 원소를 두 집합 \( S_1 \) 와 \( S_2 \) 로 나누는 문제이다. 일부 R-Tree variant 중에 한 MBR이 서로 다른 두 개의 node에 속하는 경우도 있으나, A. Korotkov의 알고리즘에서는 허용하지 않으므로, \( S_1 \)와 \( S_2 \) 는 상호 배타적이다.

이 알고리즘은 기본적으로 1차원 구간에 대해서 동작하지만, 다차원일 경우 각 차원별로 projection을 수행한 뒤 동일한 알고리즘을 수행함으로써 다차원 MBR 분할이 가능하다. 2차원의 MBR이 흔히 사용되므로 알고리즘을 서술할 때 2차원을 가정한다. 또한 알고리즘의 입력인 MBR의 집합 I의 크기는 n이라고 하자; \( (|I| = n). \) 2차원 MBR을 x축으로 projection 하게 되면, \( (x_{min}, x_{max}) \) 와 같은 구간으로 표현할 수 있다. 알고리즘의 가장 첫번째 과정은 \( x_{min} \) 한번 정렬을 하고 \( x_{max} \)로도 한번 정렬을 하는 것이다. \( x_{min} \)으로 정렬한 MBR 순서를 \( L=\{l_1, l_2, \cdots , l_n \} \)이라 하고, \( x_{max} \)로 정렬한 MBR 순서를 \( U=\{u_1, u_2, \cdots , u_n \} \) 라고 하자. 물론 각각의 \( l_k \) 와 \( u_k \) 는 1차원 interval이므로, min과 max로 나타낼 수 있는 두 수의 쌍으로 표현된다; \( ( 1 \ge k \land k \ge n ) \).

이 알고리즘의 입력은 1차원 구간이므로 출력은 2개의 구간이라고 가정해도 무방하다. (각 원소를 어느 구간에 넣을지 확인하는 작업은 쉬운 작업이다.) 이 중, 둘 중 적어도 1개의 구간의 최솟값(min)은 입력 집합 \( I \) 의 모든 구간의 하한의 최솟값(minimum of lower bound; \( low_{min} = \min_{i \in I} i_{min} \) )과 일치하고 마찬가지로 적어도 1개의 구간의 최댓값(max)은 상한의 최댓값(maximum of upper bound; \( upp_{max} = \max_{i \in I} i_{max} \))과 일치한다고 할 수 있다. 따라서 알고리즘의 결과는 구간 2개 \( (low_{min}, a) \)와 \( (b, upp_{max} ) \)이고, 다시 말하면 a와 b를 정하는 작업이라고 할 수 있다.

\(a\)와 \(b\) 값은 \(L\)와 \(U\)를 각각 반복하여 총 2번의 반복문을 통해 얻어낸다. 먼저 \(L\)을 기준으로 \(b\)의 값을 정한다. 정하는 방법은 다음과 같다. 첫번째 반복문에선 각 iteration마다 순서 \(L\)의 원소들의 distinct \(min\)값들이 \(b\)가 된다. 이 때 대응하는 \( a \) 의 값은 \( b \)보다 작은 \(min\)을 갖는 \(L\)의 원소들의 \(max\) 값 중 가장 큰 값이다.

\[ a  := \max_{i \in I : i_{min} < b} i_{max}  \]

또한 여기에 덧붙여 \( (low_{min}, a) \)에 속할 입력 구간의 최소 개수 \( n_{min} \)와 최대 개수 \( n_{max} \)도 정해지는데 이는 \(b\)보다 작은 min를 갖는 원소의 개수와 \(a\)보다 작거나 같은 max를 갖는 원소의 개수로 정해진다. 즉, 다음과 같다.

\[ n_{min} := \vert\{i \in I \mid i_{min} < b \}\vert\]

\[ n_{max}  := \vert\{i \in I \mid i_{max} \le a \}\vert\]

이를 다음 예제와 함께 살펴보자. 알고리즘의 입력 I가 다음과 같이 주어졌다고 하자.

\[ I = \{ (1, 4) , (2, 3), (2, 5), (4, 7), (6, 8) , (6, 9), (7, 8) \} \]

정렬을 하면 다음과 같다:

\[ L = \{ (1, 4), (2, 3), (2, 5), (4, 7), (6, 8), (6, 9), (7, 8) \} \]

\[ U = \{ (2, 3), (1, 4), (2, 5), (4, 7), (6, 8), (7, 8), (6, 9) \} \]

첫 iteration에서는 \( b = 1\)이지만 상응하는 a가 정의되지 않으므로 다음 값인 2부터 시작한다. \(b = 2 \)일 경우, \( I \)의 집합 중 min이 \(2\)보다 작은 원소는 \( \{ (1, 4) \} \) 이고 이 중 max의 최댓값은 4 이므로 \(a = 4\)가 된다. \( n_{min} \) 역시 자연스럽게 \( 1 \)이 된다. 다시 살펴보면 이미 \( L \)이 min을 기준으로 정렬 되어있고 iteration은 distinct min을 기준으로 반복하기 때문에 \( L \)을 순서대로 반복하는 것으로 충분하다. 다시 첫 번째 iteration으로 돌아와서 정해지는 값을 보면 다음과 같다; \( a = 4, b = 2, n_{min} = 1, n_{max} = 2\). \(n_{max}\)의 경우 \( L \)만 가지고는 쉽게 확인할 수 없고, \( U \) 를 통해 \( a = 4 \)보다 작거나 같은 max를 갖는 구간의 개수를 파악하면 된다. 이렇게 한 이터레이션에서 후보 군을 찾았으면 considerSplit라는 서브알고리즘을 통해 실제 split을 시도해보게 된다. 해당 알고리즘은 별도 section에서 서술한다.

다음 iteration부터 차례대로 a와 b값은 \( (a=5, b=4), (a=7, b=6), (a=9, b=7)\)로 선택할 것이다. 상세한 예시를 통해 바로 다음 iteration을 살펴보자. 이전 iteration에서 \( b= 2 \)로 선택했으므로 다음 distinct min 값은 \( 4 \) 이다. 따라서 \(b = 4\)로 선택하고, \(a\)의 값은 \( \{ (1,4), (2,3), (2,5) \} \) 중 가장 큰 max 값인 \( 5 \)로 설정된다. 자연스럽게 \( n_{min} = 3, n_{max} = 3 \) 으로 정해진다. ( \(a = 5) \) 보다 작거나 같은 max를 갖는 원소들은 \( \{ (2, 3), (1, 4), (2,5) \} \)이고 개수는 3개이다.) 역시 마찬가지로 각 iteration 마다 찾은 후보 군에 대해 considerSplit라는 서브 알고리즘을 수행한다.

두 번째 반복에서는 \( a \)값을 distinct max 값에 대해서 진행한다. 첫 반복문이 \( L \)위에서 반복문을 진행하며 \( b \)값을 결정했다면, 이후는 \( U \)위에서 뒤에서 반복문을 진행하며 \( a \)값을 결정하는 형태이다. 비슷하게 이 때 \( a \)에 대응하는 \( b \)의 값은 다음과 같이 정의된다. \( L \) 원소 중 \(max\)값이 \( a \)보다 큰 원소들의 \( min \) 값의 최소이다.

\[ b  := \min_{i \in I : i_{max} > a} i_{min}  \]

마찬가지로 \( a = 9 \) 값 다음인 \( a = 8 \)부터 시작한다. \( a = 8 \) 일 경우 \( max \)가 \( a \)보다 큰 원소 집합은 \( \{ (6, 9) \} \)이고, 이 집합에서 \( min \)값의 최소는 \(6\)이므로 \(b = 6\)이다. \( (low_{min}, a) \)에 속할 입력 구간의 최소 개수 \( n_{min} \)와 최대 개수 \( n_{max} \)는 이전 반복과 동일하게 정의된다. 이 경우 \( b = 6 \)보다 min이 작은 원소의 개수는 4개이므로 \( n_{min}= 4\) 이고 \( a = 8\) 보다 max가 작거나 같은 원소의 개수는 6개이므로 \( n_{max} = 6 \)이다. 이후 정해지는 값은 마찬가지로 \( a = 7 , b = 4 , n_{min} = 3, n_{max} = 4\) 가 될 것이다.

위 방법은 두 번의 반복이 각각 \( min \)과 \( max \)로 정렬된 배열 \(L\)과 \(U\)을 따라 순회함으로써 쉽게 구현할 수 있을 것이다. 첫 번째 반복에서 distinct min을 고를 때 \(L\)에서 카운터(인덱스)를 증가시켜가며 다른 값이 나올 때 까지 증가하며 현재 max값을 유지하면 \( a \) 와 \(b\)를 쉽게 찾을 수 있고, \( n_{min} \)은 그 당시 카운터의 개수와 일치하게 된다. \( n_{max} \)의 경우는 따로 찾아야 하는데, \(U\)를 따라 순회하면 \( a \)보다 max가 작거나 같은 원소의 개수를 쉽게 찾을 수 있다. 두 번째 반복에서는 유사하게 \( U \)를 따라 distinc max를 고를 때 인덱스를 감소시켜가며 진행하면 될 것이다. 이 방법은 A. Korotkov가 pseudo-code로 제시한 방법이며, 현재 postGIS에서도 R-Tree split 함수에 같은 접근법을 사용하고 있다.

considerSplit

위 반복에서 후보를 찾게 되면 해당 후보의 cost를 계산하고 현재 유지하고 있는 후보보다 좋다면 입력 후보를 선택하게 된다. 본래 R-Tree에는 각 node의 최소 degree가 존재한다. 즉, 두 개의 출력 집합의 원소의 개수는 하한이 있는 것이다. 이 과정에서 너무 치우친 split 후보를 금지한다. 이러한 조건을 만족시킨 후보를 유효하다고 하자. 후보마다 호출되는 considerSplit 함수는 해당 후보가 유효한지 살펴보고, 유효한 후보군 중 가장 좋은 후보를 찾는 함수이다. 여기서 가장 좋은 후보란 겹친 영역(overlapping area)가 가장 적은 후보를 지칭한다.

\( n_{min} \) 및 \( n_{max} \) 은 \( (low_{min}, a) \)의 최소 및 최대 원소의 개수를 의미할 뿐이므로, 실제로 \( (low_{min}, a) \)구간에 몇 개의 원소를 넣을지 계산해야 한다. 이를 \( n_{low} \) 라고 지칭하자. \( n_{min} \) 이 전체 개수의 절반을 넘는다면 \( n_{low} = n_{min} \) 이다. 아닐 경우 \( n_{max} \) 가 전체 개수의 절반을 넘지 않는다면 \( n_{low} = n_{max} \) 이고 그 외의 경우는 전체 개수의 절반으로 설정된다. \( (b, upp_{max} ) \) 에 속할 원소의 개수는 자연스럽게 정의된다. 이 후 겹친 영역을 계산하는데 이는 다음과 같이 정의된다.

\[ \frac{a - b}{upp_{max} - low_{min}} \]

겹친 영역 값을 바탕으로 최소가 되는 후보를 선택하면 완료된다.

결론

이 글에서는 R-Tree의 node split 방법 중 하나인 A. Korotkov의 알고리즘을 살펴보았다. 기본적으로 1차원 구간에 대한 알고리즘이지만 각 축 별로 독립적으로 수행할 수 있으므로 다차원 구간에 대해서도 동작하고 또한 A. Korotkov의 실험결과 기존 R*-Tree 방법에 비해 좋은 성능을 보여주는 것으로 확인된다.

Reference

PostGIS 3.0.0 source (git repository) (code)

Bibliography

1. A. Guttman. R-trees: A dynamic index structure for spatial searching. SIGMOD Rec., 14(2):47–57, June 1984.
2. D. Greene. An implementation and performance analysis of spatial dataaccess methods. In Proceedings. Fifth International Conference on Data Engineering , pages 606–615, 1989.
3. C. H. Ang and T. C. Tan. New linear node splitting algorithm for R-trees. In M. Scholl and A. Voisard, editors, Advances in Spatial Databases, pages 337–349, Berlin, Heidelberg, 1997. Springer Berlin Heidelberg.
4. N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: An efficient and robust access method for points and rectangles. In Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, SIGMOD ’90, page 322–331, New York, NY, USA, 1990. Association for Computing Machinery.  
5. A. Korotkov, A new double sorting-based node splitting algorithm for R-tree. Program Comput Soft 38, 109–118 (2012).

constexpr 함수와 constexpr static 변수를 사용하여 컴파일 타임에 계산하는 global객체 하나를 생성한다. constexpr 함수로 실제 값을 계산하고, index_sequence를 사용해 해당 값으로 배열을 초기화 한다. 여기에 나와있는 index_sequence를 사용한다면 C++11에서도 사용할 수 있다. 배열의 크기는 해당 타입이 나타낼 수 있는 최대 수의 log_10 값 이어야 하는데, 정수라면 std::numeric_limits에 있는 digits10 값을 이용하면 된다. (부동소수점의 digits10은 fraction 부분에 해당하는 값이므로 따로 계산해야 한다.) 이를 코드로 표현하면 다음과 같다.

pow10_fast_tmp는 constexpr 함수이므로 컴파일 타임에 수행될 수 있다. 즉,

std::array<int, pow10_fast_tmp<size_t>(3)> arr

와 같이 사용할 수 있다.

벤치 마크

위에서 생성한 테이블을 활용한 pow 계산 (사실상 접근)과 실제 값 계산을 비교해 보자. 다음과 같은 테스트 코드를 통해 수행시간을 확인하였다.

결과

i7-8700 환경에서 다음과 같은 옵션으로 컴파일 후 실행하였다. (clang version 6.0.0-1ubuntu2 (tags/RELEASE_600/final))

clang++ -std=c++14 -O2 pow_table.cpp

100000000 번 pow를 했을 때, std::pow의 경우 3000ms 근처, 미리 계산한 테이블의 경우 30ms 정도가 소요되었다.

TODO: Table for Floating Point Types

수정 후 double 타입 등에서도 동작할 수 있게 해보자.

std::integer_sequence의 원리는 std::tuple과 유사하게 parameter pack을 사용한다. tuple의 구현을 먼저 간단 살펴보면 다음과 같다. (gnu)

template<typename... _Elements>
class tuple : public _Tuple_impl<0, _Elements...> {};

template<std::size_t _Idx, typename _Head, typename... _Tail>
struct _Tuple_impl<_Idx, _Head, _Tail...>
  : public _Tuple_impl<_Idx + 1, _Tail...>,
    private _Head_base<_Idx, _Head> {};

template<std::size_t _Idx, typename _Head>
struct _Tuple_impl<_Idx, _Head>
  : private _Head_base<_Idx, _Head> {};  

_Head_base는 tuple의 각각의 아이템을 저장하는 클래스이므로 무시하면, variadic template의 인자들을 한 개씩 풀면서 (그리고 size_t 형식의 _Idx 값을 1씩 증가하면서) 반복적으로 상속을 통해 처리하고 있다. 여기서 템플릿 인자들이 타입을 나타내는 지정자 였지만, 숫자를 나타내는 값일 수 도 있다. 인자들이 모두 같은 타입의 숫자 값인 클래스가 integer_sequence 이다. 그러나, integer_sequence는 그저 숫자 값을 나타낼 뿐인데 어떻게 활용할 수 있을까? 이를 보조해 주는 것이 std::make_integer_sequence 라는 보조 클래스의 역할이다.

make_integer_sequence

make_integer_sequence는 어떤 값을 넣으면 그 값에 해당하는 수열을 담는 integer_sequence를 만들어 준다. (정확히는 그러한 클래스의 aliasing이 된다.) 예를 들면 다음과 같다.

std::make_integer_sequence<size_t, 10>
//==
std::integer_sequence<size_t, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9>

tuple과 유사하게 템플릿 인자들을 반복적으로 처리하며 aliasing을 반복 시키면 만들 수 있다는 것을 짐작할 수 있다. 서두에서 링크해둔 gist의 snippet의 코드를 보면 이를 쉽게 확인할 수 있다.

template<typename T, std::size_t N, T... Is>
struct make_integer_sequence : make_integer_sequence<T, N-1, N-1, Is...> {};
	
template<typename T, T... Is>
struct make_integer_sequence<T, 0, Is...> : integer_sequence<T, Is...> {};

template<typename T, T... Ints>
struct integer_sequence {
    typedef T value_type;
    static constexpr std::size_t size() { return sizeof...(Ints); }
};

이 코드를 바탕으로, 위 예제를 풀어나가면 다음과 같을 것이다.

std::make_integer_sequence<size_t, 10>
//=>
std::make_integer_sequence<size_t, 9, 9>
//=>
std::make_integer_sequence<size_t, 8, 8, 9>
//=>
//...
//=>
std::make_integer_sequence<size_t, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9>
//=>
std::make_integer_sequence<size_t, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9>
//=>
std::integer_sequence<size_t, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9>

gnu 계열에서는 이를 순차적으로 반복하지 않고 매번 절반으로 나누면서 컴파일 속도의 상승을 추구하는 것으로 추측된다. std::make_integer_sequence<size_t, 10>을 처리할 때, gnu에서는 _Build_index_tuple<5> 까지만 클래스를 정의해도 된다.

template<size_t... _Ind1, size_t... _Ind2>
struct _Itup_cat<_Index_tuple<_Ind1...>, _Index_tuple<_Ind2...>> {
    using __type = _Index_tuple<_Ind1..., (_Ind2 + sizeof...(_Ind1))...>;
};

template<size_t _Num>
struct _Build_index_tuple
    : _Itup_cat<
          typename _Build_index_tuple<_Num / 2>::__type,
	      typename _Build_index_tuple<_Num - _Num / 2>::__type
    > { };

작동 방식을 알아봤으니 이제 이를 어떻게 활용할 수 있는지 살펴보자. std::array를 std::tuple로 바꾸거나, std::tuple을 출력하는 함수를 작성하는 등의 예제는 cppreference에서 찾을 수 있으므로, 다른 없는 예제를 참고해 본다.

Instantiate std::array<T, N> and fill it in compile time

가장 쉬운 예제 중 하나는 std::array값을 균일한 값으로 채운 뒤 생성하는 것이다. 다음 코드를 보자. std::array를 출력하기 위한 함수는 cppreference의 것을 차용했다. 대신 C++14에도 돌아갈 수 있도록 재귀로 처리하였다. (본래 std::tuple 출력하는 함수를C++17의 fold expression을 통해 구현해 놓은 코드였다.)

template<class T, size_t... Is>
constexpr std::array<T, sizeof...(Is)>
array_with_one(const T& value, std::index_sequence<Is...>) {
  return {{(static_cast<void>(Is), value)...}};
}

template<class Ch, class Tr, class Arr>
void print_impl(std::basic_ostream<Ch,Tr>& os,
                const Arr& t,
                std::index_sequence<>) {  
}

template<class Ch, class Tr, class Arr, std::size_t I, std::size_t... Is>
void print_impl(std::basic_ostream<Ch,Tr>& os,
                const Arr& t,
                std::index_sequence<I, Is...>) {  
  os << (I == 0? "" : ", ") << t[I];
  print_impl(os, t, std::index_sequence<Is...>{});
}

template<class Ch, class Tr, class Ty, size_t ArrSize>
auto& operator<<(std::basic_ostream<Ch, Tr>& os,
                 const std::array<Ty, ArrSize>& t)
{
  os << "[";
  print_impl(os, t, std::make_index_sequence<ArrSize>{});
  return os << "]";
}

int main() {
  auto arr = array_with_one<double>(12.0, std::make_index_sequence<8>{});

  std::cout << arr << std::endl;
  return 0;
}
// output:
// [12, 12, 12, 12, 12, 12, 12, 12]

array_with_one 함수는 T 타입의 값 한 개와 index_sequence를 받아서 T로 초기화된 index_sequence의 크기 만큼의 T의 배열을 반환한다. array_with_one 함수를 수정하면 다음과 같은 경우도 가능하다.

template<class T, class I>
inline constexpr T pow(const T base, I exp) {
  static_assert(std::is_integral<I>::value, "Integral required in pow.");
  return     (exp == 0) ? 1 :
         (exp % 2 == 0) ?
           pow(base, exp/2)*pow(base, exp/2) :
           base * pow(base, (exp-1)/2) * pow(base, (exp-1)/2);
}

template<class T, class I>
inline constexpr T pow2(I exp) {
  return     (exp == 0) ? 1 :
         (exp % 2 == 0) ?
           pow2<T>(exp/2)*pow2<T>(exp/2) :
           2 * pow2<T>((exp-1)/2) * pow2<T>((exp-1)/2);
}

template<class T, size_t... Is>
constexpr std::array<T, sizeof...(Is)>
array_with_pow(std::index_sequence<Is...>) {
  return {{(pow2<T>(Is + 1))...}};
}

int main() {
  auto arr = array_with_pow<double>(std::make_index_sequence<10>{});

  std::cout << arr << std::endl;
  return 0;
}
// output:
// [2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]

인자로 들어온 T의 값을 그대로 사용하는 대신에, integer_sequence의 template 들을 한 개씩 다른 함수의 인자로 사용하여 함수의 리턴값으로 이루어진 array객체를 만들어 내었다.

Concatenate two std::arrays

integer_sequence는 2개 이상을 동시에 사용할 수 있다. 이를 이용하면 다음과 같이 2개의 std::array를 이을 수 도 있다. 2개의 integer_sequence와 2번의 parameter pack expansion을 사용해서 순서대로 새로운 객체의 생성자 인자로 넣어주게 된다.

template<class LA, class RA, size_t... LIs, size_t... RIs>
constexpr std::array<typename LA::value_type, sizeof...(LIs) + sizeof...(RIs)>
merge_array_internal(
  const LA& lh,
  const RA& rh,
  std::index_sequence<LIs...>,
  std::index_sequence<RIs...>
) {
  return {{
    lh[LIs]...,
    rh[RIs]...
  }};
}

template<class T1, class T2, size_t LSize, size_t RSize>
constexpr std::array<T1, LSize + RSize>
merge_array(
  const std::array<T1, LSize>& lh,
  const std::array<T2, RSize>& rh
) {
  return merge_array_internal(
    lh, rh,
    std::make_index_sequence<LSize>{},
    std::make_index_sequence<RSize>{}
  );
}

int main() {
  std::array<int, 6UL> a = {1,2,3,4,5,6};
  std::array<int, 4UL> b = {7,8,9,10};
  auto arr = merge_array(a, b);

  std::cout << arr << std::endl;
  return 0;
}

// output:
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

뿐만 아니라, 일반적인 variadic template (class... Args)와 함께 사용할 수 도 있다.

template<class T, size_t... Is, class... Args>
constexpr std::array<T, sizeof...(Is) + sizeof...(Args)>
pad_right_array_internal(
  const std::array<T, sizeof...(Is)>& tgt,
  std::index_sequence<Is...>,
  Args&&... args
) {
  return {
    tgt.at(Is)...,
    static_cast<T>(args)...
  };
}

template<class T, size_t Size, class... Args>
constexpr std::array<T, Size + sizeof...(Args)>
pad_right_array(
  const std::array<T, Size>& tgt,
  Args&&... args
) {
  return pad_right_array_internal(
    tgt, std::make_index_sequence<Size>{}, std::forward<Args>(args)...
  );
}

int main() {
  std::array<double, 6UL> a = {1,2,3,4,5,6};
  auto arr = pad_right_array(a, 7, 8, 9, 10);

  std::cout << arr << std::endl;
  return 0;
}
// output:
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

이러한 복수의 tuple-like 클래스를 합치는 다른 방법은 tuple_cat 함수를 참조하자.

정리

이렇듯, integer_sequence를 사용하면 컴파일 타임에 수열을 활용한 코드 생성을 쉽게 할 수 있다. 만약 C++17이상을 활용할 수 있다면, std::apply 같은 함수를 활용하는 방법도 있으나, C++11을 유지해야 한다면 도움이 될 것이라 기대한다.

class A {};
class B {};

struct Key {
    Key(const A& a) {}
};

struct Value {
    Value(const B& a) {}
};

std::unordered_map<Key, Value> associative_container;

A a_instance;
B b_instance;

associative_container.emplace(a_instance, b_instance);

하지만위코드는 gcc 4.8.5에서컴파일되지않았다.(CentOS7기준)이를해결하기위해선다른방법들이있을것이지만,std::pair의다른생성자를사용하여해결하기로했다.std::pair는첫번째인자가 std::piecewise_construct_t 타입일경우, tuple 2개를받아각각의 tuple로부터Key와Value객체를생성할수있다.이를 emplace에적용시켜서사용하면다음과같다.

associative_container.emplace(
    std::piecewise_construct,
    std::forward_as_tuple(a_instance),
    std::forward_as_tuple(b_instance)
);

위와같은접근법은생성자가2개이상인경우에도 emplace를호출하기위해사용했으나,1개의경우에도빌드가되지않아서적용시켰다.

C++에서 다른 타입을 갖는 객체들을 같은 인터페이스로 접근 또는 활용하기 위해서 쉽게 접근할 수 있는 방법 중 하나는 상속을 사용한 클래스 다형성을 기반으로한 방법이다. 같은 클래스를 public 상속받은 다양한 타입의 클래스들은 같은 인터페이스를 지닐 수 있고, 가상 함수 테이블을 활용하여 각기 다른 로직을 작동시킬 수 있다. 그러나 상속을 사용하지 않는 방법도 존재한다. C++의 템플릿 기능을 사용하면 공통 부모가 없고, 심지어 다형성도 만족하지 않는 클래스 타입들의 객체도 일관되게 처리할 수 있다. 특정 attribute를 정의하고, 그것을 만족하는 클래스들에 대해 다양한 로직 패스로 처리할 수 있다. 특히 원하는 멤버함수가 존재하는지 여부도 확인하고 없을 경우 기본 로직을 사용하도록 설정할 수 있다.  이 글에서 템플릿 기능을 사용하여 어떻게 다른 클래스들을 같이 처리할 수 있는지에 대해 실제 gcc-c++ 의 glibcxx 헤더파일과 예시를 통해 보여주려고 한다.

iterator & iterator_tratis

템플릿을 통한 다양한 클래스의 공통된 로직의 활용을 우리가 가장 쉽게 접하는 부분은 STL의 컨테이너 클래스들의 iterator들 일 것이다. algorithm 헤더 등에 존재하는 iterator 기반 함수들은 iterator의 타입을 클래스 인자로 받아 처리하게 된다. 이 때, 각 iterator들에 대해 공통된 인터페이스를 제공하기 위해 iterator_traits이라는 클래스를 별도로 정의하게 된다. 물론 iterator들에 대해서 iterator_traits만 정의되는 것이 아니라 특정 성질을 만족해야 한다고 명시하고 있다. 다음은 iterator들, 특히 LegacyIterator에 대한 요구조건이다.

The type It satisfies LegacyIterator if
    The type It satisfies CopyConstructible, and
    The type It satisfies CopyAssignable, and
    The type It satisfies Destructible, and
    lvalues of type It satisfy Swappable, and
    std::iterator_traits<It> has member typedefs value_type, 
    difference_type, reference, pointer, and iterator_category , and 
Given
    r, an lvalue of type It. 
The following expressions must be valid and have their specified effects:
┌────────────┬─────────────┬─────────────────────┐
│ Expression │ Return Type │ Precondition        │
├────────────┼─────────────┼─────────────────────┤
│ *r         │ unspecified │ r is dereferenceable|
├────────────┼─────────────┼─────────────────────┤
│  ++r 	     │    It&      │ r is incrementable  │
└────────────┴─────────────┴─────────────────────┘

from https://en.cppreference.com/w/cpp/named_req/Iterator

특히, iterator_traits에 대해 필요한 사항에 대하 기술하고 있는데, 그 중 iterator_category를 통해 iterator의 성질을 구분하게 된다. 이를 이용한 대표적인 함수가 std::distance이다. iterator_category의 타입을 통해 현재 iterator 클래스가 임의접근이 가능한지 여부를 확인한다. 실제 GLIBCXX의 구현 헤더파일을 보면, random_access_iterator_tag를 지닌 iterator_traits일 때와 아닐 경우를 함수 오버로딩을 통해 알맞은 로직을 찾아가도록 구현하였다.

template<typename _InputIterator>
inline _GLIBCXX17_CONSTEXPR
typename iterator_traits<_InputIterator>::difference_type
distance(_InputIterator __first, _InputIterator __last)
{
  // concept requirements -- taken care of in __distance
  return std::__distance(__first, __last,
             std::__iterator_category(__first));
}

template<typename _InputIterator>
inline _GLIBCXX14_CONSTEXPR
typename iterator_traits<_InputIterator>::difference_type
__distance(_InputIterator __first, _InputIterator __last,
           input_iterator_tag)
{
  // concept requirements
  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

  typename iterator_traits<_InputIterator>::difference_type __n = 0;
  while (__first != __last)
  {
    ++__first;
    ++__n;
  }
  return __n;
}

template<typename _RandomAccessIterator>
inline _GLIBCXX14_CONSTEXPR
typename iterator_traits<_RandomAccessIterator>::difference_type
__distance(_RandomAccessIterator __first, _RandomAccessIterator __last,
           random_access_iterator_tag)
{
  // concept requirements
  __glibcxx_function_requires(_RandomAccessIteratorConcept<
              _RandomAccessIterator>)
  return __last - __first;
}

위 함수를 std::vector 타입의 iterator에 대해 호출했을 경우, std::vector::iterator의 iterator_traits (또는 iterator 그 자체)가 random_access_iterator_tag를 지니고 있기 때문에 두 iterator의 뺄셈을 통해 distance값을 얻어낼 수 있다. 실제로 std::vector의 코드를 살펴보면 확인할 수 있다.

template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class vector : protected _Vector_base<_Tp, _Alloc>
{
  typedef _Vector_base<_Tp, _Alloc>                     _Base;
public:
  typedef _Tp                                           value_type;
  typedef typename _Base::pointer                       pointer;
  typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
};

template<typename _Iterator, typename _Container>
class __normal_iterator
{
protected:
  _Iterator _M_current;
  typedef iterator_traits<_Iterator> __traits_type;
public:
  typedef typename __traits_type::iterator_category iterator_category;
};

template<typename _Tp>
struct iterator_traits<_Tp*>
{
  typedef random_access_iterator_tag  iterator_category;
};

STL에서는 이렇게 어떤 클래스들이 만족시켜야 할 성질을 기술한 requirement 그리고 그것을 지원하기 위한 traits, tags 등의 보조 타입들을 통해 여러 다른 클래스들을 다루고 있다.

allocator & allocator_traits

iterator에서 눈을 돌려 allocator에 주목하면 여기서는 다른 방식을 사용하는 것을 확인 할 수 있다. allocator_traits이 그 주역이다. STL 컨테이너들은 동적 메모리 할당이 필요할 때 이를 위한 전략의 다변화를 위해 allocator를 템플릿 형태로 인자로 받는다. 지정해 주지 않으면 std::allocator를 사용하지만 필요하다면 커스텀한 allocator를 사용할 수 있다. 이 때, 각 allocator들에 대해 같은 인터페이스를 사용하기 위해 필요한 것이 allocator_traits이다. iterator와 마찬가지로 allocator도 만족해야할 성질들이 있다. 링크에서 확인할 수 있다.

주목해야 할 것은, allocate, deallocate, construct, destroy 함수 4개이다. 각각 메모리를 할당, 해제하고 객체를 생성, 소멸을 담당하는 함수이다. 이 중 allocate와 deallocate만 필수로 존재해야하는 함수이고 construct와 destroy는 optional 함수이다. optional 함수 2개를 정의하지 않은 allocator들에 대해서도 우리는 STL 컨테이너가 올바르게 작동하는 것을 볼 수 있는데, 해당 함수가 존재하지 않을 경우 대신 수행할 default behavior가 정의되어 있기 때문이다. 그리고 그 역할을 allocator_traits이 담당한다. 다음 코드로부터 vector에서 공간을 할당하거나 객체를 생성할 때 allocator_traits를 사용하는 모습을 확인할 수 있다.

template<typename _Tp, typename _Alloc>
struct _Vector_base
{
  pointer
  _M_allocate(size_t __n)
  {
    typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
    return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer();
  }
  void
  push_back(const value_type& __x)
  {
    if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
    {
      _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
      ++this->_M_impl._M_finish;
    }
    else
      _M_realloc_insert(end(), __x);
  }
};

여기서 핵심을 알기 위해서는 allocator_traits의 construct 함수가 construct함수가 정의되어있지 않은 allocator에 대해서 어떤 행동을 하는지를 파악해야한다. 해당 함수의 코드는 다음과 같다.

template<typename _Tp, typename... _Args>
using __has_construct
  = typename __construct_helper<_Tp, _Args...>::type;

template<typename _Alloc>
struct allocator_traits : __allocator_traits_base
{
  template<typename _Tp, typename... _Args>
  static _Require<__has_construct<_Tp, _Args...>>
  _S_construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
  { __a.construct(__p, std::forward<_Args>(__args)...); }

  template<typename _Tp, typename... _Args>
  static
  _Require<__and_<__not_<__has_construct<_Tp, _Args...>>,
  is_constructible<_Tp, _Args...>>>
  _S_construct(_Alloc&, _Tp* __p, _Args&&... __args)
  { ::new((void*)__p) _Tp(std::forward<_Args>(__args)...); }
};

리턴타입을 살펴보면 _Require와 __has_construct라는 헬퍼 클래스를 활용하고 있는것으로 보인다. _Require는 std::enable_if의 aliasing으로, SFINAE을 활용해서 해당 멤버 함수가 있는지 확인하고 있다. __has_construct 헬퍼 클래스가 실제로 함수가 존재하는지 확인하는 역할을 한다. __has_construct에서 어떻게 함수의 존재를 확인하고 있는지 살펴보자.

using true_type = std::integral_constant<bool, true>;
using false_type = std::integral_constant<bool, false>;
template<typename _Tp, typename... _Args>
struct __construct_helper
{
  template<typename _Alloc2,
  typename = decltype(std::declval<_Alloc2*>()->construct(
      std::declval<_Tp*>(), std::declval<_Args>()...))>
  static true_type __test(int);

  template<typename>
  static false_type __test(...);

  using type = decltype(__test<_Alloc>(0));
};

그렇게 복잡하지 않다. 해당 클래스의 멤버변수가 호출되는지 여부를 확인할 뿐이다. std::declval을 통해 객체생성 없이 함수를 호출시도하고 인자도 역시 마찬가지로 std::declval을 통해 객체생성없이 전달시도를 해본다. 즉, 컴파일 시도를 해본다. std::declval<_Alloc2*>()->construct(std::declval<_Tp*>(), std::declval<_Args>()...) 가 바로 그 부분이다. _Alloc2 클래스에 construct라는 멤버함수가 없거나, 또는 존재하더라도 함수의 시그니처가 다르다면 시맨틱 에러가 발생할 것이고, SFINAE에 따라 이는 컴파일 에러로 이어지지 않고 다음 substitution을 찾게 된다. 이는 곧 아래줄의 false_type __test(...)에 해당한다. 종합적으로 살펴보면 __test<_Alloc>을 발견한 템플릿 엔진이 2개의 __test중 substitution을 시도해 볼 것이고, 성공한 함수만 사용할 것이다. 그 이후 성공한 함수의 리턴값이 컴파일 타임 상수를 나타내는 클래스이므로 이를 저장하게 된다.

_Require 또는 std::enable_if는 첫번째 템플릿 인자의 컴파일 타입 상수 불리언 값을 보고 true일 경우에만 유요한 클래스가 되므로, construct함수가 호출 가능할 경우와 불가능 할 경우를 구분할 수 있다. 불가능 할 경우 ::new를 사용하여 default behavior를 통해 객체생성을 하게 된다. 별도의 생성자 호출 가능 여부를 확인하는 코드가 있지만 핵심은 결국 __construct_helper이다.

SFINAE based default behavior

이를 참고하여 특정 멤버 함수에 대해서 검출 및 default behavior를 설정할 수 있다. 다음은 Func이라는 이름의 멤버 함수가 존재하는지 여부를 확인하는 보조 클래스이다.

template<class T, class... Args>
struct DetectFunctionHelper {
    template<class T2,
    typename = decltype(std::declval<T2*>()->Func(std::declval<Args>()...))>
    static std::integral_constant<bool, true> test(int);

    template<typename>
    static std::integral_constant<bool, false> test(...);

    using type = decltype(test<T>(0));
};

template<class T, class... Args>
using HaveFunc = typename DetectFunctionHelper<T, Args...>::type;

이 보조 클래스를 활용하여 Func함수가 있을 경우와 없을 경우에 대한 예제 코드이다. Func 라는 이름의 멤버 함수가 주어진 인자를 이용하여 호출가능 할 경우 올바르게 호출하며, 그 외의 경우 default behavior를 수행한다. 클래스 A의 경우 Func 라는 이름의 함수가 인자가 없을 경우(void)에만 호출 가능하므로, Wrapper::Func(a, 0) 의 경우 호출 불가능하므로 default behavior가 호출된다.

struct A {
    void Func() {
        std::cout << "A::Func" << std::endl;
    }
};

struct B {
};

template<class T>
struct Wrapper {
private:
    template<class U, class... Args>
    static
    typename std::enable_if<HaveFunc<U, Args...>::value>::type
    __FuncHelper(U& u, Args&& ...args) {
        u.Func(std::forward<Args>(args)...);
        std::cout << "Specified Func is called." << std::endl;
    }
    template<class U, class... Args>
    static
    typename std::enable_if<!HaveFunc<U, Args...>::value>::type
    __FuncHelper(U&, Args&& ...) {
        std::cout << "Default behavior is called." << std::endl;
    }
public:
    template<class... Args>
    static auto Func(T& t, Args&& ...args) -> decltype(__FuncHelper(t, args...)) {
        __FuncHelper(t, std::forward<Args>(args)...);
    }
};

int main () {
    A a;
    B b;
    int i;
    Wrapper<decltype(a)>::Func(a); 
    Wrapper<decltype(a)>::Func(a, 0);
    Wrapper<decltype(b)>::Func(b);
    Wrapper<decltype(i)>::Func(i);
}

/*         output          */
/// A::Func
/// Specified Func is called.
/// Default behavior is called.
/// Default behavior is called.
/// Default behavior is called.

이 보조 클래스에서 함수의 리턴을 처리하기 위해서는 추가적인 작업이 필요하다. C++14에서는 auto 를 통한 함수 리턴 타입 추론이 가능하지만, C++11일 경우 decltype을 통해 지정해 주어야 하기 때문에 추가적인 작업이 필요하다. 다음 코드는 함수 리턴이 void일 경우에도 일괄로직을 작동하기 위한 변경한 코드이다. 이 시나리오를 처리하기 위해서는 다음과 같은 3가지 경우의 수를 고려했다. 1) Func 함수가 존재할 경우, 그리고 리턴 타입이 void가 아닐 경우; 2) Func 함수가 존재하지만 리턴 타입이 void일 경우; 3) Func 함수가 존재하지 않을 경우. 이러한 경우를 고려하여 처리한 코드는 다음과 같다.

struct A {
    int Func() {
        std::cout << "A::Func" << std::endl;
        return 0;
    }
};

struct B {
};

struct SomeReturnType {};

template<class T>
struct Wrapper {
private:
    /// 1) Func 함수가 존재할 경우, 그리고 리턴 타입이 void가 아닐 경우
    template<class U, class... Args>
    static
    typename std::enable_if<
        HaveFunc<U, Args...>::value
        && !std::is_void<
            decltype(std::declval<U*>()->Func(std::declval<Args>()...))
            >::value,
    decltype(std::declval<U*>()->Func(std::declval<Args>()...))>::type
    __FuncHelper(U& u, Args&& ...args) {
        std::cout << "Specified Func is called." << std::endl;
        return u.Func(std::forward<Args>(args)...);
    }
    
    /// 2) Func 함수가 존재하지만 리턴 타입이 void일 경우
    template<class U, class... Args>
    static
    typename std::enable_if<
        HaveFunc<U, Args...>::value
        && std::is_void<
            decltype(std::declval<U*>()->Func(std::declval<Args>()...))
            >::value,
    SomeReturnType>::type
    __FuncHelper(U& u, Args&& ...args) {
        std::cout << "Specified Func is called." << std::endl;
        u.Func(std::forward<Args>(args)...);
        return SomeReturnType();
    }
    
    /// 3) Func 함수가 존재하지 않을 경우
    template<class U, class... Args>
    static
    typename std::enable_if<!HaveFunc<U, Args...>::value,
    SomeReturnType>::type
    __FuncHelper(U&, Args&& ...) {
        std::cout << "Default behavior is called." << std::endl;
        return SomeReturnType();
    }
public:
    template<class... Args>
    static auto Func(T& t, Args&& ...args)
    -> decltype(__FuncHelper(std::declval<T&>(), std::declval<Args>()...)) {
        return __FuncHelper(t, std::forward<Args>(args)...);
    }
};

template<class T>
void ProcessReturnValue(T&&) {
    std::cout << "Valid return type." << std::endl;
}

template<>
void ProcessReturnValue<SomeReturnType&>(SomeReturnType&) {
    std::cout << "Invalid return type." << std::endl;
}

template<>
void ProcessReturnValue<SomeReturnType&&>(SomeReturnType&&) {
    std::cout << "Invalid return type." << std::endl;
}

int main () {
    A a;
    B b;
    int i;
    {
        auto&& ret = Wrapper<decltype(a)>::Func(a);
        ProcessReturnValue(ret);
    }
    std::cout << "====================" << std::endl;
    {
        auto&& ret = Wrapper<decltype(a)>::Func(a, 0);
        ProcessReturnValue(ret);
    }
    std::cout << "====================" << std::endl;
    {
        auto&& ret = Wrapper<decltype(b)>::Func(b);
        ProcessReturnValue(ret);
    }
    std::cout << "====================" << std::endl;
    {
        auto&& ret = Wrapper<decltype(i)>::Func(i);
        ProcessReturnValue(ret);
    }
}

/*         output          */
/// Specified Func is called.
/// A::Func
/// Valid return type.
/// ====================
/// Default behavior is called.
/// Invalid return type.
/// ====================
/// Default behavior is called.
/// Invalid return type.
/// ====================
/// Default behavior is called.
/// Invalid return type.

C++17

위 예제 코드는 C++11에서 돌아가는 것을 보장하는 코드이다. C++17에서는 if constexpr기능이 도입이 되었고, enable_if 대신 if constexpr를 사용할 수 있다. 아래 코드는 if constexpr을 활용하여 같은 동작을 수행한다. enable_if와 SFINAE을 사용하기 위한 추가적인 템플릿 함수가 필요가 없어서 더 간결하게 작성할 수 있다. 또한, C++14에서 추가된 리턴 타입 추론과 함께 함수의 리턴 처리도 더 간편해졌다.

template<class T>
struct Wrapper {
public:
    template<class... Args>
    static auto Func(T& t, Args&& ...args) {
        if constexpr(HaveFunc<T, Args...>::value) {
            std::cout << "Specified Func is called." << std::endl;
            return t.Func(std::forward<Args>(args)...);
        } else if (!HaveFunc<T, Args...>::value) {
            std::cout << "Default behavior is called." << std::endl;
            return SomeReturnType();
        }
    }
};

정리

우리는 C++에서 어떻게 컴파일 타임에 특정 멤버 변수가 존재하는지 확인하고, 존재하지 않았을 경우 우회가능한 로직을 정의하는 방법을 알아보았다. C++11에서는 SFINAE을 사용한 템플릿 추론을 통한 방법이 있었고 C++17까지 허용한다면 컴파일 타임 조건문(if constexpr)을 통한 방법을 통해 더 간편하게 코드를 작성 할 수 있었다.

C++에서 다형성을 만족하는 클래스들에게 각각 독립적인 로직을 갖는 함수를 사용하기 위해서는 가상 함수 테이블을 사용하는 것이 일반적이다. 클래스의 수가 늘어날 때 그리고 함수의 수가 늘어날 때를 고려하거나 다수의 클래스가 같은 로직을 사용할 때의 경우를 고려하여 다양한 디자인 패턴들이 소개가 되었다. 그 중에서도 특히 클래스의 수는 늘어날 가능성이 매우 희박하면서도, 클래스 특수한(class specific) 함수들의 수는 늘어나기 쉬운 경우에 대해서 일관된 로직 플로우 또는 패턴을 마련해야 할 필요성이 생겼다. 이 글에서 naïve한 접근 방식을 소개하고 이를 보안한 Visitor 패턴을 사용해 어떻게 구현하였는지 서술하려고 한다.

다음 코드조각은 전체 실험에서 사용할 기본적인 클래스 정의를 나타낸다. Base라는 한 개의 순수 가상 클래스를 정의하였고, 이를 상속받은 8개의 클래스들을 정의하였다. Visitor를 받아들이기 위한 Invite라는 멤버 함수가 가상함수로 정의되어 있다. 상속받은 자식 클래스에서도 역시 재정의하였다. 이 때, 각 Derived 클래스의 Invite 함수의 스코프에서 *this의 타입형은 자기자신 클래스의 레퍼런스가 될 것이고, 이 를 정보로 삼아 함수 오버로딩을 활용하여 각 Visitor에서 클래스 특화 함수를 호출할 수 있게 하였다.

class Base {
  protected:
    // 아주 많은 데이터
    int data[100];
  public:
    Base() {}
    virtual ~Base() {}
    
    virtual void Func() = 0;
    virtual void Invite(Visitor& visitor) {
        visitor.Visit(*this);
    }

    virtual int Id() = 0;
};

#define MAKE_DERIVED(id) \
class Derived##id : public Base { \
public: \
    int cast_id; \
    Derived##id() : Base() {} \
    Derived##id(int a) : Base(), cast_id(a) {} \
    virtual ~Derived##id() {} \
    virtual void Func() override { } \
    virtual void Invite(Visitor& visitor) override { \
        visitor.Visit(*this); \
    } \
    virtual int Id() override { \
        return cast_id; \
    } \
};

MAKE_DERIVED(A)
MAKE_DERIVED(B)
MAKE_DERIVED(C)
MAKE_DERIVED(D)
MAKE_DERIVED(E)
MAKE_DERIVED(F)
MAKE_DERIVED(G)
MAKE_DERIVED(H)

/// After preprocessing the above macro
class DerivedA : public Base {
  public:
    int cast_id;
    DerivedA() : Base() {}
    DerivedA(int a) : Base(), cast_id(a) {}
    virtual ~DerivedA() {}
    virtual void Func() override { }
    virtual void Invite(Visitor& visitor) override {
        visitor.Visit(*this);
    }
    virtual int Id() override {
        return cast_id;
    }
};

다음은 테스트를 하기 위한 데이터 준비작업이다. 10,000,000개의 클래스 인스턴스를 준비하였다.

const static size_t test_size = 10000000;

auto now = std::chrono::high_resolution_clock::now;
auto begin = now();

std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<> dis(0, 7);
std::vector<std::unique_ptr<Base>> v;
v.reserve(test_size);
for(size_t i = 0 ; i < test_size ; i++) {
    int id = dis(mt);
    switch (id) {
    case 0:
        v.emplace_back(new DerivedA(1 * 10 + dis(mt)));
        break;
    case 1:
        v.emplace_back(new DerivedB(2 * 10 + dis(mt)));
        break;        
    case 2:
        v.emplace_back(new DerivedC(3 * 10 + dis(mt)));
        break;
    case 3:
        v.emplace_back(new DerivedD(4 * 10 + dis(mt)));
        break;        
    case 4:
        v.emplace_back(new DerivedE(5 * 10 + dis(mt)));
        break;        
    case 5:
        v.emplace_back(new DerivedF(6 * 10 + dis(mt)));
        break;        
    case 6:
        v.emplace_back(new DerivedG(7 * 10 + dis(mt)));
        break;        
    case 7:
        v.emplace_back(new DerivedH(8 * 10 + dis(mt)));
        break;
    default:
        break;
    }
}
auto end = now();
auto duration =
std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count();
std::cout << "Test preparation\n" << std::setw(20)
          << std::right << duration << "us" << std::endl;

가장 naïve한 접근 방법은, 부모 클래스 타입의 포인터에 dynamic_cast를 사용하는 것이다. 이러한 cascading dyamic_cast 방식은 많은 RTTI에 기반한 비교연산을 동반하기 때문에 성능이 좋을 것이라고 기대하기 어렵다.

auto begin = now();
int cnt[8];
for(auto&& i : v) {
    auto&& p = i.get();
    if(auto ptr = dynamic_cast<DerivedA*>(p)) {
        cnt[0]++;
    } else if(auto ptr = dynamic_cast<DerivedB*>(p)) {
        cnt[1]++;
    } else if(auto ptr = dynamic_cast<DerivedC*>(p)) {
        cnt[2]++;
    } else if(auto ptr = dynamic_cast<DerivedD*>(p)) {
        cnt[3]++;
    } else if(auto ptr = dynamic_cast<DerivedE*>(p)) {
        cnt[4]++;
    } else if(auto ptr = dynamic_cast<DerivedF*>(p)) {
        cnt[5]++;
    } else if(auto ptr = dynamic_cast<DerivedG*>(p)) {
        cnt[6]++;
    } else if(auto ptr = dynamic_cast<DerivedH*>(p)) {
        cnt[7]++;
    } else {
        throw std::bad_cast();
    }
}

auto end = now();
auto duration
  = std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count();
std::cout << "Dynamic cast\n" << std::setw(20)
          << std::right << duration << "us" << std::endl;
std::cout << "---------validation----------\n";
std::cout << cnt[0] << " : " << cnt[1] << " : " << cnt[2] << " |\n"
          << cnt[3] << " : " << cnt[4] << " : " << cnt[5] << " |\n"
          << cnt[6] << " : " << cnt[7] << std::endl;
std::cout << "-----------------------------\n\n";

다음 방법은 Visitor를 활용한 방법이다. 사용할 Visitor의 인터페이스는 다음과 같다. 먼저 각 Derived class마다 Visit 함수를 지니고 있고, 각 Visit 함수 내부에서는 가상 함수인 DoWork함수를 호출하게 된다. Visit함수와 DoWork함수는 derived 클래스 별로 오버로딩이 되어있어서 타입을 알맞게 찾을 수 있다. 즉, 전체적인 플로우는 다음과 같다. Base 클래스와 Derived 클래스들의 vtable을 사용해 Visitor를 인자로 받으면, 자기 자신의 타입에 해당하는 Visit 함수를 호출하게 된다. 이 때 Derived 클래스의 구체적인 타입은 알 수 있는 상태이기 때문에 알맞은 DoWork 함수를 호출할 수 있다. 이 때 모든 가상 함수를 오버라이딩 했다면, Base 타입의 객체를 받은 DoWork함수는 필요없고, 또 호출되지 않을 것이다. 대신에 이를 기본행동을 지정하는 함수를 만들 경우에 사용할 수 있다. 특정 클래스, DerivedA와 DerivedB에만 특정 로직을 동작시키고, 그 외에는 기본 로직을 활용하고 싶다면 Base를 받는 경우를 기본 로직을 위한 함수로 설정할 수 있다. 이럴 경우 Visitor 인터페이스의 DoWork 함수들의 기본 로직을 아래 코드조각의 맨 하단 부분처럼 바꿔야 할 필요가 있을 것이다.

#define DERIVED_FORWARD_DECL(id) \
class Derived##id;

#define MAKE_VISIT_FUNC(id) \
void Visit(const Derived##id& tgt) { \
    DoWork(tgt); \
}

#define MAKE_WORK_FUNC(id, logic) \
virtual void DoWork(const Derived##id& tgt) { \
    logic \
}

class Visitor {
  public:
    virtual ~Visitor() {}

    void Visit(const Base& tgt) {
        DoWork(tgt);
    }

    MAKE_VISIT_FUNC(A)
    MAKE_VISIT_FUNC(B)
    MAKE_VISIT_FUNC(C)
    MAKE_VISIT_FUNC(D)
    MAKE_VISIT_FUNC(E)
    MAKE_VISIT_FUNC(F)
    MAKE_VISIT_FUNC(G)
    MAKE_VISIT_FUNC(H)

    virtual void DoWork(const Base& tgt) {
        throw std::logic_error("Not Reachable");
    }
    MAKE_WORK_FUNC(A, ;)
    MAKE_WORK_FUNC(B, ;)
    MAKE_WORK_FUNC(C, ;)
    MAKE_WORK_FUNC(D, ;)
    MAKE_WORK_FUNC(E, ;)
    MAKE_WORK_FUNC(F, ;)
    MAKE_WORK_FUNC(G, ;)
    MAKE_WORK_FUNC(H, ;)

};

/// DoWork에 default function을 사용할 경우
void Visiter::DoWork(const DerivedB& tgt) {
    // explicit upcasting
    DoWork(static_cast<const Base&>(tgt);
}

다음은 cascading dynamic_cast를 사용했을 때와 같은 작동을 하는 CountVisitor에 대한 정의와 테스트 코드이다.

auto begin = now();
class CountVisitor : public Visitor {
public:
    CountVisitor() : cnt{0} {}
    virtual ~CountVisitor() = default;

    MAKE_WORK_FUNC(A, cnt[0]++;)
    MAKE_WORK_FUNC(B, cnt[1]++;)
    MAKE_WORK_FUNC(C, cnt[2]++;)
    MAKE_WORK_FUNC(D, cnt[3]++;)
    MAKE_WORK_FUNC(E, cnt[4]++;)
    MAKE_WORK_FUNC(F, cnt[5]++;)
    MAKE_WORK_FUNC(G, cnt[6]++;)
    MAKE_WORK_FUNC(H, cnt[7]++;)

    int cnt[8];
};

CountVisitor cv;
for(auto&& i : v) {
    i->Invite(cv);
}       

auto end = now();
auto duration
    = std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count();
std::cout << "Dynamic cast\n" << std::setw(20)
          << std::right << duration << "us" << std::endl;
std::cout << "---------validation----------\n";
std::cout << cnt[0] << " : " << cnt[1] << " : " << cnt[2] << " |\n"
          << cnt[3] << " : " << cnt[4] << " : " << cnt[5] << " |\n"
          << cnt[6] << " : " << cnt[7] << std::endl;
std::cout << "-----------------------------\n\n";

이를 바탕으로 수행 시간을 측정해 보았다. 테스트 환경은 인텔 i5-8500이며 Ubuntu 18.04 Linux 5.0.0-27에서 측정되었다. g++ 7.4.0버전에 -O3 최적화 옵션으로 컴파일 하였다. Cascading dynamic_cast의 경우 약 1,000,000 마이크로초 (= 1초)가 소요되었다. 1,100,000 마이크로초가 넘는 테스트 회수도 있었다. Visitor를 사용할 경우, 150,000 마이크로초에서 160,000 마이크로초 사이의 시간이 소요되었다. 약 6배 정도의 성능 차이가 있는 것을 확인하였다. 다음은 특정 테스트 회수의 결과이다.

Test preparation
             2088129us
Dynamic cast
             1087401us
---------validation----------
1249520 : 1249369 : 1249623 |
1250041 : 1249819 : 1251194 |
1250905 : 1249529           |
-----------------------------
Visitor
              156315us
---------validation----------
1249520 : 1249369 : 1249623 |
1250041 : 1249819 : 1251194 |
1250905 : 1249529           |
-----------------------------

최적화 옵션을 사용하지 않았을 경우는 그 차이가 1.6배정도 (Visitor가 더 빠름) 으로 줄어들기는 하지만 그럼에도 차이가 유의미하다고 판단할 수 있을 것이다. -O1 또는 -O2의 경우에도 -O3와 유사한 비율의 성능 차이를 확인할 수 있었다.

Type checking + dynamic_cast

C++이 dynamic_cast를 하기위해 런타임 타입 정보를 얻는 방법에 대해서는 규정을 하고있지는 않지만, 각 클래스 내부에 타입에 대한 (엄격히 관리된) 정보를 int등의 타입으로 유지한다면 int타입에 대한 비교 연산이 RTTI을 사용한 dynamic_cast보다 빠를 것 같았다. 물론 타입에 대한 정보를 클래스 내부에 유지하는 것은 권장할만한 행동은 아니지만, 어째뜬 우리는 int타입의 값을 보고 클래스의 실제 타입을 추론해 볼 것이다. 테스트 케이스를 생성한 코드 또는 Base & Derived 클래스를 정의한 코드를 보면 정수의 값으로 타입 정보를 저장하였다. 10의 자리의 수를 보고 타입을 추론할 수 있을 것이다. 이를 바탕으로 다음과 같이 코드를 작성할 수 있다.

auto begin = now();
int cnt[8] = {0};
for(auto&& i : v) {
    auto&& p = i.get();  
    int id = p->Id() / 10;          
    switch (id) {
    case 1:
        {
            auto ptr = dynamic_cast<DerivedA*>(p);
            cnt[0]++;
        }
        break;
    case 2:
        {
            auto ptr = dynamic_cast<DerivedB*>(p);
            cnt[1]++;
        }
        break;        
    case 3:
        {
            auto ptr = dynamic_cast<DerivedC*>(p);
            cnt[2]++;
        }
        break;
    case 4:
        {
            auto ptr = dynamic_cast<DerivedD*>(p);
            cnt[3]++;
        }
        break;        
    case 5:
        {
            auto ptr = dynamic_cast<DerivedE*>(p);
            cnt[4]++;
        }
        break;        
    case 6:
        {
            auto ptr = dynamic_cast<DerivedF*>(p);
            cnt[5]++;
        }
        break;        
    case 7:
        {
            auto ptr = dynamic_cast<DerivedG*>(p);
            cnt[6]++;
        }
        break;        
    case 8:
        {
            auto ptr = dynamic_cast<DerivedH*>(p);
            cnt[7]++;
        }
        break;
    default:
        break;
    }
}

auto end = now();
auto duration
    = std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count();
std::cout << "Dynamic cast + with id checking\n" << std::setw(20) << std::right << duration << "us" << std::endl;
std::cout << "---------validation----------\n";
std::cout << cnt[0] << " : " << cnt[1] << " : " << cnt[2] << " |\n"
          << cnt[3] << " : " << cnt[4] << " : " << cnt[5] << " |\n"
          << cnt[6] << " : " << cnt[7] << std::endl;
std::cout << "-----------------------------\n\n";

이를 같은 환경에서 테스트했을 때, 200,000마이크로초 근처였다. Visitor보다는 빠르지 않았어도, dynamic_cast를 여러번 한 경우에 비해 짧은 수행시간을 보여주었다.

정리

dynamic_cast를 사용하지 않는 것이 권장되어도, (그리고 클래스 설계를 dynamic_cast를 쓰지 않는 방법으로 수정하는 것이 권장되더라도) 런타임에 타입을 체크하거나 상속받은 자식 클래스에 있는 특수한 함수 또는 성질에 접근해야할 필요성을 완전히 지우는 것은 노력이 필요한 일이다. 이 글에서 dynamic_cast를 cascade 처럼 사용하지 않고 비슷한 역할을 수행할 수 있는 방법 중 하나를 소개해보았다. 이 방법론을 사용하다면, 클래스의 종류가 늘어나지 않고 함수를 계속 추가해 나가야 할 때 좀 더 편하고 그리고 동작시간이 빠른 코드 및 구현을 얻어낼 수 있을 것으로 기대한다.

EBNF(wikipedia) 를 나타내는 그림을 그리는 방법 중 하나인 Rail과 LaTeX을 소개한다. LaTex은 유명한 편집기 이며, Rail이라는 플러그인을 사용하면 EBNF를 나타내는 그림을 손쉽게 그릴 수 있다.

Programs Requirements

• LaTeX & Rail
  당연히 편집하기 위한 LaTeX과 플러그인인 Rail이 필요하다. Rail은 CTAN에서 받을 수 있다. 따로 패키지 관리자를 사용하지 않고 다운받은 뒤 직접 빌드하여 사용했다. 빌드하기 위해서 스캐너와 파서인 flex와 bison이 설치되어있어야 한다. (실행할 때도 필요한지 여부는 확인하지 못했다.) 빌드 결과물로 나오는 rail 이라는 바이너리 실행파일과 rail.sty이 필요하다.
• pdfcrop.pl
  만약 LaTeX과 Rail을 통해 얻어낸 PDF파일의 크기가 그림의 크기보다 크다면 pdfcrop.pl을 사용하여 여백을 잘라줄 수 있다. 역시 CTAN에서 다운받을 수 있다. 또는, 근본적으로 크기가 알맞은 PDF파일을 만들도록 수정할 수 있을 것으로 보인다. (링크)
• ImageMagick
  PDF 파일을 그림파일로 변환하기 위한 프로그램이다. 기본 설정으로는 PDF 파일의 변환이 불가능했기 때문에, 스택오버플로우의 지침대로 profile.xml을 수정해줘야 했다.

예제 과정

본 게시글에서 사용한 예제 TeX파일은 다음과 같다.  standalone 클래스(CTAN)를 사용하여 그림만 나오는 독립적은 PDF를 얻어낼 것이다. 예제 파일의 내용은 Rail 문서에 있는 Rail을 사용하기 위한 문법을 설명하는 소스이다. 만약 길이가 너무 길어서 PDF크기가 부족하다면 geometry등의 패캐지를 사용해서 길이를 크게 지정해주는 방법 등으로 해결 할 수 있다.

% example.tex
\documentclass[preview, varwidth=true]{standalone}
\usepackage{rail}
\railoptions{-ah} % rail option 
\begin{document}
\begin{rail}
    rules	: ( rule ? + ';' ) ;

    rule	: ( identifier ':' ) ? body[1--5] ;
    body	: [1] ( ( '[' string ']' ) ? body[2--6] + '|' )
                | [2] body[3--6] '*' body[5--6]
                | [2] body[3--6] '+' body[5--6]
                | [3] ( body[4--5] + )
                | [4] body[5] '?'
                | [5] identifier ( '[' string ']' ) ?
                | [5] quote string quote
                | [5] dquote string dquote
                | [5] '(' body[1--6] ')'
                | [5] cr
                | [6]
                ;

\end{rail}
\end{document}

LaTeX으로 처리를 하고 나면, PDF파일의 그림이 완전하지 않은 것을 알 수 있다. 이 때, 파일명과 같은 rai 파일(example.rai)이 같이 떨어지게 된다.  이 파일을 Rail을 통해 처리하고 나면 파일명과 같은 rao파일(example.rao)을 얻을 수 있고, 이 것을 바탕으로 다시 LaTeX에 입력으로 넣으면 PDF를 얻을 수 있다. 이 PDF를 사진으로 바꾸면 끝이다. 위 예제의 경우 다음과 같은 사진을 얻을 수 있다.

말로 설명한 위 과정의 명령어들은 다음과 같다.

pdflatex example.tex

# rail 에 옵션을 직접 줄 수 있다. (\railoptions{-ah} 대신 rail -ah example)
# 확장자(rai)를 제외한 파일이름만 입력으로 넣는다.
$(PATH_TO_RAIL)/rail example

pdflatex example.tex

# 만약 결과 pdf가 너무 클 때,
# profcrop.pl (input_file) (output_file)
$(PATH_TO_PDFCROP)/pdfcrop.pl example.pdf example_cropped.pdf

# 결과 pdf를 사진으로 바꾸려면
convert -density 300 -quality 90 \
    example_cropped.pdf figure_output.png
# dpi = 300, quality = 90 의 png파일을 얻을 수 있다.

Rail을 사용한 EBNF 그림뿐만이 아니라 Tikz등을 이용한 그림 등도 당연히 쉽게 가능하다.

GEOS에서는 두 geometry 객체의 위상적 관계를 (topologiocal relation) DE-9IM(Dimensionally Extended nine-Intersection Model)을 사용하여 표현한다. 이에 관한 설명은 OGC의 simple feature specification에 관한 문서에서 (또는 위키피디아에서) 확인할 수 있다. 따라서, GEOS에서 위상적 관계를 파악하는 함수라는 것은 결국 이 DE-9IM(이하 IM)를 계산하는 함수를 의미하고, 곧 IM을 계산하는 알고리즘을 통해 위상적 관계를 얻어내는 알고리즘을 얻을 수 있다. 다음 코드는 GEOS에서 위상적 관계를 확인하는 방법이다. 각 함수들의 구현체를 살펴보면, IM계산한 뒤 그 값을 통해 bool값을 반환하고 있는 것을 알 수 있다.

//from a GEOS test c++ code.
//test/geostest/geostest.c

GEOSGeometry* g1;
GEOSGeometry* g2;

//Query topological relations using functions.
if ( GEOSIntersects(g1, g2) ) printf("Intersect\n");
if ( GEOSDisjoint(g1, g2) ) printf("Disjoint\n");
if ( GEOSTouches(g1, g2) ) printf("Touches\n");
if ( GEOSCrosses(g1, g2) ) printf("Crosses\n");
if ( GEOSWithin(g1, g2) ) printf("Within\n");
if ( GEOSContains(g1, g2) ) printf("Contains\n");
if ( GEOSOverlaps(g1, g2) ) printf("Overlaps\n");

//Query topological relations using IM.
auto ptr = GEOSRelate(g1, g2);
if( GEOSRelatePattern(g1, g2, ptr) )

//in each function
{
    ...
    unique_ptr<IntersectionMatrix> im ( relate(g) );
    return im->~();
}

Geometry Graph

IM을 구하는 과정을 살펴보기 전에, GEOS에서 IM계산에서 사용하는 GeometryGraph클래스를 살펴보려고 한다. GeometryGraph는 geometr을 바탕으로 생성된 노드(node)와 엣지(edge)을 가지고 있는 그래프로서 각 노드와 엣지에는 (바탕이되는) geometry의 점(들)과 선(들)이 어느 위치에 있는지에 대한 위상적 관계를 저장하고 있다. 언듯 직관적으로 이해가 되지 않으므로 다음과 같은 예제를 살펴보자. 다음은 폴리곤 형식의 geometry로, 내부에 2개의 ring이 존재한다. 내부 ring 사이의 공간은 이 폴리곤에 속한다고 간주하지 않는다. (즉, exterior 이다.) GEOS (또는 기타 라이브러리)에서 폴리곤을 저장하는 방법을 떠올리면 그림의 선은 실제로 존재하지 않는다는 것을 알 수 있다. 즉, 그림에서는 점과 선으로 표현했지만, 저장한 데이터들은 점의 좌표의 배열뿐이다. 실제로는 점 사이의 선은 (메모리에) 존재하지 않고 배열에서 연속된 두 점 사이를 직선으로 잇는 것으로 생각한다. 따라서 이 폴리곤은 3개의 점의 배열들로 구성되어 있다.

이 geometry로 생성한 GeometryGraph는 3개의 노드와 3개의 엣지로 구성되어있다. Geometry의 점들을 보고, 점의 배열을 1개의 엣지로, 점의 배열 중 몇개를 선택하여 노드로 저장한다. 다음 그림을 통해 살펴보자. 노드의 경우 그림에서 점선으로 표현한 점들이 해당한다. 엣지의 경우, 같은 색의 점들의 좌표값을 배열로 가지고 있다. 즉, 위에서 폴리곤을 나타낼 때 사용한 점의 배열마다 1개의 노드와 1개의 엣지를 생성한 것이다. 이제 각 노드 또는 엣지마다 라벨을 하나씩 가지고 있다. 빨간 선의 집합으로 인해 생성된 1개의 엣지에는 on: boundary, left: exterior, right: interior라는 라벨을 가지고 있고, 내부 링에 해당하는 파란색과 초록색으로 인해 생성된 엣지 2개는 각각 on: boundary, left: interior, right: exterior 라는 값을 가지고 있다.

 이 경우는 폴리곤의 경우였고, 라인스트링 같은 2차원 객체들은 한개의 점의 배열마다 처음 점과 마지막 점을 노드로 저장한다. 즉, 선의 양 끝점을 노드로, 전체 점의 집합을 엣지로 저장한다. 이 때, 엣지의 라벨은 on: interior이 되고 노드의 라벨은 on:boundary가 될 것이다.

Computing IM

다시 IM을 계산하기 위한 과정으로 돌아와서 GEOS의 수행과정을 살펴보자. 이 과정을 수행 해주는 클래스는 RelateOp다. RelateOp는 계산한 두 개의 geometry를 입력으로 받고 GeometryGraph을 생성한 뒤 relateComp라는 객체를 통해 IM을 계산한다. 그 후 계산한 IM을 반환하면 이 값을 통해 위상적 관계를 파악한다.

//a->relate(b) =>
//RelateOp::relate(this, other)
IntersectionMatrix*
RelateOp::relate(const Geometry *a, const Geometry *b)
{
	RelateOp relOp(a,b);
	return relOp.getIntersectionMatrix();
}

RelateOp::RelateOp(const Geometry *g0, const Geometry *g1):
	GeometryGraphOperation(g0, g1),
	relateComp(&arg)
{
}

IntersectionMatrix*
RelateOp::getIntersectionMatrix()
{
	return relateComp.computeIM();
}

따라서, IM을 계산해주는 알고리즘의 중심적인 부분을 살펴보기 위해서는 RelateComputer 클래스를 이해해야 한다.  IM을 계산하는 RelateComputer::computeIM 함수의 (간소화된) 코드는 다음과 같다.

IntersectionMatrix*
RelateComputer::computeIM()
{
    // if the Geometries don't overlap there is nothing to do
    const Envelope *e1=(*arg)[0]->getGeometry()
                ->getEnvelopeInternal();
    const Envelope *e2=(*arg)[1]->getGeometry()
                ->getEnvelopeInternal();
    if (!e1->intersects(e2)) {
        computeDisjointIM(im.get());
        return im.release();
    }

    std::unique_ptr<SegmentIntersector> si1 (
        (*arg)[0]->computeSelfNodes(&li,false)
    );
    std::unique_ptr<SegmentIntersector> si2 (
        (*arg)[1]->computeSelfNodes(&li,false)
    );

    std::unique_ptr< SegmentIntersector> intersector (
        (*arg)[0]->computeEdgeIntersections((*arg)[1], &li,false)
    );

    computeIntersectionNodes(0);
    computeIntersectionNodes(1);

    copyNodesAndLabels(0);
    copyNodesAndLabels(1);

    labelIsolatedNodes();

    computeProperIntersectionIM(intersector.get(), im.get());

    EdgeEndBuilder eeBuilder;
    std::unique_ptr< std::vector<EdgeEnd*> > ee0 (
        eeBuilder.computeEdgeEnds((*arg)[0]->getEdges())
    );
    insertEdgeEnds(ee0.get());
    std::unique_ptr< std::vector<EdgeEnd*> > ee1 (
        eeBuilder.computeEdgeEnds((*arg)[1]->getEdges())
    );

    insertEdgeEnds(ee1.get());

    labelNodeEdges();

    labelIsolatedEdges(0,1);

    labelIsolatedEdges(1,0);

    updateIM( *im );
    return im.release();
}

이제 이 코드를 파악해 보자. 먼저 두 geometry의 MBR (envelope in GEOS)이 서로 겹치지 않는다면, geometry들 끼리도 역시 아무런 위상 관계가 없다는 것은 쉽게 알 수 있다. 따라서, MBR간의 관계를 먼저 확인해본다.

const Envelope *e1=(*arg)[0]->getGeometry()->getEnvelopeInternal();
const Envelope *e2=(*arg)[1]->getGeometry()->getEnvelopeInternal();
if (!e1->intersects(e2)) {
    computeDisjointIM(im.get());
    return im.release();
}

다음은 어떤 간선 쌍이 겹치는지 확인하고 저장한다. GEOS에서는 먼저, 한 geometry 내부에서 스스로 겹치는 선이 있는지 확인한다. GeometryCollection이나 LineStirng의 경우 스스로 겹치는 선이 있을 수 있다. 이러한 경우 해당 intersection을 따로 저장한다. 다른 geometry 객체와 겹치는 부분이 아니기 때문이다. 그 다음 geometry 사이에서 겹치는 간선 쌍을 찾는다. 이 과정을 표현한 코드는 다음과 같다. Intersection에 대한 여부는 위에서 서술한 GeometryGraph에 의해 정보가 저장된다.

std::unique_ptr<SegmentIntersector> si1 (
    (*arg)[0]->computeSelfNodes(&li,false)
);
std::unique_ptr<SegmentIntersector> si2 (
    (*arg)[1]->computeSelfNodes(&li,false)
);

std::unique_ptr< SegmentIntersector> intersector (
    (*arg)[0]->computeEdgeIntersections((*arg)[1], &li,false)
);

Monotone chian sweep line algorithm

서로 겹치는 선을 찾을 때는 brute force를 사용하여 (모든 선 쌍들을 비교하는 알고리즘인) quadratic time algorithm을 사용할 수 도 있다. 그렇지만 좀 더 효율적인 계산을 위해 GEOS에서는 기본적으로 monotone-chain sweep line algorithm을 사용한다. 이 과정에서 위에서 서술한 GeometryGraph를 사용한다. 알고리즘에 대한 이론적인 설명은 다음 논문에서 확인할 수 있다. (링크) GEOS에서 사용하는 monotone-chain과는 약간 다르지만, 핵심이 되는 내용은 다음과 같다. Chain (polygonal chain)은 연결된 선의 집합이다. Monotone chain도 역시 chain의 일종으로 선의 집합으로 구성되어있다. 중요한 포인트는 monotone chain속의 선들은 서로 겹치지 않는다는 것이다. 이를 바탕으로 하면, 모든 선들을 monotone chain으로 구성하고 monotone chain사이에 intersection이 있는지 확인하면 더 효율적으로 찾을 수 있다. 논문에 따른 수학적인 monotone chain의 정의는 다음과 같다.

어떤 chain C 어떤 선 L에 수직인 모든 선 L0에 대해 교점이 최대 1개이면, 그 chain C는 선 L에 대해 monotone 이다. (A chain C is monotone w.r.t L if there is at most one intersection point between C and all lines L0 s.t. L0 is perpendicular to L.)

GEOS에서는 약간 속성을 바꾸어 monotone chain을 다르게 정의하였다. 다른 정의에 따르면 한 개의 monotone chain 속의 모든 선이 서로 겹치지 않는 것은 물론 양 끝 선의 끝 점으로 이루어진 MBR (envelope) 속에 모든 선이 속한다. 따라서, 2개의 monotone chain이 있을 때 MBR의 비교를 통해 더 빨리 intersection을 찾을 수 있을 것이다. 이를 위해 GEOS는 다음과 같은 방법으로 monotone chain을 구성한다. 아래 그림에서 같은 색의 점들이 한 monotone chain에 속한다. 색이 칠해져 있지 않는 점들은 양 쪽의 monotone chain에 속하는 것이다. 즉, 빨간색과 보라색 monotone chain은 1개의 점을 공유한다.

이제, Monotone chain을 바탕으로 sweep line algorithm을 통해 intersection을 찾는다. 일반적으로 x축으로 정렬을 하고, x축에 수직인 선(sweep line)을 긋고 이와 겹치는 객체들 (여기서는 monotone chain) 사이에서만 intersection을 찾는다. 각 점의 x좌표에 해당하는 점에 대해서만 선을 그으면 된다는 점은 쉽게 도출해 낼 수 있다. Monotone chain을 사용할 경우, 각 chain의 시작점과 끝점의 x좌표를 사용하여 현재 sweep line과 겹치는 monotone chain의 집합을 쉽게 유지할 수 있다. GEOS에는 이 정보를 event형태로 관리한다. Monotone chain의 시작점을 기준으로 insert event를 삽입하고 끝점을 기준으로 delete event를 사용한다.

Computing IM (continued)

이제 코드로 돌아와서 어떻게 위 알고리즘을 사용했는지 알아보자.

unique_ptr<EdgeSetIntersector> esi(createEdgeSetIntersector());

typedef vector<Edge*> EC;

EC self_edges_copy;
EC other_edges_copy;

EC *se = edges;
EC *oe = g->edges;
if ( env && ! env->covers(parentGeom->getEnvelopeInternal()) ) {
    collect_intersecting_edges(env, se->begin(), se->end(), self_edges_copy);
    se = &self_edges_copy;
}
if ( env && ! env->covers(g->parentGeom->getEnvelopeInternal()) ) {
    collect_intersecting_edges(env, oe->begin(), oe->end(), other_edges_copy);
    oe = &other_edges_copy;
}
esi->computeIntersections(se, oe, si);

여기서, EdgeSetInetersector를 통해 계산하는 것을 확인할 수 있다. EdgeSetIntersector는 intersection을 찾는 알고리즘의 추상화 클래스로, GEOS에서는 현재 위에 설명한 monotone chain sweep line algorithm 을 구현한 SimpleMCSweepLineIntersector를 사용하고 있다. 해당 코드에 대한 내용은 이 글에서는 생략한다. 교점(의 후보)을 찾는다면, (monotone chain algorithm이 선 2개를 반환하여) 이를 LineIntersector에 입력하여 해당 교점이 어떤 교점인지 확인한다. 3가지 경우의 수가 있다. 만나지 않거나, (입력된 두 선분의 끝점이 아닌) 1개의 교점을 갖거나 또는 두 선분이 겹치는 경우가 있다. 이 중 1개의 교점을 갖는 경우 proper하다고 한다. 이 때, 그 1개의 교점이 각 geometry의 boundary가 아닐 경우, properInterior 플래그를 추가로 설정한다.

이러한 정보를 바탕으로 IM값을 결정한다. 각 geometry의 차원, proper 여부 그리고 properInterior 여부가 중요하다. 해당 코드는 다음과 같다.

int dimA=(*arg)[0]->getGeometry()->getDimension();
int dimB=(*arg)[1]->getGeometry()->getDimension();
bool hasProper=intersector->hasProperIntersection();
bool hasProperInterior=intersector->hasProperInteriorIntersection();

if (dimA==2 && dimB==2) {
    if (hasProper) imX->setAtLeast("212101212");
} else if (dimA==2 && dimB==1) {
    if (hasProper) imX->setAtLeast("FFF0FFFF2");
    if (hasProperInterior) imX->setAtLeast("1FFFFF1FF");
} else if (dimA==1 && dimB==2) {
    if (hasProper) imX->setAtLeast("F0FFFFFF2");
    if (hasProperInterior) imX->setAtLeast("1F1FFFFFF");
} else if (dimA==1 && dimB==1) {
    if (hasProperInterior) imX->setAtLeast("0FFFFFFFF");
}

그러나 아직 끝이 아니다. 위에서 찾는 교점은 두 선분의 끝점을 고려하지 않았으므로, 이를 고려해야 한다. 이런 경우 proper한 교점을 찾는 것은 아니지만, 해당 교점을 GeometryGrah의 엣지 값에 매달아 놓게 된다.

(Will be continued)

개발 블로그에 대한 필요성을 느끼기 시작한 것은 오래전이다. 하지만, 이런 저런 이유로 막상 시작하지 못(안) 했다. 그러나 올해부터 생활 환경의 변화를 맞이하면서 블로그도 함께 시작하기로 하였다. 어떤 블로그 서비스를 사용할 지 고민한 중 ghost를 사용하기로 결정했다. 마침 Docker의 공부도 할 필요성을 느꼈기 때문에 ghost와 nginx를 docker에 올려서 사용해 봄으로써 공부도 하고 블로깅도 시작할 수 있는 기회가 되었으면 하였다.

Lightsail 인스턴스 만들기

서버는 AWS의 Lightsail을 사용했다. 기존에 개인적으로 ec2를 잠깐 사용해본 적 있으나 ec2보다 좀 더 간편하게 할 수 있다고 한 Lightsail로 서버를 호스팅하기로 결정했다. Lightsail에서 인스턴스를 생성하는 법은 정말 간단했다. ec2에서 인스턴스를 올리기 위해서 할 수 있는 설정에 비하면 Lightsail에서 할 수 있는 설정의 수는 적다. 간단히 인스턴스를 올리는 것이 목적이라면 Lightsail이 좀 더 편리한 선택이 될 것이다.

블로그를 위해 도쿄 리전의 Ubuntu 18.04 LTS인스턴스를 선택하였다. 클릭을 통해 다음과 같이 간단히 설정할 수 있다.

다음으로 사용할 플랜을 고르면 더이상 할 것이 없다. 플랜만 고르면 사용한 프로세서, 메모리, 스토리지, 그리고 네트워크 량 까지 묶어서 제공받는다.

이 것 만으로도 인스턴스를 받을 수 있지만, 나는 추가적으로 SSH key pair를 다른것으로 등록시켰다. Lightsail에서는 dbms 시스템, 추가적인 스토리지 디스크, 스냅샷 그리고 정적 IP 까지 지원한다. 가동중인 인스턴스가 있다면 그 인스턴스에 묶여있는 정적 IP의 유지비는 내지 않아도 된다. 이제 인스턴스를 손에 얻었으니 ssh를 사용해 인스턴스에 접속할 수 있다.

Docker 설치 및 docker-compose

Docker와 Docker-compose가 무엇인지 그리고 어떻게 설치할 수 있는지에 대한 훌륭한 (한국어) 글들(블로그글, 한국어 docker 문서 집합)이 인터넷에 많아서 참고로 진행하기 쉬웠다. ghost로 블로그를 호스팅하기 위해 다음과 같은 docker-compose를 작성했다.

version: '3'

services:
    nginx:
        container_name: nginx
        image: nginx
        ports:
            - 80:80
            - 443:443
        volumes:
            - ./nginx/conf.d:/etc/nginx/conf.d
            - ./nginx/ssl:/etc/ssl
        links:
            - ghost:ghost

    ghost:
        container_name: ghost
        image: ghost
        volumes:
            - ./ghost/content:/var/lib/ghost/content
            - ./ghost/config.production.json:\
                        /var/lib/ghost/config.production.json
        environment:
            - NODE_ENV=production

nginx를 사용해서 리버스 프록시를 통해 ghost의 서비스에 접속할 수 있게 하였다. MySQL을 추가로 사용하여 ghost가 db로 사용할 수 있도록 하고 싶었으나, 내가 선택한 Lightsail 플랜의 메모리 크기 (1GB)를 고려하여 사용하지 않았다. 이제 docker-compose를 사용해서 컨테이너를 한번에 올리거나, 실행 및 정지 시킬 수 있다.

처음에는 networks를 통해 네트워크를 명시적으로 지정하고, 각 컨테이너를 네트워크에 포함시키는 것을 통해 nginx가 ghost를 볼 수 있게 하고 싶었으나 잘 되지 않아서 명시적으로 links를 사용하여 볼 수 있도록 하였다.

Nginx 및 Ghost 설정

Docker-compose 설정에서 볼 수 있듯이, 설정 파일을 통해 각각 nginx와 ghost를 설정하였다. ghost의 경우 설정파일을 이용하지 않고 환경변수를 통해 설정할 수도 있다. Nginx의 기본 설정 파일을 보면 다음과 같은 사실을 알 수 있다.

user  nginx;
worker_processes  1;

error_log  /var/log/nginx/error.log warn;
pid        /var/run/nginx.pid;


events {
    worker_connections  1024;
}


http {
    include       /etc/nginx/mime.types;
    default_type  application/octet-stream;

    log_format  main  '$remote_addr - $remote_user [$time_local] "$request" '
                      '$status $body_bytes_sent "$http_referer" '
                      '"$http_user_agent" "$http_x_forwarded_for"';

    access_log  /var/log/nginx/access.log  main;

    sendfile        on;
    #tcp_nopush     on;

    keepalive_timeout  65;

    #gzip  on;

    include /etc/nginx/conf.d/*.conf;
}

맨 아래 줄을 보면 자동으로 conf.d/의 모든 conf파일을 포함하고 있다. 따라서, (컨테이너 내부에 있는) 이 폴더를 호스트와 연동시켜 호스트에서 설정한 conf 파일을 사용하게 하였다. Nginx 설정 파일에서 80포트로 들어온 http를 https로 리다이렉트 해주고, 433포트로 들어온 https에서 ssl 설정과 ghost로의 리버스 프록시를 진행하였다. 사용한 conf 파일들은 다음과 같다.

ghost의 컨테이너를 설정할 때 환경변수로 NODE_ENV =  production으로 설정하여 config.production.json을 읽도록 설정하였다. 그래야만 ghost가 올바른 설정파일을 읽는다. ghost 설정 파일 내부에는 url정보와 sqlite3를 위한 정보 등을 설정할 수 있다. 그 외 이미지 압축을 할 것인지 여부도 나는 false로 설정하였다. 공식 문서에 어떤 설정을 할 수 있는지 나와있어 참고하면서 진행했다. 내가 사용한 설정 json파일은 다음과 같다.

{
    "url": "https://elenesgu.dev",
    "server": {
        "host": "0.0.0.0",
        "port": 2368
    },
    "mail": {
        "service": "Gmail",
        "transport": "SMTP",
        "options": {
            "host": "smtp.gmail.com",
            "port": "465",
            "secureConnection": true
        }
    },
    "database": {
        "client": "sqlite3",
        "connection": {
            "filename": "/var/lib/ghost/content/data/ghost.db"
        }
    },
    "paths": {
        "contentPath": "/var/lib/ghost/content/"
    },
    "imageOptimization": {
        "resize": false
    }
}

설정 이후

지금 보고 있는 이 블로그는 위와 같은 과정 및 설정을 통해 탄생하였다. 스스로 웹 서비스를 호스팅한 경험이 없어서 새롭기도 하여 재밌게 진행할 수 있었다. 처음 SSL Lab 에서 이 블로그 사이트를 검증했을 때는, B등급으로 책정되었고 이를 해결하기 위해 검색을 통해 nginx 설정을 수정하는 과정을 걸쳤다. 아직 A+는 아니지만 차후 공부해 나가면서 수정해 나갈것이 기대된다.

도메인

이글의 개발 과정이 현재 도메인 (elenesgu.dev)에서 이루어진 것이 아니다. 지인의 도메인을 빌려 블로그를 구축하였고, 그 이후 도메인을 구입하였다. Google Domain에 구입하였으며 (서브 도메인을 포함하여) 다양한 설정이 있었으나, 나는 도메인 -> IP의 포워딩만 설정해 둔 상태다.

사진 자료에서는 2가지 방법으로 데이터를 표현하고 있다.

• 좌표를  직접적으로 표현하는 방법:
  파란색으로 표시된 객체들은 직접 좌표를 통해 표현되고 있다. 사진에서는 (시작점으로 부터) 2 단위 만큼 떨어진 곳이라는 형태로 점을 표현하거나 (역시 시작점으로부터) 11단위 만큼 떨어진 곳부터 18단위 만큼 떨어진 곳 사이라는 형태로 선을 표현하고 있다.
• 좌표를 상대 거리를 통해 표현하는 방법:
  빨간색 객체들은 특정 기준 점을 바탕으로 상대적으로 표현되고 있다. 사진에서는 특정 점 (여기서는 시작점) 으로 부터 6단위 떨어진 곳이라는 형태로 점을 표현하거나 13위에서 8단위 거리만큼이라는 형태로 선을 표현하고 있다.

기존 spatial data type으로 이런 정보를 표현할 수 없는것은 아니다. 그렇지만, LRS를 사용하면 다양한 장점이 있다. 가장 큰 장점으로는 기반으로 하는 선형 요소를 공유한다는 점이다. 만약 기반 선형 요소의 데이터에 변화가 가해질 경우 그 위에 정의된 여러 요소들은 따로 수정을 하지 않아도 맞춰서 변화가 가해진다고 볼 수 있다. 또는, LRS위의 객체들이 여러 속성을 지녀야 할 경우에도 유용하다. 한 선형 요소 위에 여러 속성들(attributes)이 있을 때, 기존의 spatial geometry types로 저장할 경우 여러객체로 나눠서 저장해야하지만, LRS에서는 쉽게 저장 가능하다. 예를 들어, 어떤 기반 요소인 도로에 대해서 속도, 포장정보(아스팔트 및 콘크리트 등),이정표 속성 등이 있을 경우, (서로 겹치지 않는) 작은 단위들로 나누어서 각 속성들을 저장할 필요가 없다.

LRS in Oracle Spatial

Spatial database인 Oracle Sptial에서도 LRS를 지원한다. LRS의 기반 선형 요소를 오라클에서는 geometric segment 라고 부른다. Geometric segment가 될 수 있는 것들은 직선, 곡선 그리고 폴리곤 등을 포함한다. 1개의 geometric segment는 시작점과 끝점이 정의되어 있어야 한다. (폴리곤의 경우 시작점과 끝점이 같다.) Geometric segment는 점의 sequence로 정의되어 있다. 이 sequence의 시작점과 끝점을 제외하고 나머지를 shape point라고 부른다. Shape point를 포함하여 모든 점들은 좌표정보와 measure라는 값을 가지고 있다. 이 measure는 위에서 서술한 상대적인 거리를 표현할 때 쓰이는 지표이다. 좌표공간상에서 두 점의 거리가 가깝다고 하여도, measure값의 조정을 통해 LRS상에서는 그 거리를 조절할 수 있다.

Geometric segment는 다음과 같은 요소 및 개념들이 있다.

• direction
  Segment의 direction은 시작점으로부터 끝점까지의 순서를 통해 정의된다. 각 점의 measure값들은 direction에 따라 계속 증가하거나 계속 감소해야한다.
• measure
  measure는 어떤 점이 시작점으로부터 얼마나 떨어져 있는지 나타내는 척도이다. 각 점에 정의된 measure들을 통해 계산할 수 있다. (linear interpolation)어떤 두 점의 measure 값이 각각 50, 80으로 정의되어있다면, 그 두 점의 정확히 중간에 있는 점의 measure 값은 65가 되는 식이다.
• offset
  offset은 segment자체의 이동을 뜻한다. 양의 offset일 경우, direction의 왼쪽 방향으로 segment의 이동을 뜻하고, 음의 offset은 그 반대를 뜻한다.
• projection
  어떤 점에 대해, segemnt위의 가장 가까운 점을 나타낸다.

 이러한 요소 및 개념들은 Oracle Spatial Concept 문서의 사진에서 시각적으로 확인할 수 있다.

Handling a geometric segment

Geometric segment는 SQL 또는 PL/SQL을 통해 객체를 생성할 수 있다. Geometric segment는 다른 spatial geometry type과 같이 SDO_GEOMETRY라는 object type에 저장된다. 2차원 좌표계에서의 geometric segment는 measure까지 합하여 한 점당 3차원의 정보를 저장한다. 따라서, SDO_GEOMETRY의 SDO_GTYPE값이 3302으로 설정된다. 이는 3차원이며, LRS의 (2차원) geometry이고, line 타입 (02) 을 나타낸다.

SDO_GEOMETRY(
  3302,  -- line string, 3 dimensions: X,Y,M
  NULL,
  NULL,
  SDO_ELEM_INFO_ARRAY(1,2,1), -- one line string, straight segments
  SDO_ORDINATE_ARRAY(
    2,2,0,   
    2,4,2,   
    8,4,8,   
    12,4,12, 
    12,10,NULL,
    8,10,22,
    5,14,27
  )
)

3번째 원소의 값이 각 점의 measure값이다. 비어있을 경우 (NULL) 자동으로 계산하여 채워주게 된다.  이렇게 생성한 geometric segment를 생성, 제어, 및 탐색 등을 지원하기 위해 Oracle Spatial에서는 PL/SQL Package (MDSYS.SDO_LRS) 를 제공한다. 공식 문서에서분류한 방법으로 PL/SQL Package 안의 subprogram을 하는 일으로 분류해보면 다음과 같다.

• Geometric segment를 생성하고 수정
• Geometric segment에 관한 정보 조회 및 검증
• SDO_GEOMETRY와 LRS geometric segment 간의 변환

이 중 몇개의 subprogram을 골라 이 글에서 소개해 보려고 한다.

Geometric segment의 생성 및 수정

여기에 속한 subprogram들을 바탕으로 할 수 있는 일들은 다음과 같다.

• Geometric segment의 clipping:
  2개의 measure 값을 입력으로 받아 해당하는 부분의 geometric segment를 반환한다.
• Intersection:
  2개의 LRS geometric segment 또는 geometric segment와 SDO_GEOMETRY 사이에서 (topologically) 겹치는 SDO_GEOMETRY를 반환한다. geometric segment는 기본적으로 선의 집합일 것이므로, 반환되는 SDO_GEOMETRY는점, 선 또는 선집합(linestring or multiline)일 것이다.
• Offset:
   위에서 서술한 offset를 반환한다. 두 개의 measure값을 받아서, 그 measure사이의 (sub) geometric segment에 대해서 offset한 geometric segment를 반환한다. 두 mesaure 값을 각각 시작점과 끝점으로 한다면 전체 segment에 대해 offset변환한 객체가 반환된다.
• 기타 Split을 통해 2개로 나누던가, Reverse등을 통해 방향을 바꿀 수 있다.

조회 및 검증

여기에 속한 subprogram들을 사용하여 데이터들의 조회 및 검증이 가능하다.

• LOCATE_PT:
  Geometric segment와 measure값을 입력으로 받아, 그 위치의 점을 SDO_GEOMETRY 형태로 반환한다.
• 기타 valid 여부를 검증 하는 함수나 간단한 값을 조회하는 subprogram들이 존재한다.

변환

SDO_GEOMETRY의 객체를  LRS geometric segment로 변환하거나 그 역이 가능하다.

LRS in another spatial database

PostGIS

PostGIS에서도 LRS 에 관한 여러 함수를 지원한다. 예를 들어, ST_LineInterpolatePoint는 선 형태의 geometry 타입 (ST_geometry 또는 OGC geometry) 과 실수 값 (0과 1사이)을 받아, 선 형태의 geometry의 시작점에서 실수 값 만큼 떨어진 점을 반환한다. ST_LineSubstring 를 사용하면, 어떤 선 형태의 geometry 상에서 특정 부분을 잘라낼 수 있다. 즉, 인자로 들어가는 두 실수가 각각 1/3, 2/3 이라면, 3등분 한 선 중 가운데 부분의 geomtry를 반환한다. Oracle Spatial과 마찬가지로 기반 선형 요소(base line element)에 measure을 추가하여 임의의 거리관계를 정의할 수 있다. LRS에 관한 다른 함수들은 공식 문서에서 찾을 수 있다.

마치며

교통사고 정보 같은 선(도로)를 따라 일어나는 정보가 많이 입력으로 들어오고 선의 부분에 대한 여러 속성을저장해야 할 때 유용하게 사용할 수 있는 LRS에 대해 공부한 내용을 공유해 보았다.