云风的cstring库
为什么要给C语言写一个string库？
（来源于README of cstring）
C语言没有原生的string类型，这使得string的管理非常麻烦。这个库主要解决的几个问题：
- 对于短字符串（小于 32 字节），进行 string interning 。这可以在文本处理时节约不少内存。短 string 相当于 symbol 类型，对它做比较操作的代价可以减少到 O(1) 。
- 对于临时字符串，如果长度不大（小于 128 字节），尽可能的放在 stack 上，避免动态内存分配。
- 支持常量字符串，对于常量短字符串只做一次 string interning 操作。
- 使用引用计数管理相同的字符串，减少字符串的拷贝。
- 短字符串，常量字符串，以及引用次数非常多（大于 64K 次）的字符串可以不动态释放，简化生命期管理。
- 惰性计算，以及缓存字符串的 hash 值，以方便实现 hashmap 。
- 这个库是线程安全的。
cstring中的数据结构
struct cstring_data {
char * cstr;
uint32_t hash_size;
uint16_t type;
uint16_t ref;
};
记录字符串的数据结构，cstr指向的内存位置和相应的字符串种类有关：
struct string_node {
struct cstring_data str;
char buffer[CSTRING_INTERNING_SIZE];
struct string_node * next;
};
struct string_pool {
struct string_node node[INTERNING_POOL_SIZE];
};
struct string_interning {
int lock;
int size; // 哈希表的大小
struct string_node ** hash;
struct string_pool * pool;
int index;
int total;
};
在存储短字符串（小于32字节）时需要进行string interning操作，每个intering string节点由一个string_node表示，所有被intering的字符串记录存放在一个string pool中，并在哈希表hash中记录它们的信息。在string_intering结构中，采用链地址法来解决hash冲突。
cstring的实现
- 临时字符串（小于128字节），直接在栈上申请分配空间，避免动态申请释放内存带来的开销；
- 短字符串（小于32字节），使用string interning技术进行存储，相同的字符串只会存储一个实例，这样的好处在于对字符串进行比较操作时时间复杂度为O(1)（云风的博文中提到它们相当于一个symbol类型），缺点在于在进行string interning和hash表expand的时候会带来一些开销；
- 常量字符串：如果它的长度小于32字节，把它当成短字符串来处理，否则当成permanent字符串来处理。
首先看看它是如何存储临时字符串（小于128字节）的：
#define CSTRING_BUFFER(var) \
char var##_cstring [CSTRING_STACK_SIZE] = { '\0' }; \
struct cstring_data var##_cstring_data = { var##_cstring , 0, CSTRING_ONSTACK, 0 }; \
cstring_buffer var; \
var->str = &var##_cstring_data;
从代码可以看出，用宏CSTRING_BUFFER来定义常量字符串时，字符串的所需内存直接在栈上分配。
然后看看string intering是怎么实现的：
static cstring
interning(struct string_interning * si, const char * cstr, size_t sz, uint32_t hash) {
if (si->hash == NULL) {
return NULL;
}
int index = (int)(hash & (si->size-1));
struct string_node * n = si->hash[index];
//先在hash表中查找，如果找到，直接返回，相同的cstr返回的cstring地址相同
while(n) {
if (n->str.hash_size == hash) {
if (strcmp(n->str.cstr, cstr) == 0) {
return &n->str;
}
}
n = n->next;
}
// 添加cstr到pool和hash表中
// 80% (4/5) threshold
if (si->total * 5 >= si->size * 4) {
return NULL;
}
if (si->pool == NULL) {
// need not free pool
// todo: check memory alloc error
si->pool = malloc(sizeof(struct string_pool));
assert(si->pool);
si->index = 0;
}
n = &si->pool->node[si->index++];
memcpy(n->buffer, cstr, sz);
n->buffer[sz] = '\0';
cstring cs = &n->str;
cs->cstr = n->buffer;
cs->hash_size = hash;
cs->type = CSTRING_INTERNING;
cs->ref = 0;
n->next = si->hash[index];
si->hash[index] = n;
return cs;
}
对常量字符串的处理：
#define CSTRING_LITERAL(var, cstr) \
static cstring var = NULL; \
if (var) {} else { \
cstring tmp = cstring_persist(""cstr, (sizeof(cstr)/sizeof(char))-1); \
if (!__sync_bool_compare_and_swap(&var, NULL, tmp)) { \
cstring_free_persist(tmp); \
} \
}
static cstring
cstring_clone(const char * cstr, size_t sz) {
if (sz < CSTRING_INTERNING_SIZE) {
return cstring_interning(cstr, sz, hash_blob(cstr,sz));
}
struct cstring_data * p = malloc(sizeof(struct cstring_data) + sz + 1);
// todo: memory alloc error
assert(p);
void * ptr = (void *)(p + 1);
p->cstr = ptr;
p->type = 0;
p->ref = 1;
memcpy(ptr, cstr, sz);
((char *)ptr)[sz] = '\0';
p->hash_size = 0;
return p;
}
cstring
cstring_persist(const char * cstr, size_t sz) {
cstring s = cstring_clone(cstr, sz);
if (s->type == 0) {
s->type = CSTRING_PERMANENT;
s->ref = 0;
}
return s;
}
思考
README中关于literal操作提到在宏CSTRING_LITERAL(var, literal)中literal必须是以引号包含的字符串常量，而不能使用指向字符串的指针？
这是由于在处理这个宏的时候作者使用了sizeof()来计算literal字符串的大小，而sizeof()是不能计算指针指向的内存的大小的。那为什么不用strlen()来代替sizeof()？sizeof()是运算符，在编译阶段可以得到结果，而strlen()是函数，需要运行阶段才能知道它的值。考虑到这个宏只用于处理常量字符串，这种要求比较合理。