circular buffer 구현 관련 문의
글쓴이: jinserk / 작성시간: 화, 2010/01/05 - 11:14오전
template<typename T> class buffer
{
private:
T* element_;
int sz_; // size of container
int fill_; // fill counter
int wpos_; // write position
int rpos_; // read position
public:
buffer() {
element_ = NULL;
sz_ = 0;
fill_ = 0;
wpos_ = 0;
rpos_ = 0;
}
buffer(int s1) {
set_size(s1);
}
~buffer() {
clear();
}
inline void set_size(int s1) {
element_ = new T [s1];
sz_ = s1;
fill_ = 0;
wpos_ = 0;
rpos_ = 0;
}
inline void clear() {
if (!element_) return;
delete [] element_;
element_ = NULL;
}
inline bool push(const T e) {
if (fill_ == sz_)
return false;
element_[wpos_] = e;
++fill_;
if (++wpos_ == sz_)
wpos_ = 0;
return true;
}
inline T& pop(void) {
if (!fill_)
???????????????????????? <---
--fill_;
if (rpos_ == sz_)
rpos_ = 0;
return element_[rpos_++];
}
inline void flush(void) {
wpos_ = 0;
rpos_ = 0;
fill_ = 0;
}
};위 코드와 같이 circular buffer 로 쓸 template 을 하나 만들었습니다.
그런데 일반적으로 circular buffer 가 full 일 경우는 push 에서 그냥 false 리턴하고
넘어가면 그만이지만, empty 일때는 뭔가 리턴을 해줘야 하는데 뭘 리턴해야 할지 모르겠네요.
buffer 운영시 empty 일때 pop() 이 호출되더라도 그냥 계속 진행하도록 만들고 싶은데요.
그리고 circular buffer 가 제대로 도는지 확인할 수 있는 test case 는 뭘 만들어야 할까요. -_-;
Forums:
exception을
raise 하시면 안되나요
예외처리의 비용이 부담스러우시면 empty를 나타내는 값을 하나 정해서 리턴하시는것두..
raise 는..
답변 감사드립니다.
사실 예외처리도 생각을 해봤는데.. raise 하면 CB 를 쓸 원 모듈에서 try catch 처리를 해줘야 하는데
가능하면 원모듈 수정을 안할 생각이다 보니.. ^^;
empty 값을 하나 정하긴 어려운것이.. 일단 template 이라 어떤 type 을 버퍼링할지도 모르는데다가
그 type 에 그 empty 값이 안들어온다는 보장이 없어서요..
Leo.
아니면 STL 스택처럼
아니면 STL 스택처럼 top(), pop()를 분리 하셔도 될듯.
bool pop();
T& top();
그리고 정의가 class 내에 있으므로 member function 앞의 inline은 생략해도 됩니다. (기억이 가물하지만 맞을거에요)
Life rushes on, we are distracted
Life rushes on, we are distracted
감사합니다.
근데 top 과 pop 을 분리하라는 말씀이 무슨 의미인지 잘 모르겠어요.
데이터 넣을때 push, 뺄때 pop 을 쓰려고 하는데요..
캐스팅을 하라는 의미신지? -_-a
정의가 class 내에 있으면 inline 없어도 inline 과 같은 효과가 나는건가요?
궁금해지네요.
Leo.
stl의 경우
http://www.sgi.com/tech/stl/stack.html
error check를 하지 않기 위한 의도라기 보다, peroformace 측면에서 분리한 것으로 보입니다.
pop()과 동시에 제거되는 element를 가져오도록 구현하면 pop을 실행 횟수만큼 element return과정도 반복합니다.
많은 경우 N번 pop() 뒤 N번째 pop()결과만 필요하므로, 이 경우 STL 식으로 (n-1)번 pop(), x = top(), pop()하는 것이 미세하나마 효율성 측면에서 낫다고 생각했겠죠.
class body 내 정의되면 자동으로 inline 시도(?)합니다.
http://www.parashift.com/c++-faq-lite/inline-functions.html (9.8항목 참고)
ps) stl 문서를 다시 보니 분리한 이유를 써놨군요.
http://www.sgi.com/tech/stl/stack.html#3 (주석 3 참고)
아아
그렇군요. top 은 레퍼런스로 리턴하고 제거는 pop 으로.. 거꾸론가? 여튼..
제가 구현한 건 사실 엄밀히 말해서 poping 을 하는건 아닙니다.. reference 를 리턴해주고 단순히 rpos 를 하나 증가시켜 버리죠.
어차피 버퍼라 pop 하는 순간 어딘가 옮겨지게 되거나 혹은 연산에 쓰이고 버려질 숫자라서, 저런식으로 구현을 했습니다.
어쨌든.. reference 를 리턴하는 pop 함수에서는 empty indication 할 방법이 마땅치가 않네요.
지금으로선 걍 is_empty() 메소드를 하나 만들고, pop 시 if (is_empty()) 처리 해주는 정도만이 떠오릅니다.
Leo.
...
testcase라면 고전적이면서 유명한 reader-writer/producer-consumer problem을 circular buffer(queue?)를 이용해서 해결해 보시는 것은 어떨까요.
네.. 일단 몇개를
네.. 일단 몇개를 넣다 뺐다 하면서 동작하는걸 테스트해보긴 했는데
그것만 갖고 잘돈다고 말할 수 있을지 확신이 안서네요.
뭔가 코너 케이스가 있을 것 같은데..
Leo.
댓글 달기