링버퍼 구현

송지석의 이미지

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;
}
buelgsk8er의 이미지

에.. 링 버퍼란게 원래 그렇지 않나요? 완전히 빈 상태와 완전히 찬 상태 둘 다 head==tail라서 구분이 안가기 때문에, 완전히 찬 상태를 한 개 빈 상태로 정의하는 거죠
혹은 full인가 empty인가를 구분하는 별도의 플래그를 두던가요.

송지석의 이미지

그렇군요 링버퍼가 원래 그런 것인 지 몰랐다는.. 역시 여러번 해보니까 RB_SZ+1은 문제가 있었습니다.

sozu의 이미지

4r7yc0d3 wrote:
에.. 링 버퍼란게 원래 그렇지 않나요? 완전히 빈 상태와 완전히 찬 상태 둘 다 head==tail라서 구분이 안가기 때문에, 완전히 찬 상태를 한 개 빈 상태로 정의하는 거죠
혹은 full인가 empty인가를 구분하는 별도의 플래그를 두던가요.

버퍼의 크기를 저장해 놓으면 구분 할수 있습니다.

-----------
청하가 제안하는 소프트웨어 엔지니어로써 재미있게 사는 법
http://sozu.tistory.com

lkjt의 이미지

원형큐 말씀하시는건가요?...

윗분 말씀대로 구별이 불가능합니다.

그래서 배열보다 1크게 잡아서

그걸로 구별을 합니다.

운형의 이미지

링버퍼 구현하실 때, 특별한 이유가 없으시다면... 리스트를 이용하는게 여러모로 편합니다.

그래도 배열을 이용해야한다면 버퍼 풀을 잡으시고, 그 안에서 리스트 자료 구조 처럼 사용하는 방법두 있구요(요건... 머리가 좀 복잡해지지만, 메모리 메니지 먼트 기능이 없는 O/S에서 써먹지 좋구요.)

Do you think that's the air you are breathing now?

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.