C 語言實現(xiàn)動態(tài)字符串
在C語言中，字符串是以連續(xù)的字節(jié)流表示的，并且以 '\0' 結(jié)尾，C語言標(biāo)準(zhǔn)庫中也提供了很多函數(shù)來操作這種形式的字符串，比如，求字符串長度 strlen( )，求子串strstr( )，字符串拷貝strcpy( )等等，但是，這些函數(shù)并不安全，很可能給系統(tǒng)或應(yīng)用程序帶來嚴(yán)重的問題，如棧溢出等，C語言字符串中并沒有記錄操作系統(tǒng)為其分配的長度，用戶必須自己將字符串長度保存在其他的變量中，很明顯如果操作不當(dāng)就會產(chǎn)生錯誤，如臭名昭著的緩沖區(qū)溢出。
其他語言中的字符串類型通常在存儲字符串本身時也保存了字符串長度，如Pascal，這樣做的好處是字符串也可以以空字符'\0'結(jié)尾，但也會產(chǎn)生緩沖區(qū)溢出錯誤，本文實現(xiàn)了一個簡單的動態(tài)字符串庫，首先考慮一下，采用什么樣的數(shù)據(jù)結(jié)構(gòu)可以避免緩沖區(qū)溢出問題呢，為簡化起見，我們定義“字符串”為內(nèi)存中無類型的字節(jié)流，因此可以避開本地化和Unicode等概念，首先定義數(shù)據(jù)結(jié)構(gòu)如下：
#ifndef __DSTRING_H
#define __DSTRING_H
typedef struct _dstring dstring;
struct _dstring
{
char *pstr;
size_t str_sz;
size_t buf_sz;
};
#endif
pstr 是指向字符串的指針，str_sz 是字符串長度，而 buf_sz則是包含該字符串的緩沖區(qū)長度。
接下來一個問題就是為字符串分配存儲空間，由于內(nèi)存分配可能失效，所以我們需要檢查內(nèi)存分配是否成功，一種可行的方法是在分配函數(shù)中返回錯誤碼，但是，這樣設(shè)計的API不太簡潔實用，另外一個可選方案是事先注冊一個回調(diào)函數(shù)，在內(nèi)存分配失敗時再調(diào)用該函數(shù)，但如果多個客戶程序同時申請內(nèi)存，該方法也會失效，C++中我們可以使用異常來處理這種情況，但是 C 不支持異常，所以該方法也不太現(xiàn)實。其實，某些其他的標(biāo)準(zhǔn)庫代碼也有類似的問題，如數(shù)學(xué)庫中某個函數(shù)對一個負(fù)數(shù)進(jìn)行求根運(yùn)算，返回結(jié)果本來是double，為了表明函數(shù)調(diào)用出錯，我們可以讓函數(shù)返回NaN(Not a Number)，因此程序在需要檢查該函數(shù)調(diào)用是否出錯時可以檢查返回值。
我們也采用與此類似的方法，如果內(nèi)存分配出錯，那么動態(tài)字符串返回NaS(Not a String)狀態(tài)，任何返回NaS的操作將維護(hù)該狀態(tài)，因此程序只需要在必要的時候檢查其返回值，為了實現(xiàn)該效果，我們可以定義如下的宏，
#define NaS ((string) {NULL, 0, 0})
#define isnas(S) (!(S)->pstr)
static size_t dstr_size(dstring *s)
{
if (isnas(s)) return 0;
return pstr->str_sz;
}
接下來的問題是字符串指針可能指向不同的位置，例如，可以是在編譯時刻就確定的靜態(tài)區(qū)，也可以棧中的某個位置，還可以只由malloc或realloc函數(shù)分配動態(tài)內(nèi)存區(qū)（堆區(qū)），只有在堆區(qū)分配的內(nèi)存才能夠被resize，即realloc( )，并且需要顯式地free( )，因此我們需要記錄字符串指向區(qū)域的類型，我們選擇了 buf_sz 的高位來保存該狀態(tài)，基于以上想法，我們?nèi)缦露x內(nèi)存分配函數(shù)：
#define DSTR_FREEABLE (1ULL << 63)
/* An initialized empty struct string */
#define DSTR_INIT ((string) {malloc(16), 0, (16)})
static dstring dstr_malloc(size_t size)
{
if (size < 16) size = 16;
return (dstring) {malloc(size), 0, size | DSTR_FREEABLE};
}
/* Try to compact string memory */
static void dstr_realloc(dstring *s)
{
char *buf;
/* Not a string? */
if (isnas(s)) return;
/* Can't realloc? */
if (!(s->buf_sz & DSTR_FREEABLE)) return;
/* Don't invoke undefined behaviour with realloc(x, 0) */
if (!s->str_sz){
free(s->pstr);
s->pstr = malloc(16);
} else {
/* Try to compact */
buf = realloc(s->pstr, s->str_sz);
if (buf) s->pstr = buf;
}
}
static void dstr_resize(dstring *s, size_t size)
{
char *buf;
size_t bsize;
/* Are we not a string? */
if (isnas(s)) return;
/* Not resizable */
if (!(s->buf_sz & DSTR_FREEABLE)) {
dstring s2;
/* Don't do anything if we want to shrink */
if (size <= s->str_sz) return;
/* Need to alloc a new string */
s2 = dstr_malloc(size);
/* Copy into new string */
memcpy(s2.pstr, s->pstr, s->str_sz);
/* Point to new string */
s->pstr = s2.pstr;
s->buf_sz = s2.buf_sz;
return;
}
/* Too big */
if (size & DSTR_FREEABLE)
{
free(s->pstr);
*s = NaS;
return;
}
bsize = s->buf_sz - DSTR_FREEABLE;
/* Keep at least 16 bytes */
if (size < 16) size = 16;
/* Nothing to do? */
if ((4 * size > 3 * bsize) && (size <= bsize)) return;
/* Try to double size instead of using a small increment */
if ((size > bsize) && (size < bsize * 2)) size = bsize * 2;
/* Keep at least 16 bytes */
if (size < 16) size = 16;
buf = realloc(s->pstr, size);
if (!buf) {
/* Failed, go to NaS state */
free(s->pstr);
*s = NaS;
} else {
s->pstr = buf;
s->buf_sz = size | DSTR_FREEABLE;
}
}
static void dstr_free(dstring *s)
{
if (s->buf_sz & DSTR_FREEABLE) free(s->pstr);
*s = NaS;
}
有了以上的函數(shù)，我們可以定義如下宏，以便將C風(fēng)格的字符串轉(zhuǎn)換為我們的動態(tài)字符串，
/*
* Copy a struct dstring to the stack.
* (Could use strdupa(), but this is more portable)
*/
#define dstr_dupstr_aux(S)\
__extension__ ({\
char *_stradupstr_aux = alloca((S).str_sz + 1);\
memcpy(_stradupstr_aux, (S).pstr, (S).str_sz);\
dstr_straux(_stradupstr_aux, (S).str_sz);\
})
#define dstr_adupstr(S) dstr_dupstr_aux(*(S))
/* A struct dstring based on a C string, stored on the stack */
#define S(C) dstr_dupstr_aux(dstr_cstr((char *)C))
static dstring dstr_straux(char *c, size_t len)
{
return (dstring) {c, len, len + 1};
}
/* A struct dstring based on a C string, stored in whatever c points to */
static dstring dstr_cstr(char *c)
{
size_t len = strlen(c);
return dstr_straux(c, len);
}
上述代碼中的宏S(C)使用了alloca在棧上分配空間，這意味著該空間不需要顯示的釋放，在函數(shù)退出時將自動被系統(tǒng)回收。
大多數(shù)時候，字符串分配在棧中，但是，有時候我們也需要將字符串保存在生命周期更長的結(jié)構(gòu)中，此時，我們就需要顯式地為字符串分配空間：
/* Create a new dstring as a copy of an old one */
static dstring dstr_dupstr(dstring *s)
{
dstring s2;
/* Not a string? */
if (isnas(s)) return NaS;
s2 = dstr_malloc(s->str_sz);
s2.str_sz = s->str_sz;
memcpy(s2.pstr, s->pstr, s->str_sz);
return s2;
}
/* Copy the memory from the source string into the dest string */
static void dstr_cpystr(dstring *dest, dstring *src)
{
/* Are we no a string */
if (isnas(src)) return;
dstr_resize(dest, src->str_sz);
if (isnas(dest)) return;
dest->str_sz = src->str_sz;
memcpy(dest->pstr, src->pstr, src->str_sz);
}
搜索公眾號C語言中文社區(qū)后臺回復(fù)“C語言”，免費領(lǐng)取200G編程資源。
當(dāng)然，既然C語言標(biāo)準(zhǔn)庫使用以Null結(jié)尾的字符串，我們需要將動態(tài)字符串轉(zhuǎn)換成C風(fēng)格的字符串，如下：
static char *dstr_tocstr(dstring *s)
{
size_t bsize;
/* Are we not a string? */
if (isnas(s)) return NULL;
/* Get real buffer size */
bsize = s->b_str_sz & ~DSTR_FREEABLE;
if (s->str_sz == bsize){
/* Increase buffer size */
dstr_resize(s, bsize + 1);
/* Are we no longer a string? */
if (isnas(s)) return NULL;
}
/* Tack a zero on the end */
s->pstr[s->str-sz] = 0;
/* Don't update the size */
/* Can use this buffer as long as you don't append anything else */
return s->pstr;
}
當(dāng)然，上面的所講的內(nèi)容并沒有完全解決緩沖區(qū)溢出的問題，因此，我們可以定義一下的宏來進(jìn)行邊界檢查，
#ifdef DEBUG_CHECK_BOUNDS
#define S_C(S, I)\
(* __extension__ ({\
assert((I) >= 0);\
assert((I) < (S)->str_sz);\
assert((I) < ((S)->buf_sz & ~DSTR_FREEABLE));\
&((S)->s[I]);\
}))
#else
#define S_C(S, I) ((S)->s[I])
#endif
接下來的任務(wù)是向動態(tài)字符串中追加新的C類型的字符串，
static void dstr_ncatcstr(dstring *s, size_t len, const char *str)
{
size_t bsize;
/* Are we not a string? */
if (isnas(s)) return;
/* Nothing to do? */
if (!str || !len) return;
/* Get real buffer size */
bsize = s->buf_sz & ~DSTR_FREEABLE;
if (s->str_sz + len >= bsize)
{
dstr_resize(s, s->str_sz + len);
/* Are we no longer a string? */
if (isnas(s)) return;
}
memcpy(&s->pstr[s->str_sz], str, len);
s->str_sz += len;
}
static void dstr_catcstr(dstring *s, const char *str)
{
if (str) dstr_ncatcstr(s, strlen(str), str);
}
static void dstr_catstr(dstring *s, const dstring *s2)
{
dstr_ncatcstr(s, s2->str_sz, s2->pstr);
}
static void dstr_catcstrs(dstring *s, ...)
{
const char *str;
va_list v;
/* Are we not a string? */
if (isnas(s)) return;
va_start(v, s);
for (str = va_arg(v, const char *); str; str = va_arg(v, const char *))
{
dstr_ncatcstr(s, strlen(str), str);
}
va_end(v);
}
static void dstr_catstrs(dstring *s1, ...)
{
const dstring *s2;
va_list v;
/* Are we not a string? */
if (isnas(s1)) return;
va_start(v, s1);
for (s2 = va_arg(v, const dstring *); s2; s2 = va_arg(v, const dstring *)) {
dstr_ncatcstr(s1, s2->str_sz, s2->pstr);
}
va_end(v);
}
最后容易出現(xiàn)緩沖區(qū)溢出情況是格式化輸入，由于不知道輸入串長度，所以使用sprintf( ) 函數(shù)也比較容易出錯（本地化），snprintf( ) 能夠解決該問題，但是輸出緩沖區(qū)太小了，很容易被截斷，
static void dstr_printf(dstring *s, const char *fmt, ...)
{
va_list v;
size_t len;
/* Are we not a string? */
if (isnas(s)) *s = DSTR_INIT;
/* Nothing to do? */
if (!fmt) return;
va_start(v, fmt);
len = vsnprintf(NULL, 0, fmt, v) + 1;
va_end(v);
dstr_resize(s, len);
/* Are we no longer a string? */
if (isnas(s)) return;
va_start(v, fmt);
vsnprintf(s->s, len, fmt, v);
va_end(v);
s->str_sz = len - 1;
}
最后，我們經(jīng)常在棧中分配格式化字符，以下函數(shù)可以將結(jié)果打印至屏幕會文件，
/* Use a (C string) format and return a stack-allocated struct dstring */
#define straprintf(...)\
__extension__ ({\
size_t _straprintf_len = snprintf(NULL, 0, __VA_ARGS__) + 1;\
char *_straprintf_buf = alloca(_straprintf_len);\
snprintf(_straprintf_buf, _straprintf_len, __VA_ARGS__);\
dstr_straux(_straprintf_buf, _straprintf_len - 1);\
})
至此，動態(tài)字符串的大部分API已經(jīng)介紹完畢，使用上面所講的函數(shù)和宏將會大大減少緩沖區(qū)溢出的危險，因此推薦各位同學(xué)在實際需要中使用上述的函數(shù)和宏。