// 获得一个空间位置 static Node *getfreepos(Table *t){ if (!isdummy(t)) { // t->node是一个数组 while (t->lastfree > t->node) { t->lastfree--; if (keyisnil(t->lastfree)) return t->lastfree; } } returnNULL; /* could not find a free place */ }
/* ** Compute the optimal size for the array part of table 't'. 'nums' is a ** "count array" where 'nums[i]' is the number of integers in the table ** between 2^(i - 1) + 1 and 2^i. 'pna' enters with the total number of ** integer keys in the table and leaves with the number of keys that ** will go to the array part; return the optimal size. (The condition ** 'twotoi > 0' in the for loop stops the loop if 'twotoi' overflows.) */ staticunsignedintcomputesizes(unsignedint nums[], unsignedint *pna){ int i; unsignedint twotoi; /* 2^i (candidate for optimal size) */ unsignedint a = 0; /* number of elements smaller than 2^i */ unsignedint na = 0; /* number of elements to go to array part */ unsignedint optimal = 0; /* optimal size for array part */ /* loop while keys can fill more than half of total size */ // 我带上了代码的英文注释,需要注意的点 // twotoi > 0 的判断是为了防止twotoi的溢出 // i从0开始;0表示区间[2^0 ~ 2^1] for (i = 0, twotoi = 1;twotoi > 0 && *pna > twotoi / 2;i++, twotoi *= 2) { a += nums[i]; // a > twotoi/2 表示的是节点数量只要大于总空间的一半 // 也就是利用率能达到50%就记录一下 if (a > twotoi/2) { /* more than half elements present? */ optimal = twotoi; /* optimal size (till now) */ na = a; /* all elements up to 'optimal' will go to array part */ } } lua_assert((optimal == 0 || optimal / 2 < na) && na <= optimal); // pna重新调整为实际统计的数组节点数量 // 数组长度为optimal时数组节点数量 *pna = na; return optimal; }
/* ** Resize table 't' for the new given sizes. Both allocations (for ** the hash part and for the array part) can fail, which creates some ** subtleties. If the first allocation, for the hash part, fails, an ** error is raised and that is it. Otherwise, it copies the elements from ** the shrinking part of the array (if it is shrinking) into the new ** hash. Then it reallocates the array part. If that fails, the table ** is in its original state; the function frees the new hash part and then ** raises the allocation error. Otherwise, it sets the new hash part ** into the table, initializes the new part of the array (if any) with ** nils and reinserts the elements of the old hash back into the new ** parts of the table. */ // newasize数组部分的长度 // nhsize哈希部分的长度 voidluaH_resize(lua_State *L, Table *t, unsignedint newasize, unsignedint nhsize){ unsignedint i; Table newt; /* to keep the new hash part */ unsignedint oldasize = setlimittosize(t); TValue *newarray; /* create new hash part with appropriate size into 'newt' */ // 重新创建哈希部分的长度 // 参见下一节(扩展哈希表核心算法) setnodevector(L, &newt, nhsize); // 数组新长度小于原有长度(缩小) if (newasize < oldasize) { /* will array shrink? */ t->alimit = newasize; /* pretend array has new size... */ // 把t的hash信息保存到newt中 exchangehashpart(t, &newt); /* and new hash */ /* re-insert into the new hash the elements from vanishing slice */ // 如果是缩小的话;把原有的数组多余节点添加到t中 for (i = newasize; i < oldasize; i++) { if (!isempty(&t->array[i])) luaH_setint(L, t, i + 1, &t->array[i]); } // 然后再恢复newt中的哈希列表信息到t中 t->alimit = oldasize; /* restore current size... */ exchangehashpart(t, &newt); /* and hash (in case of errors) */ } /* allocate new array */ // 创建新的数组部分(newarray) newarray = luaM_reallocvector(L, t->array, oldasize, newasize, TValue); if (l_unlikely(newarray == NULL && newasize > 0)) { /* allocation failed? */ freehash(L, &newt); /* release new hash part */ luaM_error(L); /* raise error (with array unchanged) */ } /* allocation ok; initialize new part of the array */ // 把哈希列表部分保存到newt中 exchangehashpart(t, &newt); /* 't' has the new hash ('newt' has the old) */ // t设置新的数组部分 t->array = newarray; /* set new array part */ t->alimit = newasize; // 数组新扩展的部分县设置为空 for (i = oldasize; i < newasize; i++) /* clear new slice of the array */ setempty(&t->array[i]); /* re-insert elements from old hash part into new parts */ // 重新把newt的哈希列表部分的节点插入到t中 reinsert(L, &newt, t); /* 'newt' now has the old hash */ // 释放newt freehash(L, &newt); /* free old hash part */ }