爱开发联盟是国内专业的网站建设资源、脚本编程学习类网站,提供asp、php、asp.net、javascript、jquery、vbscript、dos批处理、网页制作、网络编程、网站建设等编程资料。让开发变得简单起来!
爱开发联盟是国内专业的网站建设资源、脚本编程学习类网站,提供asp、php、asp.net、javascript、jquery、vbscript、dos批处理、网页制作、网络编程、网站建设等编程资料。让开发变得简单起来!
当前所在位置:主页 > 脚本 > Lua >
  • 魔艺客提供SEO\SEM推广整合营销服务
  • 提供整套互联网营销整合方案-魔艺客
  • 魔艺客高端网站建设开发服务十一大优惠服务
  • 资深的网站建设开发经验,一对一服务-魔艺客高
  • 一站式服务,从服务器到网站,三站何以尽在魔
爱开发联盟是国内专业的网站建设资源、脚本编程学习类网站,提供asp、php、asp.net、javascript、jquery、vbscript、dos批处理、网页制作、网络编程、网站建设等编程资料。让开发变得简单起来!

Lua源码中字符串类型的实现

发布时间:2017-09-08 19:42    作者:爱开发联盟    浏览:次    来源:aikaifa.com.cn 分享:

 概述

    Lua完全采用8位编码,Lua字符串中的字符可以具有任何数值编码,包括数值0。也就是说,可以将任意二进制数据存储到一个字符串中。Lua的字符串是不可变的值(immutable values)。如果修改,实质上是新建一个字符串。根据上文《Lua中数据类型的源码实现》中知道,在Lua中,字符串是自动内存管理机制所管理的对象,并且由联合体TString来实现存储字符串值的。下面将通过Lua 5.2.1的源码来看字符串的实现以及总结了在Lua中使用字符串的注意事项。

    源码实现

    首先来看字符串对应的数据结构TString,其源码如下(lobject.h):

410 /* 
411 ** Header for string value; string bytes follow the end of this structure 
412 */ 
413 typedef union TString { 
414  L_Umaxalign dummy; /* ensures maximum alignment for strings */ 
415  struct { 
416   CommonHeader; 
417   lu_byte extra; /* reserved words for short strings; "has hash" for longs */ 
418   unsigned int hash; 
419   size_t len; /* number of characters in string */ 
420  } tsv; 
421 } TString; 

对这个联合体定义,有几点值得说明:

    I、联合体TString中成员L_Umaxalign dummy是用来保证与最大长度的C类型进行对齐,其定义如下(llimits.h):

48 /* type to ensure maximum alignment */ 
49 #if !defined(LUAI_USER_ALIGNMENT_T) 
50 #define LUAI_USER_ALIGNMENT_T  union { double u; void *s; long l; } 
51 #endif 
52    
53 typedef LUAI_USER_ALIGNMENT_T L_Umaxalign; 

在其他可会回收的对象(比如table)的实现中,也可看到这个联合体成员,这样做的目的是通过内存对齐,加快CPU访问内存的速度。

    II、联合体中成员tsv才是真正用来实现字符串的。其中成员CommonHeader用于GC,它会以宏的形式在所有的可回收对象中定义,代码如下(lobject.h):

74 /* 
75 ** Common Header for all collectable objects (in macro form, to be 
76 ** included in other objects) 
77 */ 
78 #define CommonHeader  GCObject *next; lu_byte tt; lu_byte marked 

这个宏对应的结构体形式如下(lobject.h):

81 /* 
82 ** Common header in struct form 
83 */ 
84 typedef struct GCheader { 
85  CommonHeader; 
86 } GCheader; 

结构体GCheader在通用的可回收对象union GCObject的定义中有用到。

 III、lu_byte extra对于短字符串,用来记录这个字符串是否为保留字,对于长字符串,可以用于惰性求Hash值;unsigned int hash成员是字符串对应的Hash值(在后面会具体讲Lua是怎么计算字符串的Hash值的);size_t len用来表示字符串的长度。

 IV、上面的结构体只是描述了一个字符串的结构,真正的字符串数据保存是紧随在结构体后面保存。

 在Lua5.2.1之前,不区分字符串长和短的字符串,所有的字符串保存在一个全局的Hash表中,对于Lua虚拟机来说,相同的字符串只有一份数据,从Lua5.2.1开始,只是把短的字符串字符串(当前定义是长度小于等于40)放在全局Hash表中,而长字符串都是独立生成,同时在计算Hash值时,引入一个随机种子,这样做的目的防止Hash Dos——攻击者构造出非常多相同Hash值的不同字符串,从而降低Lua从外部压入字符串进入全局的字符串Hash表的效率。下面是Lua5.2.1中,生成一个新字符串的步骤,其相应的代码都在lstring.c中:

 (1)若字符串长度大于LUAI_MAXSHORTLEN(默认值是40),则是长字符串,直接调用创建字符串接口的函数createstrobj(当然字符串的长度需要能保存在成员size_t len中,否则直接返回),代码如下(lstring.c):

 95 /* 
 96 ** creates a new string object 
 97 */                                                  
 98 static TString *createstrobj (lua_State *L, const char *str, size_t l,                
 99                int tag, unsigned int h, GCObject **list) {              
100  TString *ts;                                            
101  size_t totalsize; /* total size of TString object */                       
102  totalsize = sizeof(TString) + ((l + 1) * sizeof(char));                      
103  ts = &luaC_newobj(L, tag, totalsize, list, 0)->ts; 
104  ts->tsv.len = l; 
105  ts->tsv.hash = h; 
106  ts->tsv.extra = 0;                                         
107  memcpy(ts+1, str, l*sizeof(char)); 
108  ((char *)(ts+1))[l] = '\0'; /* ending 0 */                            
109  return ts; 
110 }  

可以看到把传入的字符串具体内存放在紧随结构体TString内存后面,并且注意108行,字符串以”\0”结束与C语言字符串兼容的。

 (2)若字符串是短字符串,首先计算字符串的Hash值,找到对应的链表(短字符串的全局Hash表,使用的是链接法的方法,即把所有冲突的元素放在同一个链表中),查找当前要创建的字符串是否已经在Hash表中,若已经存在,则直接返回这个字符串。否则会调用函数newshrstr,而函数newshrstr会调用上面的createstrobj函数创建新字符串,并把新创建的字符串放到Hash表中,代码如下(lstring.c)):

130 /* 
131 ** checks whether short string exists and reuses it or creates a new one 
132 */ 
133 static TString *internshrstr (lua_State *L, const char *str, size_t l) { 
134  GCObject *o; 
135  global_State *g = G(L); 
136  unsigned int h = luaS_hash(str, l, g->seed); 
137  for (o = g->strt.hash[lmod(h, g->strt.size)]; 
138    o != NULL; 
139    o = gch(o)->next) { 
140   TString *ts = rawgco2ts(o); 
141   if (h == ts->tsv.hash && 
142     ts->tsv.len == l && 
143     (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) { 
144    if (isdead(G(L), o)) /* string is dead (but was not collected yet)? */ 
145     changewhite(o); /* resurrect it */ 
146    return ts; 
147   } 
148  } 
149  return newshrstr(L, str, l, h); /* not found; create a new string */ 
150 } 

全局的字符串Hash表是保存在虚拟机全局状态成员strt中的(lstate.h):

119  stringtable strt; /* hash table for strings */ 

而类型stringtable是一个结构体,其定义如下(lstate.h):

59 typedef struct stringtable {                                     
60  GCObject **hash; 
61  lu_int32 nuse; /* number of elements */ 
62  int size; 
63 } stringtable; 

其中成员GCObject **hash是一个指针数组,数组中每个成员实质指向TString(注意TString中包括宏CommonHeader,该宏中的next成员可以构造出Hash表中开散的链表);nuse是数组hash中已经被使用的元素个数;size是当前数组hash的大小。

在函数newshrstr插入新的字符串前,都会判断nuse值是否大于size,若大于,表明Hash表大小不够需要扩充,则把Hash表的大小扩充到原来的2倍,对应的代码如下(lstring.c):

121  if (tb->nuse >= cast(lu_int32, tb->size) && tb->size <= MAX_INT/2)                 
122   luaS_resize(L, tb->size*2); /* too crowded */  

在gc的时候,会判断nuse是否比size/2还小(在Lua 5.1中是把nuse与size/4比较),如果是的话就重新resize这个stringtable的大小为原来的一半。对应的代码如下(lgc.c):

783   int hs = g->strt.size / 2; /* half the size of the string table */               
784   if (g->strt.nuse < cast(lu_int32, hs)) /* using less than that half? */            
785    luaS_resize(L, hs); /* halve its size */ 

对于字符串比较,首先比较类型,若是不同类型字符串,则肯定不相同,然后区分短字符串和长字符串,对于短字符串,若两者指针值相等,则相同,否则不相同;对应长字符串,则首先比较指针值,若不同,则比较长度值和内容逐字符比较。

  总结

 (1)Lua中的保留字和元方法名都是做为短字符串的,他们在虚拟机启动的时候就已经放入到全局短的字符串Hash表,并且是不回收的。

 (2)查找字符是比较高效的,但是修改或插入字符串都是比较低效的,这里面除了计算外,至少要把外面的字符串拷贝到虚拟机中。

 (3)对应长字符串的Hash值,Lua是不会考察每个字符的,因而能避免快速计算长字符串的散列值,其相应的代码如下(lstring.c):

51 unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) {               
52  unsigned int h = seed ^ l;                                     
53  size_t l1;                                             
54  size_t step = (l >> LUAI_HASHLIMIT) + 1;                              
55  for (l1 = l; l1 >= step; l1 -= step)                                
56   h = h ^ ((h<<5) + (h>>2) + cast_byte(str[l1 - 1]));                       
57  return h;                                             
58 }  
21 /*                                                 
22 ** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a string to                 
23 ** compute its hash                                         
24 */                                                  
25 #if !defined(LUAI_HASHLIMIT)                                     
26 #define LUAI_HASHLIMIT   5                                    
27 #endif 

 (4)当有多个字符串连接时,不应该直接用字符串连接运算符”..”,而是用table.concat操作或者是string.format来加快字符串连接的操作。

 (5)Lua中字符串Hash算法用的是JSHash,关于字符串的各种Hash函数,网络有篇文章对它进行了总结:

以上所述谁就是本文的全部内容了,希望能对大家学习lua有所帮助。

网友评论

分类排行榜联系我们

好文推荐联系我们

爱开发联盟是国内专业的网站建设资源、脚本编程学习类网站,提供asp、php、asp.net、javascript、jquery、vbscript、dos批处理、网页制作、网络编程、网站建设等编程资料。让开发变得简单起来!
爱开发联盟是国内专业的网站建设资源、脚本编程学习类网站,提供asp、php、asp.net、javascript、jquery、vbscript、dos批处理、网页制作、网络编程、网站建设等编程资料。让开发变得简单起来!

当前最新内容联系我们

爱开发联盟是国内专业的网站建设资源、脚本编程学习类网站,提供asp、php、asp.net、javascript、jquery、vbscript、dos批处理、网页制作、网络编程、网站建设等编程资料。让开发变得简单起来!

在线手册

网站地图导航

前端 HTML/Xhtml HTML5 CSS XML/XSLT Dreamweaver教程 Frontpage教程 心得技巧 编程 JavaScript ASP.NET PHP编程 正则表达式 AJAX相关 ASP编程 JSP编程 Flex 脚本加解密 web2.0 XML/RSS 网页编辑器 相关技巧 安全相关 网页播放器 Dart 其它综合 脚本 VBS DOS/BAT HTA HTC Python perl 游戏相关 vba 远程脚本 ColdFusion ruby专题 autoit seraphzone PowerShell linux shell Lua Golang Erlang 脚本下载 广告代码 js框架 批处理 网页相关 源码下载 数据库 MsSql Mysql mariadb oracle DB2 mssql2008 mssql2005 SQLite PostgreSQL MongoDB Redis Access 数据库文摘 数据库其它 CMS dedecms ecshop z-blog UcHome UCenter 风讯CMS 科汛cms discuz 新云cms phpwind 动易cms phpcms 帝国cms WordPress drupal 其它cms 设计 photoshop教程 摄影教程 Fireworks教程 CorelDraw教程 Illustrator教程 Painter教程 Freehand教程 Indesign 设计素材 平面其它 微信相关 微信公众号 小程序 操作系统 bios 系统安装 系统进程 Windows系列 LINUX RedHat/Centos Ubuntu/Debian Fedora Solaris 麒麟系统 红旗Linux Unix/BSD 苹果MAC 注册表 其它系统 网站运营 建站经验 微信营销 网站优化 网站策划 网络赚钱 网络创业 站长故事 alexa域名 其它相关 网络安全 黑客教程 安全设置 杀毒防毒 病毒查杀 脚本攻防 黑客入侵 工具使用 业界动态 Exploit 漏洞分析 加密解密 手机黑客 安全其它 在线手册 网页制作 脚本编程 数据库相关 软件编程 系统相关 其它相关 源码下载

友情链接申请加入

51CTO 上海魔艺客 猫鼬设计开发 Erlo网站开发 猫鼬设计工作室 新发现全球资讯 信息安全与IT资讯
爱开发联盟是国内专业的网站建设资源、脚本编程学习类网站,提供asp、php、asp.net、javascript、jquery、vbscript、dos批处理、网页制作、网络编程、网站建设等编程资料。让开发变得简单起来!

283882409