The basics and design of lua table

The basics and design of lua table

1. "TABLE" IN LUA

2. OUTLINE
Basic of Lua "table"
Adapt Lua "table" for multiple data structure
Dive into Lua "table" source code

3. OVERVIEW OF LUA

4. OVERVIEW OF LUA
Lua is a powerful, ecient, lightweight, embeddable
scripting language.
multi-paradigm: Lua supports procedural
programming, object-oriented programming,
functional programming, etc.
dynamically-type: types are attached to values rather
than to variables.
Lua has automatic memory management with
incremental garbage collection.

5. OVERVIEW OF LUA
basic types (rst-class):
1. nil (like "None" in Python, including undened
variables)
2. boolean: true, false
3. number: double-precision oating-point numbers
(like "double" in C)
4. string: immutable (once internalized, cannot be
changed)
5. table: associative arrays
6. function: Lua functions, C functions
7. heavy userdata
8. light userdata
9. thread: coroutines

6. 9. thread: coroutines
OVERVIEW OF TABLE IN LUA
Tables are the main — in fact, the only — data-
structuring mechanism in Lua.
Tables in Lua are associative arrays, that is, they can be
indexed by any value (except nil) and can hold values
of any type.
Tables are dynamic in the sense that they may grow
when data is added to them (by assigning a value to a
hitherto non-existent eld) and shrink when data is
removed from them (by assigning nil to a eld).

7. BASIC

8. TABLE CREATION
-- This is a comment.
-- Empty table
local t1 = {}
-- Table as an array
local t2 = { 1, 2, "str", t1 }
-- Table as a hashtable
local t3 = {
["k1"] = "v1",
k2 = "v2",
}
-- Table as mixed data structure of array and hashtable
local t4 = {
"e1", -- stored in the array part
["k1"] = "v1", -- stored in the hash part

9. TABLE AS AN ARRAY
Array Operations:
Set the element of position "n"
Get the element of position "n"
Get the number of elements
Iterate over all elements
Delete the element of position "n"

10. TABLE AS AN ARRAY: SETTER
Set the element of position "n"
NOTE: index in Lua starts from 1
-- Way #1: specify the index
local t = {}
t[1] = "e1"
t[2] = "e2"
t[3] = "e3"
t[4] = "e4"
-- Way #2: use table.insert (list, [pos,] value)
local t = {}
table.insert(t, 1, "e1")
table.insert(t, 2, "e2")
-- table.insert(t, x) inserts x at the end of list t
table.insert(t, "e3")
table.insert(t, "e4")
See the manual of table.insert

11. TABLE AS AN ARRAY: GETTER
Get the element of position "n"
local t = {"e1", "e2", "e3", "e4"}
-- Get the fourth element
print(t[4])
--[[
This is a multi-line comment.
Output:
e4
]]

12. TABLE AS AN ARRAY: GET ELEMENT NUMBER
Get the number of elements
local t = {"e1", "e2", "e3", "e4"}
-- Way #1: the length operator "#"
print(#t)
--[[
Output:
4
]]
-- Way #2
--[[
table.unpack(t) returns "e1", "e2", "e3", "e4"
so it becomes:
print(select('#', "e1", "e2", "e3", "e4"))
]]
print(select('#', table.unpack(t)))
Refer to:
manual of the length operator "#"
manual of select
manual of table.unpack

13. TABLE AS AN ARRAY: ITERATION
Iterate over all elements
local t = {"e1", "e2", "e3", "e4"}
-- Forward iteration
for i = 1, 4 do
print(t[i])
end
--[[
Output:
e1
e2
e3
e4
]]
-- More general way:
for i = 1, #t do
print(t[i])
There's another way of using an iterator. We will talk
about that later.

14. TABLE AS AN ARRAY: DELETE
Delete the element of position "n"
-- Way #1: set the specified element as nil
local t = {"e1", "e2", "e3", "e4"}
-- Delete the third element
t[3] = nil
--[[
NOTE:
1. Lua table will not pack the elements backward to fill the empty slot
2. the number of elements will not change
]]
print("The number of elements:", #t)
for i = 1, #t do
print(t[i])
end
--[[
Output:

15. TABLE AS AN ARRAY: DELETE
Delete the element of position "n"
-- Way #2: use table.remove (list [, pos])
local t = {"e1", "e2", "e3", "e4"}
table.remove(t, 3)
print("The number of elements:", #t)
for i = 1, #t do
print(t[i])
end
--[[
Output:
The number of elements: 3
e1
e2
e4
]]
-- table.remove(t) removes the last element of list t.
See the manual of table.remove

16. TABLE AS AN ARRAY: DELETE
Common misuse of table.remove in a loop
local t = {1, 2, 3, 4}
for i = 1, #t do
if t[i] < 4 then
table.remove(t, i)
end
end
--[[
Opps...
lua: xxx.lua:4: attempt to compare nil with number
stack traceback:
xxx.lua:4: in main chunk
[C]: in ?
]]
Why?

17. TABLE AS AN ARRAY: DELETE
Trace the source code using print
local t = {1, 2, 3, 4}
for i = 1, #t do
print(i, t[i])
if t[i] < 4 then
table.remove(t, i)
end
end
--[[
1 1
2 3
3 nil
lua: xxx.lua:5: attempt to compare nil with number
stack traceback:
xxx.lua:5: in main chunk
[C]: in ?
]]

18. TABLE AS AN ARRAY: DELETE
Straightforward solution: use backward iteration.
local t = {1, 2, 3, 4}
for i = #t, 1, -1 do
if t[i] < 4 then
table.remove(t, i)
end
end
for i = 1, #t do
print(t[i])
end
--[[
Output:
4
]]
We will see another misuse case of table.remove when
we discuss iterator ;)

19. TABLE AS A HASHTABLE
Hashtable Operations:
Set the value of key "k"
Get the value of key "k"
Delete the value of key "k"
Iterate over all key-value pairs
Get the number of key-value pairs

20. TABLE AS A HASHTABLE: SETTER
local t = {}
-- Way #1
t["key"] = "value"
-- Way #2: syntactic sugar
t.key = "value"
-- Compare with the following code:
local key = "key"
t[key] = "value"

21. TABLE AS A HASHTABLE: GETTER
local t = {
"key" = "value",
}
print("t[\"key\"] = ", t["key"])
print("t.key = ", t.key)
local k = "key"
print("t[k] = ", t[k])
-- t.k is equivalent to t["k"]
print("t.k = ", t.k)
--[[
Output:
t["key"] = value
t.key = value
t[k] = value
t.k = nil

22. TABLE AS A HASHTABLE: DELETE
local t = {
"key" = "value",
}
t.key = nil

23. TABLE AS A HASHTABLE: ITERATION

24. TABLE AS A HASHTABLE: ITERATION
Meet `next (table [, index]) `
Allows a program to traverse all elds of a table. Its
rst argument is a table and its second argument is
an index in this table. next returns the next index of
the table and its associated value. When called with nil
as its second argument, next returns an initial index
and its associated value. When called with the last
index, or with nil in an empty table, next returns nil. If
the second argument is absent, then it is interpreted
as nil. In particular, you can use next(t) to check
whether a table is empty.

25. TABLE AS A HASHTABLE: ITERATION
local t = {
k1 = "v1",
k2 = "v2",
k3 = "v3",
}
local k, v
-- Note: equivalent to:
-- local k = nil
-- local v = nil
for i = 1, 3 do
k, v = next(t, k)
print(k, v)
end
-- NOTE: The order in which the indices are enumerated is not specified, even for numeric indices.
--[[
Output:
See the manual of next

26. TABLE AS A HASHTABLE: ITERATION
What if we don't know there's three key-value pairs in
the table `t`?
local t = {
k1 = "v1",
k2 = "v2",
k3 = "v3",
}
local k, v = next(t, k)
while k do
-- Note: equivalent to:
-- while k ~= nil do
print(k, v)
k, v = next(t, k)
end
--[[
Output:
k2 v2
k1 v1

27. ITERATOR
Advanced skill: meet the "generic for" in Lua.
for {var-list} in {exp-list} do
{body}
end
Now we can write an iterator and use it in the generic
for loop!

28. ITERATOR
Hand-written iterator (V1):
local t = {
k1 = "v1",
k2 = "v2",
k3 = "v3",
}
local function iter(t)
local last_k
return function()
local v
last_k, v = next(t, last_k)
return last_k, v
end
end
-- Use the iterator in the generic for loop
for k, v in iter(t) do
print(k, v)
It would be dicult to understand if you don't know
anything about closure or lambda! :(

29. ITERATOR
Hand-written iterator (V2): we can pass a function and its
parameters in {exp-list} of "generic for".
local t = {
k1 = "v1",
k2 = "v2",
k3 = "v3",
}
for k, v in next, t do
print(k, v)
end
--[[
Output:
k3 v3
k2 v2
k1 v1
]]
Simpler code :)
It would still be dicult to understand if you don't
know functions in Lua are rst-class variables! :(

30. ITERATOR
There's a built-in iterator: `pairs`! XD
local t = {
k1 = "v1",
k2 = "v2",
k3 = "v3",
}
for k, v in pairs(t) do
print(k, v)
end
--[[
Output:
k3 v3
k1 v1
k2 v2
]]
See the manual of pairs

31. ITERATOR
There's another built-in iterator for array: `ipairs`! XD
local t = {"e1", "e2", "e3", "e4"}
-- Only forward iteration
for i, v in ipairs(t) do
print(i, v)
end
--[[
Output:
1 e1
2 e2
3 e3
4 e4
]]
See the manual of ipairs

32. Now we can talk about another common misuse of
table.remove in loop.
local t = {1, 2, 3, 4}
for i, v in ipairs(t) do
print("Access the element: ", v)
if v < 4 then
table.remove(t, i)
end
end
print("Result:")
for i, v in ipairs(t) do
print(i, v)
end
--[[
Output:
Access the element: 1
Access the element: 3

33. TABLE AS A HASHTABLE: GET THE NUMBER OF KEY-VALUE PAIRS
local t = {
k1 = "v1",
k2 = "v2",
k3 = "v3",
}
-- Try the length operator "#":
print(#t)
--[[
Output:
0
]]
Opps...The length operator "#" only deals with the array
part of table. :(

34. TABLE AS A HASHTABLE: GET THE NUMBER OF KEY-VALUE PAIRS
Since we know how to iterator over the table, we know
how to count all the key-value pairs. :)
local t = {
k1 = "v1",
k2 = "v2",
k3 = "v3",
}
local cnt = 0
for i, v in pairs(t) do
cnt = cnt + 1
end
print(cnt)
--[[
Output:
3
]]
Complexity: O(N)

35. DATA STRUCTURE

36. MATRICES / MULTI-DIMENSIONAL ARRAYS
Like C array:
-- Create a matrix of zeros with dimensions N by M
-- Way #1
mt = {} -- create the matrix
for i = 1, N do
mt[i] = {} -- create a new row
for j = 1, M do
mt[i][j] = 0
end
end
-- Way #2
mt = {} -- create the matrix
for i = 1, N do
for j = 1, M do
mt[i*M + j] = 0
end
end

37. LINKED LISTS
-- local node = {next = node, value = v}
-- local list = first_node
function traverse(list)
local node = list
while node do
print(node.value)
node = node.next
end
end
-- We counting the nodes from 1
function insert_kth_node(list, k, node)
assert(k > 0, "invalid k")
-- Insert from front
if k == 1 then
node.next = list

38. STACKS
-- Use Stack as a namespace
local Stack = {}
function Stack.push(stack, element)
table.insert(stack, element)
end
function Stack.pop(stack)
table.remove(stack)
end
function Stack.top(stack)
return stack[#stack]
end
return Stack

39. QUEUES AND DOUBLE QUEUES
local Queue = {}
function Queue.new()
return {first = 0, last = -1}
end
function Queue.pushleft(queue, value)
local first = queue.first - 1
queue.first = first
queue[first] = value
end
function Queue.pushright(queue, value)
local last = queue.last + 1
queue.last = last
queue[last] = value
end

40. SETS
local Set = {}
function Set.new()
return {}
end
function Set.add(set, element)
set[element] = true
end
function Set.has(set, element)
return set[element]
end
-- Union of two sets
function Set.union(set1, set2)
local union = {}
for _, set in ipairs({set1, set2}) do

41. DIVE INTO LUA SOURCE CODE
The version of Lua source code is 5.2
I omit and modify some code for simplicity. XD

42. HOW DO LUA STORE TABLE?

43. HOW DO LUA STORE TABLE?
Denition in lobject.h:
typedef struct Table {
lu_byte lsizenode; /* log2 of size of `node' array */
TValue *array; /* array part */
Node *node;
Node *lastfree; /* any free position is before this position */
int sizearray; /* size of `array' array */
} Table;

44. WHAT DOES `TABLE` CONTAIN?
A `Table` instance has at lease three continued areas
in memory:
The `Table` instance itself.
`array`: array part of `Table`
`node`: hash part of `Table`

45. WHAT DOES `TABLE` CONTAIN?
Fields of recording the size:
size of array part: `sizearray`
size of hash part: 2^`lsizenode`
#define twoto(x) (1<<(x))
#define sizenode(t) (twoto((t)->lsizenode))

46. Macros related to `Table`:
#define gnode(t,i) (&(t)->node[i])
We will meet this macro later. ;)

47. WHAT IS `NODE`?
typedef struct Node {
TValue i_val;
TKey i_key;
} Node;
`Node` is the structure for key-value pair

48. Macros related to `Node`:
#define gval(n) (&(n)->i_val)

49. WHAT IS `TVALUE` THEN?
typedef struct lua_TValue TValue;
/*
** Tagged Values. This is the basic representation of values in Lua,
** an actual value plus a tag with its type.
*/
struct lua_TValue {
Value value_;
int tt_;
};
`TValue` = Tagged Value
`TValue` contains the value and a type tag
Lua represents values as tagged unions, that is, as
pairs (t, v), where t is an integer tag identifying the type
of the value v, which is a union of C types
implementing Lua types.
omitted source code: NaN Trick

50. Macros related to `TValue`:
#define val_(o) ((o)->value_)
/* raw type tag of a TValue */
#define rttype(o) ((o)->tt_)
#define setobj(L,obj1,obj2) \
{ const TValue *io2=(obj2); TValue *io1=(obj1); \
io1->value_ = io2->value_; io1->tt_ = io2->tt_; }
We will meet these macros later. ;)

51. HOW DOES THE TAG DISTINGUISH DIFFERENT TYPES OF LUA
VALUE?
lua.h
/*
** basic types
*/
#define LUA_TNONE (-1)
#define LUA_TNIL 0
#define LUA_TBOOLEAN 1
#define LUA_TLIGHTUSERDATA 2
#define LUA_TNUMBER 3
#define LUA_TSTRING 4
#define LUA_TTABLE 5
#define LUA_TFUNCTION 6
#define LUA_TUSERDATA 7
#define LUA_TTHREAD 8
#define LUA_NUMTAGS 9

52. HOW DOES THE TAG DISTINGUISH DIFFERENT TYPES OF LUA
VALUE?
/* raw type tag of a TValue */
#define rttype(o) ((o)->tt_)
/* Macros to test type */
#define checktag(o,t) (rttype(o) == (t))
#define ttistable(o) checktag((o), LUA_TTABLE)
#define hvalue(o) check_exp(ttistable(o), &val_(o).gc->h)
Again, we will meet these macros later. ;)

53. WHAT IS `VALUE`?
union Value {
GCObject *gc; /* collectable objects */
void *p; /* light userdata */
int b; /* booleans */
lua_CFunction f; /* light C functions */
lua_Number n; /* numbers */
};
`Value` can be:
`nil`? No! Tag of `TValue` is enough.
#define settt_(o,t) ((o)->tt_=(t))
#define setnilvalue(obj) settt_(obj, LUA_TNIL)
#define ttisnil(o) checktag((o), LUA_TNIL)

54. WHAT IS `VALUE`?
union Value {
GCObject *gc; /* collectable objects */
void *p; /* light userdata */
int b; /* booleans */
lua_CFunction f; /* light C functions */
lua_Number n; /* numbers */
};
`Value` can be:
boolean? Yes! `Value` = `b`
number? Yes! `Value` = `n`
light userdata? Yes! `Value` = `p`
light C functions? Yes! `Value` = `f`
#define val_(o) ((o)->value_)
#define num_(o) (val_(o).n)
#define nvalue(o) check_exp(ttisnumber(o), num_(o))
#define setnvalue(obj,x) \
{ TValue *io=(obj); num_(io)=(x); settt_(io, LUA_TNUMBER); }

55. WHAT IS `VALUE`?
union Value {
GCObject *gc; /* collectable objects */
void *p; /* light userdata */
int b; /* booleans */
lua_CFunction f; /* light C functions */
lua_Number n; /* numbers */
};
`Value` can be:
string, table, other function, heavy userdata, thread?
`Value` = `gc`
#define sethvalue(L,obj,x) \
{ TValue *io=(obj); \
val_(io).gc=cast(GCObject *, (x)); settt_(io, LUA_TTABLE); }

56. WHAT IS `GCOBJECT` THEN?
lstate.h
/*
** Union of all collectable objects
*/
typedef union GCObject GCObject;
union GCObject {
GCheader gch; /* common header */
union TString ts;
union Udata u;
union Closure cl;
struct Table h;
struct Proto p;
struct UpVal uv;
struct lua_State th; /* thread */
};

57. REVIEW: WHAT IS `TVALUE`?

58. WHAT IS `TKEY`?
typedef union TKey {
struct {
Value value_;
int tt_;
struct Node *next; /* for chaining */
} nk;
TValue tvk;
} TKey;

59. Macros related to `TKey`:
#define gkey(n) (&(n)->i_key.tvk)
#define gnext(n) ((n)->i_key.nk.next)

60. REVIEW: WHAT IS `NODE`?
Combine `TValue` and `TKey` into `Node`.

61. WHAT HAPPENS WHEN CREATING A
`TABLE`?

62. GENERAL PROCEDURE OF LUA PROGRAM:
Lua programs are not interpreted directly from the
textual Lua le, but are compiled into bytecode, which is
then run on the Lua virtual machine.

63. GENERAL PROCEDURE OF LUA PROGRAM:
Here we care about the execution phrase, and we will
start our analysis from function `luaV_execute`.

64. BRIEF INTRODUCTION OF LUA VM AND ITS INSTRUCTIONS
xed size (32 bit unsigned integer)
register-based
instruction formats (`sBx' : signed Bx):
We will meet the following guys later:
R(A) : Register A
RK(B) : Register B or a constant index

65. START FROM THE NAIVE EXAMPLE
local t = {}
0+ params, 2 slots, 1 upvalue, 1 local, 0 constants, 0 functions
1 [1] NEWTABLE 0 0 0
2 [1] RETURN 0 1
Instructions related to table creation:
1 [1] NEWTABLE 0 0 0

66. NEWTABLE INSTRUCTION
NEWTABLE A B C R(A) := {} (size = B,C)
Creates a new empty table at register R(A).
B: encoded size information for the array part of the
table.
C: encoded size information for the hash part of the
table.

67. EXECUTE NEWTABLE IN LUA VM
void luaV_execute (lua_State *L) {
CallInfo *ci = L->ci;
LClosure *cl;
TValue *k;
StkId base;
newframe: /* reentry point when frame changes (call/return) */
lua_assert(ci == L->ci);
cl = clLvalue(ci->func);
k = cl->p->k;
base = ci->u.l.base;
/* main loop of interpreter */
for (;;) {
Instruction i = *(ci->u.l.savedpc++);
StkId ra;
if ((L->hookmask & (LUA_MASKLINE | LUA_MASKCOUNT)) &&
(--L->hookcount == 0 || L->hookmask & LUA_MASKLINE)) {
Protect(traceexec(L));
}
A bit confused?

68. EXECUTE NEWTABLE IN LUA VM
We only need to trace the following part of code for the
naive example. ;)
vmcase(OP_NEWTABLE,
// Get the operator B from the instruction
int b = GETARG_B(i);
// Get the operator C from the instruction
int c = GETARG_C(i);
Table *t = luaH_new(L);
// Remember this macro: `sethvalue` ? ;)
sethvalue(L, ra, t);
)
Now we only need to look at `luaH_new`. :)

69. EXECUTE NEWTABLE IN LUA VM
Table *luaH_new (lua_State *L) {
Table *t = &luaC_newobj(L, LUA_TTABLE, sizeof(Table), NULL, 0)->h;
t->array = NULL;
t->sizearray = 0;
setnodevector(L, t, 0);
return t;
}
static void setnodevector (lua_State *L, Table *t, int size) {
int lsize;
if (size == 0) { /* no elements to hash part? */
t->node = cast(Node *, dummynode); /* use common `dummynode' */
lsize = 0;
}
else {
int i;
lsize = luaO_ceillog2(size);
if (lsize > MAXBITS)
Confused by `setnodevector`?

70. IT'S SIMPLER IN OUR CASE...
Table *luaH_new (lua_State *L) {
Table *t = &luaC_newobj(L, LUA_TTABLE, sizeof(Table), NULL, 0)->h;
t->array = NULL;
t->sizearray = 0;
t->node = cast(Node *, dummynode); /* use common `dummynode' */
t->lsizenode = 0;
t->lastfree = gnode(t, 0); /* all positions are free */
return t;
}

71. WHAT'S `DUMMYNODE`?
/* macro defining a nil value */
#define NILCONSTANT {NULL}, LUA_TNIL
#define dummynode (&dummynode_)
#define isdummy(n) ((n) == dummynode)
static const Node dummynode_ = {
{NILCONSTANT}, /* value */
{{NILCONSTANT, NULL}} /* key */
};
All empty table in Lua points to the same memory area.
CLEVER Lua!

72. WHAT HAPPENS WHEN CREATING A
`TABLE`?
WHAT ABOUT CREATING A NON-EMPTY TABLE?
We will come back to this topic later. ;)

73. WHAT HAPPENS WHEN ACCESSING A
`TABLE`?

74. ANOTHER NAIVE EXAMPLE:
local t = {}
return t[1]
0+ params, 2 slots, 1 upvalue, 1 local, 1 constant, 0 functions
1 [1] NEWTABLE 0 0 0
2 [2] GETTABLE 1 0 -1 ; 1
3 [2] RETURN 1 2
4 [2] RETURN 0 1
Instructions related to accessing table:
2 [2] GETTABLE 1 0 -1 ; 1

75. GETTABLE INSTRUCTION
GETTABLE A B C R(A) := R(B)[RK(C)]
Copies the value from a table element into register
R(A).
The table is referenced by register R(B).
The index to the table is given by RK(C), which may be
the value of register R(C) or a constant number.

76. EXECUTE GETTABLE IN LUA VM
Look at the for loop in `luaV_execute` (lvm.c):
vmcase(OP_GETTABLE,
Protect(luaV_gettable(L, RB(i), RKC(i), ra));
)
Now we need to look at `luaV_gettable`. :)

77. EXECUTE GETTABLE IN LUA VM
void luaV_gettable (lua_State *L, const TValue *t, TValue *key, TValue *val)
// Remember this macro: `ttistable` ? ;)
if (ttistable(t)) { /* `t' is a table? */
// Remember this macro: `hvalue` ? ;)
Table *h = hvalue(t);
const TValue *res = luaH_get(h, key); /* do a primitive get */
// Remember this macro: `ttisnil` ? ;)
if (!ttisnil(res)) { /* result is not nil? */
// Remember this macro: `setobj` ? ;)
setobj(L, val, res);
}
}
return;
}
Now only the function `luaH_get` causes our
headaches.

78. DIVE INTO `LUAH_GET`
/*
** main search function
*/
const TValue *luaH_get (Table *t, const TValue *key) {
switch (ttype(key)) {
case LUA_TSHRSTR: return luaH_getstr(t, rawtsvalue(key));
case LUA_TNIL: return luaO_nilobject;
case LUA_TNUMBER: {
int k;
lua_Number n = nvalue(key);
lua_number2int(k, n);
if (luai_numeq(cast_num(k), n)) /* index is int? */
return luaH_getint(t, k); /* use specialized version */
/* else go through */
}
default: {
Node *n = mainposition(t, key);
do { /* check whether `key' is somewhere in the chain */

79. IT'S SIMPLER IN OUR CASE...
const TValue *luaH_get (Table *t, const TValue *key) {
int k;
// Remember this macro: `nvalue` ? ;)
lua_Number n = nvalue(key);
lua_number2int(k, n);
if (luai_numeq(cast_num(k), n)) /* index is int? */
return luaH_getint(t, k); /* use specialized version */
}
What's the so-called specialized function
`luaH_getint`?

80. DIVE INTO `LUAH_GET`
/*
** search function for integers
*/
const TValue *luaH_getint (Table *t, int key) {
/* (1 <= key && key <= t->sizearray) */
if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray))
return &t->array[key-1];
else {
lua_Number nk = cast_num(key);
Node *n = hashnum(t, nk);
do { /* check whether `key' is somewhere in the chain */
if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)), nk))
return gval(n); /* that's it */
else n = gnext(n);
} while (n);
return luaO_nilobject;
}
}
If the int key is smaller than the size of array, access
the array part.
Otherwises, compute the hash value of the key, and
access the hash part.

81. WHAT DOES THIS LOOP DO?
do { /* check whether `key' is somewhere in the chain */
if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)), nk))
return gval(n); /* that's it */
else n = gnext(n);
} while (n);
return luaO_nilobject;

82. DIVE INTO `LUAH_GET`
Lua table uses open addressing to resolve hash
collision:

83. DIVE INTO `LUAH_GET`
Lua denes the index of the hash part of table as
"mainposition".
The rest part of `luaH_get` is similar to
`luaH_getint`. XD

84. WHAT HAPPENS WHEN SETTING THE
VALUE OF A `TABLE` ELEMENT?

85. ALWAYS NAIVE EXAMPLE :)
local t = {}
t[1] = 3
0+ params, 2 slots, 1 upvalue, 1 local, 2 constants, 0 functions
1 [1] NEWTABLE 0 0 0
2 [2] SETTABLE 0 -1 -2 ; 1 3
3 [2] RETURN 0 1
Instructions related to accessing table:
2 [2] SETTABLE 0 -1 -2 ; 1 3

86. SETTABLE INSTRUCTION
SETTABLE A B C R(A)[RK(B)] := RK(C)
Copies the value from register R(C) or a constant into a
table element.
The table is referenced by register R(A).
The index to the table is given by RK(B), which may be
the value of register R(B) or a constant number.

87. EXECUTE SETTABLE IN LUA VM
Look at the for loop in `luaV_execute` (lvm.c):
vmcase(OP_SETTABLE,
Protect(luaV_settable(L, ra, RKB(i), RKC(i)));
)
It looks like the case of `GETTABLE`. XD

88. EXECUTE SETTABLE IN LUA VM
Now look at function `luaV_settable`:
void luaV_settable (lua_State *L, const TValue *t, TValue *key, TValue *val)
if (ttistable(t)) { /* `t' is a table? */
Table *h = hvalue(t);
// Remember `luaH_get`?
TValue *oldval = cast(TValue *, luaH_get(h, key));
/* is there a previous entry in the table? */
if (!ttisnil(oldval) ||
/* no previous entry; must create one. (The next test is
* always true; we only need the assignment.) */
(oldval = luaH_newkey(L, h, key), 1)) {
/* (now) there is an entry with given key */
setobj(L, oldval, val); /* assign new value to that entry */
}
}
return;
}
C trick of comma operator: (a, b, c) is a sequence of
expressions, separated by commas, which evaluates to
the last expression c.

89. WHAT DOES LUAV_SETTABLE DO?
1. Get the old value of the key.
2. If
The old value is nil: create a new key by
`luaH_newkey` and write the corresponding value.
Otherwises, rewrite the value.

90. WHAT DOES LUAH_NEWKEY DO?
/*
** inserts a new key into a hash table; first, check whether key's main
** position is free. If not, check whether colliding node is in its main
** position or not: if it is not, move colliding node to an empty place and
** put new key in its main position; otherwise (colliding node is in its main
** position), new key goes to an empty position.
*/
TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {
Node *mp;
if (ttisnil(key)) luaG_runerror(L, "table index is nil");
else if (ttisnumber(key) && luai_numisnan(L, nvalue(key)))
luaG_runerror(L, "table index is NaN");
mp = mainposition(t, key);
if (!ttisnil(gval(mp)) || isdummy(mp)) { /* main position is taken? */
Node *othern;
Node *n = getfreepos(t); /* get a free place */
if (n == NULL) { /* cannot find a free place? */
rehash(L, t, key); /* grow table */
Don't be scared, we will take it apart. ;D

91. THE LUCKIEST CASE
There's free space. The main position has not been
occupied. XD
TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {
Node *mp;
mp = mainposition(t, key);
setobj(L, gkey(mp), key);
return gval(mp);
}

92. CASE 2
There's free space. The main position has been occupied,
and that bad guy is occupying its main position. :|
TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {
Node *mp;
mp = mainposition(t, key);
if (!ttisnil(gval(mp)) || isdummy(mp)) { /* main position is taken? */
Node *othern;
Node *n = getfreepos(t); /* get a free place */
lua_assert(!isdummy(n));
/* colliding node is in its own main position */
/* new node will go into free position */
gnext(n) = gnext(mp); /* chain new position */
gnext(mp) = n;
mp = n;
}
setobj(L, gkey(mp), key);
return gval(mp);
}

93. CASE 3
There's free space. The main position has been occupied,
and that bad guy is not occupying its main position. :(
TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {
Node *mp;
mp = mainposition(t, key);
if (!ttisnil(gval(mp)) || isdummy(mp)) { /* main position is taken? */
Node *othern;
Node *n = getfreepos(t); /* get a free place */
lua_assert(!isdummy(n));
othern = mainposition(t, gkey(mp));
if (othern != mp) { /* is colliding node out of its main position? */
/* yes; move colliding node into free position */
while (gnext(othern) != mp) othern = gnext(othern); /* find previous */
gnext(othern) = n; /* redo the chain with `n' in place of `mp' */
*n = *mp; /* copy colliding node into free pos. (mp->next also goes) */
gnext(mp) = NULL; /* now `mp' is free */
setnilvalue(gval(mp));
}
}
setobj(L, gkey(mp), key);

94. CASE 4
There's no free space. :(
It will cause rehashing.
The array part may grow or shrink so that at lease half
of the array is occupied. If the array part shrinks, its
rest elements will be inserted into the hash part.
The hash part may grow or shrink, too. Its size is
determined by the number of valid key-value pair,
whose value is not nil, and the number of elements
from the shrinked array part. Moreover, the size is
guaranteed to be power of two. (Remember the
`lsizenode` eld of `Table`?)
I will not show the source code of rehashing in order not
to scare you. XD

95. to scare you. XD
BACK TO THE TOPIC OF CREATING A NON-
EMPTY TABLE XD
What's the dierence between the following code
snippets?
local t = {"e1", "e2", "e3", "e4", "e5"}
local t = {}
t[1] = "e1"
t[2] = "e2"
t[3] = "e3"
t[4] = "e4"
t[5] = "e5"

96. COUNTING THE OCCURRENCES OF
REHASHING:
Zero rehash, resize the array part once at table creation.
:)
local t = {"e1", "e2", "e3", "e4", "e5"}
Rehash four times at SETTABLE. :(
local t = {}
t[1] = "e1" -- rehash
t[2] = "e2" -- rehash
t[3] = "e3" -- rehash
t[4] = "e4"
t[5] = "e5" -- rehash
The rehashing overhead can be much higher if there's
lots of small table in your Lua program.

97. LESSON LEARNED
Prefer this way to avoid initial rehashings of table.
local t = {"e1", "e2", "e3", "e4", "e5"}

98. MORE ABOUT TABLE IN LUA
metatable, metamethod
OO in Lua
Weak table
Special table: `{}` (we have meet it), `_ENV`, `_G`,
etc.
How does luajit accelerate table operations?
...

99. REFERENCES
"The Implementation of Lua 5.0" by Roberto
Ierusalimschy, Luiz Henrique de Figueiredo, Waldemar
Celes
"Programming in Lua" by the leading architect of Lua,
Roberto Ierusalimschy:
"A No-Frills Introduction to Lua 5.1 VM Instructions" by
Kein-Hong Man
"Lua Performance Tips" by Roberto Ierusalimschy
Lua ocial website
First version is free online (Lua
5.0)