Libx SDS ドキュメント

    SDSの内部構造と高度な使い方

    この文書の冒頭で、SDS文字列の確保方法を説明しましたが、利用者へ返すポインターの直前に格納する接頭部については、詳しく説明せずヘッダーと呼びました。高度な使い方のために、SDSの内部を詳しく見て、その実装に使う構造体を示します。

    struct sdshdr {
    int len;
    int free;
    char buf[];
};

    この構造体は、従来の文字列ライブラリーのものに似て見えるかもしれません。ただし、bufフィールドは異なります。ポインターではなく、長さを宣言していない配列なので、bufは実際には整数freeの直後の最初のバイトを指します。そのため、SDS文字列の作成では、sdshdr構造体のサイズと文字列長の合計に、すべてのSDS文字列で必須のNUL終端用の1バイトを加えた大きさのメモリー領域を確保するだけです。

    構造体のlenフィールドは、その名のとおりSDS文字列の現在の長さで、SDS関数の呼び出しで文字列を変更するたびに計算されます。一方、freeフィールドは、現在の確保領域のうち、さらに文字を格納するために使える空きメモリー量を表します。

    したがって、実際のSDSの配置は次のようになります。

    +------------+------------------------+-----------+---------------\
| Len | Free | H E L L O W O R L D \n | Null term |  Free space   \
+------------+------------------------+-----------+---------------\
             |
             `-> Pointer returned to the user.

    文字列の末尾に空き領域があるのは、無駄ではないかと思うかもしれません。実際、新しいSDS文字列を作成した直後には、末尾に空き領域はありません。ヘッダー、文字列、NUL終端だけを保持する、最小限のサイズを確保します。ただし、次のプログラムのような別のアクセス方法では、末尾に追加の空き領域が作られます。

    s = sdsempty();
s = sdscat(s,"foo");
s = sdscat(s,"bar");
s = sdscat(s,"123");

    SDSは効率を重視しているため、データを追加するたびに文字列を再確保することはできません。それでは非常に非効率になるため、文字列を大きくするたびに、空き領域をあらかじめ確保します。

    先行確保のアルゴリズムは次のとおりです。より多くのバイトを保持するために文字列を再確保するたびに、実際には最低限必要なサイズの2倍を確保します。たとえば、現在の文字列が30バイトを保持していて、さらに2バイトを連結する場合、SDSは合計32バイトではなく64バイトを確保します。

    ただし、先行して確保できる量には上限があり、SDS_MAX_PREALLOCで定義されています。SDSが追加で確保する領域は1MBを超えません。これは既定値で、変更できます。

    文字列の縮小

    sds sdsRemoveFreeSpace(sds s);
size_t sdsAllocSize(sds s);

    プログラムの種類によっては、メモリー使用量を非常に小さくする必要があります。文字列の連結、トリミング、範囲の取得の後には、末尾にかなりの追加領域が残る場合があります。

    sdsRemoveFreeSpace関数を使うと、現在の内容を保持するのに必要な最小サイズまで文字列を縮められます。

    s = sdsRemoveFreeSpace(s);

    指定した文字列の確保領域全体のサイズを取得する関数もあり、sdsAllocSizeと呼ばれます。

    sds s = sdsnew("Ladies and gentlemen");
s = sdscat(s,"... welcome to the C language.");
printf("%d\n", (int) sdsAllocSize(s));
s = sdsRemoveFreeSpace(s);
printf("%d\n", (int) sdsAllocSize(s));

output> 109
output> 59

    注：SDSの低水準APIは、危険を伴う操作をしていることへの注意として、キャメルケースを使っています。

    SDS文字列の手動変更

    void sdsupdatelen(sds s);

    SDS関数を使わず、SDS文字列を手動で変更したい場合があります。次の例では文字列の長さを暗黙に変更しますが、論理上の長さにも、NUL終端されたC文字列の長さを反映させたいものです。

    sdsupdatelen関数は、このための関数です。指定した文字列の内部の長さ情報を、strlenで取得した長さへ更新します。

    sds s = sdsnew("foobar");
s[2] = '\0';
printf("%d\n", sdslen(s));
sdsupdatelen(s);
printf("%d\n", sdslen(s));

output> 6
output> 2