kclib1_0010

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 *)));
  }

こめんと欄