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

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
kclib1_0010 へ行く。
- 1 (2019-04-22 (月) 14:58:28)
- 2 (2019-04-22 (月) 16:32:31)

kclib1のページ#10

(by K, 2019.04.22)

(18) KIndexS

KSizPtrを使った、ソートされたインデックスです。末尾のSはソートの略です。
この関数群はインデックス構造だけを管理するので、データ本体は管理しません。
データの登録手法としては、insで普通に入れていく方法と、addして最後にsortする方法の二通りをサポートしています。
- ins方式： O(N*N*logN)
- add+sort方式： O(N*logN)
- Nが小さいうちはinsのほうが少し速いですがすぐに逆転します。
searchのスピードは1件に付きO(logN)です。

void KIndexS_init(KIndexS *w, int s1, void *cmp, void *opt)
- KIndexSを初期化します。s1は初期サイズで、まあよくわからなければ0でいいです。cmpとoptは整列順序を決めるための比較関数でkqsortに準じます。
void KIndexS_free(KIndexS *w)
- KIndexSが管理していた内部のテーブルを解放します。
int KIndexS_search(KIndexS *w, void *key, int *cr)
- KIndexSの中からkeyがどこにあるかを二分探索で探します。見つかった場合、*cr=0になります。見つからなかった場合、*crは負の値になり、関数の戻り値は「そのkeyをinsするとしたらどこがいいか」をバイト単位で表した値になっています。
- 戻り値から「何番目」の情報なのかを知りたいときは、sizeof (void *)で割り算する必要があります。
int KIndexS_ins(KIndexS *w, void *d)
- KIndexSにデータを一つ追加します。ソート順序は保たれます。
int KIndexS_del(KIndexS *w, void *d)
- KIndexSからデータを一つ消します。
void KIndexS_add(KIndexS *w, void *d);
- KIndexSの末尾にデータを追加します。ソート順序が保たれるかどうかは追加するデータ次第です。
void KIndexS_sort(KIndexS *w);
- KInidexSの中のデータの順序の乱れを一気に修正します。
int KIndexS_getN(KIndexS *w)
- KIndexSが管理してしているデータの個数を返します。
void *KIndexS_getPtr(KIndexS *w, int i)
- KIndexSの順序で、i番目のデータへのポインタを返します。

[内部実装]

typedef struct KIndexS_ {
    KSizPtr sp;
    void *cmp, *opt;
} KIndexS;

[内部実装]

#include "kclib1.h"

void KIndexS_init(KIndexS *w, int s1, void *cmp, void *opt)
{
    KSizPtr_init(&w->sp, s1 * sizeof (void *));
    w->cmp = cmp;
    w->opt = opt;
}

void KIndexS_free(KIndexS *w)
{
    KSizPtr_free(&w->sp);
}

int KIndexS_search(KIndexS *w, void *key, int *cr)
{
    int a, b, c, cc, ccb;
    int (*cmp)(void *, void *, void *);
    void *opt = w->opt, *pk = &key;
    if (w->sp.s <= 0) {
        *cr = -1;
        return 0;
    }
    cmp = w->cmp;
    cc = cmp(opt, pk, w->sp.p);
    if (cc <= 0) {
        *cr = cc;
        return 0;
    }
    cc = cmp(opt, pk, w->sp.p + w->sp.s - sizeof (void *));
    if (cc > 0) {
        *cr = -1;
        return w->sp.s;
    }
    if (cc == 0) {
        *cr = 0;
        return w->sp.s - sizeof (void *);
    }
    ccb = cc;
    a = 0;
    b = w->sp.s - sizeof (void *);
    for (;;) {
        c = ((b - a) >> 1) & (- sizeof (void *));
        if (c == 0) break;
        c += a;
        cc = cmp(opt, pk, w->sp.p + c);
        if (cc > 0)
            a = c;
        else {
            b = c;
            ccb = c;
        }
    }
    *cr = cc;
    return b;
}

int KIndexS_ins(KIndexS *w, void *d)
{
     int cr, i;
     i = KIndexS_search(w, d, &cr);
//   if (cr == 0) return ~i;
     KSizPtr_insPtr(&w->sp, i, d);
     return i;
}

int KIndexS_del(KIndexS *w, void *d)
{
    int cr, i;
    i = KIndexS_search(w, d, &cr);
    if (cr != 0) return ~i;
    if (*((void **) (w->sp.p + i)) != d) return 0x80000000;
    KSizPtr_delPtr(&w->sp, i);
    return i;
}

void KIndexS_add(KIndexS *w, void *d)
{
    KSizPtr_addPtr(&w->sp, d);
}

void KIndexS_sort(KIndexS *w)
{
    kqsort(w->sp.p, w->sp.s / sizeof (void *), sizeof (void *), w->cmp, w->opt);
}

int KIndexS_getN(KIndexS *w)
{
     return w->sp.s / sizeof (void *);
}

void *KIndexS_getPtr(KIndexS *w, int i)
{
    return *((void **) (w->sp.p + i * sizeof (void *)));
}

↑

こめんと欄

コメント	お名前	NameLink