acl4のページ0017
(1) 概要
- a4_0017 は、 acl4v1 にとっての2番目のライブラリプログラムになります。
- 提供される主な機能は、以下の通りです。
- (1-1)vector<char> を参考にして作った VecChr クラス（動的可変長配列）
- (1-2)簡単な Key-Value Store を提供する Set0 クラス
- 以下、それぞれについてもう少し詳しく説明します。
- (1-1)vector<char> を参考にして作った VecChr クラス（動的可変長配列）
- 管理情報としては、配列の先頭位置 p と、配列の現状のサイズ N 、領域をとりあえずどこまで確保しているかの N1 があります。本来この3つを管理しようとすれば、 sizeof (VecChr) はポインタ3個分のサイズになるはずですが、少々小細工をして sizeof (VecChr) はポインタ1つ分のサイズになっています（リリースモード時）。
- これは大して重要ではないと思われるかもしれませんが、VecChrの配列などを作ったときには、アドレス計算がだいぶシンプルになって、多少高速化されるのではないかと考えています。
- (1-2)簡単な Key-Value-Store を提供する Set0 クラス
- 簡単な二分探索で探索します。 find は O(logN) 、add や rmv は O(N) になります。
- 大規模なデータ量が想定されるときは、もっと複雑で高速なやつを作るべきだと思われます。
(2) デモ
(3) ライブラリプログラム
#if (a_Version >= 1)
#define VecChr a_VecChr
#define VecChr_N a_VecChr_N
#define VecChr_N1 a_VecChr_N1
#define VecChr_ini a_VecChr_ini
#define VecChr_ini4 a_VecChr_ini4
#define VecChr_din a_VecChr_din
#define VecChr_din4 a_VecChr_din4
#define VecChr_getN a_VecChr_getN
#define VecChr_setN a_VecChr_setN
#define VecChr_reserve a_VecChr_reserve
#define VecChr_resize a_VecChr_resize
#define VecChr_resizeDiff a_VecChr_resizeDiff
#define VecChr_reserveDiff a_VecChr_reserveDiff
#define VecChr_reserve0 a_VecChr_reserve0
#define VecChr_resize0 a_VecChr_resize0
#define VecChr_shrink a_VecChr_shrink
#endif
a_class(a_VecChr) { char *p; a_DbgLv1( a_DbgObjInf doi[1]; ) };
a_static intptr_t a_VecChr_p0[2] = { 0, 0 };
#define a_VecChr_N(w) ((intptr_t *) (w)->p)[-1]
#define a_VecChr_N1(w) ((intptr_t *) (w)->p)[-2]
a_static void a_VecChr_ini(_aDef_ a_VecChr *w)
{
w->p = (char *) &a_VecChr_p0[2];
a_DbgLv2( a_DbgObjInf_ini(_aThr, w->doi, "VecChr"); )
}
a_static void a_VecChr_din(_aDef_ a_VecChr *w)
{
a_DbgLv2( a_DbgObjInf_din(_aThr, w->doi); )
if (w->p != (char *) &a_VecChr_p0[2]) {
intptr_t *p = (intptr_t *) w->p;
a_free(_a_ p - 2, p[-2] + 2 * sizeof (intptr_t));
}
}
a_static void a_VecChr_ini4(_aDef_ a_VecChr *w0, a_VecChr *w1, a_VecChr *w2, a_VecChr *w3)
{
if (w0 != NULL) a_VecChr_ini(_aThr_ w0);
if (w1 != NULL) a_VecChr_ini(_aThr_ w1);
if (w2 != NULL) a_VecChr_ini(_aThr_ w2);
if (w3 != NULL) a_VecChr_ini(_aThr_ w3);
}
a_static void a_VecChr_din4(_aDef_ a_VecChr *w0, a_VecChr *w1, a_VecChr *w2, a_VecChr *w3)
{
if (w0 != NULL) a_VecChr_din(_aThr_ w0);
if (w1 != NULL) a_VecChr_din(_aThr_ w1);
if (w2 != NULL) a_VecChr_din(_aThr_ w2);
if (w3 != NULL) a_VecChr_din(_aThr_ w3);
}
a_static intptr_t a_VecChr_getN(a_VecChr *w) { return a_VecChr_N(w); }
a_static void a_VecChr_setN(a_VecChr *w, intptr_t n) { a_VecChr_N(w) = n; }
a_static void a_VecChr_reserve(a_VecChr *w, intptr_t n)
{
intptr_t n1nsz = 2 * sizeof (intptr_t);
if (a_VecChr_N1(w) < n) {
intptr_t n1 = a_VecChr_N1(w);
if (n1 < 16/2) n1 = 16/2;
do {
n1 *= 2;
} while (n1 < n);
if (w->p != (char *) &a_VecChr_p0[2])
w->p = a_realloc(_a_ w->p - n1nsz, a_VecChr_N1(w) + n1nsz, n1 + n1nsz);
else {
w->p = a_malloc(_a_ n1 + n1nsz);
((intptr_t *) w->p)[1] = 0; // n = 0.
}
((intptr_t *) w->p)[0] = n1; // n1 = n1.
w->p += n1nsz;
}
}
a_static void a_VecChr_resize(a_VecChr *w, intptr_t n)
{
#if (a_DbgLv >= 2)
if (n < 0)
a_errExit("VecChr_resize: bad size: n=%d", n);
#endif
a_VecChr_reserve(w, n); a_VecChr_N(w) = n;
}
a_static void a_VecChr_resizeDiff(a_VecChr *w, intptr_t d)
{
#if (a_DbgLv >= 2)
if (a_VecChr_N(w) + d < 0)
a_errExit("a_VecChr_resizeDiff: bad diff: d=%d", d);
#endif
a_VecChr_resize(w, a_VecChr_N(w) + d);
}
a_static void a_VecChr_reserveDiff(a_VecChr *w, intptr_t d) { a_VecChr_reserve(w, a_VecChr_N(w) + d); }
a_static void a_VecChr_reserve0(a_VecChr *w) { a_VecChr_reserveDiff(w, 1); w->p[a_VecChr_N(w)] = '\0'; }
a_static void a_VecChr_resize0(a_VecChr *w, intptr_t n)
{
intptr_t n0 = a_VecChr_N(w);
if (n > n0) {
a_VecChr_resize(w, n);
memset(w->p + n0, 0, n - n0);
}
}
a_static void a_VecChr_shrink(a_VecChr *w, intptr_t r)
{
intptr_t n1nsz = 2 * sizeof (intptr_t);
#if (a_DbgLv >= 2)
if (r < 0)
a_errExit("VecChr_shrink: bad reserve: r=%d", r);
#endif
w->p = (char *) a_realloc(_a_ w->p - n1nsz, a_VecChr_N1(w) + n1nsz, a_VecChr_N(w) + r + n1nsz) + n1nsz;
a_VecChr_N1(w) = a_VecChr_N(w) + r;
}
#if (a_Version >= 1)
#define fnv1a32 a_fnv1a32
#define Set0 a_Set0
#define SetElm a_SetElm
#define Set0_ini a_Set0_ini
#define Set0_din a_Set0_din
#define Set0_add a_Set0_add
#define Set0_find a_Set0_find
#define Set0_rmv a_Set0_rmv
#define Set0_findKn a_Set0_findKn
#endif
a_static uint32_t a_fnv1a32(const void *p, intptr_t n)
{
uint32_t h = 2166136261U;
intptr_t i;
for (i = 0; i < n; i++) {
h ^= ((const unsigned char *) p)[i];
h *= 16777619U;
}
return h;
}
a_class(a_Set0) { a_VecChr tbl[1]; void (*elm_din)(void *); a_DbgLv1( a_DbgObjInf doi[1]; ) };
a_class(a_SetElm) { const void *k; intptr_t n, h; };
a_static void a_Set0_ini(_aDef_ a_Set0 *w, void (*elm_din)(void *))
{
a_VecChr_ini(_a_ w->tbl);
w->elm_din = elm_din;
a_DbgLv2( a_DbgObjInf_ini(_aThr, w->doi, "Set0"); )
}
a_static void a_Set0_din(_aDef_ a_Set0 *w)
{
a_DbgLv2( a_DbgObjInf_din(_aThr_ w->doi); )
if (w->elm_din != NULL) {
intptr_t i = a_VecChr_getN(w->tbl) / sizeof (void *) - 1;
void **p = (void *) w->tbl->p;
for (; i >= 0; i--)
w->elm_din(p[i]);
}
a_VecChr_din(_aThr_ w->tbl);
}
a_static intptr_t a_Set0_cmp(a_SetElm *a, a_SetElm *b)
{
if (a->h != b->h) return a->h - b->h;
if (a->n != b->n) return a->n - b->n;
return memcmp(a->k, b->k, a->n);
}
a_static void *a_Set0_add(a_Set0 *w, a_SetElm *elm)
{
elm->h = a_fnv1a32(elm->k, elm->n) & 0x7fffffff;
intptr_t i = 0, n = a_VecChr_getN(w->tbl) / sizeof (a_SetElm *), a, b, m, c;
a_SetElm **tbl = (a_SetElm **) w->tbl->p, *p;
if (n == 0) goto ins;
p = tbl[0]; c = a_Set0_cmp(elm, p); if (c == 0) goto fin;
if (c < 0) goto ins;
i = 1; if (n == 1) goto ins;
p = tbl[n - 1]; c = a_Set0_cmp(elm, p); if (c == 0) goto fin;
i = n; if (c > 0) goto ins;
a = 0; b = n - 1; m = a + ((b - a) >> 1);
i = b; if (m == a) goto ins;
do {
p = tbl[m]; c = a_Set0_cmp(elm, p); if (c == 0) goto fin;
if (c < 0) { b = m; } else { a = m; }
m = a + ((b - a) >> 1);
} while (m > a);
i = b;
ins:
a_VecChr_resizeDiff(w->tbl, sizeof (a_SetElm *));
tbl = (a_SetElm **) w->tbl->p;
if (i < n)
memmove(&tbl[i + 1], &tbl[i], (n - i) * sizeof (a_SetElm *));
tbl[i] = elm;
return NULL;
fin: return p;
}
a_static void *a_Set0_find(a_Set0 *w, a_SetElm *elm)
{
elm->h = a_fnv1a32(elm->k, elm->n) & 0x7fffffff;
intptr_t n = a_VecChr_getN(w->tbl) / sizeof (a_SetElm *), a, b, m, c;
a_SetElm **tbl = (a_SetElm **) w->tbl->p, *p;
if (n == 0) goto ins;
p = tbl[0]; c = a_Set0_cmp(elm, p); if (c == 0) goto fin;
if (c < 0) goto ins;
if (n == 1) goto ins;
p = tbl[n - 1]; c = a_Set0_cmp(elm, p); if (c == 0) goto fin;
if (c > 0) goto ins;
a = 0; b = n - 1; m = a + ((b - a) >> 1);
if (m == a) goto ins;
do {
p = tbl[m]; c = a_Set0_cmp(elm, p); if (c == 0) goto fin;
if (c < 0) { b = m; } else { a = m; }
m = a + ((b - a) >> 1);
} while (m > a);
ins: return NULL;
fin: return p;
}
a_static void *a_Set0_rmv(a_Set0 *w, a_SetElm *elm)
{
elm->h = a_fnv1a32(elm->k, elm->n) & 0x7fffffff;
intptr_t i, n = a_VecChr_getN(w->tbl) / sizeof (a_SetElm *), a, b, m, c;
a_SetElm **tbl = (a_SetElm **) w->tbl->p, *p;
if (n == 0) goto ins;
i = 0; c = a_Set0_cmp(elm, tbl[0]); if (c == 0) goto fin;
if (c < 0) goto ins;
if (n == 1) goto ins;
i = n - 1; c = a_Set0_cmp(elm, tbl[n - 1]); if (c == 0) goto fin;
if (c > 0) goto ins;
a = 0; b = n - 1; m = a + ((b - a) >> 1);
if (m == a) goto ins;
do {
i = m; c = a_Set0_cmp(elm, tbl[m]); if (c == 0) goto fin;
if (c < 0) { b = m; } else { a = m; }
m = a + ((b - a) >> 1);
} while (m > a);
ins: return NULL;
fin:
p = tbl[i];
if (i + 1 < n)
memmove(&tbl[i], &tbl[i + 1], (n - i - 1) * sizeof (a_SetElm *));
a_VecChr_resizeDiff(w->tbl, - (intptr_t) sizeof (a_SetElm *));
return p;
}
a_static void *a_Set0_findKn(a_Set0 *w, const void *k, intptr_t n)
{
a_SetElm elm[1];
elm->k = k;
elm->n = n;
return a_Set0_find(w, elm);
}
(99) 更新履歴
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
