-- Lua tables 分析 (1) Lua的tables实现了关联数组,关联数组指不仅可以通过数字下标检索数据,还可以通过别的类型的值检索数据.Lua中除了nil以外的类型都可以作为tables的索引下标.另外tables没有固定的大小,你可以根据需要动态的调整他的大小.tables是Lua主要的也是唯一的数据结构,我们可以通过他实现传统数组, 符号表, 集合, 记录(pascal), 队列, 以及其他的数据结构.Lua的包也是使用tables来描述的,io.read意味着调用io包中的read函数,对Lua而言意味着使用字符串read作为key访问io表. --引自PIL 2.5 tables的实现被分成了两个部分: 核心由ltable.[ch]完成,提供了table的基本存取方法, 外部table库(ltablib.c)提供了辅助操作接口(concat, foreach, foreachi, getn, maxn, insert, remove, setn, sort). 我们先来看看tables的逻辑布局. ------------------------ 一个table由array部分和hash部分组成. array part: 跟C传统的数组相当,非负整数下标的值被保存在该部分(正常情况下,后续会介绍一些特殊情况).特点是访问速度快. hash part: Table结构头: typedef struct Table { 对我们关心的几个成员做了注释, 已经比较容易看懂. Node为(key, value)对. 我们来看看创建表和释放表,比较常规. luaH_new() -- 创建新表 调用setarrayvector()为表的数组项分配内存 返回表指针 luaH_free() -- 释放表 在某些情况下表的大小会被调整, LUA_CORE提供该操作的对外接口是luaH_resizearray().而该接口参数里仅有数组部分大小, hash部分大小通过 我们这里要讲的是resize(), 它不单是作为外部接口的内部实现,还被很多内部接口使用(比如rehash()) 大家都知道,在两种情况下会使用resize(), 扩大和缩小.对于扩大表的操作,只需直接调用扩大内存的接口调整数组部分即可.而缩小则会涉及到截断部分的数据往哪里摆放的问题. 刚才讲到了resize对array part的处理, 而hash part的处理没什么变化, 不论扩大缩小, 都被逐条重新插入到新hash part里, 最后把旧hash part释放. 接下来,我们要讲的是表对数据的基本存取操作.提供的外部接口有: 通用取: luaH_get() 数字下标取: luaH_getnum() 字符串下标取: luaH_getstr()
通用取也是对key类型做了判断后选择调用luaH_getnum()或者luaH_getstr(), 如果key类型不属于nil, string, number, 则计算出key主位置(mainposition()), 沿该位置向后(gnext())逐一比较.下面我们分别来讲讲num取和str取. num下标取: 在luaH_get()里确定了key属于非负整数下标后(还不确定是否有效), 调用luaH_getnum(). 在luaH_getnum里判断非负整数下标是否有效(下标满足大于等于1, 并且小于等于array part总大小). 如果为有效下标,直接从array成员里取值. string下标取: 这个则只有一种机制, 计算key hash值(hashstr()), 逐节点向后(gnext())搜索匹配(ttisstring() && rawtsvalue() == key). 取值的大概过程就是这样.在讲存值之前,我们先来解释一下为什么上面hash后还需要逐节点去搜索匹配.这是table对hash碰撞的处理.一个新key要插入到table的hash part时,会先调用newkey(), newkey()用来把新key插入到表的hash部分里.首先计算key的主位置,如果已经发生碰撞,会调用getfreepos()来获取一个空闲的节点. static Node *getfreepos (Table *t) { 一个空闲节点链表, lastfree指向的是链表头(高地址), 用递减往下依次查找.碰到第一个nil就返回该节点.如果返回了NULL, newkey()将调用rehash()来扩大table大小, 并重新计算hash part.之后调用luaH_set()来重新插入新值(newkey()是被luaH_set*()调用的). 插个一小段其他内容,希望没打断思路,下面我们继续来看看如何存, 存提供了三个对外接口: luaH_set() 跟取一样, luaH_set()也是不区分key类型的通用接口.而它的通用源自luaH_get().一开始调用luaH_get()查找该value是否存在, 存在则直接返回值.不存在则调用newkey()完成添加动作. 这里要注意的是当value存在表里,将被直接返回, 而key的hash value存在则会被做碰撞处理. 接下来我们讲讲挨个取值luaH_next(), 也就是使用解释器时用到的pairs()所使用的table底层接口. for k, v pairs(t) do print(k .. ' ' .. v) end 会按何种顺序来取表里的元素呢? 看过代码后你会发现, luaH_next()首先定位key的索引值(findindex()),若在sizearray的范围内,则直接从array part取下一个值.不然则从hash part里取值. 而for的顺序显然跟传入key的顺序有关.从Lapi.c: line 972; Lbaselib.c: line 228-229可以知道.key是从1开始传的. 所以for的顺序应该是先遍历完array part, 然后再按index值递增的方式去遍历hash part. 为此,我做了个实验: test.lua for k, v in pairs(t) do print(k .. ' ' .. v) end output: 跟上述的分析是一致的,0下标也会被归入hash part.先遍历array part, 再次是hash part. 遍历顺序是按index来的,所以hash part部分的顺序看起来有点随机. 这里也许有的同志会问,为什么t={0,0,0,0,0,0,0,0,0}来得这样,是否多此一举.如果没预先扩大table的sizearray, 那么后续的数字下标会被插入hash part. 可以通过luac -l test.lua看到: 该例不预先扩大可以,但如果你断了序列,比如t[3]=1099没了.那后续的元素都将被插入到hash part.
我们再来看看下一个接口luaH_getn(),查找table边界,也就是返回有效的最大索引值. 用二分查找array part的最大值, 前提是sizearray大于0并且array[sizearray-1]等于nil.反之则查找hash part的最大边界(unbound_search()),按照逻辑组织关系,array part在前,hash part在后. luaH_getn()被用在了Lapi.c: lua_objlen();用来计算表对象的大小. tables的核心接口介绍得差不多了,这里对一些内部细节没过分介绍,我想这些在代码里写得很清楚,比如hashnum(), hashstr()的实现等. 最后,我们从头到尾回顾一下: 1. 介绍了table的大致结构. 还未能通读lua全部代码, 难免有理解不到位或错误的地方,还望来信指正. tables外层lib接口的实现我们将在后续的文章看到. |
- 本文固定链接: http://jingyan.idoubi.net/2889.html
- 转载请注明: 游戏创作者大陆 于 逗分享开发经验 发表