![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
* acl4のページ0017 -(by [[K]], 2026.04.23) ** (1) 概要 -a4_0017 は、 acl4v1 にとっての2番目のライブラリプログラムになります。 -提供される主な機能は、以下の通りです。 --(1-1)vector<char> を参考にして作った VecChr クラス（動的可変長配列） --(1-2)簡単な Key-Value-Store を提供する Set0 クラス --(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) 更新履歴 -2026.04.23(木) 初版
