今日の関数 do_search その1 (https://github.com/vim/vim)
vimで検索されると呼ばれる関数です。 検索の実行はsearchitでされますがその前後にoffsetや複数回の検索の調整をこの関数では 行います。
search.c
int
do_search(
oparg_T *oap, /* can be NULL */
int dirc, /* '/' or '?' */
char_u *pat,
long count,
int options,
proftime_T *tm) /* timeout limit or NULL */
{
pos_T pos; /* position of the last match */
char_u *searchstr;
struct soffset old_off;
int retval; /* Return value */
char_u *p;
long c;
char_u *dircp;
char_u *strcopy = NULL;
char_u *ps;
変数を初期化します。
/*
* A line offset is not remembered, this is vi compatible.
*/
if (spats[0].off.line && vim_strchr(p_cpo, CPO_LINEOFF) != NULL)
{
spats[0].off.line = FALSE;
spats[0].off.off = 0;
}
spats[0]の中にある変数を初期化します。vi compatible のためのようです。
/* * Save the values for when (options & SEARCH_KEEP) is used. * (there is no "if ()" around this because gcc wants them initialized) */ old_off = spats[0].off; pos = curwin->w_cursor; /* start searching at the cursor position */
SEARCH_KEEPのオプションをつければ前回のoffsetをそのまま使います。 ここでposを今のカーソルの位置にセットしておきます。これでカーソル位置から 検索がされるようになります。
if (dirc == 0)
dirc = spats[0].off.dir;
else
{
spats[0].off.dir = dirc;
#if defined(FEAT_EVAL)
set_vv_searchforward();
#endif
}
dircは'/'か'?'を指しています。もし何も指していない場合前回と同じdirが使われます。
if (options & SEARCH_REV)
{
#ifdef WIN32
/* There is a bug in the Visual C++ 2.2 compiler which means that
* dirc always ends up being '/' */
dirc = (dirc == '/') ? '?' : '/';
#else
if (dirc == '/')
dirc = '?';
else
dirc = '/';
#endif
}
SEARCH_REVのオプションが有効なら'/'と'?'を反転します。
#ifdef FEAT_FOLDING
/* If the cursor is in a closed fold, don't find another match in the same
* fold. */
if (dirc == '/')
{
if (hasFolding(pos.lnum, NULL, &pos.lnum))
pos.col = MAXCOL - 2; /* avoid overflow when adding 1 */
}
else
{
if (hasFolding(pos.lnum, &pos.lnum, NULL))
pos.col = 0;
}
#endif
カーソルが閉じているfoldにいたらその中の検索はしないために もし'/'前進検索ならカーソルのcolの位置をmaxの位置に持っていき '?'後進検索ならカーソルの位置を行の最初に移動します。 こうすることでもうこの行では検索がマッチしません。
#ifdef FEAT_SEARCH_EXTRA
/*
* Turn 'hlsearch' highlighting back on.
*/
if (no_hlsearch && !(options & SEARCH_KEEP))
{
redraw_all_later(SOME_VALID);
SET_NO_HLSEARCH(FALSE);
}
#endif
FEAT_SEARCH_EXTRAが定義されているならhlsearchをセットします。 hlsearchをセットすると検索で見つかったすべての文字がハイライトされます。
今日の関数 vim_chdirfile (https://github.com/vim)
misc2.c
int
vim_chdirfile(char_u *fname)
{
char_u dir[MAXPATHL];
vim_strncpy(dir, fname, MAXPATHL - 1);
*gettail_sep(dir) = NUL;
return mch_chdir((char *)dir) == 0 ? OK : FAIL;
}
ファイル名からそのファイルの親ディレクトリでchdirを呼ぶ関数です。
dirにファイルのパスをコピーします。
次にそのパスの最後のseparatorを探しそこにNULを入れ、それをchdirに送るという流れです。
vim.h
#define STRNCPY(d, s, n) strncpy((char *)(d), (char *)(s), (size_t)(n))
strncpyを呼ぶだけ。
misc1.c
/*
* Get pointer to tail of "fname", including path separators. Putting a NUL
* here leaves the directory name. Takes care of "c:/" and "//".
* Always returns a valid pointer.
*/
char_u *
gettail_sep(char_u *fname)
{
char_u *p;
char_u *t;
p = get_past_head(fname); /* don't remove the '/' from "c:/file" */
t = gettail(fname);
while (t > p && after_pathsep(fname, t))
--t;
#ifdef VMS
/* path separator is part of the path */
++t;
#endif
return t;
}
pにはファイルパスの一番最初のseparatorの次の文字を指しているポインタが得られます。例えば/Users/my_name/my_file.txtならUを指しているポインタです。(get_past_head)
tにはファイルパスの最後のseparatorから後ろ、つまりファイル名をとります。例えば/Users/my_name/my_file.txtならmy_file.txtのmを指しているポインタです。(gettail)
tのポインタがpより大きくその一つ前がseparatorなら/Users/my_name/my_file.txtのmy_fileのmから左にポインタが動きます。
/Users/my_name/my_file.txtはmy_file.txtのmから始まってafter_pathsepがtrueを返すので一つ戻って/my_file.txtの/を指すポインタが返ります。
そしてその場所にNULLを入れるので/Users/my_name\000my_file.txtがdirに入ってchdirが呼ばれます。つまりファイルの親ディレクトリにchdirすることになります。
misc1.c
/*
* Get a pointer to one character past the head of a path name.
* Unix: after "/"; DOS: after "c:\"; Amiga: after "disk:/"; Mac: no head.
* If there is no head, path is returned.
*/
char_u *
get_past_head(char_u *path)
{
char_u *retval;
#if defined(MSWIN)
/* may skip "c:" */
if (isalpha(path[0]) && path[1] == ':')
retval = path + 2;
else
retval = path;
#else
# if defined(AMIGA)
/* may skip "label:" */
retval = vim_strchr(path, ':');
if (retval == NULL)
retval = path;
# else /* Unix */
retval = path;
# endif
#endif
while (vim_ispathsep(*retval))
++retval;
return retval;
}
windowsのc:などに対処しながら最初のseparatorの次の位置を返します。(++retval)(←)
misc1.c
/*
* Get the tail of a path: the file name.
* When the path ends in a path separator the tail is the NUL after it.
* Fail safe: never returns NULL.
*/
char_u *
gettail(char_u *fname)
{
char_u *p1, *p2;
if (fname == NULL)
return (char_u *)"";
for (p1 = p2 = get_past_head(fname); *p2; ) /* find last part of path */
{
if (vim_ispathsep_nocolon(*p2))
p1 = p2 + 1;
mb_ptr_adv(p2);
}
return p1;
}
p1はp2の次のアドレス。p2はmb_ptr_advで進められていきます。separatorである時+1したものをp1に入れます。p2がNULLなったら最後にseparatorを指していたポインタに1を足したp1を返します。(←)
misc1.c
/*
* Like vim_ispathsep(c), but exclude the colon for MS-Windows.
*/
int
vim_ispathsep_nocolon(int c)
{
return vim_ispathsep(c)
#ifdef BACKSLASH_IN_FILENAME
&& c != ':'
#endif
;
}
ポインタが指している文字がseparatorならTrueを返す。vim_ispathlistsep BACKSLASH_IN_FILENAME が定義されているなら cが:でないも条件に入る。
macros.h
# define mb_ptr_adv(p) p += has_mbyte ? (*mb_ptr2len)(p) : 1
マルチバイトでもptrを進める。
misc1.c
/*
* Return TRUE if "p" points to just after a path separator.
* Takes care of multi-byte characters.
* "b" must point to the start of the file name
*/
int
after_pathsep(char_u *b, char_u *p)
{
return p > b && vim_ispathsep(p[-1])
&& (!has_mbyte || (*mb_head_off)(b, p - 1) == 0);
}
p がseparatorの次にいればtrueを返します。 (←)
いまさら聞けないjavaのpackageとimport
javaを始めるとすぐ出てくるのがpackageとimportです。
まず一番初めにpackageとfileのパスは関係がないということです。
このpackageの階層が関係してくるのはjavacでコンパイルした後のclass fileのパスです。ここがなかなか気づけませんでした。
例えばpackage com.sample の下にclass MyClassを定義したとします。
package com.sample;
class MyClass{
public static void main(String[] args){
System.out.println("hello”);
}
}
これをjavacでコンパイルして出来たMyClass.classを実行するためにはこのMyClass.classがcom/sampleの下にあってcomフォルダがある位置から
java com.sample.MyClass
と実行しなければなりません。
逆に言えば.MyClass.javaファイルはどこにいても構いません。src/MyClass.java でも com/sample/MyClass.javaでもokです。
コンパイルした時にファイルの階層を作るのは面倒なので javac の -d オプションを使います。-d ./class とやれば実行しているカレントディレクトリのclassフォルダの中に自動的にcom/sampleとフォルダを作ってそこにMyClass.classファイルを入れてくれます。
. ├── MyClass.java └── class
こういう状態でjavac -d ./class MyClass.java してみましょう。
.
├── MyClass.java
└── class
└── com
└── sample
└── MyClass.class
com/sampleとフォルダが出来ています。
次にimportです。importはclassファイルのパスを指定して使うことができるようにするためのコマンドです。
そしてこれもclassファイルのパスでありjavaファイルのパスではありません。
例えばcom.sampleの下にlibを作ってその中にAnotherClassを入れてみましょう。
package com.sample.lib;
public class AnotherClass{
public void hello(){
System.out.println("hello another class");
}
}
こんな感じです。
javac MyClass.java AnotherClass.java -d class
コンパイルすると
.
├── AnotherClass.java
├── MyClass.java
└── class
└── com
└── sample
├── MyClass.class
└── lib
└── AnotherClass.class
こうなります。MyClassからAnotherClassをimportしてみましょう。
package com.sample;
import com.sample.lib.AnotherClass;
class MyClass{
public static void main(String[] args){
AnotherClass another = new AnotherClass();
System.out.println("hello");
another.hello();
}
}
javac MyClass.java AnotherClass.java -d class
コンパイルして
cd class java com.sample.MyClass
classフォルダに移動して実行すると
hello hello another class
無事にimportできました。
glibcをデバッグしてみよう2
前回glibcを取ってきてそれをコンパイルしてみました。
そしてそのあと簡単なテストを作ってそのライブラリーをリンクしました。
今回はglibcの中に簡単な関数を作ってそれをgdbでデバッグしてみます。
mallocにhelloworldという関数を作ってみましょう。
glibcに関数を作るにはまずVersionsというファイルにその名前を書きます。
mallocフォルダーの中のVersionsにhelloworldを入れましょう。
malloc/Versions
....
# f*
free;
free2;
# h*
helloworld;
# m*
mallinfo; malloc;
....
次にmalloc.cの中にhelloworldを書いていきます。
malloc/malloc.c
int __libc_helloworld (void)
{
return 1;
}
これだけではダメでhidden_protoとhidden_defに登録します。
malloc/malloc.c
int __libc_helloworld(void); libc_hidden_proto (__libc_helloworld) ..... libc_hidden_def (__libc_helloworld)
そして最後にこの関数にaliasを作ります。
malloc/malloc.c
strong_alias (__libc_helloworld, __helloworld) strong_alias (__helloworld, helloworld)
これでhelloworldがmallocの中に追加されました。 コンパイルしてみましょう。 今回はデバッグのオプションをつけてコンパイルします。
~/download/glibc-2.21/configure --prefix=/usr --enable-debug CFLAGS='-g -O2'
makeしてできたlibc.aにhelloworldが入っているか確かめてみましょう。
nm libc.a | grep helloworld 00000000000048c0 T __helloworld 00000000000048c0 T __libc_helloworld 00000000000048c0 T helloworld
入っています。ではこのhelloworldを呼び出してみましょう。
extern int helloworld (void);
void * __gcc_personality_v0=0;
void * _Unwind_GetIP=0;
void * _Unwind_GetGR=0;
void * _Unwind_GetCFA=0;
void * _Unwind_Backtrace=0;
void * _Unwind_Resume =0;
void * __divdi3=0;
void * __moddi3=0;
int main(){
int res;
res = helloworld();
return 0;
}
前回のtest.cをちょっと変更しました。 helloworldを呼んでいるだけです。このtest.cを今コンパイルしたlibc.aとリンクしてコンパイルしてみましょう。 簡単にするためbuildディレクトリにあるlibc.aをtest.cのあるディレクトリにコピーしておきます。
cc -g -o test test.c -L./ -lc
コンパイルできたらgdbで実行してみましょう。
gdb test
ブレークポイントをhelloworldにおいてrunします。
b helloworld r
helloworldが1を返すのが確認できました。 いよいよglibcデバッグのお膳が整いました。では次回まで
いちばんやさしいCでつくるgem
C言語でシンプルなgemを作ってみましょう。
まずはフォルダーを用意します。
my_c_gemが今回のgemの名前です。
my_c_gem/
└── ext
└── my_c_gem
├── extconf.rb
└── my_c_gem.c
こんな感じです。 extconf.rbにはMakefileを自動生成するためのコードを書きます。
extconf.rb
require "mkmf" create_makefile "my_c_gem/my_c_gem"
my_c_gem.cには最初にrubyから呼ばれる初期化関数を書きます。まずは何もせずに MyCGemクラスを作るだけのコードをいれておきましょう。
my_c_gem.c
#include <ruby.h>
void
Init_my_c_gem(void) {
rb_define_class("MyCGem",rb_cObject);
}
ではまずMakefileを生成してみましょう。
cd ext/my_c_gem ruby extconf.rb
Makefileができるのでコンパイルしてみましょう。makeを実行します。
すると my_c_gem.bundleというファイルが出来上がります。このファイルがルビーに組み込まれるライブラリーファイルです。
my_c_gem/
└── ext
└── my_c_gem
├── Makefile
├── extconf.rb
├── my_c_gem.bundle
├── my_c_gem.c
└── my_c_gem.o
ではこのbundleファイルを組み込んでrubyを実行してみましょう。
bundleファイルのあるフォルダーで
ruby -Ilib:. -r my_c_gem -e "p MyCGem.new”
と実行します。
#<mycgem:0x007f9d7b87b138>
こんな感じに出力されます。
ではここまでをRakefileにして自動化してしまいましょう。
require "rake/extensiontask"
Rake::ExtensionTask.new "my_c_gem" do |ext|
ext.lib_dir = "lib/my_c_gem"
end
これでrake compileでlibフォルダーが出来その中にbundleファイルがコンパイルされるようになります。
my_c_gem/
├── Rakefile
└── ext
└── my_c_gem
├── Makefile
├── extconf.rb
└── my_c_gem.c
一度make cleanしてから rake compileをしてみましょう。
my_c_gem/
├── Rakefile
├── ext
│ └── my_c_gem
│ ├── Makefile
│ ├── extconf.rb
│ └── my_c_gem.c
├── lib
│ └── my_c_gem
│ └── my_c_gem.bundle
└── tmp
└── universal.x86_64-darwin15
├── my_c_gem
│ └── 2.0.0
│ ├── Makefile
│ ├── my_c_gem.bundle
│ └── my_c_gem.o
└── stage
└── lib
└── my_c_gem
└── my_c_gem.bundle
こんな感じでコンパイルが実行されます。
それではこれをbundle installできるようにしてみましょう。 まずはmy_c_gem.gemspecファイルをフォルダーのルートにつくります。
Gem::Specification.new do |spec|
spec.name = "my_c_gem"
spec.version = '1.0.0'
spec.authors = ["yamshing"]
spec.email = ["yamshing@..."]
spec.summary = %q{My first C gem}
spec.description = %q{This does nothing}
spec.homepage = ""
spec.license = "MIT"
spec.files = []
spec.files = %w[
ext/my_c_gem/extconf.rb
ext/my_c_gem/my_c_gem.c
]
spec.require_paths = ["lib"]
spec.extensions = %w[ext/my_c_gem/extconf.rb]
spec.add_development_dependency "bundler", "~> 1.10"
spec.add_development_dependency "rake", "~> 10.0"
spec.add_development_dependency "minitest"
end
ここで大切なのはspec.filesに必要なファイルをリストするのとspec.extensionsにextconf.rbを入れるところです。
さらにRakefileの中にrequire "bundler/gem_tasks”をたしてrake buildコマンドが使えるようにしましょう。
Rakefile
require "bundler/gem_tasks" require "rake/extensiontask" Rake::ExtensionTask.new "my_c_gem" do |ext| ext.lib_dir = "lib/my_c_gem" end
いよいよ実行です。 rake build してみましょう。
問題がなければpkgフォルダーができその中にmy_c_gem-1.0.0.gemができているはずです。
これをインストールしてみましょう。
gem install -l pkg/my_c_gem-1.0.0.gem -V
コンパイルがはじまり1 gem installedがでれば成功です。
実行してみましょう。ただrequire してp するだけです。
ruby -e "require 'my_c_gem/my_c_gem'; p MyCGem.new"
#<MyCGem:0x007f9de99c8720>のような出力がでれば成功です。
なにもしないgemが完成しました。
これは楽しいPEG.jsでパーサーづくり
javascriptで簡単にパーサーがつくれてしますみたいです。その名もPEG.js
ここで実際に使って実行もできてしまいます。
ということでそのサンプルコードをちょっと読んでみました。
/*
* Simple Arithmetics Grammar
* ==========================
*
* Accepts expressions like "2 * (3 + 4)" and computes their value.
*/
Expression
= head:Term tail:(_ ("+" / "-") _ Term)* {
var result = head, i;
for (i = 0; i < tail.length; i++) {
if (tail[i][1] === "+") { result += tail[i][3]; }
if (tail[i][1] === "-") { result -= tail[i][3]; }
}
return result;
}
Term
= head:Factor tail:(_ ("*" / "/") _ Factor)* {
var result = head, i;
for (i = 0; i < tail.length; i++) {
if (tail[i][1] === "*") { result *= tail[i][3]; }
if (tail[i][1] === "/") { result /= tail[i][3]; }
}
return result;
}
Factor
= "(" _ expr:Expression _ ")" { return expr; }
/ Integer
Integer "integer"
= [0-9]+ { return parseInt(text(), 10); }
_ "whitespace"
= [ \t\n\r]*
簡単な四則演算のパーサーのようです。
基本は
型の名前 = マッチさせるパターン
です。
一番下から見てみましょう。
_ "whitespace" = [ \t\n\r]*
“_”をスペース文字にマッチさせているのがこの部分です。
=の後はregular expressionが来ます。
これで _ と書けば "スペース \t \n \r が0個以上"にマッチします。
Integer "integer"
= [0-9]+ { return parseInt(text(), 10); }
次は数字とプラス記号をIntegerと定義します。
ここではパターンの後に{…}で実行されるjavascriptを書いています。
その際マッチした文字をtext()で取得しています。
このようにマッチしたらjavascriptを実行できるのは便利ですね。
Factor
= "(" _ expr:Expression _ ")" { return expr; }
/ Integer
次はFactorとして数字のInteger又はカッコに囲まれたExpression(この上で定義されている)にマッチします。
ここではマッチしたExpressionをexprと名付けて{}内のjavascriptでその名前を使っています。
これでカッコで囲まれたExpressionはカッコを取り除かれてかえってきます。
Expression
= head:Term tail:(_ ("+" / "-") _ Term)* {
var result = head, i;
for (i = 0; i < tail.length; i++) {
if (tail[i][1] === "+") { result += tail[i][3]; }
if (tail[i][1] === "-") { result -= tail[i][3]; }
}
return result;
}
Term
= head:Factor tail:(_ ("*" / "/") _ Factor)* {
var result = head, i;
for (i = 0; i < tail.length; i++) {
if (tail[i][1] === "*") { result *= tail[i][3]; }
if (tail[i][1] === "/") { result /= tail[i][3]; }
}
return result;
}
次はExpressionとTermです。
ここではhead: tail:と書いて最初に…最後に…というパターンを作っています。
まずはTermを見てみましょう。
head:Factor tail:(_ ("*" / "/") _ Factor)*
というパターンです。
最初にFactorがあり最後に "スペース 掛けるか割る記号 スペース Factor が0個以上"ある時にマッチします。
そしてマッチした結果はtailに配列として格納されるので後の{}内でそれにあったjavascriptを実行します。
headには最初に来た数字かカッコ内の計算結果が入っているので
if (tail[i][1] === "*") { result *= tail[i][3]; }
このコードでもしtail配列の1番目が掛ける記号ならtail配列の3番目をheadに掛けることになります。
if (tail[i][1] === "/") { result /= tail[i][3]; }
これは同じく割算をします。
最後にExpressionはこの下で定義された全て(数字、カッコ内の計算結果、掛け算)をとって
それを足し算か引き算しその結果を返します。
これで簡単な計算機のパーサーができあがりました。
freebsd rb.h remove を読んでみよう 11
最後のパターンになります。
どうすればいいでしょうか。
黒を増やすためには方法は一つしかありません。
それは赤を黒に変えることです。(*1)
もちろんこれでは左の黒が増えてしまうので
回転させて右にそれを持っていかなくてはなりません。(*2)
これで右の削除されたノードの黒の数は均衡したのですが
その左下のノードの黒の数が増えてしまいます。
しかしこれは簡単に解決できそうです。
多すぎる黒を赤にすればよいでしょう。(*3)
赤に変えてみます 黒の数をチェックしてみましょう。
あっているようですね。
コードを見てみましょう。
/* || */\
/* || */\
/* pathp(b) */\
/* / \\ */\
/* (r) (b) */\
/* \ */\
/* (b) */\
/* / */\
/* (b) */\
assert(leftright != &rbtree->rbt_nil); \
rbtn_red_set(a_type, a_field, leftright); \
//左の子の右の子を赤に変える。(*3)
rbtn_rotate_right(a_type, a_field, pathp->node,tnode);\
//右に回転させる(*2)
rbtn_black_set(a_type, a_field, tnode); \
//回転した後の親ノードを黒にする。(*1)
順番は違いますが同じことをしていますね。
これで赤黒木の削除は終わりです。
