Lua源码阅读:基本数据类型String

Lua中对于String的实现。

Lua使用TString结构体代表一个字符串对象。

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
** Header for string value; string bytes follow the end of this structure  
** (aligned according to 'UTString'; see next).  
*/  
typedef struct  {  
  CommonHeader;  
  lu_byte extra;  /* reserved words for short strings; "has hash" for longs */  
  unsigned int hash;  
  size_t len;  /* number of characters in string */  
  struct  *hnext;  /* linked list for hash table */  
} TString;  
  
  
** Ensures that address after this type is always fully aligned.  
*/  
typedef union UTString {  
  L_Umaxalign dummy;  /* ensures maximum alignment for strings 用于最大字节对齐 */  
  TString tsv;  
} UTString;  

—|—

hash用来记录字符串对应的哈希值,len用来记录字符串的长度。

在Lua中,分为长字符串和短字符串,长度大于40的是长字符串,小于40的是短字符串,这部分在luaconf.h中定义:

1  
2  
3  
4  
5  
6  
7  
@@ LUAI_MAXSHORTLEN is the maximum length for short strings, that is,  
** strings that are internalized. (Cannot be smaller than reserved words  
** or tags for metamethods, as these strings must be internalized;  
** #("function") = 8, #("__newindex") = 10.)  
*/  

—|—

对于短字符串,在实际使用中一般用来作为索引或需要进行字符串比较,存放在global_State->strt中,这个字符串表(strt)是一个stringtable类型的全局唯一的哈希表,当需要创建一个短字符串对象时,会首先在这个表中查找已有对象。所有的短字符串都是全局唯一的,不会存在两个相同的短字符串对象,如果短字符串对象的extra>0,表示这是一个系统保留的字符串;长字符串一般用来存放文本数据,很少需要比较或者索引,所以长字符串被挂接到allgc链表上当作普通的对象来处理。

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
** new string (with explicit length) 生成新字符串的函数  
*/  
TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {  
  if (l <= LUAI_MAXSHORTLEN)  /* short string? */  
    return internshrstr(L, str, l);  
  else {  
    if (l + 1 > (MAX_SIZE - sizeof(TString))/sizeof(char))  
      luaM_toobig(L);  
    return createstrobj(L, str, l, LUA_TLNGSTR, G(L)->seed);  
  }  
}  
  
/* 在global_State中存储的哈希表结构体 */  
typedef struct stringtable {  
  TString **hash;  
  int nuse;  /* number of elements  已装元素的个数 */  
  int size;	/* 实际hash桶的大小 */  
} stringtable;  

—|—

对于短字符串,在创建的时候,首先计算str的哈希值。计算时会得到一个随机种子,这个种子就是global_State->seed,然后通过LUAI_HASHLIMIT控制步长,每一个步长范围内取字符串中的一个字符,和上次hash的结果相加,得到新的hash结果,计算出hash后,开始找是否存在这个字符串,方法是遍历global_State->strt->hash,短字符串表申请内存的大小和实际使用大小由后两个字段表示。

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
** checks whether short string exists and reuses it or creates a new one  
** 检查短字符串的存在性,根据结果重用已存在的字符串或创建一个新的字符串  
*/  
static TString *internshrstr (lua_State *L, const char *str, size_t l) {  
  TString *ts;  
  global_State *g = G(L);  
  unsigned int h = luaS_hash(str, l, g->seed);  
  TString **list = &g->strt.hash[lmod(h, g->strt.size)];  
  for (ts = *list; ts != NULL; ts = ts->hnext) {  
    if (l == ts->len &&  
        (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) {  
      /* found! */  
      if (isdead(g, ts))  /* dead (but not collected yet)? */  
        changewhite(ts);  /* resurrect it */  
      return ts;  
    }  
  }  
  if (g->strt.nuse >= g->strt.size && g->strt.size <= MAX_INT/2) {  
    luaS_resize(L, g->strt.size * 2);  
    list = &g->strt.hash[lmod(h, g->strt.size)];  /* recompute with new size */  
  }  
  ts = createstrobj(L, str, l, LUA_TSHRSTR, h);  
  ts->hnext = *list;  
  *list = ts;  
  g->strt.nuse++;  
  return ts;  
}  
  
/* 对字符串按步长hash的函数 */  
unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) {  
  unsigned int h = seed ^ cast(unsigned int, l);  
  size_t l1;  
  size_t step = (l >> LUAI_HASHLIMIT) + 1;  
  for (l1 = l; l1 >= step; l1 -= step)  
    h = h ^ ((h<<5) + (h>>2) + cast_byte(str[l1 - 1]));  
  return h;  
}  

—|—

糖果

糖果
LUA教程

如果不小心安装错 SQL Server 为 Evaluation 的版本,要小心当超过 180 天之后,系统就会无法正常使用了 这几天遇到一个蛮特别的案例,原本收到的问题是 “维护计划” 忽然无法使用,即便是里面没有任何的Task,都无法顺利地执行。但从对方所提供的错误消...… Continue reading

PLUM NIZ静电容键盘怎么样?

Published on September 25, 2020

程序员如何选择合适的机械键盘

Published on September 18, 2020