utringbuffer: C用の動的リングバッファーマクロ

はじめに

utringbuffer.h の関数は、utarray.h が提供する汎用配列マクロを基にしているため、このページを読む前にutarrayのページを読んでください。

自分のCプログラムでこれらのマクロを使うには、utarray.h と utringbuffer.h の両方をソースディレクトリにコピーし、プログラムで utringbuffer.h を使用してください。

#include "utringbuffer.h"

提供される操作は、C++ STLのvectorのメソッドを大まかな基にしています。リングバッファーのデータ型は、容量を指定した構築、破棄、反復処理、pushをサポートしますが、popはサポートしません。容量がいっぱいになると、新しい要素をpushする際に、最も古い要素を自動的にpopして破棄します。リングバッファーに格納する要素には、任意の単純なデータ型や構造体を使えます。

リングバッファーの内部には、事前に割り当てたメモリー領域があり、位置0から順に要素がコピーされます。容量がいっぱいになると、次の要素は位置0にpushされて最も古い要素を上書きし、リングバッファーの「先頭」を示す内部インデックスが増加します。一度いっぱいになったリングバッファーは、空きのある状態には戻りません。

ダウンロード

ヘッダーファイル utringbuffer.h をダウンロードするには、https://github.com/troydhanson/uthash のリンクからuthashをクローンするかZIPファイルを取得し、src/ サブディレクトリを確認してください。

BSDライセンス

このソフトウェアは修正版BSDライセンスで提供されています。自由に利用できるオープンソースソフトウェアです。

プラットフォーム

utringbuffer マクロは、次の環境でテストされています。

Linux,
Mac OS X,
Windows（Visual Studio 2008およびVisual Studio 2010を使用）

使い方

宣言

格納する要素の型にかかわらず、リングバッファー自体のデータ型は UT_ringbuffer です。次のように宣言します。

UT_ringbuffer *history;

作成と解放

次に、utringbuffer_new でリングバッファーを作成します。使用を終えたら、utringbuffer_free でリングバッファーとそのすべての要素を解放します。

pushなどの操作

リングバッファーの主な機能は、要素の格納と、それらに対する反復処理です。1つの要素または一定範囲の要素を一度に扱う操作がいくつかあります。以下の例では、要素の挿入にpush操作だけを使います。

要素

整数や文字列の動的配列は、特に簡単に扱えます。例で示すのが分かりやすいでしょう。

整数

この例は、整数のリングバッファーを作成して0〜9をpushし、2通りの方法で内容を表示します。最後にリングバッファーを解放します。

整数の要素

#include <stdio.h>
#include "utringbuffer.h"

int main() {
  UT_ringbuffer *history;
  int i, *p;

  utringbuffer_new(history, 7, &ut_int_icd);
  for(i=0; i < 10; i++) utringbuffer_push_back(history, &i);

  for (p = (int*)utringbuffer_front(history);
       p != NULL;
       p = (int*)utringbuffer_next(history, p)) {
    printf("%d\n", *p);  /* prints "3 4 5 6 7 8 9" */
  }

  for (i=0; i < utringbuffer_len(history); i++) {
    p = utringbuffer_eltptr(history, i);
    printf("%d\n", *p);  /* prints "3 4 5 6 7 8 9" */
  }

  utringbuffer_free(history);

  return 0;
}

utringbuffer_push_back の第2引数は、常に要素の型へのポインターです（そのため、リテラルは使えません）。整数の場合は int* になります。

文字列

この例は、文字列のリングバッファーを作成して2つの文字列をpushし、内容を表示してから解放します。

文字列の要素

#include <stdio.h>
#include "utringbuffer.h"

int main() {
  UT_ringbuffer *strs;
  char *s, **p;

  utringbuffer_new(strs, 7, &ut_str_icd);

  s = "hello"; utringbuffer_push_back(strs, &s);
  s = "world"; utringbuffer_push_back(strs, &s);
  p = NULL;
  while ( (p=(char**)utringbuffer_next(strs,p))) {
    printf("%s\n",*p);
  }

  utringbuffer_free(strs);

  return 0;
}

この例では要素が char* なので、そのポインター（char**）を utringbuffer_push_back の第2引数に渡します。「push」は元の文字列をコピーし、そのコピーを配列にpushすることに注意してください。

UT_icdについて

配列の要素には、整数や文字列だけでなく、任意の型を使えます。基本型や構造体を要素にできます。整数や文字列（定義済みの ut_int_icd と ut_str_icd を使用）を扱う場合を除き、補助構造体 UT_icd を定義する必要があります。この構造体には、utringbuffer（またはutarray）が要素を初期化、コピー、破棄するために必要な情報がすべて含まれます。

typedef struct {
    size_t sz;
    init_f *init;
    ctor_f *copy;
    dtor_f *dtor;
} UT_icd;

3つの関数ポインター init、copy、dtor のプロトタイプは次のとおりです。

typedef void (ctor_f)(void *dst, const void *src);
typedef void (dtor_f)(void *elt);
typedef void (init_f)(void *elt);

sz は、配列に格納する要素のサイズです。

init 関数はutarrayでは使われますが、utringbufferでは一切使われません。そのため、任意の値を設定しても問題ありません。

copy 関数は、要素をバッファーにコピーするたびに使われます。utringbuffer_push_back の実行中に呼び出されます。copy が NULL の場合は、既定でmemcpyによるビット単位のコピーを行います。

dtor 関数は、バッファーから取り除く要素の後処理に使われます。utringbuffer_push_back（バッファー内の最も古い要素に対して）、utringbuffer_clear、utringbuffer_done、utringbuffer_free によって呼び出されることがあります。破棄時の後処理が不要な要素なら、dtor を NULL にできます。

スカラー型

次の例は、すべて既定の設定の UT_icd を使って、long 要素のリングバッファーを作成します。容量1のバッファーに2つのlong値をpushし、バッファーの内容（つまり、最後にpushした値）を表示してから解放します。

longの要素

#include <stdio.h>
#include "utringbuffer.h"

UT_icd long_icd = {sizeof(long), NULL, NULL, NULL };

int main() {
  UT_ringbuffer *nums;
  long l, *p;
  utringbuffer_new(nums, 1, &long_icd);

  l=1; utringbuffer_push_back(nums, &l);
  l=2; utringbuffer_push_back(nums, &l);

  p=NULL;
  while((p = (long*)utringbuffer_next(nums,p))) printf("%ld\n", *p);

  utringbuffer_free(nums);
  return 0;
}

構造体

utringbufferの要素には構造体を使えます。初期化、コピー、破棄に特別な処理が不要な構造体なら、すべて既定の設定の UT_icd を使えます。この例は、2つの整数からなる構造体です。2つの値をpushし、それらを表示してからバッファーを解放します。

構造体（単純な例）

#include <stdio.h>
#include "utringbuffer.h"

typedef struct {
    int a;
    int b;
} intpair_t;

UT_icd intpair_icd = {sizeof(intpair_t), NULL, NULL, NULL};

int main() {

  UT_ringbuffer *pairs;
  intpair_t ip, *p;
  utringbuffer_new(pairs, 7, &intpair_icd);

  ip.a=1;  ip.b=2;  utringbuffer_push_back(pairs, &ip);
  ip.a=10; ip.b=20; utringbuffer_push_back(pairs, &ip);

  for(p=(intpair_t*)utringbuffer_front(pairs);
      p!=NULL;
      p=(intpair_t*)utringbuffer_next(pairs,p)) {
    printf("%d %d\n", p->a, p->b);
  }

  utringbuffer_free(pairs);
  return 0;
}

リングバッファーに格納する要素が、初期化、コピー、破棄に特別な処理を必要とする構造体である場合に、UT_icd の真価が分かります。

たとえば、構造体のコピー時にコピーが必要で、構造体の解放時に解放が必要な関連メモリー領域へのポインターを構造体が含む場合、独自の init、copy、dtor メンバーを UT_icd に指定できます。

ここでは、整数と文字列を含む構造体を例にします。要素をコピーする際（たとえばpush時）には、s ポインターの参照先を「深いコピー」にしたいと考えます（元の要素と新しい要素が、それぞれ独立した s のコピーを指すようにするためです）。要素を破棄する際には、その s のコピーも「深い解放」を行います。この例は、s の値が NULL でも動作するように書かれています。

構造体（複雑な例）

#include <stdio.h>
#include <stdlib.h>
#include "utringbuffer.h"

typedef struct {
    int a;
    char *s;
} intchar_t;

void intchar_copy(void *_dst, const void *_src) {
  intchar_t *dst = (intchar_t*)_dst, *src = (intchar_t*)_src;
  dst->a = src->a;
  dst->s = src->s ? strdup(src->s) : NULL;
}

void intchar_dtor(void *_elt) {
  intchar_t *elt = (intchar_t*)_elt;
  free(elt->s);
}

UT_icd intchar_icd = {sizeof(intchar_t), NULL, intchar_copy, intchar_dtor};

int main() {
  UT_ringbuffer *intchars;
  intchar_t ic, *p;
  utringbuffer_new(intchars, 2, &intchar_icd);

  ic.a=1; ic.s="hello"; utringbuffer_push_back(intchars, &ic);
  ic.a=2; ic.s="world"; utringbuffer_push_back(intchars, &ic);
  ic.a=3; ic.s="peace"; utringbuffer_push_back(intchars, &ic);

  p=NULL;
  while( (p=(intchar_t*)utringbuffer_next(intchars,p))) {
    printf("%d %s\n", p->a, (p->s ? p->s : "null"));
    /* prints "2 world 3 peace" */
  }

  utringbuffer_free(intchars);
  return 0;
}

リファレンス

この表は、utringbufferのすべての操作を示します。これらはC++のvectorクラスを大まかな基にしています。

操作

`utringbuffer_new(UT_ringbuffer a, int n, UT_icd icd)`	新しいリングバッファーを割り当てる
`utringbuffer_free(UT_ringbuffer *a)`	割り当て済みのリングバッファーを解放する
`utringbuffer_init(UT_ringbuffer a, int n, UT_icd icd)`	リングバッファーを初期化する（構造体自体は割り当てない）
`utringbuffer_done(UT_ringbuffer *a)`	リングバッファーの内部リソースを解放する（構造体自体は解放しない）
`utringbuffer_clear(UT_ringbuffer *a)`	aのすべての要素を消去して空にする
`utringbuffer_push_back(UT_ringbuffer a, element p)`	要素pをaにpushする
`utringbuffer_len(UT_ringbuffer *a)`	aの長さを取得する
`utringbuffer_empty(UT_ringbuffer *a)`	aが空かどうかを取得する
`utringbuffer_full(UT_ringbuffer *a)`	aがいっぱいかどうかを取得する
`utringbuffer_eltptr(UT_ringbuffer *a, int j)`	インデックスから要素のポインターを取得する
`utringbuffer_eltidx(UT_ringbuffer a, element e)`	ポインターから要素のインデックスを取得する
`utringbuffer_front(UT_ringbuffer *a)`	aの最も古い要素を取得する
`utringbuffer_next(UT_ringbuffer a, element e)`	aの要素eの次の要素を取得する（eがNULLなら先頭要素）
`utringbuffer_prev(UT_ringbuffer a, element e)`	aの要素eの前の要素を取得する（eがNULLなら末尾要素）
`utringbuffer_back(UT_ringbuffer *a)`	aの最も新しい要素を取得する

注意事項

utringbuffer_new と utringbuffer_free は、新しいリングバッファーの割り当てと解放に使います。一方、UT_ringbufferがすでに割り当て済みで、初期化や内部リソースの解放だけが必要な場合は、utringbuffer_init と utringbuffer_done を使えます。
utringbuffer_new と utringbuffer_init は、どちらも第2パラメーター n でリングバッファーの容量を受け取ります。これは、リングバッファーが「いっぱい」とみなされ、新しくpushした要素で古い要素を上書きし始めるサイズです。
一度いっぱいになったリングバッファーは、utringbuffer_clear を使う場合を除いて、空きのある状態には戻りません。リングバッファーの先頭から古い要素を1つだけ「pop」する方法はありません。「論理的にpopした要素」の数を別の整数で保持し、utringbuffer_eltptr(a, popped_count) から反復処理を開始して、utringbuffer_front(a) からの開始に代えることで、この機能に相当する動作を実現できます。
要素へのポインター（utringbuffer_eltptr、utringbuffer_front、utringbuffer_next などで取得）は、通常 utringbuffer_push_back によって無効にはなりません。utringbufferは再割り当てを行わないためです。ただし、最も古い要素へのポインターは、突然最も新しい要素へのポインターに変わることがあります。バッファーがいっぱいの状態で utringbuffer_push_back を呼び出した場合です。
リングバッファーの要素は連続したメモリーに格納されますが、一度いっぱいになると、最も古い要素から最も新しい要素までが順番どおりに連続しているとは限りません。つまり、(element *)utringbuffer_front(a) + utringbuffer_len(a)-1 は、一般には (element *)utringbuffer_back(a) と等しくなりません。