code reading

今日の関数 searchit その5 (https://github.com/vim/vim)

/* With the SEARCH_END option move to the last character * of the match. Don't do it for an empty match, end * should be same as start then. */ if ((options & SEARCH_END) && !(options & SEARCH_NOOF) && !(matchpos.lnum == endpos.lnum && mat…

今日の関数 searchit その4 (https://github.com/vim/vim)

if (dir == BACKWARD) { /* * Now, if there are multiple matches on this line, * we have to get the last one. Or the last one before * the cursor, if we're on that line. * When putting the new cursor at the end, compare * relative to the end…

今日の関数 searchit その3 (https://github.com/vim/vim)

while (matchpos.lnum == 0 && ((options & SEARCH_END) && first_match ? (nmatched == 1 && (int)endpos.col - 1 < (int)start_pos.col + extra_col) : ((int)matchpos.col - (ptr[matchpos.col] == NUL) < (int)start_pos.col + extra_col))) { search.c …

今日の関数 searchit その2 (https://github.com/vim/vim)

search.c nmatched = vim_regexec_multi(&regmatch, win, buf, lnum, col, #ifdef FEAT_RELTIME tm #else NULL #endif ); /* Abort searching on an error (e.g., out of stack). */ if (called_emsg) break; if (nmatched > 0) { /* match may actually be …

今日の関数 searchit その1 (https://github.com/vim/vim)

search.c int searchit( win_T *win, /* window to search in; can be NULL for a buffer without a window! */ buf_T *buf, pos_T *pos, int dir, char_u *pat, long count, int options, int pat_use, /* which pattern to use when "pat" is empty */ lin…

今日の関数 do_search その2 (https://github.com/vim/vim)

search.c for (;;) { 複数の検索をループで処理していきます。 vimは;で複数の検索をすることができます。例えば/pat1/;/pat2とすればまずpat1を検索しそのカーソルの 位置からpat2を検索することができます。知ってました?私は知りませんでした。 searchst…

今日の関数 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, i…

今日の関数 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を呼ぶ関数…

glibcをデバッグしてみよう2

前回glibcを取ってきてそれをコンパイルしてみました。 そしてそのあと簡単なテストを作ってそのライブラリーをリンクしました。 今回はglibcの中に簡単な関数を作ってそれをgdbでデバッグしてみます。 mallocにhelloworldという関数を作ってみましょう。 gl…

これは楽しいPEG.jsでパーサーづくり

javascriptで簡単にパーサーがつくれてしますみたいです。その名もPEG.js http://pegjs.org/online ここで実際に使って実行もできてしまいます。 ということでそのサンプルコードをちょっと読んでみました。 /* * Simple Arithmetics Grammar * ============…

freebsd rb.h remove を読んでみよう 11

最後のパターンになります。 どうすればいいでしょうか。 黒を増やすためには方法は一つしかありません。 それは赤を黒に変えることです。(*1) もちろんこれでは左の黒が増えてしまうので回転させて右にそれを持っていかなくてはなりません。(*2) これで右の…

freebsd rb.h remove を読んでみよう 10

親が黒でその子が赤の場合を見てみましょう。これが最後のパターンになります。 このパターンは更にひ孫に赤があるかどうかで場合分けできます。 9番のひ孫に赤があるパターンから見ていきましょう。 まず最初に気になることは子が赤でひ孫が赤のパターンは…

freebsd rb.h remove を読んでみよう 9

親が黒でその孫が赤の場合を見てみましょう。 6番から見てみましょう。 右に一つ黒が足りないので右に回転させたらどうでしょう。 すると今度は左に一つ黒が足りなくなるので一つ黒を増やさなくてはなりません。 それは赤があるのでそれを黒にすることででき…

freebsd rb.h remove を読んでみよう 8

親が黒の場合を見てみましょう。 6パターンあります。 この中でまず赤がないものを見てみましょう。 if (pathp->cmp < 0) { \ \ if (rbtn_red_get(a_type, a_field, pathp->node)) { \ \ if (rbtn_red_get(a_type, a_field, rightleft)) { \ /* In the follo…

freebsd rb.h remove を読んでみよう 7

複雑な黒ノードの削除を見ていきましょう。 まずは削除されるノードにnilを入れます。 pathp->node = &rbtree->rbt_nil; 親が赤の場合から見ていきましょう。 freebsdの実装では左が削除された場合と右が削除された場合にまず場合分けしています。 if (pathp…

freebsd rb.h remove を読んでみよう 6

今回は if (pathp->node != node) { この条件のelseの部分です。 ここがelseとなるにはこの前の部分で if (cmp < 0) { \ pathp[1].node = rbtn_left_get(a_type, a_field, pathp->node); \ } else { \ pathp[1].node = rbtn_right_get(a_type, a_field, path…

freebsd rb.h remove を読んでみよう5

今回はrb.hのremoveを読んでいきましょう a_attr void \ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ struct { \ a_type *node; \ int cmp; \ } *pathp, *nodep, path[sizeof(void *) << 4]; \ /* Wind. */ \ nodep = NULL; /* Silence compile…

freebsd rb.h insert を読んでみよう4

削除を見ていきましょう。赤ノードの削除は何も変わらないので無視できます。削除されるのが黒ノードの場合削除された黒ノードを補うために赤ノードを黒に変えていきます。そうなのでその変える赤の位置で場合分けしていきます。では見てみましょう。 親が赤…

freebsd rb.h insert を読んでみよう3

rb.hのinsertをrubyで書いてみました。 https://github.com/yamshing/code_reading/blob/master/rb.rb ●が赤で○が黒です。遊んで見てください。

freebsd rb.h insert を読んでみよう2

前回は左に赤が二つつながる場合を見ました。 http://yamshing.hatenablog.com/entry/2015/09/30/205603 今回は右に赤が来る場合です。 では読んでみましょう。 a_type *right = pathp[1].node; //次のノードを rbtn_right_set(a_type, a_field, cnode, righ…

freebsd rb.h insert を読んでみよう

前に赤黒木に挿入するときは赤が2つ来るのを防ぐように調節すると書きました。 それがfreebsdのmallocではどのように実装されているのかを見てみましょう。 freebsdは9.3です。rb.hは/usr/src/lib/libc/stdlib内にありますね。 a_attr void \ a_prefix##ins…

mruby khash.h の UPPER_BOUNDとは何でしょうか?

#defineUPPER_BOUND(x) ( (x) >> 2 | (x) >> 1) とあります。さらに下の方で #define khash_upper_bound(h) (UPPER_BOUND( (h)->n_buckets) 何かのbucketの数 ( n_)の上限ということでしょうか。 if (h->n_occupied >= khash_upper_bound(h)) { \ kh_resize_…

mruby gc.c のis_deadとは何でしょうか

#define is_dead(s, o) (((o)->color & other_white_part(s) & MRB_GC_WHITES) || (o)->tt == MRB_TT_FREE) object.hで定義されています。 まずはother_white_partが何かを見てみましょう。 #define other_white_part(s) ((s)->current_white_part ^ MRB_GC_…

glibcをデバッグしてみよう

gnuのmallocも読んでみましょう。 まずはダウンロード http://ftp.gnu.org/gnu/glibc/ 最新を取ってきましょう。 そうしたらコンパイル とここでちょっと手間取ります。 glibcを展開したフォルダーに入って./configureとやると configure: error: you must c…

malloc読んでみた4 chunkとrun

chunkはarenaのrunが作られるときにmmapで取り出されるメモリーの領域です。arena_run_allocを見てみましょう。arenaのrun_avail内にすでにメモリーが取られている場合はそのメモリーをrunとして返します。 mapelm = arena_avail_tree_nsearch(&arena->runs_…

malloc読んでみた3 mallocの中のデータ型

mallocで使われるデータ型はまずarenaがあります。arenaはarena_bin_tの配列を持っています。 struct arena_s { ... arena_bin_t bins[1]; /* Dynamically sized. */ }; arena_binはarena_runの赤黒木を持っています。 struct arena_bin_s { arena_run_t *ru…

malloc読んでみた2 getpagesizes

では /usr/src/lib/libc/gen/getpagesizes.cを見てみましょう。 intgetpagesizes(size_t pagesize[], int nelem){ static u_long ps[MAXPAGESIZES]; static int nops; size_t size; int i; if (nelem < 0 || (nelem > 0 && pagesize == NULL)) { errno = EIN…

malloc読んでみた1 initからpagesizeまで

freebsdのmalloc.cを読んで見ましょう。 場所は /usr/src/lib/libc/stdlibの中にあります。 ヘッダーはusr/src/sys/sys/malloc.hですね。 では見てみましょう! スタート地点はもちろん void * malloc(size_t size) (5281行) ですよね。 この中でまず目につ…