|
|
|
|
|
|
|
HMDT - Special Issue / CoreFoundation の秘密 / Collection Services - CFArray のオブジェクトの操作
|
- Collection Services -
|
|
CoreFoundation/Collections.subproj/CFArray.c
|
CF_INLINE CFIndex __CFArrayGetCount(CFArrayRef array) {
return ((struct __CFArrayImmutable *)array)->_count;
}
|
__CFArrayImmutable 型にキャストしてやって、_count の値を返しているんだ。こういう構造だから、とうぜん、要素を追加したら削除した場合は、_count の値を変えなくてはいけない。そのときに呼び出されるのは __CFArraySetCount() ね。
|
CoreFoundation/Collections.subproj/CFArray.c
|
CF_INLINE void __CFArraySetCount(
CFArrayRef array,
CFIndex v)
{
((struct __CFArrayImmutable *)array)->_count = v;
}
|
次はインデックスを指定して、要素を取り出す場合。CFArrayGetValueAtIndex() という API が用意されている。
|
CoreFoundation/Collections.subproj/CFArray.c
|
CF_EXPORT
const void *CFArrayGetValueAtIndex(
CFArrayRef theArray,
CFIndex idx);
|
先に見た通り、CFArray および CFMutableArray では、メモリの固まりにオブジェクトが配置されているんだ。かつ、こいつらはインデックス順に並んでいて、隙間もない。だからポインタ演算することで、簡単にアクセスできるんだ。
CFArrayGetValueAtIndex() は、指定した要素を取り出すために、__CFArrayGetBucketAtIndex() を呼び出す。こいつの実装はこんな感じだ。
|
CoreFoundation/Collections.subproj/CFArray.c
|
CF_INLINE struct __CFArrayBucket *__CFArrayGetBucketAtIndex(
CFArrayRef array,
CFIndex idx)
{
switch (__CFArrayGetType(array)) {
case __kCFArrayImmutable:
case __kCFArrayFixedMutable:
case __kCFArrayMutableDeque:
return __CFArrayGetBucketsPtr(array) + idx;
...
}
return NULL;
}
|
オブジェクトの先頭アドレスを取り出して、インデックスを足すだけ。簡単でしょ。
オブジェクトがインデックス順に隙間なく並んでいるということは、動的なオブジェクトの追加、削除に、非常に手間がかかる、ということだ。追加、削除には、次のような API がある。
|
CoreFoundation/Collections.subproj/CFArray.c
|
CF_EXPORT
void CFArrayAppendValue(
CFMutableArrayRef theArray,
const void *value);
CF_EXPORT
void CFArrayInsertValueAtIndex(
CFMutableArrayRef theArray,
CFIndex idx,
const void *value);
CF_EXPORT
void CFArraySetValueAtIndex(
CFMutableArrayRef theArray,
CFIndex idx,
const void *value);
CF_EXPORT
void CFArrayRemoveValueAtIndex(
CFMutableArrayRef theArray,
CFIndex idx);
CF_EXPORT
void CFArrayRemoveAllValues(
CFMutableArrayRef theArray);
CF_EXPORT
void CFArrayReplaceValues(
CFMutableArrayRef theArray,
CFRange range,
const void **newValues,
CFIndex newCount);
|
で、こいつらは結局のところ、CFArrayReplaceValues() を呼び出すことになる。オブジェクトを置き換えるための API だ。この API は、置き換える範囲と、置き換えるオブジェクトを指定する。だから、Appned するなら置き換える範囲を配列の一番後ろにするし、Insert するなら置き換える範囲の長さを 0 にしてやればいい。
そんな CFArrayReplaceValues() を実装するために、置き換えられる配列を次のように 3 つに分けて考えてみよう。
B が置き換えられる範囲で、A と C はその前後。置き換えの手順はこうなる。
というわけだ。これを念頭において、実装を見てみよう。
|
CoreFoundation/Collections.subproj/CFArray.c
|
void CFArrayReplaceValues(
CFMutableArrayRef array,
CFRange range,
const void **newValues,
CFIndex newCount)
{
...
if (__kCFArrayFixedMutable == __CFArrayGetType(array)) {
struct __CFArrayBucket *buckets = __CFArrayGetBucketsPtr(array);
// CF: we should treat a fixed mutable array like a deque too
/* B の領域を解放 */
if (0 < range.length) {
__CFArrayReleaseValues(array, range, false);
}
/* C の領域をシフト */
if (newCount != range.length &&
range.location + range.length < cnt)
{
/* This neatly moves region C in the proper direction */
memmove(
buckets + range.location + newCount,
buckets + range.location + range.length,
(cnt - range.location - range.length) *
sizeof(struct __CFArrayBucket));
}
/* B の領域に置き換え */
if (0 < newCount) {
memmove(
buckets + range.location,
newv,
newCount * sizeof(void *));
}
__CFArraySetCount(array, futureCnt);
if (newv != buffer && newv != newValues)
CFAllocatorDeallocate(allocator, newv);
return;
}
...
}
|
コアとなる部分は、上の通りだ。オブジェクトの移動には memmove を使っているね。
というわけで、CFArray と CFMutableArray の実装では、インデックスベースのアクセスは早いけど、挿入や削除は遅い。そこんとこ頭に入れておいて使おう。
(Jan. 27, 2003)
|
Home | Link | Download | Back Number | Speciall Issue
|
