2
** $Id: ltable.c,v 2.72 2012/09/11 19:37:16 roberto Exp $
4
** See Copyright Notice in lua.h
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
** Non-negative 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.
40
** max size of array part is 2^MAXBITS
42
#if LUAI_BITSINT >= 32
45
#define MAXBITS (LUAI_BITSINT-2)
48
#define MAXASIZE (1 << MAXBITS)
51
#define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t))))
53
#define hashstr(t,str) hashpow2(t, (str)->tsv.hash)
54
#define hashboolean(t,p) hashpow2(t, p)
58
** for some types, it is better to avoid modulus by power of 2, as
59
** they tend to have many 2 factors.
61
#define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1))))
64
#define hashpointer(t,p) hashmod(t, IntPoint(p))
67
#define dummynode (&dummynode_)
69
#define isdummy(n) ((n) == dummynode)
71
static const Node dummynode_ = {
72
{NILCONSTANT}, /* value */
73
{{NILCONSTANT, NULL}} /* key */
78
** hash for lua_Numbers
80
static Node *hashnum (const Table *t, lua_Number n) {
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 */
94
** returns the `main' position of an element in a table (that is, the index
97
static Node *mainposition (const Table *t, const TValue *key) {
100
return hashnum(t, nvalue(key));
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 */
107
return hashstr(t, rawtsvalue(key));
110
return hashstr(t, rawtsvalue(key));
112
return hashboolean(t, bvalue(key));
113
case LUA_TLIGHTUSERDATA:
114
return hashpointer(t, pvalue(key));
116
return hashpointer(t, fvalue(key));
118
return hashpointer(t, gcvalue(key));
124
** returns the index for `key' if `key' is an appropriate key to live in
125
** the array part of the table, -1 otherwise.
127
static int arrayindex (const TValue *key) {
128
if (ttisnumber(key)) {
129
lua_Number n = nvalue(key);
131
lua_number2int(k, n);
132
if (luai_numeq(cast_num(k), n))
135
return -1; /* `key' did not match some condition */
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.
144
static int findindex (lua_State *L, Table *t, StkId key) {
146
if (ttisnil(key)) return -1; /* first iteration */
148
if (0 < i && i <= t->sizearray) /* is `key' inside array part? */
149
return i-1; /* yes; that's the index (corrected to C) */
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;
163
luaG_runerror(L, "invalid key to " LUA_QL("next")); /* key not found */
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 non-nil value? */
173
setnvalue(key, cast_num(i+1));
174
setobj2s(L, key+1, &t->array[i]);
178
for (i -= t->sizearray; i < sizenode(t); i++) { /* then hash part */
179
if (!ttisnil(gval(gnode(t, i)))) { /* a non-nil value? */
180
setobj2s(L, key, gkey(gnode(t, i)));
181
setobj2s(L, key+1, gval(gnode(t, i)));
185
return 0; /* no more elements */
190
** {=============================================================
192
** ==============================================================
196
static int computesizes (int nums[], int *narray) {
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) {
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 */
210
if (a == *narray) break; /* all elements already counted */
213
lua_assert(*narray/2 <= na && na <= *narray);
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 */
229
static int numusearray (const Table *t, int *nums) {
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 */
237
if (lim > t->sizearray) {
238
lim = t->sizearray; /* adjust upper limit */
240
break; /* no more elements to count */
242
/* count elements in range (2^(lg-1), 2^lg] */
243
for (; i <= lim; i++) {
244
if (!ttisnil(&t->array[i-1]))
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' */
259
Node *n = &t->node[i];
260
if (!ttisnil(gval(n))) {
261
ause += countint(gkey(n), nums);
270
static void setarrayvector (lua_State *L, Table *t, int size) {
272
luaM_reallocvector(L, t->array, t->sizearray, size, TValue);
273
for (i=t->sizearray; i<size; i++)
274
setnilvalue(&t->array[i]);
279
static void setnodevector (lua_State *L, Table *t, int size) {
281
if (size == 0) { /* no elements to hash part? */
282
t->node = cast(Node *, dummynode); /* use common `dummynode' */
287
lsize = luaO_ceillog2(size);
289
luaG_runerror(L, "table overflow");
291
t->node = luaM_newvector(L, size, Node);
292
for (i=0; i<size; i++) {
293
Node *n = gnode(t, i);
295
setnilvalue(gkey(n));
296
setnilvalue(gval(n));
299
t->lsizenode = cast_byte(lsize);
300
t->lastfree = gnode(t, size); /* all positions are free */
304
void luaH_resize (lua_State *L, Table *t, int nasize, int nhsize) {
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
/* re-insert 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]);
321
luaM_reallocvector(L, t->array, oldasize, nasize, TValue);
323
/* re-insert elements from hash part */
324
for (i = twoto(oldhsize) - 1; i >= 0; 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));
333
luaM_freearray(L, nold, cast(size_t, twoto(oldhsize))); /* free old array */
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);
343
static void rehash (lua_State *L, Table *t, const TValue *ek) {
345
int nums[MAXBITS+1]; /* nums[i] = number of keys with 2^(i-1) < k <= 2^i */
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);
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);
364
** }=============================================================
368
Table *luaH_new (lua_State *L) {
369
Table *t = &luaC_newobj(L, LUA_TTABLE, sizeof(Table), NULL, 0)->h;
371
t->flags = cast_byte(~0);
374
setnodevector(L, t, 0);
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);
387
static Node *getfreepos (Table *t) {
388
while (t->lastfree > t->node) {
390
if (ttisnil(gkey(t->lastfree)))
393
return NULL; /* could not find a free place */
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.
405
TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {
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? */
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 */
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));
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 */
436
setobj2t(L, gkey(mp), key);
437
luaC_barrierback(L, obj2gco(t), key);
438
lua_assert(ttisnil(gval(mp)));
444
** search function for integers
446
const TValue *luaH_getint (Table *t, int key) {
447
/* (1 <= key && key <= t->sizearray) */
448
if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray))
449
return &t->array[key-1];
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 */
458
return luaO_nilobject;
464
** search function for short strings
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 */
474
return luaO_nilobject;
479
** main search function
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;
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 */
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 */
500
return luaO_nilobject;
507
** beware: when using this function you probably need to check a GC
508
** barrier and invalidate the TM cache.
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);
518
void luaH_setint (lua_State *L, Table *t, int key, TValue *value) {
519
const TValue *p = luaH_getint(t, key);
521
if (p != luaO_nilobject)
522
cell = cast(TValue *, p);
525
setnvalue(&k, cast_num(key));
526
cell = luaH_newkey(L, t, &k);
528
setobj2t(L, cell, value);
532
static int unbound_search (Table *t, unsigned int j) {
533
unsigned int i = j; /* i is zero or a present index */
535
/* find `i' and `j' such that i is present and j is not */
536
while (!ttisnil(luaH_getint(t, j))) {
539
if (j > cast(unsigned int, MAX_INT)) { /* overflow? */
540
/* table was built with bad purposes: resort to linear search */
542
while (!ttisnil(luaH_getint(t, i))) i++;
546
/* now do a binary search between them */
548
unsigned int m = (i+j)/2;
549
if (ttisnil(luaH_getint(t, m))) j = m;
557
** Try to find a boundary in table `t'. A `boundary' is an integer index
558
** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
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 */
566
unsigned int m = (i+j)/2;
567
if (ttisnil(&t->array[m - 1])) j = m;
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);
580
#if defined(LUA_DEBUG)
582
Node *luaH_mainposition (const Table *t, const TValue *key) {
583
return mainposition(t, key);
586
int luaH_isdummy (Node *n) { return isdummy(n); }