脚本宝典收集整理的这篇文章主要介绍了C语言下实现的String库,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
C语言的String
C语言作为一门古老的高级语言,对于字符串的支持十分的薄弱。
入门时我们就知道我们使用数组来包含一串的ASCII字符来作为字符串的实现,如
char arr[] = "hello world!";
这样基于长度固定的数组的实现方式就导致了C的字符串的长度是不可变的,但是arr[]
的内容却是可变的。
这样的设计导致很多时候我们对字符串的处理十分的麻烦与危险,像我之前写的哈夫曼编码解码的时候,为了盛放解码后的结果,我不得不创建一个非常大的静态数组或者动态分配内存来放置函数产生的长度不定的字符串。
相较于其后辈(如Python/Java,C++基本兼容C的语法,尽管C++实现了自己的string类),C在很多方面也是比较异类的,比如C使用' '
来标志字符串的结束,因而len(arr)
这样的操作的复杂度就达到了O(n),这是一个比较大的开销,而Pascal/Python等的实现都可以做到O(1),同时,由于char
类型本身就是最短的整型再加上C语言的弱类型的类型系统,'a'- 32
也是完全有效的语法,而在Python中这会引发*TypeError*
. 这些问题在C语言诞生的年代不是大问题,毕竟当时没有那么多字符串的处理需求,而且C主要的应用场景也比较偏底层。
而现在,一些选择C实现的程序需要频繁的处理字符串(如 Redis
,需要频繁的处理键值对),为了应对这种场景,很多很有意思的自己的String实现都被提了出来。
在这里我主要是介绍ccan的xstring和sds的一些实现的思路。
xstring
/**
* struct xstring - string metadata
* @str: pointer to buf
* @len: current length of buf contents
* @cap: maximum capacity of buf
* @truncated: -1 indicates truncation
*/
typedef struct xstring {
char *str;
size_t len;
size_t cap;
int truncated;
} xstring;
xstring *xstrNew(const size_t size)
{
char *str;
xstring *x;
if (size < 1) {
errno = EINVAL;
return NULL;
}
str = malloc(size);//mark 1
if (!str)
return NULL;
x = malloc(sizeof(struct xstring));//mark 2
if (!x) {
free(str);
return NULL;
}
xstrInit(x, str, size, 0);
return x;
}
透过xstring
结构体与*xstrNew(const size_t size)
这个创建新的xstring
的函数,ccan
的这个实现的思路就比较清晰了,xstring
结构体本身占据内存,但是并不存储字符串,字符串在mark 1被分配存储空间,而结构体在mark 2被分配内存。
PS:
在刚刚学习使用C来实现数据结构的时候,我很疑惑为何不能直接
struct xstring* newStruct(){
struct xstring s;
return &s;
}
直到后来才逐渐明白了栈上的变量与动态分配的变量的微妙的区别,s在这个函数返回后就已经被销毁了,传出的这个地址是无效的,而对他的引用很可能会导致段错误(segment fault),操作系统,编译原理等课真的会让自己对于程序设计语言获得更深的理解。
而且这种写法当时很有吸引力,毕竟不用malloc,不用强制类型转换。
这种野指针是很多很难修正的错误的来源,有兴趣的同学可以去学习一下Rust语言的所有权系统,很多的概念很有意思。
| xstring
| -> | str
|
可以看出xstring
的实现中内存是分为两个部分的。
Note: xstring只需要编译器支持C89/90。
sds
redis sds(simple dynamic string)是Redis对于str的实现,在这里有官方对于sds实现的一些技巧的介绍,
在这里我会将SDS实现的主要的细节介绍以下。
// sds 类型
typedef char *sds;
// sdshdr 结构
struct sdshdr {
// buf 已占用长度
int len;
// buf 剩余可用长度
int free;
// 实际保存字符串数据的地方
// 利用c99(C99 specification 6.7.2.1.16)中引入的 flexible array member,通过buf来引用sdshdr后面的地址,
// 详情google "flexible array member"
char buf[];
};
和上面的实现不太一样的是sds只存储存储的字符串长度以及剩余长度,但是最引人瞩目的无疑是最后的那一个数组声明:
char buf[];
结构体中竟然没有声明数组的大小,这样好像与我们对于数组一贯的印象不符,但是这是合法的特性,叫做柔性数组。
具体的语法细节我不再介绍,但是注意以下几点
-
sizeof(struct sdshdr) == sizeof(len) + sizeof(buf)
,在x86_64上典型值应该为8个字节(4 + 4),这说明buf[]
没有实际占据空间,一个64位系统下的指针就要8个字节。
-
上面的写法是C99 only的,这个特性应该来自于以下这种写法,
struct header {
size_t len;
unsigned char data[1];
};
这种写法下data
就是一个 unsigned char*
型的指针,可以通过它用来访问存储的字符串。
//在分配内存的时候,结构体中存储了一个字符,其他的(n-1)个空间在
//紧随结构体结束地址的地方
// | struct (char) | (n - 1) char |
ptr = malloc(sizeof(struct header) + (n-1));
对比sds
中的实现,sds
中不存储任何一个数据,只有一个不占据内存空间的标记代表,所有的数据都存储在结构体所占空间后面
| struct | str
|
我们来看这有什么用: