南充能够建设网站的公司有,重庆seo优化公司,公需科目在哪个网站做,wordpress the7数据库1 概述2 数据结构2.1.表Table2.2 键TKey2.3 节点#xff08;键值对#xff09;Node3 操作算法3.1 查找3.1.1 通用查找luaH_get3.1.2 根据字符串查找 luaH_getstr3.1.3 根据整数查找 luaH_getnum3.2 新增元素/修改元素/删除元素 luaH_set系列3.2.1 根据key获取或创建一个value…1 概述2 数据结构2.1.表Table2.2 键TKey2.3 节点键值对Node3 操作算法3.1 查找3.1.1 通用查找luaH_get3.1.2 根据字符串查找 luaH_getstr3.1.3 根据整数查找 luaH_getnum3.2 新增元素/修改元素/删除元素 luaH_set系列3.2.1 根据key获取或创建一个value: luaH_set3.2.2 根据数字获取或创建一个value: luaH_setnum3.2.3 根据数字获取或创建一个value: luaH_setstr3.3 新建表 luaH_new3.4 迭代表 luaH_next3.5 取长度 luaH_getn1 概述
lua的表有数组部分和哈希部分数组部分的索引从1开始
2 数据结构
2.1.表Table
(lobject.h) Table
typedef struct Table
{CommonHeader;//表示表中提供了哪些元方法起初为1当查找后若有此元方法则该元方法对应的flag为0若无则对应flag为1下次查找时发现该位为1说明该表无此元方法则不查表了节约性能。lu_byte flags;//散列表大小的以2为底的对数因为散列部分规定大小就是2的幂所以这样存lu_byte lsizenode;//该表的元表struct Table* metatable;//指向数组部分的指针TValue* array;//指向散列桶数组起始位置的指针Node* node;//指向散列桶数组最后位置的指针Node* lastfree;//GC相关的链表todo以后再说GCObject* gclist;//数组部分的大小int sizearray;
} Table;2.2 键TKey
(lobject.h) TKey
typedef union TKey
{struct {TValuefields;//#define TValuefields Value value; int ttstruct Node* next;//指向下一个Node} nk;TValue tvk;
} TKey;2.3 节点键值对Node
(lobject.h) Node
typedef struct Node
{TValue i_val;//值TKey i_key;//键
} Node;3 操作算法
3.1 查找
3.1.1 通用查找luaH_get
(ltable.c) luaH_get
const TValue* luaH_get(Table* t, const TValue* key)
{switch (ttype(key)){case LUA_TNIL:{//#define luaO_nilobject (luaO_nilobject_)//LUAI_DATA const TValue luaO_nilobject_;//const TValue luaO_nilobject_ {{NULL}, LUA_TNIL}; //公共nilreturn luaO_nilobject;}case LUA_TSTRING:{//#define rawtsvalue(o) check_exp(ttisstring(o), (o)-value.gc-ts)return luaH_getstr(t, rawtsvalue(key));}case LUA_TNUMBER:{//#define nvalue(o) check_exp(ttisnumber(o), (o)-value.n)lua_Number n nvalue(key);int k;//#define lua_number2int(i,d) __asm fld d __asm fistp ilua_number2int(k, n);//若n是整数才触发 根据整数查找//#define luai_numeq(a,b) ((a)(b))if (luai_numeq(cast_num(k), n)){return luaH_getnum(t, k);}}default:{//找到key对应键值对所在的首地址由于首地址会有冲突所以不一定所有的键值对都在首地址那些无法放在首地址的键值对会作为身在首地址的键值对的后继节点所以需要next遍历查找Node* n mainposition(t, key);//mainposition见下文do{//若在链表中找到了和key相同地键则返回该键值对的值//#define key2tval(n) ((n)-i_key.tvk)if (luaO_rawequalObj(key2tval(n), key))//luaO_rawequalObj见栈章节{return gval(n);//#define gval(n) ((n)-i_val)}//没找到继续找下一个键值对n gnext(n);//#define gnext(n) ((n)-i_key.nk.next)} while(n);//没找到旧返回nilreturn luaO_nilobject;}}
}(luaconf.h) lua_number2int
//就是利用汇编指令 快速地 把浮点数转为整数
//关于浮点运算指令f指float代表浮点运算指令前缀
//fld: ld指load的意思把一个浮点数加载进浮点运算器入栈
//fistp: i指int是整数的意思st指store是存储到内存的意思p指pop是出栈的意思。连起来就是 浮点运算器把栈顶出栈以整数的形式存到内存中
#define lua_number2int(i,d) __asm fld d __asm fistp i(ltable.c) mainposition根据key获取哈希部分键值对的首地址
static Node* mainposition(const Table* t, const TValue* key)
{switch (ttype(key)){case LUA_TNUMBER:{return hashnum(t, nvalue(key));}case LUA_TSTRING:{//#define gnode(t,i) ((t)-node[i]) //获取Table的哈希部分的第i个地址//#define lmod(s,size) (check_exp((size(size-1))0, (cast(int, (s) ((size)-1)))))//#define twoto(x) (1(x))//#define sizenode(t) (twoto((t)-lsizenode)) //获取表的哈希部分大小//#define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t)))) //根据 n 对表的哈希大小求余 来获取键值对的地址//#define hashstr(t,str) hashpow2(t, (str)-tsv.hash)return hashstr(t, rawtsvalue(key));}case LUA_TBOOLEAN:{//#define hashboolean(t,p) hashpow2(t, p) //根据p的值 对表的哈希大小求余 来获取键值对的地址return hashboolean(t, bvalue(key));//#define bvalue(o) check_exp(ttisboolean(o), (o)-value.b)}case LUA_TLIGHTUSERDATA:{//#define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1)))) //根据n求余来获取表的键值对地址//#define IntPoint(p) ((unsigned int)(lu_mem)(p))//#define hashpointer(t,p) hashmod(t, IntPoint(p)) //根据对象地址来求余 来获取键值对的地址return hashpointer(t, pvalue(key));//#define pvalue(o) check_exp(ttislightuserdata(o), (o)-value.p)}default:{return hashpointer(t, gcvalue(key));//#define gcvalue(o) check_exp(iscollectable(o), (o)-value.gc)}}
}(ltable.c) hashnum根据数字获取表的哈希部分键值对的地址
static Node* hashnum(const Table* t, lua_Number n)
{//若n为0则返回哈希部分的0号地址if (luai_numeq(n, 0)){return gnode(t, 0);}//#define numints cast_int(sizeof(lua_Number)/sizeof(int)) 获取lua_Number大小是int大小的多少倍unsigned int a[numints];memcpy(a, n, sizeof(a));//已知luaNumber是int的2倍就是把luaNumber的前4字节和后4字节加起来for (int i 1; i numints; i){a[0] a[i];}return hashmod(t, a[0]);
}3.1.2 根据字符串查找 luaH_getstr
(ltable.c) luaH_getstr
const TValue* luaH_getstr(Table* t, TString* key)
{//获取hash部分索引为 (key-tsv.hash) % (1 t-lnodesize) 的键值对地址Node* n hashstr(t, key);//沿着链条一直往下找do{//若找到了键为string且和key相等的键值对则返回键值对的值if (ttisstring(gkey(n)) rawtsvalue(gkey(n)) key){return gval(n);}n gnext(n);} while(n);//没找到就返回nilreturn luaO_nilobject;
}3.1.3 根据整数查找 luaH_getnum
(ltable.c) luaH_getnum
const TValue* luaH_getnum(Table* t, int key)
{//若 1key key t-sizearray 则直接返回数组指定索引的地址//对于不满足该条件的还是从哈希部分去找if (cast(unsigned int, key - 1) cast(unsigned int, t-sizearray)){return t-array[key - 1];}//否则就根据数字在哈希部分找键值对地址lua_Number nk cast_num(key);Node* n hashnum(t, nk);//沿着链表往下找直到找到符合条件的为止do{if (ttisnumber(gkey(n) luai_numeq(gkey(n), nk))){return gval(n);}n gnext(n);} while(n);//未找到返回nilreturn luaO_nilobject;
}3.2 新增元素/修改元素/删除元素 luaH_set系列
新增修改删除元素行为其实都是一样的 例如
local a{}
a.name1 //新增元素
a.name2 //修改元素
a.namenil //删除元素luaH_set系列方法做的事情不是set但是它返回一个TValue*供外部去设置其字段。
3.2.1 根据key获取或创建一个value: luaH_set
(ltable.c) luaH_set
//虽然名字叫set其实根本不叫set个人觉得更合适的命名应该叫做 luaH_get_or_create应为返回的是TValue类型的 value 的地址
TValue* luaH_set(lua_State* L, Table* t, const TValue* key)
{//根据key获取value的地址const TValue* p luaH_get(t, key);//将table的方法标记位全部置为0todo后面再说t-flags 0;//若找到的不是nil则直接返回找到的value的地址if (p ! luaO_nilobject){return cast(TValue*, p);}//如果key是nil则报错if (ttisnil(key)){luaG_runerror(L, table index is nil);//luaG_runerror见异常章节return;}//若key是数字但为NaN则报错//#define luai_numisnan(a) (!luai_numeq((a), (a))) //不等于自身的数字就是NaNif (ttisnumber(key) luai_numisnan(nvalue(key))){luaG_runerror(L, table index is NaN);}return newkey(L, t, key);
}(ltable.c) newkey
//根据key创建一个新的value返回value所在的地址
static TValue* newkey(lua_State* L, Table* t, const TValue* key)
{//找到key对应的hash部分的索引。lua的hash部分采用闭散列的结构每个桶的链表的每个元素实际上是占据其它桶的位置的。//举个例子有几号人去坐火车。//1号的票是A座发现A空着则坐下。那么票为A的链表为[A:1]//2号的票也是A询问1号由于1号先来所以只好灰溜溜地找一个空位B坐下。那么索引为A的链表为[A:1, B:2]//3号的票是B发现B被2号占了询问2号2号只好起身再去找了另一个空位C坐下B空出来了于是3坐下。那么票为A的座位链表更新为[A:1, C:2]//4号的票是A发现A被1占了询问14只好起身找空位D坐下。那么票为A的座位链表更新为[A:1, D:4, C:2]//5号的票是C发现C被2占了询问22只好起身找到空位E坐下C空出来了于是5坐下。那么票为A的座位链表更新为[A:1, D:4, E:2]虽然是单链表但是2可以通过票找到A的位置所以要找2在的位置的前驱节点并不难Node* mp mainposition(t, key);//若key的目标位置已经被占或者目标位置是dummynode也就是说key的目标位置都是无效的只能找一个空闲的位置/*#define dummynode (dummynode_)static const Node dummynode_ {{{NULL}, LUA_TNIL},{{{NULL}, LUA_TNIL, NULL}}};*/if (!ttisnil(gval(mp)) || mp dummynode){//找一个空闲的位置Node* freepos getfreepos(t);//若没有空闲位置了则需要rehash以扩容if (n NULL){rehash(L, t, key);return luaH_set(L, t, key);}Node* othern mainposition(t, key2tval(mp));//若在mp位置的节点的mainposition不是mp位置则mp需要被空出来该节点内容被移到空位上if (othern ! mp){//找到mp的前驱节点while(gnext(othern) ! mp){othern gnext(othern);}//前驱节点指向空闲位置因为占mp位置的元素要被移到这个空闲位置gnext(othern) freepos;*freepos *mp;//mp位置空出来gnext(mp) NULL;setnilvalue(gval(mp));}//若在mp位置的节点的mainposition就是mp位置则新节点需要被移到空闲的位置, 且使这个空闲节点为mp的后继节点else{gnext(freepos) gnext(mp);gnext(mp) freepos;mp freepos;}}//最终mp更新为新节点的位置gkey(mp)-value key-value;gkey(mp)-tt key-tt;luaC_barriert(L, t, key);//luaC_barriert见GC章节lua_assert(!ttisnil(gval(mp)));return gval(mp);
}(ltable.c) getfreepos 获取table的hash部分的一个空闲的节点位置
static Node* getfreepos(Table* t)
{//注意t-lastfree是指向最后一个空闲位置的下一个位置while (t-lastfree t-node){t-lastfree--;if (ttisnil(gkey(t-lastfree))) {return t-lasfree;}}return NULL;
}(ltable.c) rehash 重新调整表的结构
static void rehash(lua_State* L, Table* t, const TValue* extra_key)
{//table的array部分最大长度为2^MAXBITS, nums[i]表示key在( 2^(i-1), 2^i ] 区间的key的个数int nums[MAXBITS 1] {0};//获取在array部分的key数量int keynum_in_array numusearray(t, nums);//numusearray见下文//正整数key数量int keynum_positive_int keynum_in_array;//获取hash部分的key数量更新正整数key数量int keynum_in_hash numusehash(t, nums, keynum_positive_int);//numusehash见下文//根据extra_key判断是否正整数key数量是否1keynum_positive_int countint(extra_key, nums);//key总数array部分key数量 hash部分key数量 extra_key数量(1)int key_num_total keynum_in_array keynum_in_hash 1;//根据正整数key数量计算array部分的新大小, 以及array中key新数量int keynum_positive_int2 keynum_positive_int;keynum_in_array computesizes(nums, keynum_positive_int2);//computesizes见下文int array_size keynum_positive_int2;keynum_in_hash key_num_total - keynum_in_array;//hash的大小就等于hash部分key数量int hash_size keynum_in_hash;//重新设置table的大小resize(L, t, array_size, hash_size);
}(ltable.c) numusearray 统计table的array部分的key个数 以及 记录key分布
static int numusearray(const Table* t, int* nums)
{int keynum_total 0;int key 1;for (int section_idx0, section_upper_limit1; section_idx MAXBITS; section_idx, section_upper_limit*2){int keynum_this_section 0;int lim section_upper_limit;if (lim t-sizearray){lim t-sizearray;if (key lim){break;}}for (; key lim; key){for (!ttisnil(t-array[key - 1])){keynum_this_section;}}nums[section_idx] keynum_this_section;keynum_total keynum_this_section;}return keynum_total;
}(ltable.c) numusehash 计算table中hash部分的key数量若有正整数则更新传入的正整数key数量
static int numusehash(const Table* t, int* nums, int* keynum_positive_int)
{//hash部分key数量int keynum_in_hash 0;//hash部分的正整数key数量int keynum_positive_int_in_hash 0;//获取hash桶的数量int hashbucket_num sizenode(t);//从后往前遍历int i hashbucket_num;while(i){i--;Node* hashbucket t-node i;if (!ttisnil(gval(n))){keynum_positive_int_in_hash countint(key2tval(n), nums);//countint见下文keynum_in_hash;}}*keynum_positive_int keynum_positive_int_in_hash;return keynum_in_hash;
}(ltable.c) countint 计算一个key是否是正整数并更新正整数索引分布
static int countint(const TValue* key, int* nums)
{int k arrayindex(key);if (0 k k MAXASIZE){//#define ceillog2(x) (luaO_log2((x) - 1) 1) //获取x的log2向上取整的值nums[ceillog2(k)];return 1;}return 0;
}(ltable.c) arrayindex 根据key返回整数值
static int arrayindex(const TValue* key)
{//key是整数则返回整数if (ttisnumber(key)){int k;lua_number2int(k, n);if (luai_numeq(cast_num(k), n)){return k;}}//若key不是整数则返回-1return -1;
}(lobject.c) luaO_log2
//求x的log2向下取整值用的是查表优化的方式避免了多次重复计算log2值
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];
}(ltable.c) computesizes
static int computesizes(int nums[], int* keynum_positive_int)
{//正整数key计数器int counter_keynum_positive_int 0;//array最优大小int array_size 0;//array的key数量int keynum_in_array 0;//选定array新的大小的原则在[1, array_size]范围key的数量array_size/2也就是array要满足空间利用率50%for (int section_idx 0, section_upperlimit 1; section_upperlimit/2 *keynum_positive_int; i, section_upperlimit * 2){if (nums[i] 0){//正整数key计数器累加counter_keynum_positive_int nums[i];//当满足空间利用率50%时更新array的最优大小以及key数量if (section_upperlimit/2 counter_keynum_positive_int){array_size section_upperlimit;keynum_in_array counter_keynum_positive_int;}}//若已经遍历完了所有的key则退出循环if (counter_keynum_positive_int *keynum_positive_int){break;}}//记录最佳的数组大小*keynum_positive_int array_size;//返回数组return keynum_in_array;
}(ltable.c) resize
//重新设置table的大小
static void resize(lua_State* L, Table* t, int array_size, int hash_size)
{int old_array_size t-sizearray;int old_hash_size twoto(t-lsizenode);Node* old_hash t-node;//若要的array大小大于原大小则array扩容if (array_size old_array_size){setarrayvector(L, t, array_size);}//重新分配hash部分内存setnodevector(L, t, hash_size);//若要的array大小小于原大小则array缩容且重新分配多出的keyif (array_size old_array_size){t-sizearray array_size;for (int i array_size; i old_array_size; i){//array部分多出的key就要重新设置位置啦 会被分配到hash部分哦if (!ttisnil(t-array i)){setobjt2t(L, luaH_setnum(L, t, i1), t-array i);}}//array部分缩容luaM_reallocvector(L, t-array, old_array_size, array_size, TValue);}//把旧的hash部分的所有元素移到新的hash部分for (int i old_hash_size - 1; i 0; i--){Node* node old_hash i;//将旧的hash上的节点设置到新的hash上if (!ttisnil(gval(node))){setobjt2t(L, luaH_set(L, t, key2tval(node)), gval(node));}//若旧的hash不是指向dummynode则释放掉if (old_hash ! dummynode){luaM_freearray(L, old_hash, old_hash_size, Node);}}
}(ltable.c) setarrayvector
//重新分配table的array部分的内存
static void setarrayvector(lua_State* L, Table* t, int size)
{//重新分配array内存luaM_rellocvector(L, t-array, t-sizearray, size, TValue);//对于[sizearray, size)区间设置值为nil对于[1, sizearray)区间暂且不管for (int i t-sizearray; i size; i){setnilvalue(t-array i);}//更新table的array大小t-arraysize size;
}(ltable.h) setnodevector
//重新分配table的hash部分的内存
static void setnodevector(lua_State* L, Table* t, int size)
{//hash部分大小的log2值int lszie 0;//若hash大小要设为0则让hash指向dummynode, 不会让其真正为0if (size0){t-node cast(Node*, dummynode);lsize 0;}else{lsize ceillog(size);//若hash部分过大则报错if (lsize MAXBITS){luaG_runerror(L, table overflow);return;}size twoto(lsize);//为hash重新分配内存注意老的t-node在外面已经记录了所以不用担心t-node luaM_newvector(L, size, Node);//遍历hash部分每个桶设置key和value都为nil且设置后继节点为空for (int i 0; i size; i){Node* n gnode(t, i);gnext(n) NULL;setnilvalue(gkey(n));setnilvalue(gval(n));}}t-lsizenode cast_byte(lsize);t-lastfree gnode(t, size);//指向最后一个空闲位置的下一个位置
}3.2.2 根据数字获取或创建一个value: luaH_setnum
(ltable.c) luaH_setnum
TValue* luaH_setnum(lua_State* L, Table* t, int key)
{const TValue* p luaH_getnum(t, key);if (p!luaO_nilobject){return cast(TValue*, p);}//构造一个数字类型的临时的keyTValue k;setnvalue(k, cast_num(key));return newkey(L, t, k);
}3.2.3 根据数字获取或创建一个value: luaH_setstr
(ltable.c) luaH_setstr
TValue* luaH_setstr(lua_State* L, Table* t, TString* key)
{const TValue* p luaH_getstr(t, key);if (p ! luaO_nilobject){return cast(TValue*, p);}TValue k;setsvalue(L, k, key);return newkey(L, t, k);
}3.3 新建表 luaH_new
(ltable.c) luaH_new
Table* luaH_new(lua_State* L, int array_size, int hash_size)
{//#define luaM_new(L,t) cast(t *, luaM_malloc(L, sizeof(t))) //分配一个长度为类型t的堆内存Table* t luaM_new(L, Table);//链接到gc链表上luaC_link(L, obj2gco(t), LUA_TTABLE);//luaC_link见GC章节t-metatable NULL;t-flags cast_byte(~0);t-array NULL;t-sizearray 0;t-lsizenode 0;t-node cast(Node*, dummynode);//分配array部分内存setarrayvector(L, t, array_size);//分配hash部分内存setnodevector(L, t, hash_size);return t;
}3.4 迭代表 luaH_next
lua table迭代不是通过迭代器而是通过key先在array部分查找数据若找到返回key的下一个数据否则在hash部分查找数据若找到则返回key的下一个数据
(ltable.c) luaH_next
//根据key找下一个键值对找到则返回1没找到则返回0
int luaH_next(lua_State* L, Table* t, StkId key)
{for i findindex(L,t,key);//先找array部分for (i; i t-sizearray; i){if (!ttisnil(t-array i)){setnvalue(key, cast_num(i1));//将key设置为i1因为lua索引比c索引大1setobj2s(L, key1, t-arrayi);//将value设置为arrayi处的内容因为value在lua栈上的为止比key大1return 1;}}//再找hash部分int size_hash sizenode(t);for (i - t-sizearray; i size_hash ; i){Node* n gnode(t, i);if (!ttisnil(gval(n))){setobj2s(L, key, key2tval(n));setobj2s(L, key 1, gval(n));return 1;}}//没找到则返回0return 0;
}(ltable.c) findindex
//根据key找到索引值若在[0,size_array)范围则表示在数组部分若在[size_array,size_arraysize_hash)范围则表示在hash部分
static int findindex(lua_State* L, Table* t, StkId key)
{if (ttisnil(key)){return -1;}//根据key获取数组索引int i arrayindex(key);if (0 i i t-size){return i - 1;}//找到key在hash部分的mainposition沿着链表往下找直到找到其keykey的节点为止Node* n mainposition(t, key);do{//#define LAST_TAG LUA_TTHREAD//#define LUA_TPROTO (LAST_TAG1)//#define LUA_TUPVAL (LAST_TAG2)//#define LUA_TDEADKEY (LAST_TAG3) //类型为死亡的key见GC章节if(luaO_rawequalObj(key2tval(n), key)|| (ttype(gkey(n)) LUA_TDEADKEY iscollectable(key) gcvalue(gkey(n)) gcvalue(key))){i cast_int(n - gnode(t, 0));return i t-size_array;}n gnext(n);} while(n)//若没找到则报错 非法的keyluaG_runerror(L, invalid key to LUA_QL(next));return 0;
}3.5 取长度 luaH_getn
(ltable.c) luaH_getn
int luaH_getn(Table* t)
{//若array部分0且最后一个元素是nil则使用二分法找一个位置n, n处不为niln1处为nilif (t-sizearray 0 ttisnil(t-array upperbound - 1)){unsigned int lowerbound 0;unsigned int upperbound t-sizearray;while (upperbound - lowerbound 1){unsigned int m (upperbound lowerbound)/2;if (ttisnil(t-array m - 1)){upperbound m;}else{lowerbound m;}}return lowerbound;}//若array部分最后一个元素不是nil 且 hash部分只有一个dummynode则返回array部分大小if (t-node dummynode){return t-sizearray;}//若array部分最后一个元素不是nil 且 hash部分 不指向dummynode则使用unbond_searchreturn unbound_search(t, t-sizearray);
}(ltable.c) unbound_search
static int unbound_search(Table* t, unsigned int upperbound)
{unsigned int lowerbound upperbound;upperbound;//j每次*2, 直到j处为nil; 当然若找的过程中j越界了则从索引1开始找找到一个位置n,处为不为niln-1处不为nilwhile (!ttisnil(luaH_getnum(t, upperbound))){lowerbound upperbound;upperbound * 2;//upperbound 越界后则从1开始重新找if (upperbound cast(unsigned int, MAX_INT)){upperbound 1;while (!ttisnil(luaH_getnum(t, upperbound))){upperbound;}return upperbound - 1;}}//既然到了upperbound处为nil则用二分法找位置upperboundupperbound处为nilupperbound-1(即lowerbound)处不为nilwhile (upperbound - lowerbound 1){unsigned int m (lowerbound upperbound)/2;if (ttisnil(luaH_getnum(t, m))){upperbound m;}else{lowerbound m;}}return lowerbound;
}
