diff options
Diffstat (limited to 'src/lua51/ltable.c')
| -rw-r--r-- | src/lua51/ltable.c | 36 |
1 files changed, 33 insertions, 3 deletions
diff --git a/src/lua51/ltable.c b/src/lua51/ltable.c index ec84f4f..f489a03 100644 --- a/src/lua51/ltable.c +++ b/src/lua51/ltable.c @@ -159,6 +159,9 @@ static int findindex (lua_State *L, Table *t, StkId key) { } +//c table的遍历操作，返回下一个node +//c 先计算key的hash，如果在array范围内，在array中找，否则在hash中找 +//c 注意实际上不会两个for循环都走 int luaH_next (lua_State *L, Table *t, StkId key) { int i = findindex(L, t, key); /* find original element */ for (i++; i < t->sizearray; i++) { /* try first array part */ @@ -208,8 +211,10 @@ static int computesizes (int nums[], int *narray) { } +//c 返回1或0，是否将这个key算进要加入表的数组部分 static int countint (const TValue *key, int *nums) { int k = arrayindex(key); + //c 所以数字key的最大范围是0~MAXASIZE if (0 < k && k <= MAXASIZE) { /* is `key' an appropriate array index? */ nums[ceillog2(k)]++; /* count as such */ return 1; @@ -294,6 +299,9 @@ static void setnodevector (lua_State *L, Table *t, int size) { } +//c 重新分配table的哈希部分大小为 +//nasize 是 array size +//nhsize 是 hash table size static void resize (lua_State *L, Table *t, int nasize, int nhsize) { int i; int oldasize = t->sizearray; @@ -330,18 +338,26 @@ void luaH_resizearray (lua_State *L, Table *t, int nasize) { } +//c 给table的散列桶部分重新hash +//c 用于给table扩容 static void rehash (lua_State *L, Table *t, const TValue *ek) { + //c 先计算落在2^(i-1)~2^i范围内的各个区间的元素数量，用于决策新容量 int nasize, na; + //c 以2的指数级扩展的数组，记录的是指数。能看出来表的最大大小是2^MAXBITS int nums[MAXBITS+1]; /* nums[i] = number of keys between 2^(i-1) and 2^i */ int i; int totaluse; for (i=0; i<=MAXBITS; i++) nums[i] = 0; /* reset counts */ + //c 遍历数组部分和散列桶部分，找出正整数key的值的数量，以此更新nums[] nasize = numusearray(t, nums); /* count keys in array part */ totaluse = nasize; /* all those keys are integer keys */ totaluse += numusehash(t, nums, &nasize); /* count keys in hash part */ /* count extra key */ + //c 加上这个key（如果在范围内的话） nasize += countint(ek, nums); totaluse++; + //c 找到一个位置i，这个位置之前的元素个数大于50%，即2^i/2。这个位置之后意味着太空了，效率比较低 + //c 这个位置 /* compute new size for array part */ na = computesizes(nums, &nasize); /* resize the table to new computed sizes */ @@ -354,7 +370,7 @@ static void rehash (lua_State *L, Table *t, const TValue *ek) { ** }============================================================= */ - +//c 新建table Table *luaH_new (lua_State *L, int narray, int nhash) { Table *t = luaM_new(L, Table); luaC_link(L, obj2gco(t), LUA_TTABLE); @@ -388,7 +404,7 @@ static Node *getfreepos (Table *t) { } - +//c 表新建key /* ** 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 @@ -398,30 +414,41 @@ static Node *getfreepos (Table *t) { */ static TValue *newkey (lua_State *L, Table *t, const TValue *key) { Node *mp = mainposition(t, key); - if (!ttisnil(gval(mp)) || mp == dummynode) { + if (!ttisnil(gval(mp)) || mp == dummynode) {//c mainposition上已经有数据 Node *othern; Node *n = getfreepos(t); /* get a free place */ + //c 如果没有空位，扩展hash table大小为2倍 if (n == NULL) { /* cannot find a free place? */ rehash(L, t, key); /* grow table */ + //c 扩展完大小后重试 return luaH_set(L, t, key); /* re-insert key into grown table */ } lua_assert(n != dummynode); + //c 先看一下现在mainposition上的这个node，它的mainposition是不是这个值 + //c 不是的话给新的key让路 othern = mainposition(t, key2tval(mp)); if (othern != mp) { /* is colliding node out of its main position? */ + // 把mp空出来,mp里的值移到n(freeposition) /* 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)); + //mp是要赋值的位置，即新key的元素的位置 } else { /* colliding node is in its own main position */ /* new node will go into free position */ + //c 将free position插入到mp后第一个 gnext(n) = gnext(mp); /* chain new position */ gnext(mp) = n; + //c 修改一下mp指针，指向freeposition，留个后续使用 mp = n; } } + //c 如果mainposition位置上是空的，可以直接用mp位置存 + //c 赋值 gkey(mp)->value = key->value; gkey(mp)->tt = key->tt; luaC_barriert(L, t, key); lua_assert(ttisnil(gval(mp))); @@ -553,6 +580,7 @@ static int unbound_search (Table *t, unsigned int j) { } +//c 获得table长度 /* ** Try to find a boundary in table `t'. A `boundary' is an integer index ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil). @@ -560,7 +588,9 @@ static int unbound_search (Table *t, unsigned int j) { int luaH_getn (Table *t) { 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 */ + // i是左界，j是右界 unsigned int i = 0; while (j - i > 1) { unsigned int m = (i+j)/2; |