ポインタのエンコード

さぁ、可変長配列データベースを作成しましょう、といいたいところですが、やはり、前準備が必要です。可変長データベースでは可変長データを複数の固定長データに分割して固定長データベースに管理するので、固定長データのリスト構造を生成します。そのために各固定長データに次の固定長データへのポインタを持つ必要があります。

たとえば８バイトの領域をポインタとして持っても良いのですが、データが少ない時には、ポインタの値も小さくなります。よほど大量にデータを保存しない限り通常８バイトのサイズは不要です。かといってサイズを小さくしてしまうと、データが増えた時に対応できなくなります。

そこで、ポインタの値の大きさに応じた可変長のデータ形式にポインタのエンコードを行うことにします。データの先頭に値の大きさを示す値を入れておくだけです。その値の大きさに応じて有効なデータ領域のサイズが可変となります。複雑なビット処理は速度低下につながるので値そのものに対してビット単位のシフトは行わずバイト単位のシフトのみするようにしています。

class Codec {
public:
  Codec(){}
  static size_t encode(size_t v, unsigned char *buf) {
    size_t mask = 0xffffffffffffff80;
    int cnt;
    for (cnt = 0; cnt < sizeof(size_t); cnt++) {
      if ((mask & v) == 0) {
        break;
      }
      mask <<= 7;
    }

    if (cnt == sizeof(size_t)) {
      valcpy(&buf[1], v, sizeof(size_t));
      buf[0] = 0xff;
    } else {
      valcpy(buf, v, cnt + 1);
      buf[0] |= (0xff << (sizeof(size_t) - cnt));
    }

    size_t validSize = cnt + 1;
    return validSize;
  }
  static size_t decode(unsigned char *buf, size_t &size) {
    int cnt;
    unsigned char mask = 0x80;
    unsigned char head = buf[0];
    for (cnt = 0; cnt < sizeof(size_t); cnt++) {
      if ((mask & head) == 0) {
        break;
      }
      mask >>= 1;
    }

    size_t v = 0;
    if (cnt > sizeof(size_t)) {
      valcpy(v, &buf[1], sizeof(size_t));
      size = 9;
    } else {
      valcpy(v, buf, cnt + 1);
      *(((unsigned char*)&v) + cnt) &= (0x7f >> cnt);
      size = cnt + 1;
    }
    return v;
  }

 private:
  static void
  valcpy(unsigned char *buf, size_t &v, int s) {
    unsigned char *vptr = (unsigned char*)&v + s - 1;
    for (int i = 0; i < s; i++) {
      *buf++ = *vptr--;
    }
  }

  static void
  valcpy(size_t &v, unsigned char *buf, int s) {
    v = 0;
    unsigned char *vptr = (unsigned char*)&v + s - 1;
    for (int i = 0; i < s; i++) {
      *vptr-- = *buf++;
    }
  }

};

前：固定長データベース

次：可変長データベース