C语言下实现的String库
solarLan 2019-07-01
C语言的String
C语言作为一门古老的高级语言，对于字符串的支持十分的薄弱。
入门时我们就知道我们使用数组来包含一串的ASCII字符来作为字符串的实现，如
char arr[] = "hello world!";
这样基于长度固定的数组的实现方式就导致了C的字符串的长度是不可变的，但是arr[]的内容却是可变的。
这样的设计导致很多时候我们对字符串的处理十分的麻烦与危险，像我之前写的哈夫曼编码解码的时候，为了盛放解码后的结果，我不得不创建一个非常大的静态数组或者动态分配内存来放置函数产生的长度不定的字符串。
相较于其后辈(如Python/Java,C++基本兼容C的语法，尽管C++实现了自己的string类)，C在很多方面也是比较异类的，比如C使用'\0'来标志字符串的结束，因而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|
我们来看这有什么用:
/*
* 返回 sds buf 的已占用长度
*/
static inline size_t sdslen(const sds s) {
struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
return sh->len;
}
/*
* 返回 sds buf 的可用长度
*/
static inline size_t sdsavail(const sds s) {
struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
return sh->free;
}
/*
* 创建一个指定长度的 sds
* 如果给定了初始化值 init 的话，那么将 init 复制到 sds 的 buf 当中
*
* T = O(N)
*/
sds sdsnewlen(const void *init, size_t initlen) {
struct sdshdr *sh;
// 有 init ？
// O(N)
if (init) {
sh = zmalloc(sizeof(struct sdshdr)+initlen+1);
} else {
sh = zcalloc(sizeof(struct sdshdr)+initlen+1);
}
// 内存不足，分配失败
if (sh == NULL) return NULL;
sh->len = initlen;
sh->free = 0;
// 如果给定了 init 且 initlen 不为 0 的话
// 那么将 init 的内容复制至 sds buf
// O(N)
if (initlen && init)
memcpy(sh->buf, init, initlen);
// 加上终结符
sh->buf[initlen] = '\0';
// 返回 buf 而不是整个 sdshdr
return (char*)sh->buf;
}我们创建一个新的sds的时候，分配sizeof(struct sdshdr) + len + 1大小的空间，len代表不包含结束符号在内的容量，最后我们返回的是字符串开始的地址，这个返回的地址可以直接作为一般的字符串被其他库函数等使用，即Redis所说的二进制兼容的(因为其内部也使用'0'结尾)。
同时结构体的地址可以通过用字符串的地址减去结构体的大小得到
struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
这样一来sds可以在常数时间内获得字符串的长度。
#include <stdio.h>
#include "./src/simple_dynamic_str.h"
int main() {
sds s = sdsnew("Hello World! K&R");
printf("%s\n", s);
printf("%zu %zu\n", sdslen(s), sdsavail(s));
printf("%c",s[0]);
return 0;
}结果: Hello World! K&R 16 0 H
这种通过指针的计算获得结构体的地址的方式还是比较少见的技巧，我也只是在Linux内核的task_struct结构体中见识过类似的技巧，当然那个更复杂。
这种操作是很危险的，但是C数组在这方面其实也没有好多少(并没有多出数组越界检查等)，不是吗?
在字符串较短时，结构体占据放入空间是比较可观的，更新版本的Redis优化了不同长度的字符串结构体的定义。
/* Note: sdshdr5 is never used, we just access the flags byte directly.
* However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* used */
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* used */
uint32_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};总结
这篇文章中有些技巧还是有些难度的，像sds我也是花了一些时间才弄明白其原理，这里的两种实现我个人更偏爱第二种，但是这毕竟是二等公民，没有语言级别的支持是硬伤。
所以如果真的需要大量处理字符串，特别是非纯ASCII码，左转Java/Python etc.
reference:
[redis sds(simple dynamic string)]()
[ccan xstring]()
Redis设计与实现
