링버퍼 구현
글쓴이: 송지석 / 작성시간: 토, 2004/06/12 - 4:49오후
c로 간단한 링버퍼를 쓸 일이 생겼습니다.
그런데 버그가 있어서 ( 그 쉬운게 ㅠㅠ) 이래저래 고생중입니다.
구글에서 좀 검색을 해봤는데 검색어 선정을 잘 못했는지 예제 코드같은 게 잘 안나오는군요.
어쨌든 지금은 어느정도 되는 것 같은데..
링버퍼 원리가
typedef struct { int head, tail; char data[RB_SZ]; } t_rb;
이렇게 두고
head tail은 처음에 같게 만들어놓고
읽을 때는
같지 않으면 buf[head]를 읽어올 수 있고 head++
쓸 때는
다음번 tail (==> (tail+1)%RB_SZ ) 이 head랑 같지 않으면 쓸 수 있고 tail 업데이트.
이렇게 되죠.
이렇게 두면 일단 동작하는 것 같긴한데..
문제가, 버퍼 하나를 사용 안합니다. 그러니까 RB_BUF가 8이면 7개 버퍼만 사용하더라고요.
잘 생각해보시면 최대 buffer 길이가 RB_SZ-1이 됩니다.
그런데, 제가 구글링해서 유일하게 찾은 예제 코드에서 떡하니 저렇게 쓰고 있단 말입니다.
제 생각엔 next tail을 (tail+1)%(RB_SZ +1)로 해야 하지 않을까 하는데 말이죠. 그래서 일단 RB_SZ+1 요렇게 해놓고 해보는데 되는 것 처럼 보이긴 합니다.
하지만 그렇게 되면 tail, head의 상태가 RB_SZ+1의 갯수만큼 바뀌잖아요? 예를 들어 RB_SZ가 4라면 tail,head는 0,1,2,3,4 이렇게 5개 상태를 가지게 됩니다. 버퍼 길이는 4개인데 상태가 5개니까 안되는 거 아닌가 하는 생각이 들기 때문에 불안합니다.
제가 멍하니 틀릴까봐 말이죠(산소가 부족해서 그런가... 머리가 안돌아가요 지금) 한번 검토해주시면 좋겠습니다.
typedef struct { int head, tail; char data[RB_SZ]; } t_rb; int rb_put( t_rb *rb , char d ) { int ntail = (rb->tail+1) % (RB_SZ+1); if (rb->head == ntail) { return FAILED; } rb->data[tail] = d; rb->tail = ntail; return SUCCESS; } char rb_get( t_rb *rb, int *err ) { char d; int nhead = (rb->head+1) % (RB_SZ+1); if (rb->head == rb->tail) { *err = FAILED; return 0; } d = rb->data[rb->head]; rb->head = nhead; *err = SUCCESS; return d; }
Forums:
에.. 링 버퍼란게 원래 그렇지 않나요? 완전히 빈 상태와 완전히 찬 상
에.. 링 버퍼란게 원래 그렇지 않나요? 완전히 빈 상태와 완전히 찬 상태 둘 다 head==tail라서 구분이 안가기 때문에, 완전히 찬 상태를 한 개 빈 상태로 정의하는 거죠
혹은 full인가 empty인가를 구분하는 별도의 플래그를 두던가요.
그렇군요 링버퍼가 원래 그런 것인 지 몰랐다는.. 역시 여러번 해보니까
그렇군요 링버퍼가 원래 그런 것인 지 몰랐다는.. 역시 여러번 해보니까 RB_SZ+1은 문제가 있었습니다.
rommance.net
^^
버퍼의 크기를 저장해 놓으면 구분 할수 있습니다.
-----------
청하가 제안하는 소프트웨어 엔지니어로써 재미있게 사는 법
http://sozu.tistory.com
원형큐 말씀하시는건가요?...윗분 말씀대로 구별이 불가능합니다.
원형큐 말씀하시는건가요?...
윗분 말씀대로 구별이 불가능합니다.
그래서 배열보다 1크게 잡아서
그걸로 구별을 합니다.
링버퍼 구현하실 때, 특별한 이유가 없으시다면... 리스트를 이용하는게
링버퍼 구현하실 때, 특별한 이유가 없으시다면... 리스트를 이용하는게 여러모로 편합니다.
그래도 배열을 이용해야한다면 버퍼 풀을 잡으시고, 그 안에서 리스트 자료 구조 처럼 사용하는 방법두 있구요(요건... 머리가 좀 복잡해지지만, 메모리 메니지 먼트 기능이 없는 O/S에서 써먹지 좋구요.)
Do you think that's the air you are breathing now?
댓글 달기