2010-12-01

TopCoderの学習記録アプリ「するめダイアリー」を作った

WEB 開発作った

最近競技プログラミングにハマりまして、本家ブログの更新ができずにいました。
半年以上ぶりの更新です。

TopCoder部のブログには既に書いた*1のですが、Google App Engineを用いて
TopCoderの学習記録アプリを作りました。
本エントリは制作物の簡単な紹介と、メイキングの解説記事になります。

http://srm-diary.appspot.com/

TopCoder*2って？

オンラインで参加できるプログラミング大会の一種で、

制限時間内に解法が決まっている問題を3つ解く「Single Round Match（略してSRM）」
ヒューリスティクスな解法が要求される、二週間の長丁場「Marathon Match（略してMM）」

などの種目があります。アメリカのラスベガスで世界大会*3も開催されてたりします。
SRMは月二回、MMは月一回ぐらいのペースであります。

これは何をするものか？

SRMの問題を公式サイト*4からクロールしてデータベースにためておき、
問題の難易度、カテゴリごとに検索できるようにしました。
そして、「解いた問題」「解いてない問題」をコードと一緒に記録できます。
さらに、解いた問題をブログ形式に書き出せるようにしました。

以下のスクリーンショットを見ていただければ雰囲気は分かっていただけるかと。

どうやって作ったの？

URLから分かるように、Google App Engine(Python版)をつかいました。
Google App Engine用のPython フレームワークとして、tipfy*5を使ってます。
tipfyは気軽に使えてオススメですが、日本語の解説記事があまり無いので
次回エントリで簡単なチュートリアルを書きたいと思います。

エディタはTextMate *6を使いました。(MacBookで開発してます)
有料ですがEclipseより軽いし多機能だし便利です。

感想

楽だった点

GAEでの開発だったので、

ボタン一発で本番環境にデプロイできる
データベースの管理ツールが用意されている

点が良かったです。

苦労した点

Python版に限らないのですが、データベース周りの制限がきついです。
例えば、

クエリにOR、JOINが使えない
一度に取って来れるデータは1000件まで
条件によってはソートが効かない

などなど。
なので、一度個別に取ってきたデータをつなげてORを無理矢理実装したり、
わざとテーブルを非正規化してJOINを使わなくてすむようにしたりしました。

詳しい開発の話

長くなるのでまた後程。

まとめ

みんなTopCoderに参加すればいいと思うよ。
そしてするめダイアリーへの登録も忘れずに！

*1:http://topcoder.g.hatena.ne.jp/hama_DU/20101118

*2:http://www.topcoder.com/

*3:http://www.topcoder.com/tco10

*4:http://www.topcoder.com/tc?module=ProblemArchive

*5:http://www.tipfy.org/

*6:http://macromates.com/

2010-03-12

CentOS5.3にTrac 0.11.6.ja1を導入してみた。

Linux

自分用メモ。

インスコ前の環境

CentOS5.3
Apache2.2.3(+mod_python)
Python 2.4.3
プロジェクトのsvn リポジトリは既にある

必要なライブラリをダウンロード

python-clearsilver

# yum install clearsilver

sqlite

# yum install sqlite python-sqlite

easy install(Trac-jaのセットアップに必要)

# wget http://peak.telecommunity.com/dist/ez_setup.py
python ez_setup.py

Trac-jaのダウンロードとインストール

http://www.i-act.co.jp/project/products/products.html
からダウンロードできます。

# wget http://www.i-act.co.jp/project/products/downloads/Trac-0.11.6.ja1.zip
# unzip Trac-0.11.6.ja1.zip
# cd Trac-0.11.6.ja1
# python ./setup.py install

プロジェクト用ページを作成

まずtracのデータ、設定ファイルを格納する場所を用意します。

# mkdir -p /opt/trac

tracの管理ツールtrac-adminを用いてプロジェクトの初期化を行います。

# cd /opt/trac
# trac-admin projectname initenv

プロジェクト名、リポジトリへのパスが聞かれるので答えます。
それ以外はたぶんデフォルトでOK。

Apacheの設定

trac-admin でフォルダ /opt/trac/projectname が作成されるので、
apacheが読めるように権限を設定します。

# chown -R apache:apache /opt/trac/projectname
# chmod -R 700 /opt/trac/projectname

httpd.confの編集を行います。
とりあえずバーチャルホストでポート8888番で動作するように設定してみました。

# vi /etc/httpd/conf.d/trac.conf

Listen 8888
NameVirtualHost example.com:8888

<VirtualHost example.com:8888>
  ServerName example.com
  <Location "/trac">
    SetHandler mod_python
    PythonHandler trac.web.modpython_frontend
    PythonOption TracEnv /opt/trac/projectname
    PythonOption TracUriRoot /trac
  </Location>

  <Location "/trac/login">
    AuthType Basic
    AuthName "input username and password."
    AuthUserFile /path/to/svn/.htpasswd
    Require valid-user
  </Location>
</VirtualHost>

apacheを再起動します。

# /etc/init.d/httpd configtest
# /etc/init.d/httpd restart

準備完了

http://example.com:8888/trac にアクセス。

2010-02-11

OS自作入門を勝手に続けてみる - ファイルシステムの開発1

C OS

今回の目標

とりあえずファイルとディレクトリを作れるようにしてみる。

どう作るか？

ディスクI/Oがまだ実装できていないため、ファイルの中身とファイル情報は
さしあたってメモリ上に配置することにした。

「ファイルの情報」を表すような構造体をつくり、
そこにファイルのID、名前、種類、内容へのポインタなどを格納していくことにした。

また、各ファイルには親ディレクトリのID、子供のID(のうちの一つ)を持たせ、
ディレクトリをたどれるようにしてみた。同一レベルでのアクセスはどうするか悩んだが、
ファイルに「次のファイル情報」へのポインタを持たせ、ループするリンクリストを作った。

以上を図にすると以下のような形になる。

ファイルの情報を得る

構造体はFILEINFOと名付けることにした。

struct FILEINFO {
  int id, parent, child;
  unsigned char name[16], type;
  unsigned int timestamp;
  unsigned int *addr;
  unsigned int size;
  struct FILEINFO *next
};

名前はとりあえず16文字まで、typeにはファイルの種別、アクセス権を代入する予定。
addrはmemman_allocで確保したファイルの内容へのポインタにする予定である。

メモリ上の位置は 0x00102600 に設定、id順に並べることにしたので、
「あるファイルidを持つFILEINFOを取得する」関数は簡単に書けそうである。

struct FILEINFO* file_getinfo(int id)
{
  struct FILEMAN *fileman = (struct FILEMAN *) FILEMAN_ADDR;
  return (struct FILEINFO*) (fileman->info_top + sizeof(struct FILEINFO) * id);
}

filemanにはFILEINFOの先頭位置(info_top = 0x00102600)や、現在割り当てられているid数の情報を持たせてある。
場所も決めうちで、

#define FILEMAN_ADDR 0x00300000

とした。

指定された名前のファイルを探す

指定されたパスのファイルを探す関数を書いてみた。

// 指定されたパスのファイルを探す
struct FILEINFO* file_search_path(char *name, int current)
{
  int p;
  char s[32];
  struct FILEINFO *dir_file;

  if ((p = strutil_search(name, '/')) == -1) {
    return file_search(name, current);
  } else {
    if (p == 0) {
      dir_file = file_getinfo(0);
    } else {
      strutil_substr(s, name, 0, p);
      dir_file = file_search(s, current);
    }
    if (dir_file != -1) {
      current = dir_file->id;
      p++;
      return file_search_path(name + p, current);
    } else {
      return (struct FILEINFO*) -1;
    }
  }
}

strutil_ で始まる関数は自前で作成したもので、意味はそれぞれ

strutil_search: 文字列の中で指定された文字の位置を返す関数
strutil_searchl: strutil_searchと同じだが文字列の末尾から検索する
strutil_substr: 部分文字列を切り出す。PHP等のsubstrとほぼ同じ

である。

ディレクトリの階層移動を表す文字「/」をパスの中から探し、見つからなければ、現在のディレクトリの中で該当するファイルを探す処理をする。
「/」が見つかったなら、最初の「/」までの文字をstrutil_substrを用いて切り出し、その名前を持ったディレクトリを探す。
見つかれば、現在のディレクトリをそのディレクトリに設定し、最初の「/」以降の文字を新たなパスとして、再度file_search_pathを実行する。

また、file_searchの処理内容は以下のようにした。

// 指定された名前のファイルを探す
struct FILEINFO* file_search(char *name, int current)
{
  struct FILEINFO *current_dir = file_getinfo(current);
  struct FILEINFO *first_child, *child;
	
  if (strlen(name) == 0) {
    return current_dir;
  }
  if (name[0] == '.' && name[1] == '.') {
    return file_getinfo(current_dir->parent);
  }
  if (current_dir->child != FILE_NO_CHILD) {
    first_child = file_getinfo(current_dir->child);
    child = first_child;
    do {
      if (strcmp(child->name, name) == 0) {
        return child;
      }
      child = child->next;
    } while(child != first_child);
  }
  return (struct FILEINFO*) -1;
}

現在のディレクトリのFILEINFOを取得し、そのchildの値を見る。
childの値が FILE_NO_CHILD であった子供はいないと判断し、ファイルは見つからなかったことにする。
そうでなければディレクトリの子供(のひとつ)のFILEINFOを取得する。

そのFILEINFOからnextの値を見ていき、nextが最初に取得した子供のFILEINFOを指すまでループする。
その中で、FILEINFOのnameの値が指定された名前であるものを探している。

ファイルをリンク、アンリンクする

ファイルを作成する関数を作成する前に、
ファイルを特定のディレクトリの中に入れたり(リンク)、ディレクトリから外したり(アンリンク)する関数を書いた。
また、ファイルそのものを削除する(FILEINFOが指し示す先のメモリを開放し、アンリンクを行う)関数も作成した。
処理内容は以下の通り。

// 指定したファイルを消す（ファイルだったらメモリを開放する）
void file_remove(struct FILEINFO *file, char recursive)
{
  struct MEMMAN *memman = (struct MEMMAN *) MEMMAN_ADDR;
  struct FILEINFO *child, *first;
  if (!FILE_IS_DIRECTORY(file)) {
    memman_free_4k(memman, (int) file->addr, file->size);
  } else if (file->child != FILE_NO_CHILD && recursive){
    first = child = file_getinfo(file->child);
    do {
      file_remove(child, recursive);
      child = child->next;
    } while(first != child);
  }
  file_unlink(file);
}

// 指定したファイルのリンクを解除する（中身・確保したメモリは消さない）
void file_unlink(struct FILEINFO *file)
{
  struct FILEINFO *parent, *brother;
  brother = file->next;
  parent = file_getinfo(file->parent);
  if (file == brother) {
    parent->child = FILE_NO_CHILD;
  } else {
    while( brother->next != file ) {
      brother = brother->next;
    }
    brother->next = file->next;
    parent->child = file->next;
  }
}

// 指定したファイルを特定の場所にリンクする
void file_link(struct FILEINFO *file, struct FILEINFO *directory)
{
  struct FILEINFO *brother, *sister;
  if (directory->child == FILE_NO_CHILD) {
    // 子供がいないなら、自分で自分を指してループを作る
    file->next = file;
    directory->child = file->id;
  } else {
    // 子供がいる場合は、間に挿入する
    brother = file_getinfo(directory->child);
    sister = brother->next;
    file->next = sister;
    brother->next = file;
  }
}

file_removeはファイルの削除を行う。
fileがディレクトリならばメモリの確保は行っていないため後述のunlinkのみ行う。
また、recursiveにtrueが指定されていたときは、fileの子供についても同様の処理を行う。

file_unlinkではfileを自身のparentの子供から外す処理を行っている。
unlinkによって子どもがなくなってしまう場合はchildにFILE_NO_CHILDを代入する。

file_linkでは、directoryの子ファイルとしてfileを登録する。
directoryの子どもがいないならfileのnextは自分自身を指すようにし、
子どもがいる場合は間に挿入するようにしてある。

ファイルを作成する

そして、上記関数を用いてファイルシステムにファイルを追加する関数を書いてみた。
これは後ほどのコマンド「mkfile」「mkdir」で使用する予定である。

// 指定した場所へデータを書き込む。
struct FILEINFO* file_write(char *name, char *data, int parent, int fid, char is_directory)
{
  struct FILEMAN *fileman = (struct FILEMAN *) FILEMAN_ADDR;
  struct MEMMAN *memman = (struct MEMMAN *) MEMMAN_ADDR;
  int id = fid;
  struct FILEINFO *info;
  struct FILEINFO *parent_info;
  
  // ファイルがnameであるものを探す。見つからなかったら新しく作成する
  // 見つかればそのファイルをいったん削除し、同じidにファイルを作成する
  info = file_search_path(name,  parent);
  if (info == -1) {
    id = fileman->allocated_id++;
    info = file_getinfo(id);
  } else {
    id = info->id;
    file_remove(info, 0);
  }
  if (!is_directory) {
    int *to = memman_alloc_4k(memman, strlen(data));
    int i = 0, size = strlen(data);
    // データのコピー
    for (i = 0 ; i < size ; i++) {
      to[i] = data[i];
    }
    info->addr = to;
    info->size = size;
  }

  // FILEINFOに書き込む
  strncpy(info->name, name, FILE_MAX_NAME);
  info->id = id;
  info->parent = parent;
  info->type = file_generate_type(is_directory, 1, 1);
  info->child = FILE_NO_CHILD;
  
  // 親のデータを取得してリンク作成
  parent_info = file_getinfo(parent);
  file_link(info, parent_info);
  
  return info;
}

まとめ

長くなってしまったので今回はここまで。
次回はこれらの関数を用いて、各コマンドを実装する。

今回作成した関数

ファイル情報とファイル検索

struct FILEINFO* file_getinfo(int id): 指定された番号のFILEINFOへのポインタを得る
struct FILEINFO* file_search_path(char *name, int current): 指定されたパスのファイルを探し、FILEINFOへのポインタを返す
struct FILEINFO* file_search(char *name, int current): 指定されたディレクトリの中でファイル名がnameであるものを探す。

ファイルの削除

void file_remove(struct FILEINFO *file, char recursive): ファイルを削除する。指定されたファイルがディレクトリであり、かつrecuresiveがtrueならば子となるファイルも再帰的に削除する。
void file_unlink(struct FILEINFO *file): ファイルをリンクから外す。削除は行わない。

ファイルの追加

struct FILEINFO* file_write(char *name, char *data, int parent, int fid, char is_directory): 指定されたディレクトリにファイルnameを追加する。すでにnameがあったらファイルを削除し、新たに作成する。
void file_link(struct FILEINFO *file, struct FILEINFO *directory): 指定されたファイルをdirectoryの子として登録する。

2010-01-02

「30日でできる！OS自作入門」を読了、オリジナルOSの開発について書く

C OS

緒言

これから僕がちまちま作っているオリジナルOS開発の過程について書いていきたいと思う。
せっかくやっていることなので、やはり公開してフィードバックをもらえたらな、と思ったので。
本日は導入のみで、次回から実際の開発について詳しく述べる。

「30日でできる！OS自作入門」について

「30日でできる！OS自作入門」は、アセンブラとC言語を駆使して
OSを自作してしまおう！という趣旨の本である。
プートプログラムの作成から、メモリ管理、キーボードやマウスからの情報の読み取り、
マルチタスクシステム、アプリケーションの起動、APIの作成・・・などなどを
本の内容にしたがって少しずつ自分で手を動かしてOSを作っていく、といった内容である。
昨年から気になっていた本だが、ついに手に取る機会が訪れた。

30日でできる! OS自作入門

作者: 川合秀実
出版社/メーカー: 毎日コミュニケーションズ
発売日: 2006/03/01
メディア: 単行本
購入: 36人クリック: 700回
この商品を含むブログ (302件) を見る

きっかけ

というのも、大学の情報学科ではオペレーティングシステムの授業があるのだが、
その授業では「通常コース」か「実践コース」かが選べるようになっている。
「実践コース」をとった場合、授業への出席*1や課題の提出義務は無い。
その代わり、上記の本を学習し、本の内容に加えてOSとしての完成度を高めたものを学期末に先生へ提出する必要がある。
僕は課題を出すのが面倒であったため、「実践コース」を選んだ。

結果、なんとか12月半ばぐらいに学習を終えることができた。
しかし、大変なのはここからで、単位をとるためには本で作成したOSを改造し、
多機能なOSとして完成度を高めなくてはならない。
だが、本で作成するOSには未完成、未実装である部分もあり、改造のしがいはある。
具体的には、

ファイルシステム
ディスクの読み書き
マルチタスクによるアクセス競合の解決

などなど、である。

どんなOSを作るか

本で作成しているサンプルOSは、どちらかというとWindowsライクなOSである。
デスクトップがあり、タスクバー（使われてないが）があり、コマンドプロンプトっぽいものがある。

僕は、CUIベースの、どちらかというとUNIXに近いシステムを作ろうと思っている。なぜなら・・・

ウィンドウシステムのプログラミングが面倒。学期末に間に合うかどうか微妙。
1.が省けるため、OS開発の本質であるファイルシステムやディスクへの読み書きなどに時間が割けそう。
最悪、オープンソースなのでアイデアをいただける。ネット上にも情報が落ちていそう。

したがって、本の後半で出てくる

グラフィック関連のAPI
ウィンドウの切り替え
日本語表示

などはおそらく今回作成するOSには必要ないため、
これからの開発は21日目の終わりの成果物(harib18g)をベースに行うことにした。

これから

とりあえずファイルシステム、とそれにまつわる各種コマンド(cd, mv, rm, ls等)を作成しようと思う。
lsに相当するものは本でも例示されていたが、ディレクトリ等の概念が無いので書き直す予定。

*1:一応2/3出席は必要なのか？不安なので授業への出席はしている

hama_duのブログ

ノンジャンル記事置き場