探索Lua5.2內部實現:TString

原文http://blog.csdn.net/yuanlin2008/article/details/8423923

Lua使用TString結構體代表一個字符串對象。

[cpp] view plain copy print ?

1. /* 
2. ** Header for string value; string bytes follow the end of this structure 
3. */  
4. typedef  union  TString {  
5.   L_Umaxalign dummy;   /* ensures maximum alignment for strings */  
6.   struct  {  
7.     CommonHeader;  
8.     lu_byte extra;   /* reserved words for short strings; "has hash" for longs */  
9.     unsigned  int  hash;  
10.     size_t  len;   /* number of characters in string */  
11.   } tsv;  
12. } TString;  

hash用來記錄字符串對應的哈希值，len用來記錄字符串長度。

這個結構體其實只是字符串對象的頭數據，後面緊跟著字符竄內容和一個'\0'結尾。字符串"abc"對應的TString對象應該如下圖所示：

字符串對象的最終大小應該是TString的大小+字符串長度+1。

TString對應的lua對像類型為LUA_TSTRING。根據字符串長度（luaconf.h中的LUAI_MAXSHORTLEN，默認為40）的不同，TString對像還被分成兩種子類型：LUA_TSHRSTR（短字符串）和LUA_TLNGSTR（長字符串）。

對於短字符串，在實際使用中一般用來作為索引或者需要進行字符串比較。不同於其他的對象，Lua並不是將其連接到全局的allgc對象鍊錶上，而是將其放到全局狀態global_State中的字符串表中進行管理。這個字符串表是一個stringtable類型的全局唯一的哈希表。當需要創建一個短字符串對象時，會首先在這個表中查找已有對象。所有的短字符串都是全局唯一的，不會存在兩個相同的短字符串對象。如果需要比較兩個短字符串是否相等，只需要看他們指向的是否是同一個TString對象就可以了，速度非常快。如果短字符串對象的extra > 0，表示這是一個系統保留的字符串。extra的值直接對應著詞法分析時的一個token值，這樣可以加速詞法分析的速度。

對於長字符串，與短字符串相反，在實際使用中一般只是用來存儲文本數據，很少需要比較或者索引。所以長字符串直接被掛接到allgc鍊錶上當作普通的對象來處理。Lua不會對新創建的長字符串對象計算哈希值，也不保證長字符串對象的唯一性。當長字符串需要被用來當作索引時，會為其計算一次哈希值，並使用extra來記錄是否已經為其計算了哈希值。

計算字符串的哈希值需要遍歷字符串的每一個字符，如果字符串很長，會非常影響效率。對於大於等於32的字符串，Lua不會遍歷每個字符，而是按照一定的間隔獲取字符，最多遍歷31次。這使得字符串的哈希值計算與字符串長度無關。

如果要將Lua部署到web上面來處理大量的基於文本的http請求，文本處理的安全性就變得尤為重要。為了防止Hash DoS攻擊，字符串哈希值生成需要一個seed，這個seed是每次啟動Lua時隨機生成的。這就使不同的Lua實例對於同一個字符串會有不同的哈希值。