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_##name(mrb, h, h->n_buckets*2); \
}
こんな風に使われていますよ。
なるほど何かのoccupiedの数がbucketの数の上限を超えたらリサイズする
と読めてきました。
ではこのUPPER_BOUNDは何をしているのでしょうか。
xという数字を
x>>2 ( 割る4)したものと x>>1(割る２)したものを OR しています。
ぱっと見ると足しているようにも見えますがいろいろ数字を入れてみると
そうでもなさそうです。
試してみましょう
48を入れて見ましょうか。
48(0b110000)です。
(48 >> 2) は 0b1100 (48 >> 1)は0b11000です。
この２つをorしてみましょう。
0b01100
OR
0b11000
= 0b11100 (28)ですね。
48を割る４したものと割る２したものとを足すと(つまり3/4すると)36なのでこの結果とは
違っていますね。
36(0b100100)ならばどうでしょう
36>>2 = 9(0b1001)
36>>1 = 18(0b10010)
orすると
0b01001
OR
0b10010
=0b11011で27になります。
これは36の3/4ですね。
この２つの違いはなんでしょうか。
それは下の36の時は36>>2と36>>1の足し算に繰り上げが無いということでしょう。
0b01001 と 0b10010の間には”両方１”の部分がありません。
一方
0b01100 と 0b11000の間には右から4番目が1と1になり、ORするとき繰り上がらなければ
いけないところが消えています。つまり0b1000が一つ無くなっているということです。
こう考えるとUPPER_BOUND(48)が28になるのもうなずけますね。
48 * 3/4 = 36 = 28 + 8 (0b1000)
この8がORの際に無くなっていたのですね。
となるとUPPER_BOUNDはうまく行けば(x>>2とx>>1が0と1が互い違いに来るとき)
xの3/4を返し。それ以外ではxの3/4より小さい値を返す関数と言えます。
xの3/4より小さいとはどこまで小さくなるのでしょうか。
最悪のケースつまり x>>2 と x>>1 のORが最大限1 と 1になってしまうケースが最小と言えるでしょう。
255(0b11111111)がその一つでしょうか。
255>>2 = 0b0111111
255>>1 = 0b1111111
この２つをORすると0b0111111がまるまる消えてしまいます。つまりUPPER_BOUNDは
255 * (3/4) - 255 * (1/2) = 255 * (1/2)を返します。
これでUPPER_BOUNDの全貌が見えましたね。
UPPER_BOUNDは与えられた数の1/2から3/4の数を返すようです。
