자료구조 queue 링 버퍼 c 예제 소스

본 글은 자료 구조 큐(queue)를 사용한 링 버퍼의 c 예제 소스를 싣고 있다.



보통 링 버퍼의 구조는 위 그림과 같다. 가상의 원형의 버퍼를 가지고 데이터를 입력 위치에 데이터 넣고, 데이터 출력에서 데이터를 뽑아 간다. 그리고, 그때마다 데이터 입력/출력 위치를 증가시키고, 일정 크기가 되면 다시 0으로 되어 반복된다. 

[ring queue buffer c source code]
아래 예제 코드에서는 char 형식의 데이터를 지원하는 링 버퍼가 구현되어 있다.

데이터 구조체 선언은 아래와 같다. 데이터를 저장할 버퍼 포인터와 버퍼의 크기, 저장 데이터의 크기, 입력 및 출력 위치 등이 있다. multi-thread를 위해 mutex도 추가했다.

typedef struct _ring_q_t
{
#if defined(WIN32)
HANDLE mutex;
#else
pthread_mutex_t mutex;
#endif
char *q; /*q buffer*/
int nqsize; /*q 버퍼 크기*/
int ndatasize; /*저장된 데이터 크기*/
int in;
int out;
}ring_q_t;


mutex lock/unlock 구문을 define 문으로 선언했다. 

#if defined(WIN32)
#define _lock(x) WaitForSingleObject(x->mutex, INFINITE);
#else 
#define _lock(x) pthread_mutex_lock(&x->mutex);
#endif

#if defined(WIN32)
#define _unlock(x) ReleaseMutex(x->mutex);
#else 
#define _unlock(x) pthread_mutex_unlock(&x->mutex);
#endif


구현된 함수는 아래와 같다.

ring_q_t *ring_q_init(int size)
{
ring_q_t *rq = (ring_q_t*)malloc(sizeof(ring_q_t));
if (rq)
{
memset(rq, 0, sizeof(ring_q_t));
#if defined(WIN32)
rq->mutex = CreateMutex(NULL, FALSE, TEXT("ringq mutex"));
#else
pthread_mutex_init(&rq->mutex, NULL);
#endif
rq->nqsize = size;

rq->q = (char*)malloc(sizeof(char)*size);
if (!rq->q)
{
ring_q_deinit(rq);
return NULL;
}

memset(rq->q, 0, sizeof(char)*size);
}

return rq;
}

void ring_q_deinit(ring_q_t *rq)
{
if (rq)
{
#if defined(WIN32)
CloseHandle(rq->mutex);
#else
pthread_mutex_destroy(&rq->mutex);
#endif
safe_free(rq->q);
safe_free(rq);
}
}

void ring_q_reset(ring_q_t *rq)
{
if (rq)
{
_lock(rq);

memset(rq->q, 0, sizeof(char)*rq->nqsize);

rq->ndatasize = 0;
rq->in = 0;
rq->out = 0;

_unlock(rq);
}
}


ring_q_size는 버퍼내 데이터의 크기를 반환하는 함수다.
int ring_q_size(ring_q_t *rq)
{
int size = 0;
if (rq)
{
_lock(rq);
size = rq->ndatasize;
_unlock(rq);
}

return size;
}

ring_q_push를 통해 링 버퍼에 데이터를 넣는다. 데이터를 넣을 때 아래 그림과 같이 할당된 버퍼의 끝부분을 사용할 때의 처리도 해 두었다.


int ring_q_push(ring_q_t *rq, char *data, int nsize)
{
char *src = NULL;
char *dst = NULL;
int push_size1 = 0;
int push_size2 = 0;

if (!rq || !data) return 0;
_lock(rq);

if (rq->ndatasize + nsize >= rq->nqsize)
{
// overflow
_unlock(rq);
return -1;
}

src = data;
dst = &rq->q[rq->in];
push_size1 = rq->nqsize - rq->in;

if (push_size1 > nsize) push_size1 = nsize;

push_size2 = nsize - push_size1;
memcpy(dst, src, push_size1*sizeof(char));
rq->ndatasize += push_size1;

if (push_size2 > 0)
{
int src_offset = push_size1;
dst = rq->q;
memcpy(dst, src + src_offset, push_size2*sizeof(char));
rq->ndatasize += push_size2;
}

rq->in = (rq->in + nsize) % rq->nqsize;

_unlock(rq);
return nsize;
}

ring_q_peek를 통해 링 버퍼에서 데이터를 받아온다. 단 이때 받아온 데이터는 링 버퍼 내부에서 지워지지 않는다. ring_q_flush를 통해 링 버퍼내의 데이터를 삭제한다. 경험상 링 버퍼에서 데이터를 받아올 때 바로 지우는 것 보다, 나중에 따로 지우는 것이 더 데이터 처리 및 사용에 유용하다. 네트웍을 통해 데이터를 받아오는 경우를 예로 들면, 링 버퍼내 데이터가 정상적인지 원하는 양의 데이터가 들어왔는지 확인하는 루틴 등을 사용할 때 바로 지우는 것 보다, 남겨 두었다 나중에 지우는 것이 코딩하기 편한 경우가 더 많았다.
데이터를 받아올 때 아래 그림과 같이 할당된 버퍼의 끝부분을 사용할 때의 처리도 해 두었다.


int ring_q_peek(ring_q_t *rq, char *data, int nsize)
{
int peek_size1 = 0;
int peek_size2 = 0;

if (!rq || !data || nsize <= 0) return 0;

_lock(rq);
if (rq->ndatasize <= 0)
{
_unlock(rq);
return 0;
}

if (rq->ndatasize < nsize)
{
nsize = rq->ndatasize;
}

peek_size1 = rq->nqsize - rq->out;
if (peek_size1 > nsize)
{
peek_size1 = nsize;
}

peek_size2 = nsize - peek_size1;

if (peek_size1 > 0)
{
memcpy(data, &rq->q[rq->out], peek_size1*sizeof(char));
}

if (peek_size2 > 0)
{
memcpy(data + peek_size1, rq->q, peek_size2*sizeof(char));
}

_unlock(rq);
return peek_size1 + peek_size2;
}

ring_q_flush를 사용해 링 버퍼내의 데이터를 삭제한다.
int ring_q_flush(ring_q_t *rq, int nsize)
{
int i = 0;
if (!rq || nsize <= 0) return -1;

_lock(rq);

if (nsize > rq->ndatasize)
{
nsize = rq->ndatasize;
}

while (i<nsize)
{
rq->out = (rq->out + 1) % rq->nqsize;
rq->ndatasize--;
i++;
}

_unlock(rq);

return nsize;
}


위 코드 사용 예는 아래와 같다.

ring_q_t *rq = ring_q_init(128);
char *push_data = "abcd1234";
char peek_data[32] = { 0, };
int ret = 0;
if (rq)
{
ret = ring_q_push(rq, push_data, strlen(push_data));

ret = ring_q_peek(rq, peek_data, 32);
_trace(TEXT("%d : %S\n"), ret, peek_data);
ring_q_flush(rq, ret);
ring_q_deinit(rq);
}

실행 결과
8 : abcd1234


댓글

이 블로그의 인기 게시물

간단한 cfar 알고리즘에 대해

windows에서 간단하게 크롬캐스트(Chromecast)를 통해 윈도우 화면 미러링 방법

쉽게 설명한 파티클 필터(particle filter) 동작 원리와 예제

base64 인코딩 디코딩 예제 c 소스

간단한 칼만 필터(Kalman Filter) 소스 코드와 사용 예제