자료구조 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