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

概述

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函数,网络有篇文章对它进行了总结:https://www.byvoid.com/blog/string-hash-compare

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

(0)

相关推荐

  • Lua字符串库中的几个重点函数介绍

    在<Lua中的一些库>中也说到了,要对string库的模式匹配进行单独的讲解.对于字符串的处理,对于任何语言的学习来说,都是一个难点,而且也是一个必会的知识点.给你一个字符串,让你按照某种需求进行处理,你不会,那是多么尴尬的一件事情.所以,看完<Lua中的一些库>和这篇文章之后,我争取做到让你在处理字符串时,不再感到捉襟见肘,不再尴尬. 说到Lua中的模式匹配,基本上就是围绕着以下几个函数展开的: 1.find: 2.match: 3.gsub: 4.gmatch. 我的总结也就是

  • Lua教程(五):C/C++操作Lua数组和字符串示例

    本文将介绍如何在C/C++里面操作Lua的数组和字符串类型,同时还会介绍如何在C/C++函数里面存储Lua状态(registry和upvalue),而registry在使用C/C++自定义类型时非常有用,可以方便地为userdata指定metatable. C/C++操作Lua数组 Lua数组Overview 在Lua里面,数组只不过是key为整数的table而已.比如一个table为array = {12,"Hello", "World"},它是一个数组,可以用下

  • 使用lua实现split字符串分隔

    LUA并不象其它许多"大而全"的语言那样,包括很多功能,比如网络通讯.图形界面等.但是LUA可以很容易地被扩展:由宿主语言(通常是C或C++)提供这些功能,LUA可以使用它们,就像是本来就内置的功能一样.LUA只包括一个精简的核心和最基本的库.这使得LUA体积小.启动速度快,从而适合嵌入在别的程序里.因此在lua中并没有其他语言那样多的系统函数.习惯了其他语言的字符串分割函数,与是就自己写了一个,记录在此,以备使用. 下面在简单介绍下lua: Lua 是一个小巧的脚本语言.作者是巴西人

  • Lua中使用table.concat连接大量字符串实例

    最近2天都没有写新的文章了,主要是最近的内容没有特别有意思的. 之前的协同程序也暂时没有感觉到特别适用的地方,今天在看数据结构的部分,也是没多大意思(不代表没用). 但是突然发现了一个有意思的地方,那就是--连接大量字符串的时候,如何解决效率问题. 1.预备知识,在Lua中获取系统时间 为了直观地看到效率的差别,我们要计算一下代码的执行时间,所以,先来看看如何计算吧: 复制代码 代码如下: local startTime = os.clock();     for i = 1, 19900000

  • Lua函数与字符串处理简明总结

    函数的定义是以function关键字开始的,后面函数的名称,然后是要传递给函数的参数,如果没有参数传给函数,仍然需要用()来表示一个空的参数列表,以end关键字结尾. 复制代码 代码如下: function 函数名()  ...  ...  ... end 1. 单一参数 复制代码 代码如下: function F_1(var)  print("My website is: "  var) end 参数var传递给了函数,并在函数中使用,同时,函数中的参数是局部变量,在函数调用结束后被

  • Lua中字符串(string)浅析

    Lua中字符串可以使用""或''声明,类似Javascript中的用法. 复制代码 代码如下: > ="sdfdsf" sdfdsf > ='sfdd' sfdd > ='abc"' abc" > ="abc'" abc' 同Java.Python一样,Lua的字符串是不可修改的值,可以通过string.gsub函数来替换字符串中的子串: 复制代码 代码如下: > s = string.gsub(

  • Lua字符串库(string库)学习笔记

    Lua 最强大的特性之一就是它的字符串处理能力,它支持字符格式化输出,具有可扩展的模式匹配查找功能,以及一些实用的字符操作,例如查询.截取.替换和删除等字符串操作,这些字符串操作函数都封装在一个名为 string 的模块里. Lua 里的字符索引是从 1 开始,索引值也可以是负数,这种情况将被解释成向后索引,从字符串末尾开始算起. 下面是 Lua 5.2 提供的字符串操作函数: byte 函数 string.byte 把字符串里的第 i 个字符转为 ASCII编码,默认是输出第一个字符的编码(只

  • Lua中的string库(字符串函数库)总结

    Lua解释器对字符串的支持很有限.一个程序可以创建字符串并连接字符串,但不能截取子串,检查字符串的大小,检测字符串的内容.在Lua中操纵字符串的功能基本来自于string库. 字符串库中的一些函数是非常简单的: string.len(s)          返回字符串s的长度: string.rep(s, n)      返回重复n次字符串s的串:你使用string.rep("a", 2^20)可以创建一个1M bytes的字符串(比如,为了测试需要): string.lower(s)

  • Lua字符串模式匹配函数小结

    模式匹配函数 在string库中功能最强大的函数是: 复制代码 代码如下: string.find(字符串查找) string.gsub(全局字符串替换) string.gfind(全局字符串查找) string.gmatch(返回查找到字符串的迭代器) 这些函数都是基于模式匹配的.与其他脚本语言不同的是,Lua并不使用POSIX规范的正则表达式[4](也写作regexp)来进行模式匹配.主要的原因出于程序大小方面的考虑:实现一个典型的符合POSIX标准的regexp大概需要4000行代码,这比

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

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

  • Vue源码中要const _toStr = Object.prototype.toString的原因分析

    在vue的源码中,vue/src/shared/util.js文件中存放的是一些方法.其中作者用了Object.prototype.toString这个方法来判断类型,但是并没有直接用,而是单独保存在一个变量: const _toStr = Object.prototype.toString 那么为什么要这么做呢? 先说下判断类型.众所周知,typeof在判断对象时不能正确判断Null,并且不能识别出Array,但在判断基础类型时是没问题的.所以尤大也写了: export function is

  • Android源码中final关键字的用法及final,finally,finalize的区别

    hi 大家好,今日,天气剧变,非常冷,不想出门,于是给大家写了篇文章,关于android final关键字及final,finally,finalize的区别相关知识,具体详情如下所示: 先预告一下,下文中仅涉及java语法的讨论,和Android源码关系不大,请不要有阅读压力. 我发现在Android的源码中很多地方对final关键字的用法很是"别出心裁",之所以这么说是因为我从没看过是这么使用final关键字的,一个典型的例子是View类中onScrollChanged方法(不妨将

  • 详解Vue源码中一些util函数

    JS中很多开源库都有一个util文件夹,来存放一些常用的函数.这些套路属于那种常用但是不在ES规范中,同时又不足以单独为它发布一个npm模块.所以很多库都会单独写一个工具函数模块. 最进尝试阅读vue源码,看到很多有意思的函数,在这里分享一下. Object.prototype.toString.call(arg) 和 String(arg) 的区别? 上述两个表达式都是尝试将一个参数转化为字符串,但是还是有区别的. String(arg) 会尝试调用 arg.toString() 或者 arg

  • JDK源码中一些实用的“小技巧”总结

    前言 这段时间比较闲,就看起了jdk源码.一般的一个高级开发工程师, 能阅读一些源码对自己的提升还是蛮大的.本文总结了一些JDK源码中的"小技巧",分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. 1 i++ vs i-- String源码的第985行,equals方法中 while (n--!= 0) { if (v1[i] != v2[i]) return false; i++; } 这段代码是用于判断字符串是否相等,但有个奇怪地方是用了i--!=0来做判断,我们通

  • 最通俗的白话讲解JDK源码中的ThreadLocal

    目录 引言 ThreadLocal是什么?它能干什么? ThreadLocal实现线程隔离的秘密 为什么ThreadLocal会出现OOM的问题? 内存泄漏演示 内存泄漏问题分析 父子线程的参数传递 总结 引言 其实网上有很多关于ThreadLocal的文章了,有不少文章也已经写的非常好了.但是很多同学反应还有一些部分没有讲解的十分清楚,还是有一定的疑惑没有想的十分清楚.因此本文主要结合常见的一些疑问.ThreadLocal源码.应用实例以注意事项来全面而深入地再详细讲解一遍ThreadLoca

  • react 源码中位运算符的使用详解

    位运算符基本使用 按位与(&):a & b对于每一个比特位,两个操作数都为 1 时, 结果为 1, 否则为 0 按位或(|):a | b对于每一个比特位,两个操作数都为 0 时, 结果为 0, 否则为 1 按位异或(^):a ^ b对于每一个比特位,两个操作数相同时, 结果为 1, 否则为 0 按位非(~):~ a反转操作数的比特位, 即 0 变成 1, 1 变成 0 0000 0000 0000 0000 0000 0000 0000 0011 -> 3 1111 1111 111

  • webpack源码中一些精妙的方法总结

    目录 前言 精妙方法 缓存函数 属性劫持 数组比较 配置项校验 结尾 前言 过年这一段时间一直在研究webpack的源码,由于过年周围气氛比较欢快,心态有点飘导致没有沉下心来仔细研究其中的细节.经过反思之后,静心重新捋顺webpack的源码,这时发现不少巧妙的方法值得学习.这里我已经迫不及待的跟大家分享了,希望对大家平常开发过程中有所帮助. 精妙方法 缓存函数 这个方法最精妙的地方在于将执行结果缓存,减少函数的重复执行以达到提升性能的目的,对于执行越复杂越耗时的函数收益越大.但是,不适用于动态执

  • 深入分析React源码中的合成事件

    目录 热身准备 明确几个概念 事件系统角色划分 事件注册 registerSimpleEvents registerEvents$2 registerEvents$1 registerEvents$3 registerEvents 事件监听 事件派发 合成事件 捕获和冒泡 总结 热身准备 明确几个概念 在React@17.0.3版本中: 所有事件都是委托在id = root的DOM元素中(网上很多说是在document中,17版本不是了): 在应用中所有节点的事件监听其实都是在id = root

  • Android源码中常用的接口传参实例详解

    Android源码中常用的接口传参实例详解 把MyCclass中的参数传到MyDclass /*接口传参例子2 * MyCclass.java发送MyDclass.java接收 * 原理和MyAclass.java发送MyDclass.java接收完全一样 * */ public class MyCclass { public void getEditext(GetMyFragmentData myFragmentData){ String edStr="人的生命是有限的,可是为人民服务是无限的

随机推荐