- 浏览: 333898 次
- 性别:
- 来自: 福建福州
文章分类
最新评论
-
jw72jw:
最后这个是打表求值
LUA源码分析三:table分析(1) -
dyllove98:
"一些非常重要的问题,涉及面少。那这个时候,我更崇尚 ...
乱写:团队里的独裁和民主一点看法 -
jvmlover:
被踩10次了,什么思想感情啊。
LUA源码分析三:table分析(1) -
chenchenfly99:
chenchenfly99 写道
MMO游戏终极内测开服一周,问题记录 -
chenchenfly99:
...
MMO游戏终极内测开服一周,问题记录
版本整理日期:2011/3/27
分析函数:getn,tinsert
table在里面数据方式比较直观,但是算法很复杂。一些算法的坑会慢慢补上。
先总括下table的数据结构:
1)由一个hash表和一个数组构成,当插入一个小标元素,会根据当前数组的大小决定插入哪儿
2)hash表上会有冲突,通过一个链表的形式组织冲突的元素
3)通过源码,我们还能得到的是一些table的使用技巧方式,尤其是在大数据量上的效率开销
4)我在分析的方法上是这样的:首先分析luaH_getn这个函数,通过获取的方式来对table存储的方式有个大致了解;然后分析tinsert,两者进行迭代阅读
//ltable.c int luaH_getn (Table *t) { //array数组个数 unsigned int j = t->sizearray; if (j > 0 && ttisnil(&t->array[j - 1])) { /* there is a boundary in the array part: (binary) search for it */ unsigned int i = 0; while (j - i > 1) { unsigned int m = (i+j)/2; if (ttisnil(&t->array[m - 1])) j = m; else i = m; } return i; } /* else must find a boundary in hash part */ else if (t->node == dummynode) /* hash part is empty? */ return j; /* that is easy... */ else return unbound_search(t, j); }
//ltable.c static int unbound_search (Table *t, unsigned int j) { unsigned int i = j; /* i is zero or a present index */ j++; /* find `i' and `j' such that i is present and j is not */ while (!ttisnil(luaH_getnum(t, j))) { i = j; j *= 2; if (j > cast(unsigned int, MAX_INT)) { /* overflow? */ /* table was built with bad purposes: resort to linear search */ i = 1; while (!ttisnil(luaH_getnum(t, i))) i++; return i - 1; } } /* now do a binary search between them */ while (j - i > 1) { unsigned int m = (i+j)/2; if (ttisnil(luaH_getnum(t, m))) j = m; else i = m; } return i; }
观察第一个while,有2种情况
1.对j进行判断,i等于j扩大两倍前的值。如果luaH_getnum取到的值为空,则退出循环
2.如果j扩大两倍大于MAX_INT时,则以i从1开始,线性的查找。(是否可以优化为从j/4开始?)
经过第一个while后,取到下面的情况。
有值,有值,有值(i在这),有值(下一轮while要查找的目标),空值,空值(j可能在这)
继续二分查找,找到最末尾有值的下标。然后返回。
那么这个函数的功能就可以总结为,先从1-MAX_INT中探测到一个范围,然后从这个范围中查找
末尾的有值节点
继续跟入luaH_getnum
//ltable.c /* ** search function for integers */ const TValue *luaH_getnum (Table *t, int key) { /* (1 <= key && key <= t->sizearray) */ /* cast很熟悉了,值转换. 从这个判断可以得到信息是sizearray可以存储一定量的数据, 如果超出则用其他方式存储 */ if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray)) return &t->array[key-1]; else { lua_Number nk = cast_num(key); Node *n = hashnum(t, nk); do { /* check whether `key' is somewhere in the chain */ /* 这里也预读到一些信息 1.基本上不是为了出错校验 2.看来是和插入的算法有关。插入的算法可能会导致一些重复 3.能存多少数据,跟nk的类型有关。虽然nk是double,但是小数能否用到 还得继续跟。否则就是一个2^32的总数了 */ if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)), nk)) return gval(n); /* that's it */ else n = gnext(n); } while (n); return luaO_nilobject; } }
else段里走的流程大概是,根据nk从hashnum里面取到Node,然后进行判断,如果不符合则next个Node.
看来hashnum是个算法。先把gkey,nvalue,luai_numeq几个宏和Node结构体拆开看看
//ltable.c #define gkey(n) (&(n)->i_key.nk) #define gval(n) (&(n)->i_val) #define gnext(n) ((n)->i_key.nk.next) //luaconf.h #define luai_numeq(a,b) ((a)==(b)) //lobject.h #define nvalue(o) check_exp(ttisnumber(o), (o)->value.n) //lobject.h #define TValuefields Value value; int tt typedef union TKey { struct { TValuefields; struct Node *next; /* for chaining */ } nk; TValue tvk; } TKey; typedef struct Node { TValue i_val; TKey i_key; } Node;
TValuefields;其实也是个TValue的结构体。用宏扩展开,可以少一层访问的封装。或者可以看成是
TValue多加了个Node *Next,这样可以保证和ttisnumber兼容访问。有了这些,那么可以对这句重新
认识
//hashnum表示一种算法,取到目标节点 Node *n = hashnum(t, nk); do { /* 算法导致的节点可能会多个,则根据key里的n来和nk校验 这个就很好理解了,比如1-100算到的因子都是20。20这个node下可能挂了100个节点。然后 依次比较取出正确的。 */ if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)), nk)) }while(n)
最后来看下hashnum算法
//lobject.h #define twoto(x) (1<<(x)) #define sizenode(t) (twoto((t)->lsizenode)) //ltable.h #define gnode(t,i) (&(t)->node[i]) //ltable.c /* ** for some types, it is better to avoid modulus by power of 2, as ** they tend to have many 2 factors. */ /* 算法比想象中的简单。sizenode对table里的lsizenode取一个指数,在源代码也能找到这段注释: lu_byte lsizenode; /* log2 of size of `node' array */ -1表示0~(1<<(x)-1)范围,|1没弄明白什么意思。防止出现小于0的吗? hashmod仅仅是为了大下标的处理。 */ #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1))))
//跟调do..while里面的hashnum函数 static Node *hashnum (const Table *t, lua_Number n) { unsigned int a[numints]; int i; if (luai_numeq(n, 0)) /* avoid problems with -0 */ return gnode(t, 0); /* lua_Number是个double型,这里是把n的高低4个字节相加, 作为去模的对象 */ memcpy(a, &n, sizeof(a)); //#define numints cast_int(sizeof(lua_Number)/sizeof(int)) for (i = 1; i < numints; i++) a[0] += a[i]; return hashmod(t, a[0]); }
那么luaH_getnum这个函数就很好理解了。首先判断传入的key是否满足当前sizearray,如果满足则返回。
否则可以看成一个大下标的存储,根据hashmod算法取到节点。
//ltablib.c static int tinsert (lua_State *L) { //调用的是getn,取回table的元素总数。 imt e = aux_getn(L, 1) + 1; /* first empty element */ int pos; /* where to insert new element */ switch (lua_gettop(L)) { case 2: { /* called with only 2 arguments */ pos = e; /* insert new element at the end */ break; } /* 如果插入的范围小于当前元素总数,则移出空位 */ case 3: { int i; pos = luaL_checkint(L, 2); /* 2nd argument is the position */ if (pos > e) e = pis; /* `grow' array if necessary */ for (i = e; i > pis; i--) { /* move up elements */ lua_rawgeti(L, 1, i+1); lua_rawseti(L, 1, i); /* t[i] = t[i-1] */ } break; } default: { return luaL_error(L, "wrong number of arguments to " LUA_QL("insert")); } } luaL_setn(L, 1, e); /* new size */ lua_rawseti(L, 1, pos); /* t[pos] = v */ return 0; }
//lapi.c LUA_API void lua_rawseti (lua_State *L, int idx, int n) { StkId o; lua_lock(L); api_checknelems(L, 1); o = index2adr(L, idx); api_check(L, ttistable(o)); /* L->top上的排列为 table, 插入的位置,插入的值. L->top-1不知道取的啥值,略过。跟调发现取的是插入的值。 luaH_setnum的名字比较奇怪,按道理叫luaH_getnum比较合适,不过也间接 的透露了信息, 1.首先要确保空间节点的存在 2.对于空间必然有一个扩展的操作,而不是预先安排 */ setobj2t(L, luaH_setnum(L, hvalue(o), n), L->top-1); //这段先不管 luaC_barriert(L, hvalue(o), L->top-1); //栈减1 L->top--; lua_unlock(L); }
//ltable.c //这个函数叫setnum, TValue *luaH_setnum (lua_State *L, Table *t, int key) { /* 看到了吧,会先尝试一个获取。取不到则进行扩展key的节点 luaH_getnum前面分析过了,这里略过 */ const TValue *p = luaH_getnum(t, key); if (p != luaO_nilobject) return cast(TValue *, p); else { TValue k; setnvalue(&k, cast_num(key)); return newkey(L, t, &k); } }
//ltable.c /* ** inserts a new key into a hash table; first, check whether key's main ** position is free. If not, check whether colliding node is in its main ** position or not: if it is not, move colliding node to an empty place and ** put new key in its main position; otherwise (colliding node is in its main ** position), new key goes to an empty position. */ /* 有点悲剧,这个函数看来比较复杂,否则也不会这么多注释。段首所透露的信息大概如下: 1.key所对应的hash节点可能存在可能不存在(也就是冲突) 2.如果存在,那么有2个点需要互斥:main position、an empty place。暂时不知道 这2个所指什么意思 3.通过几个if not,otherwise可知,main position只能有一个key占着,剩下的要去 an empty place 4.虽然key所对应的hash节点在,但是main position不一定有key. */ static TValue *newkey (lua_State *L, Table *t, const TValue *key) { /* 又冒了一个mainposition出来,跟调一下发现是通过hash算法得到的节点 上文跟过,不细展开了 */ Node *mp = mainposition(t, key); /* !ttisnil(gval(mp))表示一个新的节点, mp == dummynode同上。 先解决if之外的。之外的意思很简单,把值给新得到的节点。 对应Node结构体查看 typedef struct Node { TValue i_val; TKey i_key; //把key记录在i_key结构里边 } Node; 继续刨下面难的那段 */ if (!ttisnil(gval(mp)) || mp == dummynode) { Node *othern; /* getfreepos里面操作的是t->lastfree值,怎么来的不知道。 只知道也是个指针数组 */ Node *n = getfreepos(t); /* get a free place */ if (n == NULL) { /* cannot find a free place? */ /* 如果为空,那么rehash一个值,这个值相对比较NB, 不然luaH_set又要执行newkey。我把这段放到了后面,大家 可以先跳到后面1.1 */ rehash(L, t, key); /* grow table */ return luaH_set(L, t, key); /* re-insert key into grown table */ } lua_assert(n != dummynode); /* 第一个if可以反过来分析: 最终目的是把mp赋给n n是作为一个末尾节点。说明这是一个链表结构 othern节点是通过key2tval宏取得的,该宏扩展开来&(n)->i_key.tvk。可以看成是key 的value值。 while()语句可以得出一个互斥信息:通过key算出来的mp是同个节点,因此把一样的节点 串起来。 */ othern = mainposition(t, key2tval(mp)); if (othern != mp) { /* is colliding node out of its main position? */ /* yes; move colliding node into free position */ while (gnext(othern) != mp) othern = gnext(othern); /* find previous */ gnext(othern) = n; /* redo the chain with `n' in place of `mp' */ *n = *mp; /* copy colliding node into free pos. (mp->next also goes) */ gnext(mp) = NULL; /* now `mp' is free */ setnilvalue(gval(mp)); } /* 这段就很简单了,说明当前还没有插入其他的相同算法key, 则n做为链表头 */ else { /* colliding node is in its own main position */ /* new node will go into free position */ gnext(n) = gnext(mp); /* chain new position */ gnext(mp) = n; mp = n; } } gkey(mp)->value = key->value; gkey(mp)->tt = key->tt; luaC_barriert(L, t, key); lua_assert(ttisnil(gval(mp))); return gval(mp); }
/* 这段函数算法可以暂时不分析得非常非常细致。我们可以先用黑盒测试它的一些行为。 比如用insert插入的两次下标不在同个位置,那么getn得到的是0;如果插入的位置是序列 的,那么rehash会认为是排列紧密的,getn得到是2。可以看出,这个函数主要是个重新 归纳和分配节点算法的东西。后面留个坑,慢慢补。那么table中插入元素的排列位置如下图: */ static void rehash (lua_State *L, Table *t, const TValue *ek) { int nasize, na; int nums[MAXBITS+1]; /* nums[i] = number of keys between 2^(i-1) and 2^i */ int i; int totaluse; //MAXBITS为 26。清零 for (i=0; i<=MAXBITS; i++) nums[i] = 0; /* reset counts */ //小段1.1.1,计算这个数组中已有的元素个数 nasize = numusearray(t, nums); /* count keys in array part */ totaluse = nasize; /* all those keys are integer keys */ //小段1.1.2,计算已使用的hash节点个数 totaluse += numusehash(t, nums, &nasize); /* count keys in hash part */ /* count extra key */ //小段1.1.3,调用的核心算法也是hash的一种 nasize += countint(ek, nums); totaluse++; /* compute new size for array part */ //小段1.1.4,没看太懂,只是做了个黑盒测试。会根据下标重算一个大小 na = computesizes(nums, &nasize); /* resize the table to new computed sizes */ //小段1.1.5,这个版本留坑。第一次table目的已达到 resize(L, t, nasize, totaluse - na); }
/* 1.1.1 先观察退出的条件:i>lim, lim为ttlg,ttlg变化范围是个2^lg, i是个ttlg叠加的和,包括空和非空的元素. 而当i>lim时,lim的值实际上是t->sizearray。这个思路和上文的while 很像,都是一个预加的试探方法。当ttlg叠加的和大于t->sizearray,说明已经统计完毕。 */ static int numusearray (const Table *t, int *nums) { int lg; int ttlg; /* 2^lg */ int ause = 0; /* summation of `nums' */ int i = 1; /* count to traverse all array keys */ for (lg=0, ttlg=1; lg<=MAXBITS; lg++, ttlg*=2) { /* for each slice */ int lc = 0; /* counter */ int lim = ttlg; if (lim > t->sizearray) { lim = t->sizearray; /* adjust upper limit */ if (i > lim) break; /* no more elements to count */ } /* count elements in range (2^(lg-1), 2^lg] */ for (; i <= lim; i++) { if (!ttisnil(&t->array[i-1])) lc++; } //lg,表示对应的下标 nums[lg] += lc; ause += lc; } return ause; }
/* 1.1.2 返回值totaluse,表示非空的t->node数 ause,通过countint统计 */ static int numusehash (const Table *t, int *nums, int *pnasize) { int totaluse = 0; /* total number of elements */ int ause = 0; /* summation of `nums' */ //#define sizenode(t) (twoto((t)->lsizenode)) int i = sizenode(t); while (i--) { Node *n = &t->node[i]; if (!ttisnil(gval(n))) { //#define key2tval(n) (&(n)->i_key.tvk) //countint见1.1.2.1 ause += countint(key2tval(n), nums); totaluse++; } } *pnasize += ause; return totaluse; }
/* 1.1.2.1 / 1.1.3 */ static int countint (const TValue *key, int *nums) { int k = arrayindex(key); if (0 < k && k <= MAXASIZE) { /* is `key' an appropriate array index? */ nums[ceillog2(k)]++; /* count as such */ return 1; } else return 0; } /* ** returns the index for `key' if `key' is an appropriate key to live in ** the array part of the table, -1 otherwise. */ //没看太懂,为了浮点数偏差比较吗? static int arrayindex (const TValue *key) { if (ttisnumber(key)) { lua_Number n = nvalue(key); int k; //一条汇编扩展,浮点变整形 lua_number2int(k, n); if (luai_numeq(cast_num(k), n)) return k; } return -1; /* `key' did not match some condition */ } //ceillog2对应 //没看懂,略过 #define ceillog2(x) (luaO_log2((x)-1) + 1) int luaO_log2 (unsigned int x) { static const lu_byte log_2[256] = { 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8 }; int l = -1; while (x >= 256) { l += 8; x >>= 8; } return l + log_2[x]; }
评论
发表评论
-
lua调试器:运行时的值查看
2011-05-04 17:55 3862最近在看一个lua调试器,remdebug,实现远程断点 ... -
LUA源码分析九:Debug."getlocal"
2011-04-28 17:26 4664函数:{"getlocal", db ... -
LUA源码分析八:小总结,完整分析dofile的过程和堆栈
2011-04-27 17:57 6867关于一些语法包装的问题不涉及(可见前面某篇),主要对 ... -
LUA源码分析七:require的函数调用堆栈
2011-04-26 17:23 7148require的调用其实很简单,熟悉完env的设置后,其 ... -
LUA源码分析六:环境设置
2011-04-22 18:50 4400LUA源码分析五:环境设置 版本日期 201 ... -
LUA源码分析五:元表
2011-04-22 00:08 3044版本整理日期:2011/4/21 元表其实就是可 ... -
LUA源码分析四:通过luaL_dofile分析IO载入流程和内部函数调用结构
2011-03-31 21:11 8570版本整理日期:2011/3/31 本篇主要说明两个点: ... -
LUA源码分析二:了解lua的文件结构和思考方式
2011-03-27 23:21 4693版本整理日期:2011/3/27 对lmathlib.c ... -
LUA源码分析一:总括
2011-03-27 23:21 43561.lua语言短小,而且是我目前开发用到的语言之一,我会把它作 ...
相关推荐
Lua源码分析Lua源码分析Lua源码分析Lua源码分析Lua源码分析Lua源码分析Lua源码分析Lua源码分析
所有版本LUA源码 lua-5.3.5 lua-5.3.4 lua-5.3.3 lua-5.3.2 lua-5.3.1 lua-5.3.0 lua-5.2.4 lua-5.2.3 lua-5.2.2 lua-5.2.1 lua-5.2.0 lua-5.1.5 lua-5.1.4 lua-5.1.3 lua-5.1.2 lua-5.1.1 lua-5.1 lua-5.0.3 lua-...
这个是lua的源码分析,lua的源码写的非常好,整个设计的结构非常巧妙,不管是对于学习lua本身还是c语言的数据结构都非常有帮助。
第一章概览由甮由源文件划分 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮 甮
里面有风云 大神写的对lua 的源码剖析。还有lua5.2源码。
详细描述Lua和C之间相互传递Table类型数据 /* ====================================================== */ // 遍历Lua传入的Table类型参数, 获取它的Key/Value, 其关键操作是 lua_next() // lua_next() 返回1表示...
Lua 源码赏析.pdf, 其中有着非常棒的lua源代码资源可供学习。下载文件为该书的百度云连接地址。
云风写的Lua源码欣赏,基于lua5.2版本源代码解析,对于初初学习lua语言的有很不错的帮助
转自 云风'blog 2013-1-31 22:49:58 "我上次通读 Lua 的源代码时,Lua 还在 5.1 。当然 Lua 5.0 我也读过,4.0 和 3.2 则读的不多。 最近有一点空闲,想续写我那本 Lua 源码欣赏。按我心里的计划,还有大约 6 章。...
lua库函数
Lua CJSON 为 Lua 语言提供高性能的 JSON 解析器和编码器,其性能比纯 Lua 库要高 10 到 20 倍。Lua CJSON 完全支持 UTF-8 ,无需依赖其他非 Lua/LuaJIT 的相关包。
做了那么多 Lua 脚本破解,我们来尝试写一个不能被破解的加密。 所谓不能被破解,并不是真正不能被破解,只是在没有密码的情况下很难破解。
云风新作-----lua源码导读。目前网上最好的lua源代码阅读教程。帮助你快速理解lua实现原理。
lua源码欣赏 lua源代码分析,来之云风!
Lua是一个小巧而简单的语言,因为Lua不致力于做C语言已经做得很好的领域,比如:性能、底层操作以及与第三方软件的接口。Lua依赖于C去做完成这些任务。Lua所提供的机制是C不善于的:高级语言、动态结构、简洁、易于...
通过执行python脚本(jsonToLua.py)
a utf-8 support module for Lua and LuaJIT 源码地址:https://github.com/starwing/luautf8 编译后可用的库: Linux版:lua-utf8.so Windows版:lua-utf8.dll(若是用在openresty中,openresty版本需使用32位版本...
redis-lua 是 Redis 的 Lua 语言的客户端开发包。 示例代码: require 'redis' local redis = Redis.connect('127.0.0.1', 6379) local response = redis:ping() -- true redis:set('usr:nrk', 10) redis:set('usr...
讲解lua语言的实现源代码,由于lua是基于C语言实现,所以需要有一定C语言基础。 请配合《the implementation of Lua5.0中文版》一起阅读。 http://download.csdn.net/detail/havesnag/5071833