6月13日、alurm氏が「A generic dynamic array in C that stores no capacity and needs no struct · GitHub」と題した記事を公開した。この記事では、構造体を使わずに容量情報も保存しない、独特なC言語の汎用動的配列実装について詳しく紹介されている。

長さをポインタに格納する斬新なアイデア

この実装の最も驚くべき点は、ポインタ型の変数に整数値（uintptr_t）をキャストして長さ情報を格納していることだ。通常のC言語による動的配列実装では、データポインタ、長さ、容量を格納する構造体を定義するのが一般的だが、この手法は全く異なるアプローチを取っている。

vec_[0] = (typeof(vec_[0]))(len + 1);  // 長さをポインタとして格納
auto len = (uintptr_t)vec_[0];         // ポインタから長さを取得

この手法は実装定義の動作に依存しており、ポインタから読み出したuintptr_t値が格納時と同じ値になることを前提としている。技術的には危険な領域だが、多くの実用的なシステムで動作する。

2つのポインタだけで実現する動的配列

C言語で動的配列を実装する際の一般的な課題は、データとメタデータ（長さ、容量）を管理する構造体の設計だ。しかし、この実装では構造体を一切使わずに2つのポインタ配列だけで動的配列を実現している：

• 1番目のポインタ：動的配列の長さを格納（実際は整数値をキャスト）
• 2番目のポインタ：実際のデータを指す

例えば、int *vec[2] = { 0 };は空の整数動的配列、struct person *people[2] = { 0 };は空の人物構造体動的配列となる。配列の長さは(uintptr_t)vec[0]、データはvec[1]でアクセスする。

容量を保存しないメモリ効率戦略

従来のstd::vectorのような実装では、データ、長さ、容量の3つの情報が必要だが、この実装では容量情報を一切保存しない。代わりに、配列の長さが0または2の累乗の場合にのみreallocを呼び出し、次の2の累乗まで容量を拡張する巧妙な戦略を採用している。

具体的には、長さが1、2、4、8、16...に達したタイミングで、それぞれ2、4、8、16、32...の容量に拡張される。この戦略により、メモリ使用量を最小限に抑えながら効率的な拡張を実現している。

// 長さが0または2の累乗かチェック
if ((len & (len - 1)) == 0) {
    auto capacity = len ? len * 2 : 1;
    // reallocで次の2の累乗まで拡張
}

実装の核心：vec_pushマクロ

動的配列への要素追加は、以下のvec_pushマクロで行う：

#define vec_push(vec_expr, value_expr) ({ \
    auto vec_ = (vec_expr); \
    typeof(**vec_) value_ = (value_expr); \
    auto ok = true; \
    auto len = (uintptr_t)vec_[0]; \
    if ((len & (len - 1)) == 0) { \
        auto capacity = len ? len * 2 : 1; \
        if (capacity > SIZE_MAX / sizeof(**vec_) || capacity <= len) ok = false; \
        else { \
            auto allocation = realloc(vec_[1], sizeof(**vec_) * capacity); \
            if (allocation == nullptr) ok = false; \
            else vec_[1] = allocation; \
        } \
    } \
    if (ok) { \
        vec_[1][len] = value_; \
        vec_[0] = (typeof(vec_[0]))(len + 1); \
    } \
    ok; \
})

このマクロは成功時にtrueを返し、オーバーフローチェックとメモリ割り当て失敗の処理も含んでいる。C23の機能とGNU Cのstatement expression拡張を活用している。

使用例と制約事項

実際の使用例は以下の通りだ：

int *ints[2] = { 0 };
for (uintptr_t i = 0; i < 5; i++) {
    if (!vec_push(ints, i + 42)) return 1;
}
// 42, 43, 44, 45, 46が格納される

ただし、この実装には要素数の事前確保が困難という制約がある。長さが2の累乗に達すると必ず次の2の累乗まで再割り当てされるため、手動での大きな容量確保は効果的に機能しない。

この実装は、構造体名を考える必要がなく、メモリ効率に優れた興味深いアプローチだが、ポータビリティの観点では慎重な検討が必要だろう。

詳細はA generic dynamic array in C that stores no capacity and needs no struct · GitHubを参照していただきたい。