0

1 
/*


2 
** $Id: ltable.c,v 2.72.1.1 2013/04/12 18:48:47 roberto Exp $


3 
** Lua tables (hash)


4 
** See Copyright Notice in lua.h


5 
*/


6 


7 


8 
/*


9 
** Implementation of tables (aka arrays, objects, or hash tables).


10 
** Tables keep its elements in two parts: an array part and a hash part.


11 
** Nonnegative integer keys are all candidates to be kept in the array


12 
** part. The actual size of the array is the largest `n' such that at


13 
** least half the slots between 0 and n are in use.


14 
** Hash uses a mix of chained scatter table with Brent's variation.


15 
** A main invariant of these tables is that, if an element is not


16 
** in its main position (i.e. the `original' position that its hash gives


17 
** to it), then the colliding element is in its own main position.


18 
** Hence even when the load factor reaches 100%, performance remains good.


19 
*/


20 


21 
#include <string.h>


22 


23 
#define ltable_c


24 
#define LUA_CORE


25 


26 
#include "lua.h"


27 


28 
#include "ldebug.h"


29 
#include "ldo.h"


30 
#include "lgc.h"


31 
#include "lmem.h"


32 
#include "lobject.h"


33 
#include "lstate.h"


34 
#include "lstring.h"


35 
#include "ltable.h"


36 
#include "lvm.h"


37 


38 


39 
/*


40 
** max size of array part is 2^MAXBITS


41 
*/


42 
#if LUAI_BITSINT >= 32


43 
#define MAXBITS 30


44 
#else


45 
#define MAXBITS (LUAI_BITSINT2)


46 
#endif


47 


48 
#define MAXASIZE (1 << MAXBITS)


49 


50 


51 
#define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t))))


52 


53 
#define hashstr(t,str) hashpow2(t, (str)>tsv.hash)


54 
#define hashboolean(t,p) hashpow2(t, p)


55 


56 


57 
/*


58 
** for some types, it is better to avoid modulus by power of 2, as


59 
** they tend to have many 2 factors.


60 
*/


61 
#define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)1)1))))


62 


63 


64 
#define hashpointer(t,p) hashmod(t, IntPoint(p))


65 


66 


67 
#define dummynode (&dummynode_)


68 


69 
#define isdummy(n) ((n) == dummynode)


70 


71 
static const Node dummynode_ = {


72 
{NILCONSTANT}, /* value */


73 
{{NILCONSTANT, NULL}} /* key */


74 
};


75 


76 


77 
/*


78 
** hash for lua_Numbers


79 
*/


80 
static Node *hashnum (const Table *t, lua_Number n) {


81 
int i;


82 
luai_hashnum(i, n);


83 
if (i < 0) {


84 
if (cast(unsigned int, i) == 0u  i) /* use unsigned to avoid overflows */


85 
i = 0; /* handle INT_MIN */


86 
i = i; /* must be a positive value */


87 
}


88 
return hashmod(t, i);


89 
}


90 


91 


92 


93 
/*


94 
** returns the `main' position of an element in a table (that is, the index


95 
** of its hash value)


96 
*/


97 
static Node *mainposition (const Table *t, const TValue *key) {


98 
switch (ttype(key)) {


99 
case LUA_TNUMBER:


100 
return hashnum(t, nvalue(key));


101 
case LUA_TLNGSTR: {


102 
TString *s = rawtsvalue(key);


103 
if (s>tsv.extra == 0) { /* no hash? */


104 
s>tsv.hash = luaS_hash(getstr(s), s>tsv.len, s>tsv.hash);


105 
s>tsv.extra = 1; /* now it has its hash */


106 
}


107 
return hashstr(t, rawtsvalue(key));


108 
}


109 
case LUA_TSHRSTR:


110 
return hashstr(t, rawtsvalue(key));


111 
case LUA_TBOOLEAN:


112 
return hashboolean(t, bvalue(key));


113 
case LUA_TLIGHTUSERDATA:


114 
return hashpointer(t, pvalue(key));


115 
case LUA_TLCF:


116 
return hashpointer(t, fvalue(key));


117 
default:


118 
return hashpointer(t, gcvalue(key));


119 
}


120 
}


121 


122 


123 
/*


124 
** returns the index for `key' if `key' is an appropriate key to live in


125 
** the array part of the table, 1 otherwise.


126 
*/


127 
static int arrayindex (const TValue *key) {


128 
if (ttisnumber(key)) {


129 
lua_Number n = nvalue(key);


130 
int k;


131 
lua_number2int(k, n);


132 
if (luai_numeq(cast_num(k), n))


133 
return k;


134 
}


135 
return 1; /* `key' did not match some condition */


136 
}


137 


138 


139 
/*


140 
** returns the index of a `key' for table traversals. First goes all


141 
** elements in the array part, then elements in the hash part. The


142 
** beginning of a traversal is signaled by 1.


143 
*/


144 
static int findindex (lua_State *L, Table *t, StkId key) {


145 
int i;


146 
if (ttisnil(key)) return 1; /* first iteration */


147 
i = arrayindex(key);


148 
if (0 < i && i <= t>sizearray) /* is `key' inside array part? */


149 
return i1; /* yes; that's the index (corrected to C) */


150 
else {


151 
Node *n = mainposition(t, key);


152 
for (;;) { /* check whether `key' is somewhere in the chain */


153 
/* key may be dead already, but it is ok to use it in `next' */


154 
if (luaV_rawequalobj(gkey(n), key) 


155 
(ttisdeadkey(gkey(n)) && iscollectable(key) &&


156 
deadvalue(gkey(n)) == gcvalue(key))) {


157 
i = cast_int(n  gnode(t, 0)); /* key index in hash table */


158 
/* hash elements are numbered after array ones */


159 
return i + t>sizearray;


160 
}


161 
else n = gnext(n);


162 
if (n == NULL)


163 
luaG_runerror(L, "invalid key to " LUA_QL("next")); /* key not found */


164 
}


165 
}


166 
}


167 


168 


169 
int luaH_next (lua_State *L, Table *t, StkId key) {


170 
int i = findindex(L, t, key); /* find original element */


171 
for (i++; i < t>sizearray; i++) { /* try first array part */


172 
if (!ttisnil(&t>array[i])) { /* a nonnil value? */


173 
setnvalue(key, cast_num(i+1));


174 
setobj2s(L, key+1, &t>array[i]);


175 
return 1;


176 
}


177 
}


178 
for (i = t>sizearray; i < sizenode(t); i++) { /* then hash part */


179 
if (!ttisnil(gval(gnode(t, i)))) { /* a nonnil value? */


180 
setobj2s(L, key, gkey(gnode(t, i)));


181 
setobj2s(L, key+1, gval(gnode(t, i)));


182 
return 1;


183 
}


184 
}


185 
return 0; /* no more elements */


186 
}


187 


188 


189 
/*


190 
** {=============================================================


191 
** Rehash


192 
** ==============================================================


193 
*/


194 


195 


196 
static int computesizes (int nums[], int *narray) {


197 
int i;


198 
int twotoi; /* 2^i */


199 
int a = 0; /* number of elements smaller than 2^i */


200 
int na = 0; /* number of elements to go to array part */


201 
int n = 0; /* optimal size for array part */


202 
for (i = 0, twotoi = 1; twotoi/2 < *narray; i++, twotoi *= 2) {


203 
if (nums[i] > 0) {


204 
a += nums[i];


205 
if (a > twotoi/2) { /* more than half elements present? */


206 
n = twotoi; /* optimal size (till now) */


207 
na = a; /* all elements smaller than n will go to array part */


208 
}


209 
}


210 
if (a == *narray) break; /* all elements already counted */


211 
}


212 
*narray = n;


213 
lua_assert(*narray/2 <= na && na <= *narray);


214 
return na;


215 
}


216 


217 


218 
static int countint (const TValue *key, int *nums) {


219 
int k = arrayindex(key);


220 
if (0 < k && k <= MAXASIZE) { /* is `key' an appropriate array index? */


221 
nums[luaO_ceillog2(k)]++; /* count as such */


222 
return 1;


223 
}


224 
else


225 
return 0;


226 
}


227 


228 


229 
static int numusearray (const Table *t, int *nums) {


230 
int lg;


231 
int ttlg; /* 2^lg */


232 
int ause = 0; /* summation of `nums' */


233 
int i = 1; /* count to traverse all array keys */


234 
for (lg=0, ttlg=1; lg<=MAXBITS; lg++, ttlg*=2) { /* for each slice */


235 
int lc = 0; /* counter */


236 
int lim = ttlg;


237 
if (lim > t>sizearray) {


238 
lim = t>sizearray; /* adjust upper limit */


239 
if (i > lim)


240 
break; /* no more elements to count */


241 
}


242 
/* count elements in range (2^(lg1), 2^lg] */


243 
for (; i <= lim; i++) {


244 
if (!ttisnil(&t>array[i1]))


245 
lc++;


246 
}


247 
nums[lg] += lc;


248 
ause += lc;


249 
}


250 
return ause;


251 
}


252 


253 


254 
static int numusehash (const Table *t, int *nums, int *pnasize) {


255 
int totaluse = 0; /* total number of elements */


256 
int ause = 0; /* summation of `nums' */


257 
int i = sizenode(t);


258 
while (i) {


259 
Node *n = &t>node[i];


260 
if (!ttisnil(gval(n))) {


261 
ause += countint(gkey(n), nums);


262 
totaluse++;


263 
}


264 
}


265 
*pnasize += ause;


266 
return totaluse;


267 
}


268 


269 


270 
static void setarrayvector (lua_State *L, Table *t, int size) {


271 
int i;


272 
luaM_reallocvector(L, t>array, t>sizearray, size, TValue);


273 
for (i=t>sizearray; i<size; i++)


274 
setnilvalue(&t>array[i]);


275 
t>sizearray = size;


276 
}


277 


278 


279 
static void setnodevector (lua_State *L, Table *t, int size) {


280 
int lsize;


281 
if (size == 0) { /* no elements to hash part? */


282 
t>node = cast(Node *, dummynode); /* use common `dummynode' */


283 
lsize = 0;


284 
}


285 
else {


286 
int i;


287 
lsize = luaO_ceillog2(size);


288 
if (lsize > MAXBITS)


289 
luaG_runerror(L, "table overflow");


290 
size = twoto(lsize);


291 
t>node = luaM_newvector(L, size, Node);


292 
for (i=0; i<size; i++) {


293 
Node *n = gnode(t, i);


294 
gnext(n) = NULL;


295 
setnilvalue(gkey(n));


296 
setnilvalue(gval(n));


297 
}


298 
}


299 
t>lsizenode = cast_byte(lsize);


300 
t>lastfree = gnode(t, size); /* all positions are free */


301 
}


302 


303 


304 
void luaH_resize (lua_State *L, Table *t, int nasize, int nhsize) {


305 
int i;


306 
int oldasize = t>sizearray;


307 
int oldhsize = t>lsizenode;


308 
Node *nold = t>node; /* save old hash ... */


309 
if (nasize > oldasize) /* array part must grow? */


310 
setarrayvector(L, t, nasize);


311 
/* create new hash part with appropriate size */


312 
setnodevector(L, t, nhsize);


313 
if (nasize < oldasize) { /* array part must shrink? */


314 
t>sizearray = nasize;


315 
/* reinsert elements from vanishing slice */


316 
for (i=nasize; i<oldasize; i++) {


317 
if (!ttisnil(&t>array[i]))


318 
luaH_setint(L, t, i + 1, &t>array[i]);


319 
}


320 
/* shrink array */


321 
luaM_reallocvector(L, t>array, oldasize, nasize, TValue);


322 
}


323 
/* reinsert elements from hash part */


324 
for (i = twoto(oldhsize)  1; i >= 0; i) {


325 
Node *old = nold+i;


326 
if (!ttisnil(gval(old))) {


327 
/* doesn't need barrier/invalidate cache, as entry was


328 
already present in the table */


329 
setobjt2t(L, luaH_set(L, t, gkey(old)), gval(old));


330 
}


331 
}


332 
if (!isdummy(nold))


333 
luaM_freearray(L, nold, cast(size_t, twoto(oldhsize))); /* free old array */


334 
}


335 


336 


337 
void luaH_resizearray (lua_State *L, Table *t, int nasize) {


338 
int nsize = isdummy(t>node) ? 0 : sizenode(t);


339 
luaH_resize(L, t, nasize, nsize);


340 
}


341 


342 


343 
static void rehash (lua_State *L, Table *t, const TValue *ek) {


344 
int nasize, na;


345 
int nums[MAXBITS+1]; /* nums[i] = number of keys with 2^(i1) < k <= 2^i */


346 
int i;


347 
int totaluse;


348 
for (i=0; i<=MAXBITS; i++) nums[i] = 0; /* reset counts */


349 
nasize = numusearray(t, nums); /* count keys in array part */


350 
totaluse = nasize; /* all those keys are integer keys */


351 
totaluse += numusehash(t, nums, &nasize); /* count keys in hash part */


352 
/* count extra key */


353 
nasize += countint(ek, nums);


354 
totaluse++;


355 
/* compute new size for array part */


356 
na = computesizes(nums, &nasize);


357 
/* resize the table to new computed sizes */


358 
luaH_resize(L, t, nasize, totaluse  na);


359 
}


360 


361 


362 


363 
/*


364 
** }=============================================================


365 
*/


366 


367 


368 
Table *luaH_new (lua_State *L) {


369 
Table *t = &luaC_newobj(L, LUA_TTABLE, sizeof(Table), NULL, 0)>h;


370 
t>metatable = NULL;


371 
t>flags = cast_byte(~0);


372 
t>array = NULL;


373 
t>sizearray = 0;


374 
setnodevector(L, t, 0);


375 
return t;


376 
}


377 


378 


379 
void luaH_free (lua_State *L, Table *t) {


380 
if (!isdummy(t>node))


381 
luaM_freearray(L, t>node, cast(size_t, sizenode(t)));


382 
luaM_freearray(L, t>array, t>sizearray);


383 
luaM_free(L, t);


384 
}


385 


386 


387 
static Node *getfreepos (Table *t) {


388 
while (t>lastfree > t>node) {


389 
t>lastfree;


390 
if (ttisnil(gkey(t>lastfree)))


391 
return t>lastfree;


392 
}


393 
return NULL; /* could not find a free place */


394 
}


395 


396 


397 


398 
/*


399 
** inserts a new key into a hash table; first, check whether key's main


400 
** position is free. If not, check whether colliding node is in its main


401 
** position or not: if it is not, move colliding node to an empty place and


402 
** put new key in its main position; otherwise (colliding node is in its main


403 
** position), new key goes to an empty position.


404 
*/


405 
TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {


406 
Node *mp;


407 
if (ttisnil(key)) luaG_runerror(L, "table index is nil");


408 
else if (ttisnumber(key) && luai_numisnan(L, nvalue(key)))


409 
luaG_runerror(L, "table index is NaN");


410 
mp = mainposition(t, key);


411 
if (!ttisnil(gval(mp))  isdummy(mp)) { /* main position is taken? */


412 
Node *othern;


413 
Node *n = getfreepos(t); /* get a free place */


414 
if (n == NULL) { /* cannot find a free place? */


415 
rehash(L, t, key); /* grow table */


416 
/* whatever called 'newkey' take care of TM cache and GC barrier */


417 
return luaH_set(L, t, key); /* insert key into grown table */


418 
}


419 
lua_assert(!isdummy(n));


420 
othern = mainposition(t, gkey(mp));


421 
if (othern != mp) { /* is colliding node out of its main position? */


422 
/* yes; move colliding node into free position */


423 
while (gnext(othern) != mp) othern = gnext(othern); /* find previous */


424 
gnext(othern) = n; /* redo the chain with `n' in place of `mp' */


425 
*n = *mp; /* copy colliding node into free pos. (mp>next also goes) */


426 
gnext(mp) = NULL; /* now `mp' is free */


427 
setnilvalue(gval(mp));


428 
}


429 
else { /* colliding node is in its own main position */


430 
/* new node will go into free position */


431 
gnext(n) = gnext(mp); /* chain new position */


432 
gnext(mp) = n;


433 
mp = n;


434 
}


435 
}


436 
setobj2t(L, gkey(mp), key);


437 
luaC_barrierback(L, obj2gco(t), key);


438 
lua_assert(ttisnil(gval(mp)));


439 
return gval(mp);


440 
}


441 


442 


443 
/*


444 
** search function for integers


445 
*/


446 
const TValue *luaH_getint (Table *t, int key) {


447 
/* (1 <= key && key <= t>sizearray) */


448 
if (cast(unsigned int, key1) < cast(unsigned int, t>sizearray))


449 
return &t>array[key1];


450 
else {


451 
lua_Number nk = cast_num(key);


452 
Node *n = hashnum(t, nk);


453 
do { /* check whether `key' is somewhere in the chain */


454 
if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)), nk))


455 
return gval(n); /* that's it */


456 
else n = gnext(n);


457 
} while (n);


458 
return luaO_nilobject;


459 
}


460 
}


461 


462 


463 
/*


464 
** search function for short strings


465 
*/


466 
const TValue *luaH_getstr (Table *t, TString *key) {


467 
Node *n = hashstr(t, key);


468 
lua_assert(key>tsv.tt == LUA_TSHRSTR);


469 
do { /* check whether `key' is somewhere in the chain */


470 
if (ttisshrstring(gkey(n)) && eqshrstr(rawtsvalue(gkey(n)), key))


471 
return gval(n); /* that's it */


472 
else n = gnext(n);


473 
} while (n);


474 
return luaO_nilobject;


475 
}


476 


477 


478 
/*


479 
** main search function


480 
*/


481 
const TValue *luaH_get (Table *t, const TValue *key) {


482 
switch (ttype(key)) {


483 
case LUA_TSHRSTR: return luaH_getstr(t, rawtsvalue(key));


484 
case LUA_TNIL: return luaO_nilobject;


485 
case LUA_TNUMBER: {


486 
int k;


487 
lua_Number n = nvalue(key);


488 
lua_number2int(k, n);


489 
if (luai_numeq(cast_num(k), n)) /* index is int? */


490 
return luaH_getint(t, k); /* use specialized version */


491 
/* else go through */


492 
}


493 
default: {


494 
Node *n = mainposition(t, key);


495 
do { /* check whether `key' is somewhere in the chain */


496 
if (luaV_rawequalobj(gkey(n), key))


497 
return gval(n); /* that's it */


498 
else n = gnext(n);


499 
} while (n);


500 
return luaO_nilobject;


501 
}


502 
}


503 
}


504 


505 


506 
/*


507 
** beware: when using this function you probably need to check a GC


508 
** barrier and invalidate the TM cache.


509 
*/


510 
TValue *luaH_set (lua_State *L, Table *t, const TValue *key) {


511 
const TValue *p = luaH_get(t, key);


512 
if (p != luaO_nilobject)


513 
return cast(TValue *, p);


514 
else return luaH_newkey(L, t, key);


515 
}


516 


517 


518 
void luaH_setint (lua_State *L, Table *t, int key, TValue *value) {


519 
const TValue *p = luaH_getint(t, key);


520 
TValue *cell;


521 
if (p != luaO_nilobject)


522 
cell = cast(TValue *, p);


523 
else {


524 
TValue k;


525 
setnvalue(&k, cast_num(key));


526 
cell = luaH_newkey(L, t, &k);


527 
}


528 
setobj2t(L, cell, value);


529 
}


530 


531 


532 
static int unbound_search (Table *t, unsigned int j) {


533 
unsigned int i = j; /* i is zero or a present index */


534 
j++;


535 
/* find `i' and `j' such that i is present and j is not */


536 
while (!ttisnil(luaH_getint(t, j))) {


537 
i = j;


538 
j *= 2;


539 
if (j > cast(unsigned int, MAX_INT)) { /* overflow? */


540 
/* table was built with bad purposes: resort to linear search */


541 
i = 1;


542 
while (!ttisnil(luaH_getint(t, i))) i++;


543 
return i  1;


544 
}


545 
}


546 
/* now do a binary search between them */


547 
while (j  i > 1) {


548 
unsigned int m = (i+j)/2;


549 
if (ttisnil(luaH_getint(t, m))) j = m;


550 
else i = m;


551 
}


552 
return i;


553 
}


554 


555 


556 
/*


557 
** Try to find a boundary in table `t'. A `boundary' is an integer index


558 
** such that t[i] is nonnil and t[i+1] is nil (and 0 if t[1] is nil).


559 
*/


560 
int luaH_getn (Table *t) {


561 
unsigned int j = t>sizearray;


562 
if (j > 0 && ttisnil(&t>array[j  1])) {


563 
/* there is a boundary in the array part: (binary) search for it */


564 
unsigned int i = 0;


565 
while (j  i > 1) {


566 
unsigned int m = (i+j)/2;


567 
if (ttisnil(&t>array[m  1])) j = m;


568 
else i = m;


569 
}


570 
return i;


571 
}


572 
/* else must find a boundary in hash part */


573 
else if (isdummy(t>node)) /* hash part is empty? */


574 
return j; /* that is easy... */


575 
else return unbound_search(t, j);


576 
}


577 


578 


579 


580 
#if defined(LUA_DEBUG)


581 


582 
Node *luaH_mainposition (const Table *t, const TValue *key) {


583 
return mainposition(t, key);


584 
}


585 


586 
int luaH_isdummy (Node *n) { return isdummy(n); }


587 


588 
#endif
