a4_0005 のバックアップ(No.2)

[ トップ ]   [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ ]

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• a4_0005 へ行く。
  • 1 (2026-01-30 (金) 10:31:48)
  • 2 (2026-01-30 (金) 12:39:52)

---

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->tbl); }
a_static void a_Set0_din(a_Set0 *w) { a_VecChr_din(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 = w->tbl->n / sizeof (a_SetElm *), a, b, m, c;
    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 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(_arg_  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 = w->tbl->n / sizeof (a_SetElm *), a, b, m, c;
    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 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 = w->tbl->n / sizeof (a_SetElm *), a, b, m, c;
    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 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(_arg_  w->tbl, - (intptr_t) sizeof (a_SetElm *));
    return p;
}

(2) Set0

• 任意長のバイト列をkeyとして、一致するものを O(logN) で検索できるクラスです。動的配列を使った単純なものです。
• 普通ならkeyの順番にソートして二分探索するのですが、memcmpがあまり速くないので、ハッシュ値を計算してまずハッシュ値hやkeyの長さnをつかって二分探索して範囲を絞った後に、memcmpして順番を決めています。
• そのため、動的配列の中は正しい辞書順にはソートされていません。
• 挿入や削除のコストは O(N) なので、Nがそこそこ大きくて挿入や削除が多いなら最適とは言えないクラスです。
• 将来に平衡二分木かB木を使ったSet1を作りたいと思っています。その時にSet0と比べてどのくらい速くなったかを比較できたらいいなと思ったので、まずSet0を作ることにしました。
• ハッシュ値の計算は FNV-1a アルゴリズムを使っています。Set0はハッシュテーブルを使った方法ではないので、ハッシュ値の衝突があっても検索時間が O(N) になるリスクはありません。だからハッシュ値の質はそれほど重要ではなくて、軽量な FNV-1a を採用しています。

• add関数は、keyに重複がなくて追加に成功した場合にNULLを返します。keyに重複があって追加しなかった場合は重複している要素を返します。
• find関数は、発見できた場合にその要素を返します。見つからなかったときはNULLを返します。
• rmv関数は、削除に成功した場合に削除した要素を返します。一致するkeyがなくて削除できなかった場合はNULLを返します。

(3) Q&A

• [Q:00]なんかgotoがたくさんあるように思いますが、なぜそうしているのですか？
  • [A:00]これはまだCコンパイラがあまり速くなかった時期に、速度を上げようと思って書いた時の名残りです。
  • 今回acl4に入れるにあたって、コンパイラの最適化を当てにして簡単で読みやすい形に書き直そうかなとは思ったのですが、まあこのコードで問題なく動いているわけですし、それならわざわざ手を入れなくてもいいかなと思って、ほぼそのまま持ってきてしまいました。

• [Q:01]ハッシュ値のうちの最上位ビットを捨てて、31ビットしか使わないようにしているのはなぜですか？
  • [A:01]それはcmp関数で、ハッシュ値の引き算だけで高速に大小比較したかったからです。32ビットをフルに使った状態だと、たとえば a:0xffffffff と b:0x00000001 を引き算したときに、プラスの答えを出すことができません（int64_t)にキャストしてから引き算して、int64_tで値を返すなら問題なく処理できますが、それだと32bit-CPUで使ったときに高速に処理できません。
  • ・・・というか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[0].phone = "090-8765-4321";
    data[1].elm->k = "Suzuki";   data[1].age = 22; data[1].phone = "0X0-XXXX-XXXX";
    data[2].elm->k = "Tanaka";   data[2].age = 25; data[2].phone = "0Y0-YYYY-YYYY";
    data[3].elm->k = "Yamamoto"; data[3].age = 30; data[3].phone = "0Y0-YYYY-YYYY";
    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->k);
    else
        printf("name(key)=%s: age=%d phone=%s\n", (char *) p->elm->k, p->age, p->phone);

    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[1]); SetElm elm[1], *pe;

    // nameだけではなく、phoneでもデータを検索できるようにした例.
    Data data[4], *p; int i;
    data[0].elm[0].k = "Kawai";    data[0].age = 20; data[0].elm[1].k = "090-8765-4321";
    data[1].elm[0].k = "Suzuki";   data[1].age = 22; data[1].elm[1].k = "0X0-XXXX-XXXX";
    data[2].elm[0].k = "Tanaka";   data[2].age = 25; data[2].elm[1].k = "0Y0-YYYY-YYYY";
    data[3].elm[0].k = "Yamamoto"; data[3].age = 30; data[3].elm[1].k = "0Y0-YYYY-YYYY";
    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->k);
    else
        printf("name=%s age=%d phone=%s\n", (char *) p->elm[0].k, p->age, (char *) p->elm[1].k);

    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 *) elm->k);
    else
        printf("name=%s age=%d phone=%s\n", (char *) p->elm[0].k, p->age, (char *) p->elm[1].k);

    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(金) 初版

     

Site admin: K

PukiWiki 1.4.7 Copyright © 2001-2006 PukiWiki Developers Team. License is GPL.
Based on "PukiWiki" 1.3 by yu-ji. Powered by PHP 5.6.40. HTML convert time: 0.011 sec.