C 语言实现动态字符串
C语言题库
共 17523字，需浏览 36分钟
·
2021-07-03 19:36
在C语言中，字符串是以连续的字节流表示的，并且以 '\0' 结尾，C语言标准库中也提供了很多函数来操作这种形式的字符串，比如，求字符串长度 strlen( )，求子串strstr( )，字符串拷贝strcpy( )等等，但是，这些函数并不安全，很可能给系统或应用程序带来严重的问题，如栈溢出等，C语言字符串中并没有记录操作系统为其分配的长度，用户必须自己将字符串长度保存在其他的变量中，很明显如果操作不当就会产生错误，如臭名昭著的缓冲区溢出。
其他语言中的字符串类型通常在存储字符串本身时也保存了字符串长度，如Pascal，这样做的好处是字符串也可以以空字符'\0'结尾，但也会产生缓冲区溢出错误，本文实现了一个简单的动态字符串库，首先考虑一下，采用什么样的数据结构可以避免缓冲区溢出问题呢，为简化起见，我们定义“字符串”为内存中无类型的字节流，因此可以避开本地化和Unicode等概念，首先定义数据结构如下：
#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则是包含该字符串的缓冲区长度。
接下来一个问题就是为字符串分配存储空间，由于内存分配可能失效，所以我们需要检查内存分配是否成功，一种可行的方法是在分配函数中返回错误码，但是，这样设计的API不太简洁实用，另外一个可选方案是事先注册一个回调函数，在内存分配失败时再调用该函数，但如果多个客户程序同时申请内存，该方法也会失效，C++中我们可以使用异常来处理这种情况，但是 C 不支持异常，所以该方法也不太现实。其实，某些其他的标准库代码也有类似的问题，如数学库中某个函数对一个负数进行求根运算，返回结果本来是double，为了表明函数调用出错，我们可以让函数返回NaN(Not a Number)，因此程序在需要检查该函数调用是否出错时可以检查返回值。
我们也采用与此类似的方法，如果内存分配出错，那么动态字符串返回NaS(Not a String)状态，任何返回NaS的操作将维护该状态，因此程序只需要在必要的时候检查其返回值，为了实现该效果，我们可以定义如下的宏，
#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;
}
接下来的问题是字符串指针可能指向不同的位置，例如，可以是在编译时刻就确定的静态区，也可以栈中的某个位置，还可以只由malloc或realloc函数分配动态内存区（堆区），只有在堆区分配的内存才能够被resize，即realloc( )，并且需要显式地free( )，因此我们需要记录字符串指向区域的类型，我们选择了 buf_sz 的高位来保存该状态，基于以上想法，我们如下定义内存分配函数：
#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;
}
有了以上的函数，我们可以定义如下宏，以便将C风格的字符串转换为我们的动态字符串，
/*
* 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在栈上分配空间，这意味着该空间不需要显示的释放，在函数退出时将自动被系统回收。
大多数时候，字符串分配在栈中，但是，有时候我们也需要将字符串保存在生命周期更长的结构中，此时，我们就需要显式地为字符串分配空间：
/* 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语言中文社区后台回复“C语言”，免费领取200G编程资源。
当然，既然C语言标准库使用以Null结尾的字符串，我们需要将动态字符串转换成C风格的字符串，如下：
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;
}
当然，上面的所讲的内容并没有完全解决缓冲区溢出的问题，因此，我们可以定义一下的宏来进行边界检查，
#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
接下来的任务是向动态字符串中追加新的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);
}
最后容易出现缓冲区溢出情况是格式化输入，由于不知道输入串长度，所以使用sprintf( ) 函数也比较容易出错（本地化），snprintf( ) 能够解决该问题，但是输出缓冲区太小了，很容易被截断，
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;
}
最后，我们经常在栈中分配格式化字符，以下函数可以将结果打印至屏幕会文件，
/* 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);\
})
至此，动态字符串的大部分API已经介绍完毕，使用上面所讲的函数和宏将会大大减少缓冲区溢出的危险，因此推荐各位同学在实际需要中使用上述的函数和宏。
评论