a24_AMapSim11 のバックアップ(No.1)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
a24_AMapSim11 へ行く。
- 1 (2024-09-20 (金) 11:55:31)

AMapSim11

(by K, 2024.09.20)

(0)

AMap11の実装の一つ。動的配列を使って、key-valueの関係を記憶する。
keyとvalueは別々で同じ大きさの動的配列になっているが、これはkeyのアクセス頻度がvalueよりもずっと高くなることを踏まえて、データの局在化を意図したものである（気キャッシュヒット率の向上）。
AMapSim11は小規模のとき以外には性能的にかなり劣ると思うが、とりあえずデフォルトで入れておく分にはたいして邪魔にもならないだろう。

(1) ver.1.00 [2024.09.20] (69行)

AClass(AMapSim11) {
    void *add, *del, *sch, *dst;
    AInt n1, n, flags;
    AM *m;
    void **tk, **tv;
};

AStatic AInt AMapSim11_schSub(AMapSim11 *w, void *k)
{
    AInt i, n = w->n;
    void **tk = w->tk;
    for (i = 0; i < n; i++) {
        if (k == tk[i]) break;
    }
    return i;
}

AStatic void AMapSim11_add(AMapSim11 *w, void *k, void *v)
{
    if (w->n >= w->n1) {
        w->tk = AM_rlc(w->m, 0, w->tk, w->n1 * sizeof (void *), w->n1 * (2 * sizeof (void *)));
        w->tv = AM_rlc(w->m, 0, w->tv, w->n1 * sizeof (void *), w->n1 * (2 * sizeof (void *)));
        w->n1 *= 2;
    }
    w->tk[w->n] = k;
    w->tv[w->n] = v;
    w->n++;
}

AStatic void *AMapSim11_sch(AMapSim11 *w, void *k, void *v0)
{
    AInt i = AMapSim11_schSub(w, k);
    if (i >= w->n) return v0;
    return w->tv[i];
}

AStatic int AMapSim11_del(AMapSim11 *w, void *k)
{
    AInt i = AMapSim11_schSub(w, k);
    if (i >= w->n) return 1;
    w->tk[i] = w->tk[w->n - 1];
    w->tv[i] = w->tv[w->n - 1];
    w->n--;
    return 0;
}

AStatic void AMapSim11_dst(AMapSim11 *w)
{
    AM_fre(w->m, w->tk, w->n1 * sizeof (void *));
    AM_fre(w->m, w->tv, w->n1 * sizeof (void *));
    AM_fre(w->m, w, sizeof (AMapSim11));
}

AStatic AMap11 *AMapSim11_opn(int f, AM *m)
{
    AMapSim11 *w = AM_alc(m, 0, sizeof (AMapSim11));
    w->add = AMapSim11_add;
    w->del = AMapSim11_del;
    w->sch = AMapSim11_sch;
    w->dst = AMapSim11_dst;
    w->flags = f;
    w->n = 0;
    w->n1 = 4;
    w->tk = AM_alc(m, 0, w->n1 * sizeof (void *));
    w->tv = AM_alc(m, 0, w->n1 * sizeof (void *));
    w->m = m;
    if ((f & 1) != 0) AM_arp(m, AMap11_dst, w, 0, 0);
    return (AMap11 *) w;
}