728x90

방문자 패턴은 연산(행동)을 적용할 클래스를 변경하지 않고도 새로운 연산을 정의할 수 있게 하는 패턴이다.

 

방문자 패턴은 단일 클래스로만 구성 되어 있을때도 유용하지만, 이미 수많은 클래스가 "군"(많은 결합)

이루고 있어서, 새로운 기능 추가시 많은 비용( 많은 수정 )이 들어갈때 매우 유용하게 사용할 수 있다.

(수정하는 양이 많아지면, qa 대상도 곱으로 늘어난다)

 

예를 들어 현재 라이브 서비스중인 게임회사에 새로 입사했다.

프로그래머가 1명뿐이던 영세 회사인데, 이전 프로그래머가 그만두면서 들어와서 legacy 코드를 물어볼 사람도 없다.

(실제 상황이라면, 뤈)

 

현재 웹서버 기반(HTTP)으로 게임을 만들었으나, 답답한 지연성 때문에 좀더 compact하게

깡 TCP로 만들기로 하여, 일단 간단히 TCP Socket으로 송수신 가능한 기능을 만들었다.

class TCPClient
{
public:
	//@brief : socket 초기화 및 서버 연결등의 처리
	void init(void) noexcept;

	//@brief : 별도의 스레드에서 로그아웃, 종료, 서버 응답 없음 등의 이유로 게임이 종료되어야 할때까지 실행됨
	void run(void) noexcept;

	//@brief : 송/수신 관련 인터페이스. 
	//{@
	void send(void) noexcept;
	void receive(void) noexcept;
	//@}
};

이제 기존에 HTTP로 요청하던 부분들을 다음과 같이 변경할 것이다.

class Player
{
public:
	void func(void) noexcept
	{
		// 플레이어 관련 동기화 데이터 전송
		//httpClient->requect();
		tcpClient->send();
	}
};

 

근데 얼마 안가서 또 이번에는 TCP의 "연결지향성"이 여전히 느리다 판단하고, UDP로 변경하자고 한다....

이럴때마다, 코드를 다 엎는 거는 힘들고(심지어 라이브 서비스중) 지친다. 이럴때 "방문자 패턴"을 적용해보자.

class NetworkingVisitor
{
public:
	virtual void visit(Player* player) noexcept = 0;
};

class TCPVisitor : public NetworkingVisitor
{
public:
	virtual void visit(Player* player) noexcept
	{
		// tcp용 패킷 만들기
		_tcpClient->send();
	}
};

class HTTPVisitor : public NetworkingVisitor
{
public:
	virtual void visit(Player* player) noexcept
	{
		// http용 패킷 만들기
		_httpClient->request();
	}
};

networking 기능을 확장시킬 NetworkingVisitor를 interface로 만들고, 프로토콜별로 기능을 수행할 TCPVisitor와

HTTPVisitor를 추가하였다. 

 

이제 Player class는 visitor를 방문하기만 하면 해당 기능을 사용할 수 있다!

#define Networking_Method new TCPVisitor()
//#define Networking_Method new HTTPVisitor();

class Player : GameObject
{
public:
	void func(void) noexcept
	{
		// 플레이어 관련 동기화 데이터 전송
		//httpClient->requect();
		//tcpClient->send();

		NetworkingVisitor* visitor = Networking_Method;
		visitor->visit(this);
	}
};

이렇게 Player코드에서 아예 네트워킹 관련 코드는 빠지게 되고, Player class와

TCPClient class(혹은 HTTPClient)와의 결합도 사라졌다. (c++이니까 define으로 switch 쉽게 해둔 것은 덤.)


서두에서 말했듯 수많은 클래스에 걸쳐서 비슷한 연산(기능)을 추가할때 기존 구조를 확장할 수 있어서

유용하게 사용할 수 있다.

 

또한, 위 예제 처럼 visitor만 교체하면 새로운 기능을 할 수 있으므로, 일종의 "전략 패턴"으로도 볼 수 있다.

728x90

'프로그래밍 > C++' 카테고리의 다른 글

Observer Pattern  (0) 2021.08.13
Bridge Pattern  (0) 2021.07.15
Prototype Pattern  (0) 2021.07.13
Adaptor Pattern  (0) 2021.06.30
Factory Pattern - Simple Factory  (1) 2021.02.21
728x90

옵저버 패턴은 어떤 객체의 상태가 변할 때 함께 동작하고 싶은 즉, 그 객체에 의존성을 가진

객체들이 자동으로 감지하고 갱신될 수 있게 하는 패턴이다.

 

1. 의존 관계 분리

 

보통 이러한 패턴들을 접해보지 않은 분들( 혹은 패턴을 접했어도, 그 중요성(존재 이유)을 잘 모르는 분들)은

어떤 객체의 변화에 따라 함께 변화해야할때 다음과 같이 작성한다.

class Player
{
public:
	void move(void) noexcept
	{
		// 소유하고 있는 인형을 움직여 준다.
		_puppet.move();
	}
private:
	Puppet  _puppet;
};

void main()
{
	Player player;
	player.move();
}

player의 움직임에 따라 player가 보유 및 소환한 퍼펫들이 있다면, 퍼펫들의 move() 메소드를 같이 호출한다.

player가 이러한 아주 간단한 클래스 라면 문제가 없지만, 점점 복자해지고 수많은 필드를 가지게 되면

문제가 발생한다.

void move(void) noexcept
{
	// 소유하고 있는 인형을 움직여 준다.
	_puppet.move();

	// 카메라 위치를 적절히 바꾼다.
	_camera.move();

	// 캐릭터를 중심으로 표시하는 미니맵 정보들
	_minimap.updateActors();

	// 캐릭터를 따라다니는 status 정보
	_status.updateInfos();

	// ... 수많은 의존 객체들 ...
}

좀 극단적인 예 이지만, 이러한 코드 작성이 있을법한 얘기이다. (게임 뿐만 아니라, 응용 프로그램, 웹 등에서도....)

 

요러한 의존 관계를 옵저버 패턴을 통해 분리할 수 있다.

 

2. 옵저버 패턴 구현

객체의 상태변화가 여러개 라면 옵저버들은 어떤건 받고 어떤건 받고 싶지 않을 때가 있다. 그래서 옵저버들의

"관심사"를 표현할 event type 객체를 만든다.

class EventType
{
public:
	EventType(const std::string& typeName) noexcept
		: _typeName(typeName)
	{
	}

	const std::string& getTypeName(void) const noexcept
	{
		return _typeName;
	}

private:
	std::string	_typeName;
};

그 다음은 주체(Subject, 위 예제에서 Player)의 상태가 변경이 일어나면 자동으로 감지하여

update()가 호출 되는는 단순 Observer 객체이다. update() 메소드는 재구현 되도록 virtual로 만든다.

class Observer
{
public:
	virtual void update(const EventType* eventType) noexcept
	{
		std::cout << "event 처리중" << eventType->getTypeName().c_str() << std::endl;
	}
};

옵저버들을 등록하고 관리할 Subject 객체 이다. (편의를 위해 detach()및 메모리 해제는 작성하지 않았다)

class Subject
{
public:
	void attach(const EventType* eventType, Observer* observer) noexcept
	{
		TObservers* observers = nullptr;

		TAccessor accessor = _mapper.find(eventType->getTypeName());

		//1) find 실패시 TObservers 새로 만들어서 넣어두자
		if (accessor == _mapper.end())
		{
			observers = new TObservers;
			_mapper.insert(make_pair(eventType->getTypeName(), observers));
		}
		else
		{
			observers = accessor->second;
		}

		//2) event type에 대한 observer 목록에 넣는다.
		observers->push_back(observer);
	}

	void notify(const EventType* eventType) noexcept
	{
		TObservers* observers = nullptr;

		TAccessor accessor = _mapper.find(eventType->getTypeName());

		//1) find 실패시 아무것도 안함
		if (accessor == _mapper.end())
		{
			return;
		}

		//2) observer 목록을 돌며 update
		observers = accessor->second;
		for (int i = 0; i < observers->size(); ++i)
		{
			observers->at(i)->update(eventType);
		}
	}

private:
	using TObservers = std::vector<Observer*>;
	using TEventObserverMapper = std::unordered_map<std::string, TObservers*>;
	using TAccessor = TEventObserverMapper::iterator;

	TEventObserverMapper	_mapper;
};

event type객체의 type 명으로 _mapper에 옵저버 그룹을 등록을 한다. 이제 옵저버들은 관심사(event type)에 따라

원하는대로 통지를 받을 수 있다. notify() 메소드가 그 구현 예이다.

 

이제 Player의 move() 메소드를 간단하게 만들자. 기존에는 Player 객체에서 "강한 결합"상태로 직접 호출 시켜 줬기

때문에, 필드(멤버)로 가지고 있거나 어딘가에서 get() 해 와서 update()를 호출해야 했다.

 

이제는 해당 필드를 제거 하고 다음과 같이 한다.

class PlayerEvent
{
public:
	static EventType	_MOVE_;
};
EventType PlayerEvent::_MOVE_("Move");


class Player : public Subject
{
public:

	void move(void) noexcept
	{
		notify(&PlayerEvent::_MOVE_);
	}
};

Player 객체가 Subject를 상속하고, move()시 notify()를 호출하도록 했다. 이제 Player객체의 move에 관심이 있는

객체들은 다음과 같이 구현 하면 된다.

class Puppet : public Observer
{
public:
	virtual void update(const EventType* eventType) noexcept
	{
		move();
	}

	void move(void) noexcept
	{
		std::cout << "Puppet::move() 호출됨!" << std::endl;
	}
};


void main()
{
	Player player;
	Puppet puppet;

	//1) 옵저버 등록
	player.attach(&PlayerEvent::_MOVE_, &puppet);

	//2) Puppet::move()도 자동으로 호출된다.
	player.move();
}

대략적 클래스 다이어그램

Subject 구현시 mapper("관심사"와 옵저버들 매핑)를 기본으로 구현했는데, GOF 책에서는 단순 옵저버 리스트로

설명하고 있다. 나는 좀더 일반적 event system의 모습으로 구현하고 싶어서 그렇게 하였다.

 

모든 객체를 "복합체"로 구성하면 "통지"를 쉽게 해줄 수 있지만,

프로젝트 전체에 걸쳐서 모든 객체를 복합체로 만들 수도 없는 노릇이다..

 

그냥 유명 프레임워크(보편적 event 시스템을 갖추고 있다) 없이 밑바닥 부터 시스템을 만든다면,

무조건 옵저버 패턴의 구현체를 만들어두자!! (제발..ㅠ)

728x90

'프로그래밍 > C++' 카테고리의 다른 글

Visitor Pattern  (0) 2021.08.21
Bridge Pattern  (0) 2021.07.15
Prototype Pattern  (0) 2021.07.13
Adaptor Pattern  (0) 2021.06.30
Factory Pattern - Simple Factory  (1) 2021.02.21
728x90

브리지(가교) 패턴은 추상과 구현을 분리하여 각각이 독립적으로 확장될 수 있도록 하는 패턴이다.

 

 

들어가기 앞서, 확실히 해야할 것이 있다. 우리는 "상속"을 할때 보통 2가지 이유로 사용한다.

 

1. 추상적 개념 구현

추상의 구현

이건 용어적으로 JAVA에는 해당하지 않을 수 있다. (interface, implements 키워드가 따로 있기 때문)

어쨌든 그림과 같이 추상적 개념(기능)을 여러 형태로 구현하기 위해 "상속"시킨다.

 

2. 기능 확장

기능 확장

기존 클래스를 활용 및 확장하여 새로운 기능을 사용자에게 제공하기 위해 상속시킨다.


1번 2번 둘다 상속을 이용하지만 1번의 경우 서브 클래스에 특화된 기능을 추가하기 어렵다.

client는 FileSystem으로만 추상적 기능을 이용하기 때문이다.

반대로 2번은 client는 서브 클래스인 TV class만 사용하기 때문에 마음껏 확장 가능하다.

1번과 2번의 차이를 알면 브리지 패턴의 필요성을 잘 알게 된다.


여러분은 게임내 다양한 요소들을 하나의 추상적 개념으로 핸들링 하기 위해 다음과 같은 class를 정의하였다.

그리고나서, 한번 배치되면 움직이지 않는 StaticObject와 물리 엔진에 따라 움직이고,

충돌하는 등의 움직일 수 있는 DynamicObject로 두 형태로 구현하였다.

이때 사용자 입력에 따라 조작이 되는 Object 즉, UI 기능을 하는 Object의 추가 요구사항이 발생하였다.

그래서 UIObject를 추가하였다.

근데 생각해보면, UIObject는 확장 기능이다.

StaticObject가 조작될 수 있고, DynamicObject가 조작될 수 있다.

StaticObject도 DynamicObject도 UIObject가 될 수 있어야 한다.

죽음의 다이아몬드 2개~

이렇게 되니 죽음의 다이아몬드가 된다... UIStaticObject와 UIDynamicObject는 하는 수 없이

StaticObject, DynamicObject를 상속받지 않고 중복 구현하여 피할 수 있긴 하지만 여전히 구리다.

그래서 다음과 같이 변경하였다.

이런 구조를 가지면 좀더 깔끔하게 해결되지만, 문제는 이제 StaticObject와 DynamicObject는

UIObject에 강한 의존을 가지게 되었다... UI기능을 하지 않아도 상속하고 있으니 실제

코드에서 처리가 복잡해질 것이다.

 

앞서 얘기한 추상부 구현과 기능 확장이 상속으로만 해결하려 하여 이러한 문제가 발생하였다.

브리지 패턴은 이것을 분리해주는 패턴이다!

브리지 패턴을 적용하여 재설계된 모습

추상 기능부와 구현부를 분리하여 GameObject와 GameObjectImpl로 나누었다.

UIObject는 GameObject에 UI 조작기능을 확장한 것으로 GameObject를 확장시켰고,

StaticObject와 DynmiacObject는 GameObject 기능의 구체적 구현이므로 GameObjectImpl를 구현하고 있다.

이제 UI 조작이 필요한 GameObject를 다룰때 사용자는 UIObject를 인스턴스화하고,

필드에 있는 _impl를 통하여 StaticObject나 DynamicObject를 GameObjectImpl을 통하여 조작하면 된다.

추상과 구현이 분리되어 있어서 각각 따로 확장할 수 있게 되었다!


브릿지 패턴의 이러한 유연한 구조에도 불구하고 역시 단점은 있다. 

1. 기본적으로 코드 복잡성을 늘린다.

2. 기능 클래스를 통해야 하는 추가 오버헤드

728x90

'프로그래밍 > C++' 카테고리의 다른 글

Visitor Pattern  (0) 2021.08.21
Observer Pattern  (0) 2021.08.13
Prototype Pattern  (0) 2021.07.13
Adaptor Pattern  (0) 2021.06.30
Factory Pattern - Simple Factory  (1) 2021.02.21
728x90

프로토타입 패턴은 생성패턴중 하나로, 인스턴스 생성시 원형이 되는 인스턴스로부터

새로운 인스턴스를 만드는 패턴이다.

원형이 되는 나루토로부터 분신을 만든다.

우리가 코딩할때 stack overflow나 블로그를 뒤져가면서 관련 코드를 찾고, 그대로 따라서 타이핑 해도 되지만,
바로 복사해서 쓰듯(ㅋㅋ), 객체의 생성때마다 매번 재생성 하고 관련 파라미터를 세팅해주는 것이 아니라,
이미 세팅된 애를 복사해서 사용할때 유용하다.

이미 세팅된 애를 복사해서 쓰기 때문에, 객체 생성과정이 매우 복잡 or 비용이 크다면 ( DB 에서 참조, File I/O 등 )
해당 비용을 줄일 수 있다!

또, 팩토리 패턴처럼 별도의 creator를 만들지 않아도 되니 서브클래스 숫자가 줄어드는 장점도 있다.


여러분은 npc를 만들고 배치 시키는 기능을 지원하기 위한 사전 작업을 하기로 했다.

오픈월드 게임을 해본 분들은 아시겠지만, 메쉬만 다르고 똑같은 액션 똑같은 행동들을
하는 npc들이 즐비해있다. 실제 게임을 만들때 그러한 npc들을 여기저기 배치해둘 것이다.
(안그럼 밋밋해보이고, 모든 npc를 개성있게 만들기에는 시간이 부족하며 가성비가 안나온다...)

순찰하는 npc

모든 npc들을 핸들링하는데 사용할 NPC 클래스를 만든다.

class NPC
{
public:
	virtual NPC* clone(void) = 0;
#ifdef _DEBUG
	virtual void info(void) = 0;
#endif
};

NPC의 종류에 따라 외부 data(xml, csv, db 등)에서 세팅되는 애들도 있고, 처음부터 값을 static하게 가지는 애들도 있고

천차만별이다. 따라서, npc들 종류에 따라 prototype들을 관리할 store를 만든다.

(GoF에서도 prototype의 관리를 위해 'manager'에 등록하여 구현할 것을 제안하고 있다.)

spawn시킬 npc는 이 store에서 얻어온다.

class NPCStore
{
public:
	static NPCStore* This(void)
	{
		if (nullptr == s_instance)
		{
			s_instance = new NPCStore();
		}

		return s_instance;
	}

	void addNPCPrototype(const std::string& npcName, NPC* npcPrototype)
	{
		_actorRegistry.insert(make_pair(npcName, npcPrototype));
	}

	NPC* getNPC(const std::string& npcName)
	{
		TAccessor npcPrototype = _actorRegistry.find(npcName);

		//1) find 실패 검사
		if (npcPrototype == _actorRegistry.end())
		{
			//1-1) 보통 assert를 띄움
			std::cout << "[NPCStore::getNPC] " << npcName.c_str() << " find 실패하였습니다." << std::endl;
			return nullptr;
		}

		//2) clone 반환
		return npcPrototype->second->clone();
	}

private:
	NPCStore(void) {}

private:
	using TNPCRegistry = std::unordered_map<std::string, NPC*>;
	using TAccessor = TNPCRegistry::iterator;
	static NPCStore*		s_instance;
	TNPCRegistry			_actorRegistry;
};
NPCStore* NPCStore::s_instance = nullptr;

store는 아무래도 전역으로 하나만 존재해야 할 것 같아서 간단한 '싱글턴'으로 구현하였다.

: NPCStore::addNPCPrototype() 메소드로 npc종류에 따른 prototype을 스토어에 등록시킨다.

: getNPC() 메소드로 npc prototype으로부터 npc 인스턴스를 만든다.

 

임의로 무적인 행인 npc와 죽일 수 있는 고정형 npc 두 종류가 있다 가정하자.

// 행인 NPC
class WalkerNPC : public NPC
{
public:
	WalkerNPC(float speed) : _walkingSpeed(speed) {}

	virtual NPC* clone(void) override
	{
		NPC* cloned = new WalkerNPC(0);
		cloned = this;
		return cloned;
	}

#ifdef _DEBUG
	virtual void info(void) override
	{
		std::cout << "[WalkerNPC] speed : " << _walkingSpeed << std::endl;
	}
#endif

private:
	float		_walkingSpeed;
};

// 고정 NPC (고정된 위치에서 특정 행동만 수행 ex: 대장장이)
class FixedNPC : public NPC
{
public:
	FixedNPC(float hp) : _hp(hp) {}

	virtual NPC* clone(void) override
	{
		NPC* cloned = new FixedNPC(0);
		cloned = this;
		return cloned;
	}

#ifdef _DEBUG
	virtual void info(void) override
	{
		std::cout << "[FixedNPC] hp : " << _hp << std::endl;
	}
#endif

private:
	float		_hp;
};

clone 메소드를 override하여 각 종류의 npc 인스턴스를 만든뒤 대입 연산자를 통해 copy 한다.

(인스턴스의 copy를 shallow copy로 할지 deep copy로 할지는 요구사항에 따라 결정하여 구현한다.)

 

이제 npc들의 '원형'들을 만들어 store에 등록해두자!

(예제라 코드로 하지만, 실제 엔진이라면 툴 차원에서 지원할 것이다.)

NPCStore* store = NPCStore::This();

//1) speed가 빠른 행인 npc
NPC* npc = new WalkerNPC(200);
store->addNPCPrototype("Fast_NPC", npc);

//2) speed가 느린 행인 npc
npc = new WalkerNPC(10);
store->addNPCPrototype("Slow_NPC", npc);

//3) hp가 높은 고정 npc
npc = new FixedNPC(100000);
store->addNPCPrototype("High_Hp_NPC", npc);

//4) hp가 낮은 고정 npc
npc = new FixedNPC(20);
store->addNPCPrototype("Low_Hp_NPC", npc);

이처럼 store 같은 'manager'가 있으면 같은 class의 인스턴스라도 다른 state( WalkerNPC의 speed, FixedNPC의 hp)를

가지는 새로운 원형으로 등록시키는게 가능하다!

 

NPC* clonedNPC;

//1) speed가 느린 행인 npc
clonedNPC = store->getNPC("Slow_NPC");
clonedNPC->info();

//2) hp가 높은 고정 npc
clonedNPC = store->getNPC("High_Hp_NPC");
clonedNPC->info();

스토어로부터 새로운 npc 인스턴스를 얻었으니 배치할 수 있다!


이처럼 유용한 패턴이지만 역시 단점도 있다.

바로 clone() 메소드이다.

clone() 메소드를 반드시 구현해야 하는데, 다음과 같은 3가지 사항에서 clone() 메소드 구현이 어려울 수 있다.

1. 이미 존재하는 class를 prototype으로 만드려 할때 어려울 수 있다.

2. 언어적으로 '복사'를 지원하지 않는다.

3. 환형참조가 있는 object

 

또한, concrete class에서만 아주 특별하게 쓰는 field( member variable )가 있고, 이 field를 외부에서

참조해야 하는경우 결국 down cast가 발생한다.

(근데 이건 subclass를 은닉시키는 모든 상황에서 발생가능한 것이므로, 그러한 상황이 나오지 않게

설계해야한다.)

728x90

'프로그래밍 > C++' 카테고리의 다른 글

Observer Pattern  (0) 2021.08.13
Bridge Pattern  (0) 2021.07.15
Adaptor Pattern  (0) 2021.06.30
Factory Pattern - Simple Factory  (1) 2021.02.21
[C++] Cyclic Reference - Weak Reference  (0) 2020.11.11
728x90

어댑터 패턴은 인터페이스간 호환성을 제공하기 위해 사용되는 패턴이다.

 

여행 필수품

우리가 외국가서 콘센트 규격 (전기를 사용하기 위한 인터페이스)이 달라 "어댑터"를 들고 가듯,

 

클라이언트에게 동일한 인터페이스로 제공해야할때 유용하게 쓸 수 있는 패턴이다.

 

(우리는 대한민국 220V 규격의 (ㅇ ㅇ) 콘센트로만 동작하는 기계들을 가지지만, 어댑터를 통해

다른 여러 나라에서도 사용이 가능하다!)

 

 

 

다수의 몬스터를 등장시키는 게임을 만든다고 하자.

 

몬스터 개체를 만들고 특정 버튼을 누르면 진화시키는 요구사항이 있어 evolve() interface가 있다.

class IMonster
{
public: virtual void evolve(void) = 0;
};

디지몬 관련 기능은 신규 기능이라, 여러분이 직접 만들기에 interface를 잘 재정의 하여 만들었다.

class Digimon : public IMonster
{
public: virtual void evolve(void) override
{
  // 진화
}
};

이제 포켓몬 기능을 붙이려 하는데, 문제가 발생했다. 기존에 개발된 포켓몬 모듈을 수정하려 했는데,

 

인터페이스를 상속시킬 수가 없다. 기존 포켓몬 기능의 요구사항중에 외부에서는 "절대" 진화를 못시키는 요구사항이

 

있는 것이다. (최근 디지몬 사이버 슬루스를 재밌게 하고 있는데, 조건만 맞추면 아무때나 진화시킬 수 있는

디지몬에 반해 포켓몬은 진화레벨에 도달해야 자동으로 진화한다. #진화의돌은 무시...)

 

여기서 여러분은 2가지 고민을 한다.

 

1. 이전 요구사항을 무시하고 상속시킨뒤, 관련 사항들을 모두 고친다.

 => 리소스(시간, 돈, 열정, .. )이 많다면 OK다. 아무도 말리지 않는다. 하지만 넘 고된 노가다가 기다린다.

2. 포켓몬 모듈을 건들이지 않고 인터페이스를 맞출 방법 고민

 => 현명하다. 기존 시스템(모듈)을 마구마구 건들이는것은 현명하지 못하다. 잘 설계되어 있건 아니건을 떠나 이미

      잘 동작하고 있는 "콘크리트" 코드이기 때문이다.

 

현명한 여러분은 2번을 생각하여 "어댑터" 패턴을 적용하였다.

class Pokemon
{
//@return : 진화레벨 도달하여 진화한 여부.
public:	bool levelUp(void);
};

class PokemonAdaptor : public IMonster
{
public: PokemonAdaptor(Pokemon* pokemon) : _pokemon(pokemon) {}

public: virtual void evolve(void) override
{
  // 포켓몬이 진화할때까지 레벨업한다.
  while (false == _pokemon->levelUp())
  {
  }

  // 진화
}

private:  Pokemon* _pokemon;
};

이제 이 간단한 adaptor를 도입하여 무사히 프로젝트를 완수하였다.

꼭 위와 같은 형태가 아니어도, 인터페이스 호환을 맞추는 형태라면 여러 형태가 될 수 있다.

 

이런 팔방미인이지만 단점도 존재한다.

 

Adaptor는 클라이언트에게 제공하기 위한 인터페이스와 기존 모듈 양쪽에 "의존성"이 생기기 때문에

 

어느정도 인터페이스가 확립된 두 모듈간 사용하는것이 좋다. 양쪽다 숱하게 수정된다면,

 

Adaptor를 만들어둔 담당자는 스트레스가 많이 올라갈 것이다. ㅋㅋ

728x90

'프로그래밍 > C++' 카테고리의 다른 글

Bridge Pattern  (0) 2021.07.15
Prototype Pattern  (0) 2021.07.13
Factory Pattern - Simple Factory  (1) 2021.02.21
[C++] Cyclic Reference - Weak Reference  (0) 2020.11.11
[C++] Reference Counting  (2) 2020.11.04
728x90

디자인 패턴을 따로 공부하지는 않았고(학부때 관련 전공필수 과목이 없었다...), 현업에서 개발을 하다가

 

접하게 되어 조금씩 생각날때 정리를 해보려한다. 들어가기 전에 기억해야할 것은

 

책에 나온 패턴들을 곧이곧대로 사용하려 하면 안된다. "만능, 치트키" 같은 물건이 아니며, 맹목적으로

 

그러한 설계(상속, 연관등의 구조)를 따를 필요는 없다. 개념을 이해하고 유연하게 바꾸어 사용하자.

 

어차피 곧이 곧대로 적용할 수 있을 정도로 프로덕트 코드들이 단순하지 않다.

(늘 문제는 생각하지 못한곳에서 발생하는 프로그래밍의 오묘한 세계...)

 

개요

먼저는 Manager 계열의 Class 설계시 아주 빈번하게 사용되고 있는 "생성" 패턴인 Factory에대해 알아보려 한다.

 

그중에 가장 단순한 형태인 Simple Factory가 이번 주제인데, 사실 Simple Factory라고 부르지만

 

실제 "패턴"으로 치지는 않는 아주 단순한 구조이다.

 

왜 사용할까?

구상 클래스를 중심으로 작성되는 코드는 결합도가 높아서 나중에 수정사항들이 생기면 "빈번한" 수정을 가해야한다.

 

그래서 결합도를 줄여 유지보수성을 높이기 위해 자주 사용된다.

 

예를들어 다음과 같은 코드가 있다.

class Monster
{
public:
	virtual void attack(void) = 0;
};

class MushroomMonster : public Monster
{
public:
	virtual void attack(void)
	{
		std::cout << "Mushroom attacked!" << std::endl;
	}
};

class SnailMonster : public Monster
{
public:
	virtual void attack(void)
	{
		std::cout << "Snail attacked!" << std::endl;
	}
};

int main(void)
{
	Monster* monster1 = new MushroomMonster();
	Monster* monster2 = new SnailMonster();

	monster1->attack();
	monster2->attack();

	/*
	  ...
	 */

	Monster* monster3 = new MushroomMonster();
	Monster* monster4 = new SnailMonster();

	monster1->attack();
	monster2->attack();

	return 0;
}

Monster class를 상속받는 버섯몬스터 클래스와 달팽이몬스터 클래스가 있고, 단순하게 new를 해서

 

부모 class의 pointer로 받아서 객체를 핸들링 하는 코드가 있다. 이때 기획이 바뀌어 몬스터들에게

 

"체력 게이지"라는 스펙을 넣게 되었다 하자. 모든 몬스터는 반드시 hp를 가져야 하므로, 

 

setter 메소드가 아닌, constructor에 강제하는것이 좋으므로 다음과 같이 변경했다.

class MushroomMonster : public Monster
{
public:
	MushroomMonster(int hp)
		: _hp(hp)
	{
	}

	virtual void attack(void)
	{
		std::cout << "Mushroom attacked!" << std::endl;
	}

private:
	int	_hp;
};

class SnailMonster : public Monster
{
public:
	SnailMonster(int hp)
		: _hp(hp)
	{
	}

	virtual void attack(void)
	{
		std::cout << "Snail attacked!" << std::endl;
	}

private:
	int	_hp;
};

# _hp를 Monster에 추가해줄 수 있지만, 여기서는 순수 interface의 역할만 수행하도록하여 넣지 않음.

 

이렇게 되면 main 함수에서 다음과 같이 수정해줘야 한다.

int main(void)
{
	Monster* monster1 = new MushroomMonster(10); // 수정
	Monster* monster2 = new SnailMonster(20); // 수정

	monster1->attack();
	monster2->attack();

	/*
	  ...
	 */

	Monster* monster3 = new MushroomMonster(10); // 수정
	Monster* monster4 = new SnailMonster(20); // 수정

	monster1->attack();
	monster2->attack();

	return 0;
}

new operator로 구상클래스를 인스턴스화 하고 있는 모든 부분에 수정이 가해진다. 의존도가 높아(결합도가 큼)

 

유지보수가 어려워진다. 생성만 담당하는 간단한 Factory로 결합도를 줄일 수 있다.

class MonsterFactory
{
public:
	enum class MonsterType : int
	{
		eMushroom = 0,
		eSnail,
		eCount
	};

	static Monster* createMonster(MonsterType type)
	{
		switch (type)
		{
		case MonsterType::eMushroom:
			return new MushroomMonster(10);
		case MonsterType::eSnail:
			return new SnailMonster(20);
		default:
			// assertion
			break;
		}
	}
};

int main(void)
{
	Monster* monster1 = MonsterFactory::createMonster(MonsterFactory::MonsterType::eMushroom);
	Monster* monster2 = MonsterFactory::createMonster(MonsterFactory::MonsterType::eSnail);

	monster1->attack();
	monster2->attack();

	/*
	  ...
	 */

	Monster* monster3 = MonsterFactory::createMonster(MonsterFactory::MonsterType::eMushroom);
	Monster* monster4 = MonsterFactory::createMonster(MonsterFactory::MonsterType::eSnail);

	monster1->attack();
	monster2->attack();

	return 0;
}

Factory 클래스는 주로 생성만 담당한다 하지만, 게임쪽에서 Manager란 클래스는 생성&관리 까지하여,

 

Simple Factory의 기능 + 라이프사이클관리(= 소유권 관리) 까지 포함하는 경우가 더러 있다.

 

이제 비지니스 로직에서 new의 직접 사용은 지양하자~

728x90

'프로그래밍 > C++' 카테고리의 다른 글

Prototype Pattern  (0) 2021.07.13
Adaptor Pattern  (0) 2021.06.30
[C++] Cyclic Reference - Weak Reference  (0) 2020.11.11
[C++] Reference Counting  (2) 2020.11.04
힙(Heap)과 완전 이진 트리(Complete binary tree)  (1) 2019.10.31
728x90

Reference Counting 를 알고있어야 합니다. 잘 모르신다면 이쪽으로....

 

개요

순환 참조 문제는 비단 Reference Counting 뿐만이 아니라 다양한 영역에서 이를 피하는것이 매우 중요합니다.

 

설계적 관점에서, 서로 참조를 하는 두 객체가 있다면 의존 관계가 양방향이 되고

 

의존성(Dependency)이 커지기 때문에 코드 관리에 어려움이 생깁니다. (스파게티 요리사!)

 

멀티 스레드( or 프로세스 ) 환경에서는 Resource를 점유한 상태로 새 Resource의 요청이 "순환"하는 경우

 

교착 상태(Dead Lock)에 빠져 무한 대기 상태에 빠지게 됩니다.

 

다시 본론으로 와서, 순환 참조는 항상 안좋다! 라는 것을 기억하시고 살펴볼까요??

 

 

만약 두 객체 다음과 같이 서로를 참조하고 있다면 어떻게 될까요?

<그림1> 순환참조 예

바로 코드로 작성하여 확인 해보죠.

RefCounted 코드는 저번 Reference Counting 내용의 non-Intrusive 구현을 사용하였습니다. (대입 연산자만 추가)

class ObjectA
{
public:
	ObjectA(void) { std::cout << "::A Initailized!" << std::endl; }
	~ObjectA(void) { std::cout << "::A Deinitialized!" << std::endl; }
	RefCounted<ObjectB> referenceB;
};

class ObjectB
{
public:
	ObjectB(void) { std::cout << "::B Initailized!" << std::endl; }
	~ObjectB(void) { std::cout << "::B Deinitialized!" << std::endl; }
	RefCounted<ObjectA> referenceA;
};

int main(void)
{
	RefCounted<ObjectA> countA(new ObjectA);
	RefCounted<ObjectB> countB(new ObjectB);

	std::cout << "countA : " << countA.getCount() << std::endl;
	std::cout << "countB : " << countB.getCount() << std::endl;

	// 여기서 순환 참조 발생!
	countA.get()->referenceB = countB;
	countB.get()->referenceA = countA;

	std::cout << "countA : " << countA.getCount() << std::endl;
	std::cout << "countB : " << countB.getCount() << std::endl;

	return 0;
}

결과:

===========================================

::A Initailized!
::B Initailized!
countA : 1
countB : 1
countA : 2
countB : 2

===========================================

 

결과에서 알 수 있듯이 ObjectA와 ObjectB가 해제되지 않습니다. 해제 과정은 다음과 같은데요.

 

  1. countB가 해제 되며 ObjectB의 count는 1이됩니다. (stack이라 countB가 먼저 해제 됩니다!)

  2. countA가 해제 되며 ObjectA의 count는 1이 됩니다.

  3. ObjectB와 ObjectA를 강제로 해제하지 않는 이상 서로에 대한 참조 카운트가 내려가지 않아

     해제가 되지 않습니다.

 

메모리 관리를 용이하게 하려고 Reference Count를 사용했는데 메모리가 해제 되지 않아버리면 정말 난감 하겠죠?

 

이를 해결 하기 위해 많은 방법이 있지만, 1가지 방법을 소개하고자 합니다.

 

Automatic Reference Counting (Weak Reference)

 

용어 자체는 swift의 출현과 함께 나온 듯 합니다. Objective-C 시절 MRC (Manual Referenc Counting)에서 카운트를

 

내리거(해제)나 올리기(획득) 위해 개발자 직접 Releas, Retain과 같은 코드를 작성했다가, ARC가 출현하면서

 

컴파일타임에 컴파일러가 자동으로 추가해줘서 더이상 적지 않아도 되니 ARC다!! 라는것에 기인한다고 합니다.

(iOS 개발 해본 적은 없어 정확하지 않다면 알려주세요 ㅠㅠ)

 

사실 이게 중요한 것이 아니라, 눈여겨 봐야할건 바로 참조의 수준을 나눈 것입니다.

 

strong, weak 참조로 나누어 순환 참조를 해결하였습니다!!!

 

"약한 참조"는 실제 객체의 참조 카운트를 올리지 않는 것입니다!!

 

어? 그럼 c++이면 걍 한쪽은 raw pointer를 들고 있으면 되지 않나요?

class ObjectA
{
public:
	ObjectA(void) { std::cout << "::A Initailized!" << std::endl; }
	~ObjectA(void) { std::cout << "::A Deinitialized!" << std::endl; }
	ObjectB* referenceB;
};

class ObjectB
{
public:
	ObjectB(void) { std::cout << "::B Initailized!" << std::endl; }
	~ObjectB(void) { std::cout << "::B Deinitialized!" << std::endl; }
	RefCounted<ObjectA> referenceA;
};

이런식으로???

 

좋은 시도지만 애석하게도 dangling이 발생할 수 있습니다. 만약 다른 곳에서 ObjectB의 참조 카운트가 0이 되어

 

해제되었는데 referenceB를 사용하려 한다면 valid한지 알 길이 없습니다.

 

raw pointer만으로 약한 참조를 흉내낼 수 있지만 해당 객체를 사용할 수 있는지 없는지도 알아야 겠죠???

 

c++에서 그 구현체가 바로 weak_ptr 입니다.

 

구현

non-Intrusive 참조 카운터를 구현하며 count를 단순히 object의 count만 만들었는데

 

이제는 count가 두개가 됩니다! 기존 object의 count는 strong count, 약한 참조용으로 weak count가 추가되어

 

"약한 참조자"가 참조를 하는 경우 strong count가 아닌 weak count가 올라갑니다.

 

따라서 피참조자 Object는 strong count가 0이 되면 해제되며, Count Object는

 

strong count도 0이고 weak count가 0이 되면 해제됩니다.

 

: 실제 count를 관장하는 count helper class

class RefCountHelper
{
public:
	RefCountHelper(void)
		: _strongCount(0)
		, _weakCount(0)
	{
	}

	int getStrongCount(void)
	{
		return _strongCount;
	}

	void addStrongCount(void)
	{
		++_strongCount;
	}

	int releaseStrongCount(void)
	{
		return --_strongCount;
	}

	int getWeakCount(void)
	{
		return _weakCount;
	}

	void addWeakCount(void)
	{
		++_weakCount;
	}

	int releaseWeakCount(void)
	{
		return --_weakCount;
	}

private:
	int		_strongCount;
	int		_weakCount;
};

: Count Helper class를 사용하여 strong count를 제어하도록 수정된 RefCouted

template<class Type>
class RefCounted
{
public:
	template<class Type> friend class WeakRefCounted;

	RefCounted(void)
		: _pObject(nullptr)
		, _pRefCount(nullptr)
	{
	}

	RefCounted(Type* pObject)
		: _pObject(pObject)
		, _pRefCount(nullptr)
	{
		addCount();
	}

	RefCounted(RefCounted<Type>& pObject)
		: _pObject(pObject.get())
		, _pRefCount(pObject._pRefCount)
	{
		addCount();
	}

	RefCounted<Type>& operator = (const RefCounted<Type>& lvalue)
	{
		_pObject = lvalue._pObject;
		_pRefCount = lvalue._pRefCount;

		addCount();
		return *this;
	}

	~RefCounted(void)
	{
		if (nullptr != _pObject)
		{
			reset();
		}
	}

	Type* get(void)
	{
		return _pObject;
	}

	int getCount(void) const
	{
		return _pRefCount->getStrongCount();
	}

private:
	void reset(void)
	{
		if (0 >= releaseCount())
		{
			delete _pObject;
		}
	}

	void addCount(void)
	{
		if (nullptr == _pRefCount)
		{
			_pRefCount = new RefCountHelper();
		}
		_pRefCount->addStrongCount();
	}

	int releaseCount(void)
	{
		return _pRefCount->releaseStrongCount();
	}

private:
	Type*			_pObject;
	RefCountHelper*	_pRefCount;
};

: Count Helper class를 사용하여 weak count를 제어하는 WeakRefCounted

template<class Type>
class WeakRefCounted
{
public:
	WeakRefCounted(void)
		: _pObject(nullptr)
		, _pRefCount(nullptr)
	{
	}

	WeakRefCounted(RefCounted<Type>& pObject)
		: _pObject(pObject.get())
		, _pRefCount(pObject._pRefCount)
	{
		addCount();
	}

	WeakRefCounted<Type>& operator = (const RefCounted<Type>& lvalue)
	{
		_pObject = lvalue._pObject;
		_pRefCount = lvalue._pRefCount;

		addCount();
		return *this;
	}

	~WeakRefCounted(void)
	{
		if (nullptr != _pObject)
		{
			reset();
		}
	}

	Type* get(void)
	{
		if (0 >= _pRefCount->getStrongCount())
		{
			// 이미 해제 되었다.
			return nullptr;
		}

		return _pObject;
	}

	int getCount(void) const
	{
		return _pRefCount->getWeakCount();
	}

private:
	void reset(void)
	{
		if (0 >= releaseCount() && 0 >= _pRefCount->getStrongCount())
		{
			delete _pRefCount;
		}
	}

	void addCount(void)
	{
		_pRefCount->addWeakCount();
	}

	int releaseCount(void)
	{
		return _pRefCount->releaseWeakCount();
	}

private:
	Type*			_pObject;
	RefCountHelper*	_pRefCount;
};

WeakRefCounted의 get 메소드를 보시면 strong count가 0이면 nullptr를 반환 합니다. 따라서 이미 해제되었는지

 

알 수 있어서 매우 "스마트"합니다! 이제 ObjectA, ObjectB의 순환 참조 문제를 해결할 수 있습니다!

class ObjectA
{
public:
	ObjectA(void) { std::cout << "::A Initailized!" << std::endl; }
	~ObjectA(void) { std::cout << "::A Deinitialized!" << std::endl; }
	void print(void) { std::cout << "print called!" << std::endl; }
	WeakRefCounted<ObjectB> referenceB; // 약한 참조!
};

class ObjectB
{
public:
	ObjectB(void) { std::cout << "::B Initailized!" << std::endl; }
	~ObjectB(void) { std::cout << "::B Deinitialized!" << std::endl; }
	RefCounted<ObjectA> referenceA;
};

int main(void)
{
	RefCounted<ObjectA> countA(new ObjectA);
	RefCounted<ObjectB> countB(new ObjectB);

	std::cout << "countA : " << countA.getCount() << std::endl;
	std::cout << "countB : " << countB.getCount() << std::endl;

	countA.get()->referenceB = countB;
	countB.get()->referenceA = countA;

	std::cout << "countA : " << countA.getCount() << std::endl;
	std::cout << "countB : " << countB.getCount() << std::endl;

	return 0;
}

결과:

===========================================

::A Initailized!
::B Initailized!
countA : 1
countB : 1
countA : 2
countB : 1
::B Deinitialized!
::A Deinitialized!

===========================================

 

결론

weak_ptr을 적극적으로 쓰자!

728x90

'프로그래밍 > C++' 카테고리의 다른 글

Adaptor Pattern  (0) 2021.06.30
Factory Pattern - Simple Factory  (1) 2021.02.21
[C++] Reference Counting  (2) 2020.11.04
힙(Heap)과 완전 이진 트리(Complete binary tree)  (1) 2019.10.31
[c] SHA-1 구조 및 코드  (2) 2017.12.09
728x90

개요

Reference Counting은 객체의 소유권 관리( = 라이프 사이클 )의 방법 중 하나로 객체를 참조(포인팅) 하고 있는

 

횟수를 추적하여 그 횟수가 0이 되면 메모리에서 해제(소멸)한다.

 

대부분의 Managed Language (python, c#, swift등 메모리 관리를 직접 하지 않는 언어 ) 에서 널리 사용되고 있다.

 

Unmanaged Language (c, c++등) 에서도 결국 객체 관리를 위해 (또한 프로그래머의 실수를 줄이기 위해) 

 

Reference Counting을 구현하여 사용하고 있다...

 

장점

  - 메모리를 직접 해제하는 번거로움이 사라진다. (잘가라 delete)

  - 객체의 소유권을 공유할 수 있다

  - 빠르다. (객체 관리 매커니즘이 비교적 단순하다. feat. Garbage Collection...)

단점

  - 순환 참조 문제가 있다.

 

구현

c++ 에서의 구현방식에는 크게 두가지가 있다.

Intrusive Reference Counting (침습성 참조 카운팅)

  - 객체에 대한 참조 카운트가 "내장" 되어있다.

  - 참조 카운트 매커니즘을 객체가 제공해야한다.

  - 메모리사용은 보통 "비침습성"에 비해 작다.

  - object 해제시 count 정보도 날아가기 때문에 약한 참조를 구현할 수 없다. (=> 순환참조 문제)

<그림1> Intrusive Reference Counting 예시

!주의 : 이해를 돕기 위한 코드로 현업에서 사용시 뚝배기가 깨집니다!!

#include <iostream>

class MyObject
{
public:
	MyObject(void) : _refCount(0) { std::cout << ":: Initailized!" << std::endl; }
	~MyObject(void) { std::cout << ":: Deinitialized!" << std::endl; }

	int getCount(void)
	{
		return _refCount;
	}

	void addCount(void)
	{
		++_refCount;
	}

	void releaseCount(void)
	{
		if (0 >= --_refCount)
		{
			delete this;
		}
	}

private:
	int _refCount;
};

template<class Type>
class RefCounted
{
public:
	RefCounted(Type* pObject)
		: _pObject(pObject)
	{
		_pObject->addCount();
	}

	RefCounted(RefCounted<Type>& pObject)
		: _pObject(pObject.get())
	{
		_pObject->addCount();
	}

	~RefCounted(void)
	{
		reset();
	}

	Type* get(void)
	{
		return _pObject;
	}

private:
	void reset(void)
	{
		_pObject->releaseCount();
	}

private:
	Type* _pObject;
};

int main(void)
{
	RefCounted<MyObject> count1(new MyObject);
	std::cout << "count1 : " << count1.get()->getCount() << std::endl;

	RefCounted<MyObject> count2(count1);
	std::cout << "count1 : " << count1.get()->getCount() << std::endl;
	std::cout << "count2 : " << count2.get()->getCount() << std::endl;

	return 0;
}

결과:

===========================================

:: Initailized!
count1 : 1
count1 : 2
count2 : 2
:: Deinitialized!

===========================================

 

non-Intrusive Reference Counting (비침습성 참조 카운팅; c++의 shared_ptr)

  - 객체에 대한 참조 카운트를 따로 관리한다.

  - 참조 카운트에 대한 포인터가 추가되어 보통 메모리사용이 "침습성"에 비해 크다

  - count 정보가 따로 있어 약한 참조를 구현할 수 있다.

<그림2> non-Intrusive Reference Counting 예시

!주의 : 이해를 돕기 위한 코드로 현업에서 사용시 뚝배기가 깨집니다!!

#include <iostream>

class MyObject
{
public:
	MyObject(void) { std::cout << ":: Initailized!" << std::endl; }
	~MyObject(void) { std::cout << ":: Deinitialized!" << std::endl; }
};

template<class Type>
class RefCounted
{
public:
	RefCounted(Type* pObject)
		: _pObject(pObject)
		, _pRefCount(nullptr)
	{
		addCount();
	}

	RefCounted(RefCounted<Type>& pObject)
		: _pObject(pObject.get())
		, _pRefCount(pObject._pRefCount)
	{
		addCount();
	}

	~RefCounted(void)
	{
		reset();
	}

	Type* get(void)
	{
		return _pObject;
	}

	int getCount(void) const
	{
		return *_pRefCount;
	}

private:
	void reset(void)
	{
		if (0 >= releaseCount())
		{
			delete _pObject;
			delete _pRefCount;
		}
	}

	void addCount(void)
	{
		if (nullptr == _pRefCount)
		{
			_pRefCount = new int;
			(*_pRefCount) = 0;
		}
		++(*_pRefCount);
	}

	int releaseCount(void)
	{
		return --(*_pRefCount);
	}

private:
	Type*	_pObject;
	int*	_pRefCount;
};

int main(void)
{
	RefCounted<MyObject> count1(new MyObject);
	std::cout << "count1 : " << count1.getCount() << std::endl;

	RefCounted<MyObject> count2(count1);
	std::cout << "count1 : " << count1.getCount() << std::endl;
	std::cout << "count2 : " << count2.getCount() << std::endl;

	return 0;
}

결과:

===========================================

:: Initailized!
count1 : 1
count1 : 2
count2 : 2
:: Deinitialized!

===========================================

결론

우리의 C++을 모던하게 쓰자! 적극적으로 shared_ptr을 쓰자!

728x90
728x90

Complete binary tree

 

단 두개의 자식 노드만 갖는 "이진 트리"중 노드가 왼쪽부터 차례대로 채워져 있는 트리를 말한다.

왼쪽은 완전 이진 트리, 오른쪽은 단순 이진 트리

위 그림의 왼쪽은 왼쪽부터 차례대로 채워져 있으므로 완전 이진 트리이다.

(3번 노드의 자식 노드 두개가 모두 채워질 경우 "포화 이진 트리"가 된다.)

 

오른쪽은 2번 노드의 왼쪽 자식 노드가 비어있고 오른쪽 자식 노드가 채워져 있으므로

 

완전 이진 트리를 만족하지 못한다.

 

Heap

 

개발자 채용 필기 테스트에 단골로 나오는 자료구조이므로 잘 알아두자.

 

최소 힙을 기준으로 부모 노드가 항상 자식 노드보다 작은 형태의 "완전 이진 트리"를 말한다.

 

보통 배열로 간단하게 구할 수 있다. 배열로 구현시 (부모 노드 인덱스 = 자식 노드 인덱스 / 2)

 

(왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2) (오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2 + 1)

 

로 인덱싱을 쉽게 할 수 있다.

 

우선 순위 큐(priopriority queue)의 구현시 가장 많이 쓰는 구조가 바로 Heap이다.

 

최소 힙의 조건에 의해 root 노드는 항상 전체 노드중 가장 작은 값이 위치하게 된다.

 

삽입, 삭제만 알면 간단히 구현할 수 있다.

 

삽입

현재 그림과 같은 Heap이 있다고 하자. Heap의 삽입은 먼저 가장 끝의 노드에 이루어진다.

 

여기에 "2"를 추가해 보자. 그럼 다음과 같이 추가가 될 것이다.

부모 노드는 항상 자식 노드 보다 작아야 한다. 현재 새로 추가된 2보다 부모 노드인 6이 더 크므로

 

최소 힙을 만족하지 못한다. 따라서, 둘이 swap을 해준다.

swap후 또 부모 노드를 보니 여전히 최소 힙을 만족하지 못한다. 다시 swap을 한다.

이제서야 최소 힙을 만족하는 형태가 되었다. 이처럼 삽입의 경우 가장 마지막 노드에 새 노드를 추가한 후

 

부모 노드 보다 커지거나 루트 노드가 될 때 까지 swap을 해준다.

 

비교 노드의 인덱스가 1/2씩 줄음으로 시간 복잡도는 O(logN) 이다.

 

삭제

힙의 삭제는 루트 노드에서 이뤄진다. 따라서 2가 pop되어 삭제가 되고 마지막 노드가 루트 노드가 된다.

삽입과 달리 이번에는 최소 힙을 만족 하기 위해 루트 노드로부터 자식 노드로 비교를 한다.

 

왼쪽 자식 노드 부터 확인하는데 마침 3이므로 swap한다.

다시 자식 노드를 확인 해 보니 7이므로 종료한다. 삽입과 동일한 과정을 반대로 할 뿐이므로

 

시간 복잡도는 O(lonN)이다.

 

Code

 

위 삽입, 삭제 기능만 잘 구현하면 된다.

#include <iostream>
using namespace std;

class Heap {
private:
	int* nodes;
	int size;
	int capacity;

public:
	Heap(int defaultCapacity) {
		this->capacity = defaultCapacity;
		this->size = 0;
		this->nodes = new int[this->capacity];
	}

	~Heap() {
		delete this->nodes;
	}

	void add(int data) {
		// 예외 발생( 크기 재할당을 해주어도 된다 )
		if (this->size >= this->capacity)
			throw this->size;

		// 배열로 구현 시 인덱스는 1부터 시작
		this->nodes[++this->size] = data;

		// 순위 조정
		int i = this->size;
		while (i > 1 && this->nodes[i] < this->nodes[i / 2]) {
			swap(i, i / 2);
			i /= 2;
		}
	}

	int pop() {
		// 예외 발생
		if (this->size == 0)
			throw this->size;

		// 첫번째 원소 반환 후 마지막 원소를 첫번째에 대입
		int ret = this->nodes[1];
		this->nodes[1] = this->nodes[this->size--];

		// 조정
		int i = 1;
		while (this->size >= (i * 2 + 1)) {
			if (this->nodes[i] > this->nodes[i * 2]) {
				swap(i, i * 2);
				i *= 2;
			}
			else if (this->nodes[i] > this->nodes[i * 2 + 1]) {
				swap(i, i * 2 + 1);
				i = i * 2 + 1;
			}
			else {
				break;
			}
		}

		return ret;
	}

	void printAll() {
		if (this->size == 0) {
			cout << "This heap has no element." << endl;
			return;
		}

		cout << "size : " << this->size << endl;
		for (int i = 1; i <= this->size; i++) {
			cout << this->nodes[i] << " ";
		}
		cout << endl;
	}

private:
	void swap(int idx1, int idx2) {
		int tmp = this->nodes[idx1];
		this->nodes[idx1] = this->nodes[idx2];
		this->nodes[idx2] = tmp;
	}
};
728x90

'프로그래밍 > C++' 카테고리의 다른 글

[C++] Cyclic Reference - Weak Reference  (0) 2020.11.11
[C++] Reference Counting  (2) 2020.11.04
[c] SHA-1 구조 및 코드  (2) 2017.12.09
[c] AES 구조 및 코드  (2) 2017.11.15
[c] DES 구조 및 코드  (21) 2017.10.26
728x90

SHA는 Secure Hash Algorithm의 줄임말로 1993년 미국 국가안보국(NSA)에 의해 설계되고 표준으로 지정되었다.

 

이때 출간된 SHA는 구분상 SHA-0이라하고 2년 뒤인 1995년에 개정된 SHA-1을 발표했고 현재 널리 쓰이는 해쉬 알고리즘이다.

 

이후 변형 버전인 SHA-2라 불리는 SHA-224, 256, 384, 512가 나왔으며 보통은 SHA-1을 사용하고 더 암호학적 안전을 요하는 곳에는

 

SHA-2를 사용한다.

 

sha-1 전체 구조

 

 

SHA-1은 메시지 길이에 상관없이 512비트씩 잘라서 메시지 다이제스트 함수를 돌린 뒤 160비트의 출력을 낸다.

 

원본 메시지 + 패딩 + 원본 메시지 길이(64비트) 가 512비트의 배수가 되도록 만든다. (메시지가 없어도 한다.)

 

패딩은 맨 뒤 64비트에는 메시지 전체 길이를 넣고 나머지 비트는 최상위 비트 1을 제외하고 0으로 채운다.

 

메시지가 512비트보다 길 경우 다음 번 메시지 다이제스트 함수의 입력으로 전 함수의 출력을 받는다.

 

맨 앞 초기값 ABCDE는 정해진 상수값이다.

 

초기값 160bit

 


void SHA_1(FILE* fptr, BYTE* result) {
	int i, size = 0;

	BYTE msg[HASH_BLOCK * 2] = { 0, };
	UINT64 f_size = 0;

	SHA_1_init();

	while ((size = fread(msg, sizeof(BYTE), HASH_BLOCK, fptr))) {
		f_size += size;

		if (size < HASH_BLOCK)
			padding(msg, f_size);

		SHA_1_digest(msg);
		if (isAddpad) SHA_1_digest(msg + HASH_BLOCK);
		memset(msg, 0, HASH_BLOCK * 2);
	}

	for (i = 0; i < HASH_DATA; i++)
		result[i] = digest[i];
}

void padding(BYTE* in, UINT64 msg_len)
{
	int i;
	BYTE* ptr = (BYTE*)&msg_len;

	in[msg_len % HASH_BLOCK] = 0x80;
	msg_len *= 8;

	// 메시지가 448비트 보다 작은 경우와 448비트 보다 큰 경우로 나누어 처리
	// 448비트보다 큰 경우에는 512비트의 블록을 추가하여 패딩을 수행한다
	if ((msg_len % HASH_BLOCK) < 56)
	{
		for (i = 0; i<8; i++)
			in[HASH_BLOCK - i - 1] = *(ptr + i);
	}
	else
	{
		isAddpad = 1;
		for (i = 0; i<8; i++)
			in[HASH_BLOCK * 2 - i - 1] = *(ptr + i);
	}
}

 

 

파일을 읽고 크기가 64바이트(512비트)보다 작으면 패딩을 한다. 패딩에서 메시지가 448비트보다 커서 문자열 길이를 담을 수 없는 경우

 

블록을 하나 더 늘리고 메시지 다이제스트 함수도 한번 더 한다.

 

메시지 다이제스트 함수

 

 

메시지 다이제스트 함수는 총 80라운드를 돌며 초기 입력 160비트와 마지막 80번째 라운드의 출력 160비트를 32비트씩 법 2^32상에서의 덧셈을 한다.

 

그 값이 메시지 다이제스트 함수의 최종 출력값이 된다.

 

각 라운드

   

라운드별 F함수

 

 

각 라운드는 위 그림과 같이 구성되는데 32비트씩 나누어 A->B', B->C', C->D', D->E'로 간단한데 (B->C'일때 좌측 순환쉬프트 30비트를 해준다.)

 

E->A'로 할때에는 A의 좌측 순환쉬프트를 5비트해준 값과 B,C,D를 F함수에 넣은 출력값과 E값과 Wt와 라운드 상수 Kt를 법 2^32상에서 덧셈을 하여

 

구한다. F함수는 오른쪽 그림과 같으며 F2와 F4는 같은 동작을 한다.

 

Wt의 생성방법

 

 

Wt는 입력블록을 32비트씩 잘라 16개의 W0~W15를 만들고 이를 이용하여 W79까지 생성할 수 있다.

 

라운드 상수 Kt

 


void SHA_1_digest(BYTE* in) {
	int i;
	UINT M[16] = { 0, };
	UINT W[80] = { 0, };
	UINT reg[5] = { 0, };
	UINT temp;

	reg[0] = init_reg[0];
	reg[1] = init_reg[1];
	reg[2] = init_reg[2];
	reg[3] = init_reg[3];
	reg[4] = init_reg[4];

	for (i = 0; i < 64; i += 4) {
		M[i / 4] = BTOW(in[i], in[i + 1], in[i + 2], in[i + 3]);
	}

	for (i = 0; i < 80; i++) {
		if (i < 16)
			W[i] = M[i];
		else
			W[i] = CIR_SHIFT((W[i - 16] ^ W[i - 14] ^ W[i - 8] ^ W[i - 3]), 1);
	}

	for (i = 0; i < 80; i++) {

		if (i < 20) {
			temp = CIR_SHIFT(reg[0], 5) + F1(reg[1], reg[2], reg[3]) + reg[4] + W[i] + K0;
		}
		else if (i < 40) {
			temp = CIR_SHIFT(reg[0], 5) + F2(reg[1], reg[2], reg[3]) + reg[4] + W[i] + K1;
		}
		else if (i < 60) {
			temp = CIR_SHIFT(reg[0], 5) + F3(reg[1], reg[2], reg[3]) + reg[4] + W[i] + K2;
		}
		else {
			temp = CIR_SHIFT(reg[0], 5) + F2(reg[1], reg[2], reg[3]) + reg[4] + W[i] + K3;
		}

		reg[4] = reg[3];
		reg[3] = reg[2];
		reg[2] = CIR_SHIFT(reg[1], 30);
		reg[1] = reg[0];
		reg[0] = temp;
	}

	init_reg[0] += reg[0];
	init_reg[1] += reg[1];
	init_reg[2] += reg[2];
	init_reg[3] += reg[3];
	init_reg[4] += reg[4];

	make_Bit160(init_reg[0], init_reg[1], init_reg[2], init_reg[3], init_reg[4]);
}

 

 

728x90

'프로그래밍 > C++' 카테고리의 다른 글

[C++] Reference Counting  (2) 2020.11.04
힙(Heap)과 완전 이진 트리(Complete binary tree)  (1) 2019.10.31
[c] AES 구조 및 코드  (2) 2017.11.15
[c] DES 구조 및 코드  (21) 2017.10.26
[소켓 프로그래밍] IOCP echo server 예제  (0) 2016.11.17

+ Recent posts