文档章节

从cTags的vString学习动态字符串

htfy96
 htfy96
发布于 2015/02/24 21:46
字数 1615
阅读 23
收藏 0
点赞 0
评论 0

在ctags中,vString分布在`vString.h`和`vString.c`两个文件中,代码非常简洁,加起来仅有300余行,是初学c语言与动态字符串一个很好研究的范例。

结构定义

在vString.h中,vString定义如下:

struct sVString {
        size_t  length;  /* size of buffer used */
        size_t  size;    /* allocated size of buffer */
        char   *buffer;  /* location of buffer */
};

这也差不多是绝大多数动态字符串的实现方式。

buffer存储内容,size存储实际内容长度,按理说这样两个成员已经可以起到vString的作用了,但是为了速度起见,还是增加了length变量,使得每次增加新内容时不是分配一个单位大小,而是到达上限后一次分配多个单位。

为方便起见,在定义下面的函数的时候,如果一个参数是vString,另一个参数可以是vString也可以是char *的,统一只定义了vString版本,因为vString.buffer本身就是一个传统的char* 字符串。在这里通过宏,构造出char* 版本:

#define vStringValue(vs)      ((vs)->buffer)
#define vStringCat(vs,s)      vStringCatS((vs), vStringValue((s)))

exxx

凡是带exxx的函数(如eFree),实际上是在原函数(如Free)上加上了相应的检查,如果有错误就报错,这种技术在sqlite中也有使用。

xXXX

带x前缀的函数是自己实现的方便书写的宏。

#define xMalloc(n,Type)    (Type *)eMalloc((size_t)(n) * sizeof (Type)) //分配n个Type类型并初始化
#define xCalloc(n,Type)    (Type *)eCalloc((size_t)(n), sizeof (Type))
#define xRealloc(p,n,Type) (Type *)eRealloc((p), (n) * sizeof (Type))

DebugStatement(x)

#ifdef DEBUG
# define DebugStatement(x) x
#else
# define DebugStatement(x)
#endif

括号内的语句只有在定义了DEBUG宏时才会被编译,这样对于调试单条语句减少了代码量。

函数定义

vString *vStringNew (void);

新建一个vString并返回指针。

vString *vStringNew (void)
{
    vString *const string = xMalloc (1, vString);
    string->length = 0;
    string->size   = vStringInitialSize;
    string->buffer = xMalloc (string->size, char);
    vStringClear (string);
    return string;
}

vStringInitialSize是32,就像标准库sort的那个常数一样是实验出来的。太大占用空间,太小开始时刻需要频繁分配内存影响速度。

vString *const,后置const不允许修改指针本身,涉及到指针操作在定义时就应该给予其最小的权限,这样即使误操作也有可能被编译器检查出来。

void vStringClear (vString *const string)

清空vString。

void vStringClear (vString *const string)
{
    string->length = 0;
    string->buffer [0] = '\0';
    DebugStatement ( memset (string->buffer, 0, string->size); )
}

以char*的通常规范,首位填\0,长度清空即可。注意这里clear的是buffer的大小,对字符串本身的size没有变动。默认情况下不用buffer清零,因为之后使用该部分时必然是先赋值的。

void vStringSetLength (vString *const string)

自动根据buffer中实际内容大小设置size。

void vStringSetLength (vString *const string)
{
    string->length = strlen (string->buffer);
}

使用strlen,避免重复造轮子。

void vStringDelete (vString *const string)

彻底清空vString空间。

void vStringDelete (vString *const string)
{
    if (string != NULL)
    {
        if (string->buffer != NULL)
            eFree (string->buffer);
        eFree (string);
    }
}

预先检查,防止重复清空。

void vStringResize (vString *const string, const size_t newSize)

给buffer分配新的大小。

void vStringResize (vString *const string, const size_t newSize)
{
    char *const newBuffer = xRealloc (string->buffer, newSize, char);

    string->size = newSize;
    string->buffer = newBuffer;
}

否则可能会发生实际给buffer赋值时赋值到了未定义区段,造成程序崩溃或内存被篡改等问题。

realloc有可能新的指针和旧指针一样,也有可能不同。

boolean vStringAutoResize (vString *const string)

精华。决定了一次分配多大空间。

 boolean vStringAutoResize (vString *const string)
{
    boolean ok = TRUE;
    if (string->size <= INT_MAX / 2)
    {
        const size_t newSize = string->size * 2;
        vStringResize (string, newSize);
    }
    return ok;
}

如果有空间则分配当前空间的两倍。

这个也属于一些经验之道,因为一般来说,一个字符串本身的大小越大,它需要更大空间可能性越大,这个方法也在这里使用。

void vStringPut (vString *const string, const int c)

新增加一个字符。

注意到由于这个函数用得非常频繁,为了减少调用开支,定义了一个宏版本。

void vStringPut (vString *const string, const int c)
{
    if (string->length + 1 == string->size)  /*  check for buffer overflow */
        vStringAutoResize (string);

    string->buffer [string->length] = c;
    if (c != '\0')
        string->buffer [++string->length] = '\0';
}
#define vStringPut(s,c) \
    (void)(((s)->length + 1 == (s)->size ? vStringAutoResize (s) : 0), \
    ((s)->buffer [(s)->length] = (c)), \
    ((c) == '\0' ? 0 : ((s)->buffer [++(s)->length] = '\0')))
#endif

在string->length+1==string->size时,由于有末尾\0实际上存储已满,故增大buffer大小。

注意不能添加'\0',否则结果会错误。

宏版本用,运算符精炼地连接了多个语句,用?来进行if的作用。

void vStringCatS (vString *const string, const char *const s)

将s的内容增加到string的后面。

void vStringCatS (vString *const string, const char *const s)
{
#if 1
    const size_t len = strlen (s);
    while (string->length + len + 1 >= string->size)/*  check for buffer overflow */
        vStringAutoResize (string);
    strcpy (string->buffer + string->length, s);
    string->length += len;
#else
    const char *p = s;
    do
        vStringPut (string, *p);
    while (*p++ != '\0');
#endif
}

后面那一段是原本注释掉的内容,还是一句话:strcpy这些标准库内置的东西,在实现时都是经过反复测试的,在绝大多数情况下比自己写的要快要安全,不要重复造轮子。

为什么不用strcat?

因为在这里, string的结束地址是已知的(我们已经记录了length),strcat会从头扫一遍string,效率太低。

void vStringNCatS (vString *const string, const char *const s, const size_t length)

将s的前length个字符拷贝到string中。

void vStringNCatS (
        vString *const string, const char *const s, const size_t length)
{
    const char *p = s;
    size_t remain = length;

    while (*p != '\0'  &&  remain > 0)
    {
        vStringPut (string, *p);
        --remain;
        ++p;
    }
    vStringTerminate (string); //在buffer末尾添加'\0'
}

这里为什么不使用strncpy?动态扩容固然是一方面,但如果我们一开始就扩容好呢?我们看一下strncpy的情况:

  • If count is reached before the entire string src was copied, the resulting character array is not null-terminated.

  • If, after copying the terminating null character from src, count is not reached, additional null characters are written to dest until the total of count characters have been written.

简而言之:

  1. 在length<s长度时,strncpy不会添加'\0'

  2. 在length==s长度时,strncpy会添加'\0'

  3. 在length>s长度时,strncpy会添加多个'\0'

而我们是要始终末尾有'\0'。虽然我们可以在末尾强制加一个'\0'快速解决问题,但在情况3时,效率低。



© 著作权归作者所有

共有 人打赏支持
htfy96
粉丝 8
博文 5
码字总数 10027
作品 0
闵行
程序员
C++字符串库--vstring

VSTRING 是一个C++字符串库,提供动态字符串,兼容 char* ,Perl 类数组和散列,正则表达式对象。

叶秀兰 ⋅ 2014/01/08 ⋅ 0

RDVTabBarController--可自由定制的iOS底部导航控件

RDVTabBarController:一个十分完善的tabBarController,可以自定义角标个数,爽的停不下来。 RDVTabBarController地址:RDVTabBarController Demo地址:欢迎Star --- 说明 此教程是旨在让你...

ios122 ⋅ 2015/10/10 ⋅ 0

linux 命令 vim 命令 学习笔记

linux: 查找: sudo find /var/ -name dao.log 查找: grep -r "dao.log *" 删除目录 : rm -rf var 切换用户 : sudo -i sudo - zyh 6. 动态显示log日志: tail -f dao.log 7.清楚日志 : ......

杰思 ⋅ 2017/06/19 ⋅ 0

如何定义一个不能被继承的类

class VString{//默认的存取控制方式就是私有 VString(); VString(char*); VString(string); friend class String;};class String:virtual VString{public: String(){ //写你的代码 } String......

兔之 ⋅ 2014/11/18 ⋅ 1

Cygwin下的ctags

Cygwin下的ctags Posted onFebruary 17, 2010byMrBear 今天,在Cygwin 下试图用ctags 为项目的代码建立tags 给vim 用。 输入习惯的ctags -R 之后,却发现这样的错误 又尝试了一下ctags –rec...

llfnana ⋅ 2013/06/06 ⋅ 0

Linux源代码分析工具链

vim+ctags+cscope 源码阅读三剑客.vim配合ctags和cscope,足以在源代码里面自由翱翔,在函数和变量间自由跳转. 安装 1 sudo apt-get install vim ctags cscope 使用 vim vim的使用就略过了,网上...

CasparLi ⋅ 2015/09/06 ⋅ 0

gvim---配置自动代码提示

下载autocomplpop的相关文件,地址为http://www.vim.org/scripts/script.php?scriptid=1879,将这个文件下载下来之后将文件夹中的文件按照安装的目录的名字对应的放在对应的目录中。但是会u...

durban ⋅ 2012/02/12 ⋅ 0

Linux下源代码阅读工具

转载链接:http://www.cnblogs.com/lidabo/p/4957908.html Linux源代码分析和阅读工具比较 Windows下的源码阅读工具Souce Insight 凭 借着其易用性和多种编程语言的支持,无疑是这个领域的“...

lengxujun ⋅ 2016/06/28 ⋅ 0

Webbench网站压力测试

Webbench网站压力测试 Webbench是有名的网站压力测试工具,能测试处在相同硬件上,不同服务的性能以及不同硬件上同一个服务的运行状况。webBech的标准测试可以向我们展示服务器的 两项 内容:...

MK先生 ⋅ 2017/04/11 ⋅ 0

Vim安装配置和常用技巧精选

本文旨在用最简短语言介绍Vim最实用的技巧。帮助Linux/Unix开发者快速掌握它。要想深入研究Vim的使用,大家可以参考Vim官方网站:http://www.vim.org 本文不断修改中,任何问题大家都可以在下...

雷阿曼 ⋅ 2013/12/06 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

MySQL主从复制原理、半同步操作步骤及原理

1.1 企业Linux运维场景数据同步方案 1.1.1 文件级别的异机同步方案 1、scp/sftp/nc 命令可以实现远程数据同步。 2、搭建ftp/http/svn/nfs 服务器,然后在客户端上也可以把数据同步到服务器。...

xiaomin0322 ⋅ 11分钟前 ⋅ 0

Oracle10g 数据及文件迁移过程[原]

QL*Plus: Release 10.2.0.1.0 - Production on 星期三 5月 11 10:22:35 2011 Copyright (c) 1982, 2005, Oracle. All rights reserved. 连接到: Oracle Database 10g Enterprise Edition Re......

harrypotter ⋅ 17分钟前 ⋅ 0

nginx安装

1:安装工具包 wget、vim和gcc yum install -y wget yum install -y vim-enhanced yum install -y make cmake gcc gcc-c++ 2:下载nginx安装包 wget http://nginx.org/download/nginx-1......

壹丶贰 ⋅ 20分钟前 ⋅ 0

ideaVim安装及配置

1.安装插件 File-Settings-Plugins,Browse Repositories,输入ideavim,安装。 重启后,在Tools-Vim Emulator启用。 2.快捷键设置 ideaViim键与idea快捷键有冲突,可以在Settings-Other Se...

Funcy1122 ⋅ 24分钟前 ⋅ 0

MySQL中B+Tree索引原理

B+树索引是B+树在数据库中的一种实现,是最常见也是数据库中使用最为频繁的一种索引。B+树中的B代表平衡(balance),而不是二叉(binary),因为B+树是从最早的平衡二叉树演化而来的。在讲B...

浮躁的码农 ⋅ 39分钟前 ⋅ 0

两道面试题,带你解析Java类加载机制

在许多Java面试中,我们经常会看到关于Java类加载机制的考察,例如下面这道题: class Grandpa{ static { System.out.println("爷爷在静态代码块"); }} cl...

1527 ⋅ 43分钟前 ⋅ 0

SpringCloud(Data Flow)

dataflow-server

赵-猛 ⋅ 53分钟前 ⋅ 0

深入理解Java虚拟机

这本书我读到第8章,之后就是在读不下去了。 读到后面是一种痛苦的体验,太多的东西是不全面的,大量的专有名词是没有解释的,读到最后很多东西仅仅是一个侧面,所以我觉得,这本书不适合初学...

颖伙虫 ⋅ 59分钟前 ⋅ 0

NanoPi NEO core/ Ubuntu16.04单网卡配置3个IP地址(2个静态,1个动态)

配置 root@NanoPi-NEO-Core:/etc/network# cat interfacesauto loiface lo inet loopbackallow-hotplug eth0iface eth0 inet static address 172.31.188.249 netmask 255.......

SamXIAO ⋅ 今天 ⋅ 0

三步为你的App集成LivePhoto功能

摘要:LivePhoto是iOS9新推出的一种拍照方式,类似于拍摄Gif图或录制视频片段生成图片。如果没有画面感,可以联想《哈利波特》霍格沃茨城堡的壁画,哈哈,很炫酷有木有,但坑爹的是只有iphone6S以...

壹峰 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部