Lua源码分析 - 数据结构篇 - 字符串池实现（05）

joe

目录

一、字符串 - 数据结构

二、字符串 - 初始化luaS_init

三、字符串 - 创建一个字符串luaS_new

四、字符串 - 清除缓存luaS_clearcache

前面两章我们讲解了Lua的整个栈操作。本篇文章开始，我们重点阅读一下Lua的几个重要数据结构：字符串、内存操作、对象操作等。

字符串操作对应的文件：lstring.c

一、字符串 - 数据结构
Lua的字符串管理都会统一挂载到global_State全局状态机上。

字符串都会存储在TString对象结构上。Lua的字符串管理分两种类型：链表方式存储（短字符串（<40）） 和 HashMap 缓存方式

链表方式：存储在stringtable strt; 链表结构上
缓存方式：存储在TString *strcache[STRCACHE_N][STRCACHE_M] HashMap的结构上。
PS：这里有一个点没看懂，当调用*luaS_new函数，字符串存储会走缓存方式；当单独调用luaS_newlstr函数，短字符串会统一管理，但是长字符串就没有统一地方管理。这块还没太明白

通过下面这个大图，可以一眼看清楚整个Lua的字符串管理方式。



/* 字符串管理 */
stringtable strt;  /* 处理小于40的字符串，链表结构 - hash table for strings */
TString *strcache[STRCACHE_N][STRCACHE_M];  /* 字符串缓存，HashMap - cache for strings in API */

/*
** Header for string value; string bytes follow the end of this structure
** (aligned according to 'UTString'; see next).
** 字符串结构
*/
typedef struct TString {
  CommonHeader;
  lu_byte extra;  /* reserved words for short strings; "has hash" for longs */
  lu_byte shrlen;  /* 字符串长度 length for short strings */
  unsigned int hash; //hash值，字符串table 索引值
  union {
    size_t lnglen;  /* length for long strings 长字符串存储形式 */
    struct TString *hnext;  /* 链表形式存储下一个TSring，短字符串用到 linked list for hash table */
  } u;
} TString;
二维数组strcache的表索引，通过字符串hash值，并对桶做求余实现。

桶的默认值是：STRCACHE_N，默认53个桶
链表的默认长度：STRCACHE_M，默认2个元素
但是list长度是STRCACHE_M=2，list比较小，估计作者认为hash冲突的概率会非常小，同时每次都会将最早的元素element淘汰出去
unsigned int i = point2uint(str) % STRCACHE_N;  /* hash */
二、字符串 - 初始化luaS_init
在全局状态机f_luaopen函数中，对字符串池进行了初始化。

初始化主要做两件事情：初始化链表、初始化缓存池

/*
** Initialize the string table and the string cache
** 初始化字符串链表和字符串缓存
*/
void luaS_init(lua_State *L) {
        global_State *g = G(L);
        int i, j;
        luaS_resize(L, MINSTRTABSIZE); /* 默认大小128 字符串table initial size of string table */
        /* pre-create memory-error message */
        g->memerrmsg = luaS_newliteral(L, MEMERRMSG); //错误处理字符串
        luaC_fix(L, obj2gco(g->memerrmsg)); /* it should never be collected */
        for (i = 0; i < STRCACHE_N; i++) /* 缓存表中填充默认支付 fill cache with valid strings */
                for (j = 0; j < STRCACHE_M; j++)
                        g->strcache[j] = g->memerrmsg;
}
三、字符串 - 创建一个字符串luaS_new
创建字符串函数有两个：luaS_new 和 luaS_newlstr

luaS_new：创建一个新的字符串，带缓存方式
luaS_newlstr：创建一个新的字符串，不带缓存
这里有一点没明白，如果调用了 luaS_newlstr，并且是长字符串，这种方式如何来管理和跟踪这个内存分配？因为两个函数遍历了整个代码，都会使用，有些地方走缓存，有些地方不走缓存。

/*
** new string (with explicit length)
** 创建一个存新的字符串，不带缓存
** 字符串不能超过最大限制
** 新的字符串会memcpy拷贝一个副本，挂载到TString结构上
*/
TString *luaS_newlstr(lua_State *L, const char *str, size_t l) {
        if (l <= LUAI_MAXSHORTLEN) /* short string?  40字节 */
                return internshrstr(L, str, l);
        else {
                TString *ts;
                if (l >= (MAX_SIZE - sizeof(TString)) / sizeof(char))
                        luaM_toobig(L);
                ts = luaS_createlngstrobj(L, l);
                memcpy(getstr(ts), str, l * sizeof(char)); //内存拷贝副本
                return ts;
        }
}

/*
** Create or reuse a zero-terminated string, first checking in the
** cache (using the string address as a key). The cache can contain
** only zero-terminated strings, so it is safe to use 'strcmp' to
** check hits.
** 创建一个新的字符串，带缓存方式
** 会调用luaS_newlstr方法
** 1. 先通过字符串，获取字符串hash值
** 2. 通过hash值取字符串，如果相同的字符串已经存在，则复用
** 3. 否则创建一个新的字符串
**
** 字符串Table表，通过字符串的hash值找到list
** 但是list长度是STRCACHE_M=2，list比较小，估计作者认为hash冲突的概率会非常小
** 同时每次都会将最早的元素element淘汰出去
*/
TString *luaS_new(lua_State *L, const char *str) {
        unsigned int i = point2uint(str) % STRCACHE_N; /* hash */
        int j;
        TString **p = G(L)->strcache;
        for (j = 0; j < STRCACHE_M; j++) {
                if (strcmp(str, getstr(p[j])) == 0) /* hit? */
                        return p[j]; /* that is it */
        }
        /* normal route */
        for (j = STRCACHE_M - 1; j > 0; j--)
                p[j] = p[j - 1]; /* move out last element */
        /* new element is first in the list */
        p[0] = luaS_newlstr(L, str, strlen(str));
        return p[0];
}
四、字符串 - 清除缓存luaS_clearcache
/*
** Clear API string cache. (Entries cannot be empty, so fill them with
** a non-collectable string.)
** 清楚缓存
*/
void luaS_clearcache(global_State *g) {
        int i, j;
        for (i = 0; i < STRCACHE_N; i++)
                for (j = 0; j < STRCACHE_M; j++) {
                        if (iswhite(g->strcache[j])) /* will entry be collected? */
                                g->strcache[j] = g->memerrmsg; /* replace it with something fixed */
                }
}

————————————————
版权声明：本文为CSDN博主「老码农zhuli」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/initphp/article/details/104126140