diff options
author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2015-03-30 16:51:00 -0300 |
---|---|---|
committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2015-03-30 16:51:00 -0300 |
commit | 63720a4290e1ed3042e3b356af56374ecb635a20 (patch) | |
tree | 6f2e10fab4cbb1ba58d0cd1a130d52f440dbd713 | |
parent | 484bf14a6bac3174900f0b7783f41c5b3bab0217 (diff) | |
download | lua-63720a4290e1ed3042e3b356af56374ecb635a20.tar.gz lua-63720a4290e1ed3042e3b356af56374ecb635a20.tar.bz2 lua-63720a4290e1ed3042e3b356af56374ecb635a20.zip |
janitor work (comments, variable names, some other details)
-rw-r--r-- | ltable.c | 56 |
1 files changed, 31 insertions, 25 deletions
@@ -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 | */ |
226 | static unsigned int computesizes (unsigned int nums[], unsigned int *narray) { | 227 | static 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 | */ | ||
259 | static unsigned int numusearray (const Table *t, unsigned int *nums) { | 265 | static 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 | ||
285 | static int numusehash (const Table *t, unsigned int *nums, | 291 | static 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 | */ |
379 | static void rehash (lua_State *L, Table *t, const TValue *ek) { | 384 | static 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 | ||