From 63720a4290e1ed3042e3b356af56374ecb635a20 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Mon, 30 Mar 2015 16:51:00 -0300 Subject: janitor work (comments, variable names, some other details) --- ltable.c | 56 +++++++++++++++++++++++++++++++------------------------- 1 file 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 @@ /* -** $Id: ltable.c,v 2.106 2015/03/03 19:53:13 roberto Exp roberto $ +** $Id: ltable.c,v 2.107 2015/03/30 15:36:53 roberto Exp roberto $ ** Lua tables (hash) ** See Copyright Notice in lua.h */ @@ -14,8 +14,8 @@ ** Implementation of tables (aka arrays, objects, or hash tables). ** Tables keep its elements in two parts: an array part and a hash part. ** Non-negative integer keys are all candidates to be kept in the array -** part. The actual size of the array is the largest 'n' such that at -** least half the slots between 0 and n are in use. +** part. The actual size of the array is the largest 'n' such that +** more than half the slots between 1 and n are in use. ** Hash uses a mix of chained scatter table with Brent's variation. ** A main invariant of these tables is that, if an element is not ** 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) { /* ** 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. Put in '*narray' the optimal size, and -** return the number of elements that will go to that part. +** 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. */ -static unsigned int computesizes (unsigned int nums[], unsigned int *narray) { +static unsigned int computesizes (unsigned int nums[], unsigned int *pna) { int i; - unsigned int twotoi; /* 2^i */ + unsigned int twotoi; /* 2^i (candidate for optimal size) */ unsigned int a = 0; /* number of elements smaller than 2^i */ unsigned int na = 0; /* number of elements to go to array part */ - unsigned int n = 0; /* optimal size for array part */ - for (i = 0, twotoi = 1; twotoi/2 < *narray; i++, twotoi *= 2) { + unsigned int optimal = 0; /* optimal size for array part */ + /* loop while keys can fill more than half of total size */ + for (i = 0, twotoi = 1; *pna > twotoi / 2; i++, twotoi *= 2) { if (nums[i] > 0) { a += nums[i]; if (a > twotoi/2) { /* more than half elements present? */ - n = twotoi; /* optimal size (till now) */ - na = a; /* all elements up to 'n' will go to array part */ + optimal = twotoi; /* optimal size (till now) */ + na = a; /* all elements up to 'optimal' will go to array part */ } } - if (a == *narray) break; /* all elements already counted */ } - *narray = n; - lua_assert(*narray/2 <= na && na <= *narray); - return na; + lua_assert((optimal == 0 || optimal / 2 < na) && na <= optimal); + *pna = na; + return optimal; } @@ -256,6 +257,11 @@ static int countint (const TValue *key, unsigned int *nums) { } +/* +** Count keys in array part of table 't': Fill 'nums[i]' with +** number of keys that will go into corresponding slice and return +** total number of non-nil keys. +*/ static unsigned int numusearray (const Table *t, unsigned int *nums) { int lg; unsigned int ttlg; /* 2^lg */ @@ -282,8 +288,7 @@ static unsigned int numusearray (const Table *t, unsigned int *nums) { } -static int numusehash (const Table *t, unsigned int *nums, - unsigned int *pnasize) { +static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) { int totaluse = 0; /* total number of elements */ int ause = 0; /* elements added to 'nums' (can go to array part) */ int i = sizenode(t); @@ -294,7 +299,7 @@ static int numusehash (const Table *t, unsigned int *nums, totaluse++; } } - *pnasize += ause; + *pna += ause; return totaluse; } @@ -377,21 +382,22 @@ void luaH_resizearray (lua_State *L, Table *t, unsigned int nasize) { ** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i */ static void rehash (lua_State *L, Table *t, const TValue *ek) { - unsigned int nasize, na; + unsigned int asize; /* optimal size for array part */ + unsigned int na; /* number of keys in the array part */ unsigned int nums[MAXABITS + 1]; int i; int totaluse; for (i = 0; i <= MAXABITS; i++) nums[i] = 0; /* reset counts */ - 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 */ + na = numusearray(t, nums); /* count keys in array part */ + totaluse = na; /* all those keys are integer keys */ + totaluse += numusehash(t, nums, &na); /* count keys in hash part */ /* count extra key */ - nasize += countint(ek, nums); + na += countint(ek, nums); totaluse++; /* compute new size for array part */ - na = computesizes(nums, &nasize); + asize = computesizes(nums, &na); /* resize the table to new computed sizes */ - luaH_resize(L, t, nasize, totaluse - na); + luaH_resize(L, t, asize, totaluse - na); } -- cgit v1.2.3-55-g6feb