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_…

gtags で ruby のコードを解析できるように pygments を使おう。

gtagsでrubyのコードが解析できれば良いなと思い調べてみました。 pygmentsが良いらしいです。 ではexuberant-ctagsとpygmentsをインストールします。 次にubuntuのglobalは古いようなのでまずはaptitude purge globalをダウンロードしてconfigure make inst…

mruby parse.y scan_hexを読んでみよう

static int32_tscan_hex(const int *start, int len, int *retlen) scan_hex名前の通り十六進数の数字を渡したらintを返してくるのでしょう。 まずローカル変数を準備します。 static const char hexdigit[] = "0123456789abcdef0123456789ABCDEF"; const in…

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行) ですよね。 この中でまず目につ…

赤黒木をやってみよう 2

ちょっと複雑な挿入 前回挿入をしたのはいつも大きい数字だったので比較的 単純にいきました。今度は少し複雑な挿入をやってみよう。 ルール 赤の子に赤が来ることはできない。 赤の子に赤が来るパターンとはどのようなものでしょうか? 赤の右の子が赤 赤の…

赤黒木をやってみよう

赤黒木のルールは ルートは常に黒 新ノードは赤で右に追加 右下の子だけが赤の時左回り 両方の子が赤の時上下の色を変える まずはルートに2を挿入 右下が赤なので左回り。 ルートは黒に 次のノードを挿入 両方の子が赤なので色を交換 ルートは黒に ノードを…

MRubyのincremental_sweep_phaseを読んでみた。

struct heap_page *page = mrb->sweeps; でpageをスタート。 while (page && (tried_sweep < limit)) でnextのpageへループその中で RVALUE *p = page->objects;RVALUE *e = p + MRB_HEAP_PAGE_SIZE このpとeの間でまたループ。 while (p<e) if (is_minor_gc(mrb) && page->old) { /* skip a sl</e)>…

はろーわーるど

プログラミングについてのブログです。 class Voila { public: // Voila static const string VOILA = "Voila"; // will not interfere with embedded tags. }