简单的string_builder和string_table

一、有些时候需要逐步构建一个字符串，需要用到类似其它语言中的StringBuilder的组件。有必要自己写一个把它搞清楚。

string_builder有两个基本操作。一个是push操作，向末尾追加一个字符，若空间不够就自动额外申请。一个是获取string操作，拿到最终的串，串以空字符结尾。其它格式化的功能都是建立在这两个功能上的。我们用的时候假设是这样：

char *S = NULL;
(void) string_builder_push(&S, 'a');
(void) string_builder_push(&S, 'b');
// ...
bool bOK = string_builder_done(&S);
// S="ab...\0"
free(S);

意图很清晰。我有一个字符类型的空指针并把它交给string_builder_push，这个函数想办法把字符存进去之后返回给我一个新指针。最后执行对这个指针执行string_builder_done，S就指向了一个以空字符结尾的字符串。用完直接使用free函数释放内存。这意味着在追加字符的过程中有关内存布局的所有信息都在S所指向的内存区域里，string_builder_done执行之后关于内存布局的信息没了，它仅为我们留下了字符数据，这些数据被S直接指向，因而能被free函数使用。考虑这种字符数据的布局：

#define ALIGN_PAD 4
struct str
{
    int nchar;//存储了多少个有效字符
    int nmax;//最多能容纳多少字符
    char s[ALIGN_PAD];//存放字符数据的地方
};

也就是：指针S→［4Byte nchar｜4Byte nmax｜s[0]｜s[1]｜s[2]｜s[3]．．．］，追加字符的时候让它自己增加内存大小就行了。刚开始时需要新建一个str结构。

#define INIT_SLEN 8
static struct str *string_builder_new(void)
{
    struct str *p = (struct str*)malloc(
　　　　　　sizeof(char) * (INIT_SLEN-ALIGN_PAD) + sizeof(struct str));
    if(!p)
        return NULL;
    p->nchar = 0;
    p->nmax = INIT_SLEN;
    return p;
}

那么追加字符的操作就是：

string_builder_push(char **psb, char c)
{
    if(!psb || *psb == NULL && !(*psb = (char*)string_builder_new()))
        return false; //若第一个参数指向空指针则申请内存并初始化结构
    pstr = (struct str*) *psb;
    ifeq(pstr->nchar, pstr->nmax) //无法容纳新字符则重新申请足够的内存
    {
        *psb = (char*)realloc(pstr, sizeof(struct str) +
                sizeof(char) * (2*pstr->nmax - ALIGN_PAD));
        if(*psb == NULL) return false;
        pstr = (struct str*) *psb;
        pstr->nmax *= 2;
    }
    pstr->s[pstr->nchar++] = c;
    return true;
}

结束追加字符并获取字符串时有两种选择，一种是创建一份字符串拷贝并释放旧内存，另一种是借助原来的内存。前者得到的字符串尺寸刚好，结尾不会有多余内存，而后者很可能在字符串的空字符标记后面还有若干字节空闲内存，不过好处是不用申请新内存并释放旧内存。下面的代码采用后者。

string_builder_done(char **psb)
{
    if(!psb || *psb == NULL) return false;
    pstr = (struct str*) *psb;
    n = pstr->nchar;//保存起来，内存移动后值就没了
    memmove(*psb, &(pstr->s[0]), n);//把字符串移到起始位置
    *((*psb) + n) = 0; //追加空字符标记
    return true;
}

是不是很简单呢？(*^_^*)

二、拿到了字符串我们通常要保存起来，偶尔还要查询，例如一张名字表。

没人愿意频繁地申请一小段内存，所以我们都是把它们放到一个大块公共内存区里面，我们只要知道每个字符串首个字节相对于公共内存区起始点的偏移量X就能拿到每个字符串了。存的时候用一个散列表，给字符串算一个散列值并据此找到冲突的链表头，新建一个包含X的链表项，最后给它挂接上就行了。代码放下面，我想应该不用多解释了。

#define BUCKET_N 1023
#define ITEM_MAX_COUNT 8192
#define SBUF_INIT_SIZE 64
struct item{
    struct item *next; // 下一个散列值冲突的字符串
    size_t index; //该字符串在存储区的位置
};
static struct{
    struct item *buckets[BUCKET_N]; // 一堆链表，存放（冲突的）键值
    size_t item_count; //一共存了几个字符串
    char  *sbuf; //字符串数据在这个存储区存放
    size_t smax; //这个存储区有多大
    size_t slen; //用了多少字节
} string_table;

bkdr_hash(char *str) // BKDR散列函数
{
    size_t hash = 0, ch;
    while((ch = (size_t)(*str++))) hash = hash * 131 + ch;
    return hash;
}
string_table_init()
{
    memset(&string_table, 0, sizeof string_table);
    string_table.sbuf = (char*)malloc(sizeof(char) * SBUF_INIT_SIZE);
    if(string_table.sbuf) {
        string_table.smax = SBUF_INIT_SIZE;
        return true;
    }
    return false;
}
string_table_destroy()
{
    free(string_table.sbuf);
    for(int i = 0; i < BUCKET_N; i++)
    {
        struct item *p, *q = string_table.buckets[i];
        while(q) {
            p = q->next; free(q); q = p;
        }
    }
}
string_table_get(offset) // 根据偏移量拿原来的字符串
{
    if(offset >= BUCKET_N) return NULL;
    return string_table.sbuf + offset;
}
string_table_has(char *sz) //查询表里有没有给定字符串
{
    for(struct item *p =
            string_table.buckets[bkdr_hash(sz) % BUCKET_N];
            p; p = p->next)
        if(!strcmp(sz, string_table.sbuf + p->index))
            return true;
    return false;
}
//给它一个字符串，它把字符串添加到表里，若已存在则无动作
//最后给你一个偏移值，并告诉你操作成功了没
size_t string_table_add(char *sz, bool *success)
{
    char *w;
    struct item *p;
    size_t ndx, szlen, h;
　　 //村太多了就拒绝再存，(●ˇ∀ˇ●)
    if(!sz || string_table.item_count >= ITEM_MAX_COUNT)
        goto err;
    h = bkdr_hash(sz) % BUCKET_N;
    for(p = string_table.buckets[h]; p; p = p->next){
        w = string_table.sbuf + p->index;
        if(!strcmp(sz, w)) goto done; //已经存在了，结束
    }
    szlen = strlen(sz) + 1;
    if(string_table.slen + szlen > string_table.smax)
    {   //放不下，申请内存
        w = (char*)realloc(string_table.sbuf,
             sizeof(char) * 2 * string_table.smax);
        if(!w) goto err;
        string_table.sbuf = w;
        string_table.smax *= 2;
    }
    //把字符串存到公共存储区里
    ndx = string_table.slen;
    memcpy(string_table.sbuf + ndx, sz, szlen);
    string_table.slen += szlen;
    //新建链表项，然后挂接上
    if(!(p = (struct item*)malloc(sizeof(struct item)))) {
        string_table.slen -= szlen; goto err;
    }
    p->index = ndx;
    p->next = string_table.buckets[h];
    string_table.buckets[h] = p;
done:
    string_table.item_count++;
    if(success) *success = true;
    return p->index;
err:if(success) *success = false;
    return ((size_t)-1);
}        

代码删了一部分无关紧要的内容以缩减篇幅，复制可运行不了哦(●ˇ∀ˇ●)