文字列共有のハナシ

結論：std::map(set)、もしくはstd::stringつかいなさい。

はじめに

変更しない文字列があった場合、いちいち構造体とかにメモリをchar str[STR_MAX]とか確保すると
メモリ無駄遣いだし、同じ文字列があった場合さらに無駄になります。
なので、一括で管理する領域に同じ文字列があったらその位置の参照を返却して、もし管理領域に
同じ文字列が無かったら新しく文字列を入れて参照を返すようにすれば、メモリ参照分だけで
文字列参照ができます。

ただし、その参照を使って文字列を書き換えないという前提。
あと、Lispのシンボル管理とかに使えるかも←これが本題

用途

1) 一意な文字列の管理を行う場合
2) メモリを削減して文字列を保存する場合(ただし保存して開放、再利用はしない)

実装

Cで書くと以下のような感じかな。確保するメモリ量は固定ですがちょっと改造すると
メモリが足りなくなったら拡張できます。

#define CHUNK_MAX 8192
char chunk[CHUNK_MAX];

//initialize
void init_chunk() {
  memset(chunk, 0, sizeof(chunk));
}

//search and entry
char *get_chunk(char *s) {
  char *ret = NULL;
  char *scan = chunk;
  while(*scan) {
    if(!strcmp(s, scan)) {
      ret = scan;
      break;
    }
    scan += strlen(scan) + 1;
  }

  if(!ret) {
    strcpy(scan, s);
    ret = scan;
  }
  return ret;
}

//dump chunk
void dump_chunk(char *filename) {
  FILE *fp = fopen(filename, "wb");
  if(fp) {
    fwrite(chunk, 1, sizeof(chunk), fp);
    fclose(fp);
  }
}

init_chunk()をコールした後、文字列の参照取得はget_chunkで行います。
中の様子を見たい場合はdump_chunkでファイル化してバイナリエディタで見ます。

注意点

コードを見てもらうと分かるのですが、マルチバイト文字に対応していません。
あと固定長でメモリ破壊する可能性があるので調整するか、strcpy前に文字列 + NULL分のバイト数を計測して
CHUNK_MAXを超えるならFATALとするなど対処が必要です。

本当の用途

俺が自前のschemeを作ろうとしたときに必要になった。
どうせメモリ足りなくなるのでもうちょっととってもいいかもしれない。

Back

2009/09/30 Gyabo