summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2015-03-30 16:51:00 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2015-03-30 16:51:00 -0300
commit63720a4290e1ed3042e3b356af56374ecb635a20 (patch)
tree6f2e10fab4cbb1ba58d0cd1a130d52f440dbd713
parent484bf14a6bac3174900f0b7783f41c5b3bab0217 (diff)
downloadlua-63720a4290e1ed3042e3b356af56374ecb635a20.tar.gz
lua-63720a4290e1ed3042e3b356af56374ecb635a20.tar.bz2
lua-63720a4290e1ed3042e3b356af56374ecb635a20.zip
janitor work (comments, variable names, some other details)
Diffstat
-rw-r--r--ltable.c56
1 files changed, 31 insertions, 25 deletions
diff --git a/ltable.c b/ltable.c
index 1a1b78d0..014e9171 100644
--- a/ltable.c
+++ b/ltable.c
@@ -1,5 +1,5 @@
1/* 1/*
2** $Id: ltable.c,v 2.106 2015/03/03 19:53:13 roberto Exp roberto $ 2** $Id: ltable.c,v 2.107 2015/03/30 15:36:53 roberto Exp roberto $
3** Lua tables (hash) 3** Lua tables (hash)
4** See Copyright Notice in lua.h 4** See Copyright Notice in lua.h
5*/ 5*/
@@ -14,8 +14,8 @@
14** Implementation of tables (aka arrays, objects, or hash tables). 14** Implementation of tables (aka arrays, objects, or hash tables).
15** Tables keep its elements in two parts: an array part and a hash part. 15** Tables keep its elements in two parts: an array part and a hash part.
16** Non-negative integer keys are all candidates to be kept in the array 16** Non-negative integer keys are all candidates to be kept in the array
17** part. The actual size of the array is the largest 'n' such that at 17** part. The actual size of the array is the largest 'n' such that
18** least half the slots between 0 and n are in use. 18** more than half the slots between 1 and n are in use.
19** Hash uses a mix of chained scatter table with Brent's variation. 19** Hash uses a mix of chained scatter table with Brent's variation.
20** A main invariant of these tables is that, if an element is not 20** A main invariant of these tables is that, if an element is not
21** in its main position (i.e. the 'original' position that its hash gives 21** in its main position (i.e. the 'original' position that its hash gives
@@ -220,28 +220,29 @@ int luaH_next (lua_State *L, Table *t, StkId key) {
220/* 220/*
221** Compute the optimal size for the array part of table 't'. 'nums' is a 221** Compute the optimal size for the array part of table 't'. 'nums' is a
222** "count array" where 'nums[i]' is the number of integers in the table 222** "count array" where 'nums[i]' is the number of integers in the table
223** between 2^(i - 1) + 1 and 2^i. Put in '*narray' the optimal size, and 223** between 2^(i - 1) + 1 and 2^i. 'pna' enters with the total number of
224** return the number of elements that will go to that part. 224** integer keys in the table and leaves with the number of keys that
225** will go to the array part; return the optimal size.
225*/ 226*/
226static unsigned int computesizes (unsigned int nums[], unsigned int *narray) { 227static unsigned int computesizes (unsigned int nums[], unsigned int *pna) {
227 int i; 228 int i;
228 unsigned int twotoi; /* 2^i */ 229 unsigned int twotoi; /* 2^i (candidate for optimal size) */
229 unsigned int a = 0; /* number of elements smaller than 2^i */ 230 unsigned int a = 0; /* number of elements smaller than 2^i */
230 unsigned int na = 0; /* number of elements to go to array part */ 231 unsigned int na = 0; /* number of elements to go to array part */
231 unsigned int n = 0; /* optimal size for array part */ 232 unsigned int optimal = 0; /* optimal size for array part */
232 for (i = 0, twotoi = 1; twotoi/2 < *narray; i++, twotoi *= 2) { 233 /* loop while keys can fill more than half of total size */
234 for (i = 0, twotoi = 1; *pna > twotoi / 2; i++, twotoi *= 2) {
233 if (nums[i] > 0) { 235 if (nums[i] > 0) {
234 a += nums[i]; 236 a += nums[i];
235 if (a > twotoi/2) { /* more than half elements present? */ 237 if (a > twotoi/2) { /* more than half elements present? */
236 n = twotoi; /* optimal size (till now) */ 238 optimal = twotoi; /* optimal size (till now) */
237 na = a; /* all elements up to 'n' will go to array part */ 239 na = a; /* all elements up to 'optimal' will go to array part */
238 } 240 }
239 } 241 }
240 if (a == *narray) break; /* all elements already counted */
241 } 242 }
242 *narray = n; 243 lua_assert((optimal == 0 || optimal / 2 < na) && na <= optimal);
243 lua_assert(*narray/2 <= na && na <= *narray); 244 *pna = na;
244 return na; 245 return optimal;
245} 246}
246 247
247 248
@@ -256,6 +257,11 @@ static int countint (const TValue *key, unsigned int *nums) {
256} 257}
257 258
258 259
260/*
261** Count keys in array part of table 't': Fill 'nums[i]' with
262** number of keys that will go into corresponding slice and return
263** total number of non-nil keys.
264*/
259static unsigned int numusearray (const Table *t, unsigned int *nums) { 265static unsigned int numusearray (const Table *t, unsigned int *nums) {
260 int lg; 266 int lg;
261 unsigned int ttlg; /* 2^lg */ 267 unsigned int ttlg; /* 2^lg */
@@ -282,8 +288,7 @@ static unsigned int numusearray (const Table *t, unsigned int *nums) {
282} 288}
283 289
284 290
285static int numusehash (const Table *t, unsigned int *nums, 291static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) {
286 unsigned int *pnasize) {
287 int totaluse = 0; /* total number of elements */ 292 int totaluse = 0; /* total number of elements */
288 int ause = 0; /* elements added to 'nums' (can go to array part) */ 293 int ause = 0; /* elements added to 'nums' (can go to array part) */
289 int i = sizenode(t); 294 int i = sizenode(t);
@@ -294,7 +299,7 @@ static int numusehash (const Table *t, unsigned int *nums,
294 totaluse++; 299 totaluse++;
295 } 300 }
296 } 301 }
297 *pnasize += ause; 302 *pna += ause;
298 return totaluse; 303 return totaluse;
299} 304}
300 305
@@ -377,21 +382,22 @@ void luaH_resizearray (lua_State *L, Table *t, unsigned int nasize) {
377** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i 382** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i
378*/ 383*/
379static void rehash (lua_State *L, Table *t, const TValue *ek) { 384static void rehash (lua_State *L, Table *t, const TValue *ek) {
380 unsigned int nasize, na; 385 unsigned int asize; /* optimal size for array part */
386 unsigned int na; /* number of keys in the array part */
381 unsigned int nums[MAXABITS + 1]; 387 unsigned int nums[MAXABITS + 1];
382 int i; 388 int i;
383 int totaluse; 389 int totaluse;
384 for (i = 0; i <= MAXABITS; i++) nums[i] = 0; /* reset counts */ 390 for (i = 0; i <= MAXABITS; i++) nums[i] = 0; /* reset counts */
385 nasize = numusearray(t, nums); /* count keys in array part */ 391 na = numusearray(t, nums); /* count keys in array part */
386 totaluse = nasize; /* all those keys are integer keys */ 392 totaluse = na; /* all those keys are integer keys */
387 totaluse += numusehash(t, nums, &nasize); /* count keys in hash part */ 393 totaluse += numusehash(t, nums, &na); /* count keys in hash part */
388 /* count extra key */ 394 /* count extra key */
389 nasize += countint(ek, nums); 395 na += countint(ek, nums);
390 totaluse++; 396 totaluse++;
391 /* compute new size for array part */ 397 /* compute new size for array part */
392 na = computesizes(nums, &nasize); 398 asize = computesizes(nums, &na);
393 /* resize the table to new computed sizes */ 399 /* resize the table to new computed sizes */
394 luaH_resize(L, t, nasize, totaluse - na); 400 luaH_resize(L, t, asize, totaluse - na);
395} 401}
396 402
397 403
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-16 14:25:57 +0000