retainしないCFDictionary

先日SYさんからアイデアをいただいたのでその実装を開始した。ぼちぼち実装しながら、いくつか面白い問題が発生してそれについて考察したのでまとめておく。

2  retainしないCFDictionary

2.1  コールバック関数

コールバック関数にNULLを設定することでretain/releaseしない（retain countを増やさない）CFDictionaryができることは確認した。つまり

static NSMutableDictionary  *dictionaryWithHashedKeyCreate()
{
    CFDictionaryValueCallBacks  valueCallBacks = kCFTypeDictionaryValueCallBacks;
    CFDictionaryKeyCallBacks    keyCallBacks = kCFTypeDictionaryKeyCallBacks;
    keyCallBacks.retain = NULL;
    keyCallBacks.release = NULL;
    keyCallBacks.equal = NULL;
    keyCallBacks.hash = NULL;
    keyCallBacks.copyDescription = NULL;
    return (NSMutableDictionary *)CFDictionaryCreateMutable(
                              kCFAllocatorDefault, 0,
                              &keyCallBacks, &valueCallBacks);
}

というような関数でNSMutableDictionaryのオブジェクト（CFMutableDictionaryRefとToll-freeなのでキャストしている）を作ることができる。

ところでhashコールバック関数をNULLに設定するとhashはアドレスの値を使う、と書いてある。copyDescriptionコールバック関数はNULLにしなくてもデフォルトと同じ動作になる。ところでこの辺の話は 「Collections Programming Topics for Core Foundation」にあった。ちゃんと読んでいない、ということがバレてしまった。

2.2  key-valueペアの設定

これに普通のオブジェクトをセットしてみる。

    NSMutableDictionary *dic = dictionaryWithHashedKeyCreate();
    [dic setObject:[NSNumber numberWithInt:0] forKey:@"key"];

これは問題なく実行できる。ところが

    NSMutableDictionary *dic = dictionaryWithHashedKeyCreate();
   [dic setObject:[NSNumber numberWithInt:0] forKey:(id)0x01];

これはクラッシュする。このかわりにCFの同じ機能の関数

    NSMutableDictionary *dic = dictionaryWithHashedKeyCreate();
    CFDictionaryAddValue((CFMutableDictionaryRef)dic,
                         (id)0x01, [NSNumber numberWithInt:0]);

とするとこれは問題ない。どうもsetObject:forKey:メッソドは単にCore Foundationと同等の関数を呼んでいるわけではないらしい。

今回はhash値をポインタとして設定している。当然ポインタとしての実体は存在しない。したがってポインタの実体をアクセスするようなコードはクラッシュする。

Cocoaではisaポインタが存在しているという前提でメソッドが書かれている可能性が高く、retain/releaseしないとしてもなんらかの付加的な操作をしている可能性がある。例えばCocoaのメソッド内に、渡されたオブジェクトがCocoaのものか、Core Foundationのものかを判断するようなコードが含まれている場合（これは十分あり得る）にはisaをアクセスしにいったときにクラッシュすることになる。

こうなるとCocoaのメソッドは一通り疑う必要がある。とりあえず必要なメソッドを確認してみる。

2.3  keyEnumeratorメソッド

使う可能性の高いメソッドとしてkeyを順番に取り出すkeyEnumeratorメソッドを確認してみる。

動作確認用として

#define NUM 3

    int n;
    NSMutableDictionary *dic = dictionaryWithHashedKeyCreate();
    id  val[NUM];
    id  key[NUM];
    for (n = 0 ; n < NUM ; n ++) {
        key[n] = (id)((NSUInteger)(n * 10 + 1));
        val[n] = [[NSNumber alloc] initWithInt:n];
    }
    for (n = 0 ; n < NUM ; n ++)
        CFDictionaryAddValue((CFMutableDictionaryRef)dic, key[n], val[n]);

とした。つまりretain/releaseしないNSMutableDictionaryのオブジェクトを作ってそこにkeyとして適当な（オブジェクトではない）数、valueとしてCocoaのオブジェクトをセットする。これは問題なく設定される。

そして、keyの列挙子（NSEnumerator）を作って、keyを順に取り出すコードを書いてみる。

    id  en = [dic keyEnumerator];
    id  k;
    while (k = [en nextObject])
        NSLog(@"%d\t%@", k, [dic objectForKey:k]);

これを実行させると

2010-11-01 21:35:24.306 CFDictionaryTest[95504:a0f] 21	2
2010-11-01 21:35:25.491 CFDictionaryTest[95504:a0f] 1  0
2010-11-01 21:35:26.713 CFDictionaryTest[95504:a0f] 11	1

となって問題が発生しなかった。whileループでちゃんとvalueのほうも取り出すことができている。

列挙子が使えると便利である。

2.4  countメソッド

countメソッドは基本的なメソッドである。さっきのdicに

    NSLog(@"%d", [dic count]);

とすると問題なく動作した。

2.5  allValuesメソッド

allkeysメソッドはNSArrayのなかに要素が入るので動作しない。しかしvalueは普通のCocoaのオブジェクトを保持するので動作する可能性がある。例えば

countメソッドと同じように

    id  allvals = [dic allValues];
    NSLog(@"%@", allvals);

とすると、ちゃんと中身ができていた。これも問題ない。

2.6  addEntriesFromDictionaryメソッド

ふたつの辞書をマージするメソッドaddEntriesFromDictionaryの動作を見てみる。

ふたつの辞書を

    NSMutableDictionary *dic = dictionaryWithHashedKeyCreate();
    NSMutableDictionary *dic2 = dictionaryWithHashedKeyCreate();

のように作ってそれぞれにkeyとvalueを設定し

    [dic addEntriesFromDictionary:dic2];

とすると、これはクラッシュした。一方から取り出してもう一方に設定する、という作業をやる必要がある。

2.7  ここまでのまとめとして

これを考えると、やはりCocoaのメソッドを使うのは厳しそうである。今回のような特殊な使い方もCore Foundationにとっては想定の範囲内で、Core Foundationの関数だけ呼ぶのであれば問題が発生しないということは保証される。

しかしCocoaのレベルではそうではない。どのような実装がなされているかもわからないので、安全のためにはCocoaのメソッドではなく、Core Foundationを呼ぶか、カテゴリを作って別のメソッドを定義して中身はCoure Foundationを呼ぶようなWrapperを作るかしたほうが良さそうである。ちょっと残念。

keyに対する列挙子もとりあえず今回は動作したが、疑いの目で見ていた方が安全かもしれない。とりあえずvalueのほうの列挙子は問題はないだろう、おそらく。

3  CFDictionaryにNULLが入ってしまう

このあいだコメントいただいたhash関数の定義

NS_INLINE   id  hashValueFromPoint(AIPoint pos)
{
#ifdef __LP64__
    return (id)(AlternateFilledBitsMake((uint32_t)pos.x) |
                 (AlternateFilledBitsMake((uint32_t)(pos.y)) << 1));
#else
    return (id)(AlternateFilledBitsMake((uint16_t)pos.x) |
                (AlternateFilledBitsMake((uint16_t)(pos.y)) << 1));
#endif    
}

をそのまま使おうとした。そうすると原点(0,0)ではこの関数は0を返す。これをこのままCFDictionaryのkeyに使おうとすると原点には0、つまりNULLが設定されることになる。すべてのコールバックをNULLにしてあればチェックは行われないので設定の時点では問題なくできてしまう。

ところが、NULLのポインタはいろいろなところで特別な意味に使われている。こういうのはデバグはそれほど難しくはないけど、必要な機能が使えない、ということが起こりやすい。真っ先に考えられるのは列挙子を使ったwhileループである。nil（=NULL）が終わりを表すことになっているので途中で終わってしまう可能性がある。

ということで今回のようなhash値をポインタと同一視する（ポインタに実体のない）ような特殊な場合、どんな場合にでも0（NULL）にはならないhash関数を考えないといけない。まず、xとyをすべての整数で使えるようにしたら、0を避けるperfect hashは不可能であることとは簡単にわかる（足りなくなる）。

原点の場合だけ、普通ならまずあり得ないような値（例えば32ビット整数を使っていたとすると2³¹−1にするとか）と差し替える、という手がある。しかしこれは厳密な意味でperfect hashにならない。原点からグライダーを飛ばすと2147483647世代めに問題が起こる。しかしこれは1世代1msecとしても、1ヶ月近く追跡しないと発生しない。現実的には起こりえない、といってもいい。

こういうやり方は今回の場合には問題はほとんど起こらないが、もっとクリティカルなアプリではやめた方がいい。「こういう場合がある」ということを覚えていればいいけど、それを忘れてしまってこれで問題が発生するとデバグは非常に困難なものになる。プログラマとしての基本的な躾として、こういうことはやるべきではない。

とするとどうするか、というと例えば、座標値として偶数だけを使うことにして

NS_INLINE   id  hashValueFromPoint(AIPoint pos)
{
#ifdef __LP64__
    return (id)(AlternateFilledBitsMake((uint32_t)pos.x) |
                 (AlternateFilledBitsMake((uint32_t)(pos.y)) << 1) | 1);
#else
    return (id)(AlternateFilledBitsMake((uint16_t)pos.x) |
                (AlternateFilledBitsMake((uint16_t)(pos.y)) << 1) | 1);
#endif    
}

とするのである。座標値の最下位ビットは常に0なのでそのビットはいつも立てておく。原点でもhash値は1となる。この場合奇数を使った方がhash関数は簡単になる（1を立てる必要はない）けど座標の計算にオーバーヘッドが増える。逆にもっと簡単にただ最上位ビットを立てるだけでもいい。しかしその場合全平面がトーラス（東端と西端、南端と北端が一致する）でなくなる。これは数学的には美しくない。

座標値を偶数に制限した場合、座標値は

−230 ≤ x, y ≤ 230 −1

(1)

と同じになって面積は1/4になる。しかし0のhash値がないことを保証することができる。これがプログラミングの作法としては正しいだろう。

ああ、またいっぱい書いてしまった。でも、面白いと集中できて時間を忘れてしまう。とは言うものの、明日に影響があるのは間違いない。歳は争えない。

コメント 3

この手のCocoaレイヤの範囲外を扱うものは、NSに入れてしまうと落とし穴がそこら中にできてしまうので、CFのまま扱うほうが無難だと思いますが…
NULLについて、おっしゃる通りNSEnumeratorでは正しく扱えません。が、抜け道があります。NSFastEnumerationは長さ情報を含んでいるため、inディレクティブでループさせると正しく扱えます。
ちょっと調べてみると、NSEnumerator に NSFastEnumeration を掛けると長さ情報が欠落しているので失敗。直接コレクションオブジェクトを掛けると成功します。逆順を作れないのが歯がゆいところです。
by SY (2010-11-02 14:43) 

追記：
[dic setObject:[NSNumber numberWithInt:0] forKey:(id)0x01];
上のコードがクラッシュを招く理由は、NSDictionaryがキーに対してNSCopyingプロトコル準拠の確認をやっているからだと思われます。この確認のときに isa にアクセスするため。

by SY (2010-11-02 15:12) 

コメントありがとうございます。
CFのまま扱うのが無難であるのはその通りですね。でもObjective-Cのスタイルは簡単なのでやはりそれで通したくなってしまいます。昔ゴリゴリとCで書いていたことを思い出すと、どうもCocoa/Objective-Cにスポイルされてしまっている気もします。
おかげさまでちょうど気持ちも乗ってきているので、今から実装に突入しようと思います。
明日が休みだからと気を許して、徹夜にならないように気をつけないと．．．
by decafish (2010-11-02 22:14)