Project: finder, src: docid.c

#include "docid.h"
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
#include <string.h>

/* 内部で使用する構造体 */
typedef struct DOC_OPTION {
  unsigned long long lastid; // 最後に生成するべき ID
  off_t parent; // offset == 0 の場合は最後の entry のオフセット
  unsigned char level; // このノードのレベル; 0 で leaf node
  unsigned char next; // 空いている最小の配列要素
  unsigned char dummy[6];
} DOC_OPTION;

#define MAX_DOC_ENTRY (253ULL)

typedef struct DOC_ENTRY {
  DOC_OPTION option;
  off_t offset[MAX_DOC_ENTRY];
} DOC_ENTRY;

/* entry 内の配列の隣接する要素の「近さ」 */
static unsigned long long DIV_DOC_ENTRY[] = {
  1, // level:0
  MAX_DOC_ENTRY, // level:1
  MAX_DOC_ENTRY * MAX_DOC_ENTRY, // level:2
  MAX_DOC_ENTRY * MAX_DOC_ENTRY * MAX_DOC_ENTRY, // level:3
  MAX_DOC_ENTRY * MAX_DOC_ENTRY * MAX_DOC_ENTRY * MAX_DOC_ENTRY // level:4
};

/**
 * 新しい entry を確保する
 */
static void createElbowRoom(int fd, off_t *poff, DOC_ENTRY *e) {
  if (*poff != 0) {
    off_t parent = e->option.parent, child;
    DOC_ENTRY ep, ec;
    lseek(fd, parent, SEEK_SET);
    read(fd, &ep, sizeof(ep));

    // 親に空きがない場合、再帰で空きを探索する
    if (ep.option.next >= MAX_DOC_ENTRY) {
      createElbowRoom(fd, &parent, &ep);
    }

    child = lseek(fd, 0, SEEK_END);
    memset(&ec, 0, sizeof(ec));
    ec.option.level = ep.option.level - 1;
    ec.option.parent = parent;
    write(fd, &ec, sizeof(ec));
    ep.offset[ep.option.next++] = child;
    lseek(fd, parent, SEEK_SET);
    write(fd, &ep, sizeof(ep));
    memcpy(e, &ec, sizeof(*e));
    *poff = child;
  } else {
    // root entry の場合は root の内容を退避して新しい entry を作成する
    DOC_ENTRY ep, ec;
    off_t child = lseek(fd, 0, SEEK_END);
    write(fd, e, sizeof(*e));
    memset(&ep, 0, sizeof(ep));
    ep.option.level = e->option.level + 1;
    ep.option.lastid = e->option.lastid;
    ep.offset[ep.option.next++] = child;
    memset(&ec, 0, sizeof(ec));
    ec.option.level = e->option.level;
    child = lseek(fd, 0, SEEK_END);
    write(fd, &ec, sizeof(ec));
    ep.offset[ep.option.next++] = child;
    lseek(fd, 0, SEEK_SET);
    write(fd, &ep, sizeof(ep));
    *poff = child;
    memcpy(e, &ec, sizeof(*e));
  }
}

/**
 * text を DB に登録し、ドキュメント ID を取得する
 */
unsigned long long createDocId(int fd, const char *text, int len) {
  DOC_ENTRY e;
  unsigned long long id;
  off_t nextOffset, textOffset; 
  if (lseek(fd, 0, SEEK_END) == (off_t)0) {
    // 新しいファイル
    memset(&e, 0, sizeof(e));
    write(fd, &e, sizeof(e));
  }

  // テキストを登録する
  textOffset = lseek(fd, 0, SEEK_END);
  write(fd, &len, sizeof(len));
  write(fd, text, len);

  // root を読み込む
  lseek(fd, 0, SEEK_SET);
  read(fd, &e, sizeof(e));
  id = e.option.lastid++;
  lseek(fd, 0, SEEK_SET);
  write(fd, &e, sizeof(e));

  // 次の空きエントリを読み込む
  nextOffset = e.option.parent;
  lseek(fd, nextOffset, SEEK_SET);  
  read(fd, &e, sizeof(e));
  if (e.option.next >= MAX_DOC_ENTRY) {
    DOC_ENTRY root;

    // entry を分割する
    createElbowRoom(fd, &nextOffset, &e);

    // root entry に nextOffset を登録する
    lseek(fd, 0, SEEK_SET);
    read(fd, &root, sizeof(root));
    root.option.parent = nextOffset;
    lseek(fd, 0, SEEK_SET);
    write(fd, &root, sizeof(root));
  }

  // テキストオフセットを保存する
  e.offset[e.option.next++] = textOffset;
  lseek(fd, nextOffset, SEEK_SET);
  write(fd, &e, sizeof(e));
 
  return id;
}

/**
 * ドキュメント ID に対応する text を取得する
 * 取得できない場合は NULL を返す
 */
char *getDocFromId(int fd, unsigned long long id, int *plen) {
  DOC_ENTRY e;
  unsigned long long div, mod, cur = id;
  int len;
  char *text;
  unsigned char level;

  // id が現在 DB に含まれている最大の ID より大きかったらエラー
  lseek(fd, 0, SEEK_SET);
  if (read(fd, &e, sizeof(e)) < sizeof(e)) {
    return NULL;
  }
  if (e.option.lastid <= id) {
    return NULL;
  }

  // entry をたどっていく
  level = e.option.level;
  while (level > 0) {
    div = cur / DIV_DOC_ENTRY[level];
    mod = cur % DIV_DOC_ENTRY[level];
    lseek(fd, e.offset[div], SEEK_SET);
    read(fd, &e, sizeof(e));
    cur = mod;
    level = e.option.level;
  }

  lseek(fd, e.offset[cur], SEEK_SET);
  read(fd, &len, sizeof(len));
  text = (char *)malloc(len + 1);
  read(fd, text, len);
  text[len] = '\0';
  if (plen != NULL) {
    *plen = len;
  }
  return text;
}

/**
 * 次の登録に使用するドキュメント ID を返す
 * ドキュメント ID は 0 から開始する
 */
unsigned long long getLastDocId(int fd) {
  DOC_ENTRY e;
  lseek(fd, 0, SEEK_SET);
  if (read(fd, &e, sizeof(e)) < sizeof(e)) {
    e.option.lastid = 0;
  }
  return e.option.lastid;
}

#ifdef DEBUG
#include <stdio.h>
#include <sys/stat.h>
#include <fcntl.h>

void testSize(int fd) {
  unsigned long long lastid = getLastDocId(fd);
  printf("last doc id is:%llu\n", lastid);
}

void testGetId(int fd, int id) {
  int len;
  char *doc = getDocFromId(fd, id, &len);
  if (doc == NULL) {
    printf("id:%d not archived\n", id);
  } else {
    printf("id:%d title:%.*s\n", id, len, doc);
  }
}

void testArchive(int fd, char *title) {
  unsigned long long docid = createDocId(fd, title, strlen(title));
  printf("title archived as id:%llu\n", docid);
}

int main(int argc, char **argv) {
  int opt, action = 0, fd;
  char *arg;
  char *dbname = "./title.docdb";

  while ((opt = getopt(argc, argv, "d:a:g:s")) != -1) {
    switch (opt) {
    case 'd':
      dbname = optarg;
      break;
    case 'a':
    case 'g':
      action = opt;
      arg = optarg;
      break;
    case 's':
      action = opt;
      break;
    default:
      printf("unknown option: usage: docid [-s / -a <string> / -g <id> ]\n");
      exit(1);
    }
  }

  fd = open(dbname, O_RDWR | O_CREAT, 0644);
  if (fd < 0) {
    printf("failed to open %s\n", dbname);
    exit(1);
  }

  switch(action) {
  case 's':
    testSize(fd);
    break;
  case 'a':
    testArchive(fd, arg);
    break;
  case 'g':
    testGetId(fd, atoi(arg));
    break;
  default:
    printf("unknown option: usage: docid [-s / -a <string> / -g <id> ]\n");
  }
  close(fd);
  return 0;
}

#endif // DEBUG