원형버퍼

영어로는 ring buffer 또는 circular buffer

두 개의 인덱스

slot 하나를 낭비하게 되지만, 구현이 간단해서 애용하는 방식

1
2
3
4
5
6
mod(n) { return n % capacity; }
init() { index = outdex = 0; }
write(val) { buffer[index] = val, index = mod(index + 1); }
read() { res = buffer[outdex], outdex = mod(outdex + 1); return res; }
empty() { return index == outdex; }
full() { return mod(index + 1) == outdex; }

modmask(n) { n & (capacity - 1); } 로 최적화 할 수 있다.

하나의 인덱스와 카운트 변수

slot 하나를 낭비하는 위 방법과는 달리 버퍼 내 모든 공간을 활용하지만, write, read 두 함수 모두에서 카운트 변수를 변경한다.

1
2
3
4
5
init() { outdex = count = 0; }
write(val) { buffer[mod(outdex + count++)] = val; }
read() { return count--, buffer[mod(outdex++)]; }
empty() { return count == 0; }
full() { return count == capacity; }

증가하기만 하는 두 개의 인덱스

첫번째 방식에서 인덱스가 버퍼 크기를 벗어나지 않도록 모듈로 연산을 사용한 반면, 아래는 unsigned integer overflow 를 활용해 인덱스를 증가시키기만 하는 방식. 낭비하는 slot 없이 버퍼 내 모든 공간을 활용한다.

1
2
3
4
5
init() { index = outdex = 0; }
write(val) { buffer[mod(index++)] = val; }
read() { return buffer[mod(outdex++)]; }
empty() { return index == outdex; }
full() { return (index - outdex) == capacity; }

알고 나면 별거 아니고 사소한 것 같지만, 이런 발견을 하는 사람들의 태도에 매번 놀란다.

여하간 주의할 점은:

  • 범위를 벗어나는 +1 의 경우(오버플로우의 경우) 0이 되기 때문에 버퍼 크기는 2의 제곱승만 사용할 수 있다
  • C 에서 signed 데이터 타입의 오버플로우는 undefined 이기 때문에 인덱스는 반드시 unsigned 여야 한다

References