a4_0005
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
* acl4のページ0005
-(by [[K]], 2026.01.30)
** (1)
#if (a_Version >= 1)
#define Set0 a_Set0
#define SetElm a_SetElm
#define fnv1a32 a_fnv1a32
#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
#endif
a_class(a_Set0) { a_VecChr tbl[1]; };
a_class(a_SetElm) { const void *k; intptr_t n, h; };
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_static void a_Set0_ini(a_Set0 *w) { a_VecChr_ini(w->tb...
a_static void a_Set0_din(a_Set0 *w) { a_VecChr_din(w->tb...
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 = w->tbl->n / sizeof (a_SetElm *),...
a_SetElm **tbl = (a_SetElm **) w->tbl->p, *p;
if (w->tbl->n == 0) goto ins;
p = tbl[0]; c = a_Set0_cmp(elm, p); if (c == 0) goto...
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) ...
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) ...
if (c < 0) { b = m; } else { a = m; }
m = a + ((b - a) >> 1);
} while (m > a);
i = b;
ins:
a_VecChr_resizeDiff(_arg_ w->tbl, sizeof (a_SetElm ...
tbl = (a_SetElm **) w->tbl->p;
if (i < n)
memmove(&tbl[i + 1], &tbl[i], (n - i) * sizeof (...
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 = w->tbl->n / sizeof (a_SetElm *), a, b, ...
a_SetElm **tbl = (a_SetElm **) w->tbl->p, *p;
if (w->tbl->n == 0) goto ins;
p = tbl[0]; c = a_Set0_cmp(elm, p); if (c == 0) goto...
if (c < 0) goto ins;
if (n == 1) goto ins;
p = tbl[n - 1]; c = a_Set0_cmp(elm, p); if (c == 0) ...
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) ...
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 = w->tbl->n / sizeof (a_SetElm *), a, ...
a_SetElm **tbl = (a_SetElm **) w->tbl->p, *p;
if (w->tbl->n == 0) goto ins;
i = 0; c = a_Set0_cmp(elm, tbl[0]); if (c == 0) goto...
if (c < 0) goto ins;
if (n == 1) goto ins;
i = n - 1; c = a_Set0_cmp(elm, tbl[n - 1]); if (c ==...
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) ...
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) * size...
a_VecChr_resizeDiff(_arg_ w->tbl, - (intptr_t) size...
return p;
}
** (2) Set0
-任意長のバイト列をkeyとして、一致するものを O(logN) で検...
-普通ならkeyの順番にソートして二分探索するのですが、memcm...
-そのため、動的配列の中は正しい辞書順にはソートされていま...
-挿入や削除のコストは O(N) なので、Nがそこそこ大きくて挿...
-将来に平衡二分木かB木を使ったSet1を作りたいと思っていま...
-ハッシュ値の計算は FNV-1a アルゴリズムを使っています。Se...
-add関数は、keyに重複がなくて追加に成功した場合にNULLを返...
-find関数は、発見できた場合にその要素を返します。見つから...
-rmv関数は、削除に成功した場合に削除した要素を返します。...
** (3) Q&A
-[Q:00]なんかgotoがたくさんあるように思いますが、なぜそう...
--[A:00]これはまだCコンパイラがあまり速くなかった時期に、...
--今回acl4に入れるにあたって、コンパイラの最適化を当てに...
-[Q:01]ハッシュ値のうちの最上位ビットを捨てて、31ビットし...
--[A:01]それはcmp関数で、ハッシュ値の引き算だけで高速に大...
--・・・というかint64_tを使うなら、ハッシュも63ビットで計...
** (4) サンプルプログラム: t0005a.c
-acl4ライブラリは以下のようにして利用します。
-[1]まずa4_0001～a4_0005のプログラムをつなげて"acl4.c"と...
-[2]次にacl4を使ったプログラムを書きます。
-[3]コンパイル時に、"acl4.c"のあるパスをインクルードパス...
#define a_Version 1
#include <acl4.c>
class_(Data) {
SetElm elm[1];
int age;
const char *phone;
};
int main()
{
Set0 set[1]; Set0_ini(set);
Data data[4], *p; int i;
data[0].elm->k = "Kawai"; data[0].age = 20; data[...
data[1].elm->k = "Suzuki"; data[1].age = 22; data[...
data[2].elm->k = "Tanaka"; data[2].age = 25; data[...
data[3].elm->k = "Yamamoto"; data[3].age = 30; data[...
for (i = 0; i < 4; i++) {
data[i].elm->n = strlen(data[i].elm->k);
Set0_add(set, data[i].elm);
}
SetElm elm[1];
elm->k = "Tanaka"; elm->n = strlen(elm->k);
p = (Data *) Set0_find(set, elm);
if (p == NULL)
printf("name(key)=%s: not found\n", (char *) elm...
else
printf("name(key)=%s: age=%d phone=%s\n", (char ...
Set0_din(set);
a_malloc_debugList(_arg);
return 0;
}
>t0005a
name(key)=Tanaka: age=25 phone=0Y0-YYYY-YYYY
t0005a.c(33): malloc_debugList()
** (5) サンプルプログラム: t0005b.c
-acl4ライブラリは以下のようにして利用します。
-[1]まずa4_0001～a4_0005のプログラムをつなげて"acl4.c"と...
-[2]次にacl4を使ったプログラムを書きます。
-[3]コンパイル時に、"acl4.c"のあるパスをインクルードパス...
#define a_Version 1
#include <acl4.c>
class_(Data) {
SetElm elm[2];
int age;
};
int main()
{
Set0 index[2]; Set0_ini(&index[0]); Set0_ini(&index[...
// nameだけではなく、phoneでもデータを検索できるよう...
Data data[4], *p; int i;
data[0].elm[0].k = "Kawai"; data[0].age = 20; dat...
data[1].elm[0].k = "Suzuki"; data[1].age = 22; dat...
data[2].elm[0].k = "Tanaka"; data[2].age = 25; dat...
data[3].elm[0].k = "Yamamoto"; data[3].age = 30; dat...
for (i = 0; i < 4; i++) {
data[i].elm[0].n = strlen(data[i].elm[0].k);
data[i].elm[1].n = strlen(data[i].elm[1].k);
Set0_add(&index[0], &data[i].elm[0]);
Set0_add(&index[1], &data[i].elm[1]);
}
elm->k = "Tanaka"; elm->n = strlen(elm->k);
pe = Set0_find(&index[0], elm);
p = (Data *) pe;
if (p == NULL)
printf("name(key)=%s: not found\n", (char *) elm...
else
printf("name=%s age=%d phone=%s\n", (char *) p->...
elm->k = "0X0-XXXX-XXXX"; elm->n = strlen(elm->k);
pe = Set0_find(&index[1], elm);
p = NULL; if (pe != NULL) p = (Data *) (pe - 1);
if (p == NULL)
printf("phone(key)=%s: not found\n", (char *) el...
else
printf("name=%s age=%d phone=%s\n", (char *) p->...
Set0_din(&index[0]); Set0_din(&index[1]);
a_malloc_debugList(_arg);
return 0;
}
>t0005b
name=Tanaka age=25 phone=0Y0-YYYY-YYYY
name=Suzuki age=22 phone=0X0-XXXX-XXXX
t0005b.c(43): malloc_debugList()
** (99) 更新履歴
-2026.01.30(金) 初版
終了行:
* acl4のページ0005
-(by [[K]], 2026.01.30)
** (1)
#if (a_Version >= 1)
#define Set0 a_Set0
#define SetElm a_SetElm
#define fnv1a32 a_fnv1a32
#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
#endif
a_class(a_Set0) { a_VecChr tbl[1]; };
a_class(a_SetElm) { const void *k; intptr_t n, h; };
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_static void a_Set0_ini(a_Set0 *w) { a_VecChr_ini(w->tb...
a_static void a_Set0_din(a_Set0 *w) { a_VecChr_din(w->tb...
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 = w->tbl->n / sizeof (a_SetElm *),...
a_SetElm **tbl = (a_SetElm **) w->tbl->p, *p;
if (w->tbl->n == 0) goto ins;
p = tbl[0]; c = a_Set0_cmp(elm, p); if (c == 0) goto...
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) ...
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) ...
if (c < 0) { b = m; } else { a = m; }
m = a + ((b - a) >> 1);
} while (m > a);
i = b;
ins:
a_VecChr_resizeDiff(_arg_ w->tbl, sizeof (a_SetElm ...
tbl = (a_SetElm **) w->tbl->p;
if (i < n)
memmove(&tbl[i + 1], &tbl[i], (n - i) * sizeof (...
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 = w->tbl->n / sizeof (a_SetElm *), a, b, ...
a_SetElm **tbl = (a_SetElm **) w->tbl->p, *p;
if (w->tbl->n == 0) goto ins;
p = tbl[0]; c = a_Set0_cmp(elm, p); if (c == 0) goto...
if (c < 0) goto ins;
if (n == 1) goto ins;
p = tbl[n - 1]; c = a_Set0_cmp(elm, p); if (c == 0) ...
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) ...
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 = w->tbl->n / sizeof (a_SetElm *), a, ...
a_SetElm **tbl = (a_SetElm **) w->tbl->p, *p;
if (w->tbl->n == 0) goto ins;
i = 0; c = a_Set0_cmp(elm, tbl[0]); if (c == 0) goto...
if (c < 0) goto ins;
if (n == 1) goto ins;
i = n - 1; c = a_Set0_cmp(elm, tbl[n - 1]); if (c ==...
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) ...
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) * size...
a_VecChr_resizeDiff(_arg_ w->tbl, - (intptr_t) size...
return p;
}
** (2) Set0
-任意長のバイト列をkeyとして、一致するものを O(logN) で検...
-普通ならkeyの順番にソートして二分探索するのですが、memcm...
-そのため、動的配列の中は正しい辞書順にはソートされていま...
-挿入や削除のコストは O(N) なので、Nがそこそこ大きくて挿...
-将来に平衡二分木かB木を使ったSet1を作りたいと思っていま...
-ハッシュ値の計算は FNV-1a アルゴリズムを使っています。Se...
-add関数は、keyに重複がなくて追加に成功した場合にNULLを返...
-find関数は、発見できた場合にその要素を返します。見つから...
-rmv関数は、削除に成功した場合に削除した要素を返します。...
** (3) Q&A
-[Q:00]なんかgotoがたくさんあるように思いますが、なぜそう...
--[A:00]これはまだCコンパイラがあまり速くなかった時期に、...
--今回acl4に入れるにあたって、コンパイラの最適化を当てに...
-[Q:01]ハッシュ値のうちの最上位ビットを捨てて、31ビットし...
--[A:01]それはcmp関数で、ハッシュ値の引き算だけで高速に大...
--・・・というかint64_tを使うなら、ハッシュも63ビットで計...
** (4) サンプルプログラム: t0005a.c
-acl4ライブラリは以下のようにして利用します。
-[1]まずa4_0001～a4_0005のプログラムをつなげて"acl4.c"と...
-[2]次にacl4を使ったプログラムを書きます。
-[3]コンパイル時に、"acl4.c"のあるパスをインクルードパス...
#define a_Version 1
#include <acl4.c>
class_(Data) {
SetElm elm[1];
int age;
const char *phone;
};
int main()
{
Set0 set[1]; Set0_ini(set);
Data data[4], *p; int i;
data[0].elm->k = "Kawai"; data[0].age = 20; data[...
data[1].elm->k = "Suzuki"; data[1].age = 22; data[...
data[2].elm->k = "Tanaka"; data[2].age = 25; data[...
data[3].elm->k = "Yamamoto"; data[3].age = 30; data[...
for (i = 0; i < 4; i++) {
data[i].elm->n = strlen(data[i].elm->k);
Set0_add(set, data[i].elm);
}
SetElm elm[1];
elm->k = "Tanaka"; elm->n = strlen(elm->k);
p = (Data *) Set0_find(set, elm);
if (p == NULL)
printf("name(key)=%s: not found\n", (char *) elm...
else
printf("name(key)=%s: age=%d phone=%s\n", (char ...
Set0_din(set);
a_malloc_debugList(_arg);
return 0;
}
>t0005a
name(key)=Tanaka: age=25 phone=0Y0-YYYY-YYYY
t0005a.c(33): malloc_debugList()
** (5) サンプルプログラム: t0005b.c
-acl4ライブラリは以下のようにして利用します。
-[1]まずa4_0001～a4_0005のプログラムをつなげて"acl4.c"と...
-[2]次にacl4を使ったプログラムを書きます。
-[3]コンパイル時に、"acl4.c"のあるパスをインクルードパス...
#define a_Version 1
#include <acl4.c>
class_(Data) {
SetElm elm[2];
int age;
};
int main()
{
Set0 index[2]; Set0_ini(&index[0]); Set0_ini(&index[...
// nameだけではなく、phoneでもデータを検索できるよう...
Data data[4], *p; int i;
data[0].elm[0].k = "Kawai"; data[0].age = 20; dat...
data[1].elm[0].k = "Suzuki"; data[1].age = 22; dat...
data[2].elm[0].k = "Tanaka"; data[2].age = 25; dat...
data[3].elm[0].k = "Yamamoto"; data[3].age = 30; dat...
for (i = 0; i < 4; i++) {
data[i].elm[0].n = strlen(data[i].elm[0].k);
data[i].elm[1].n = strlen(data[i].elm[1].k);
Set0_add(&index[0], &data[i].elm[0]);
Set0_add(&index[1], &data[i].elm[1]);
}
elm->k = "Tanaka"; elm->n = strlen(elm->k);
pe = Set0_find(&index[0], elm);
p = (Data *) pe;
if (p == NULL)
printf("name(key)=%s: not found\n", (char *) elm...
else
printf("name=%s age=%d phone=%s\n", (char *) p->...
elm->k = "0X0-XXXX-XXXX"; elm->n = strlen(elm->k);
pe = Set0_find(&index[1], elm);
p = NULL; if (pe != NULL) p = (Data *) (pe - 1);
if (p == NULL)
printf("phone(key)=%s: not found\n", (char *) el...
else
printf("name=%s age=%d phone=%s\n", (char *) p->...
Set0_din(&index[0]); Set0_din(&index[1]);
a_malloc_debugList(_arg);
return 0;
}
>t0005b
name=Tanaka age=25 phone=0Y0-YYYY-YYYY
name=Suzuki age=22 phone=0X0-XXXX-XXXX
t0005b.c(43): malloc_debugList()
** (99) 更新履歴
-2026.01.30(金) 初版
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
