blob: 04326dbb2ef6e073ea916a5ec8872fa558c911f7 (plain)

ofs	hex dump	ascii
0000	89 50 4e 47 0d 0a 1a 0a 00 00 00 0d 49 48 44 52 00 00 04 00 00 00 02 00 08 03 00 00 00 2b 13 ee	.PNG........IHDR.............+..
0020	8b 00 00 00 4e 50 4c 54 45 00 00 00 ff ff ff 8c 8c 8c de de de e7 e7 e7 f7 f7 f7 7b 7b 7b bd bd	....NPLTE..................{{{..
0040	bd 63 63 63 a5 a5 a5 ef ef ef ce ce ce d6 d6 d6 c6 c6 c6 94 9c 94 ad b5 ad e7 ef e7 de e7 de d6	.ccc............................
0060	de d6 f7 ff f7 bd c6 bd b5 bd b5 b5 b5 b5 ce d6 ce 9c a5 9c ad ad ad a7 e2 bd d0 00 00 00 01 74	...............................t
0080	52 4e 53 00 40 e6 d8 66 00 00 b1 50 49 44 41 54 78 5e ec bd 87 96 ac 38 cf 36 aa c7 39 01 5f f8	RNS.@..f...PIDATx^.....8.6..9._.
00a0	4f ba ff 1b 3d 0b 21 2d 6d a0 a0 aa 3a cc f4 3b d3 9a 3d c8 72 94 93 b0 5d 3c 6d 7a 40 bf f4 4b	O...=.!-m...:..;..=.r...]<mz@..K
00c0	bf d4 07 b3 d1 57 e6 9d f3 44 04 d7 a6 55 04 88 7d fd ab e9 08 37 61 04 12 92 22 6e 8b b7 14 46	.....W...D...U..}....7a..."n...F
00e0	b7 99 8b e7 17 d1 1c 28 cc f4 05 f4 4b 00 9c 08 0e c0 a9 3f 83 c5 b4 c0 b3 4f 8d 26 00 7b 07 60	.......(....K......?.....O.&.{.`
0100	2e 71 7c 3f d5 06 10 08 68 95 de 27 d0 17 e8 19 fa cb 7d b0 67 18 ef f5 20 fd 07 52 f2 40 48 3a	.q|?....h..'......}.g......R.@H:
0120	be 8c 00 69 fc da 28 ce 44 ec ce c8 44 cc fb e6 13 33 e5 48 ec 7e 4c ce 13 75 a0 eb 98 63 36 ca	...i..(.D...D....3.H.~L..u...c6.
0140	c6 d2 5a 7e 04 7b 72 e8 14 61 52 0a ac 59 f2 9c fc 8e 96 18 17 a2 b9 a1 25 ed 07 00 08 33 d1 1c	..Z~.{r..aR..Y..........%....3..
0160	10 97 55 6a 59 33 56 c6 61 95 a3 ab a7 a6 64 cf 16 6c 28 2c 44 0b 08 d8 a2 5b 85 46 62 69 92 02	..UjY3V.a.....d..l(,D....[.Fbi..
0180	13 51 1a 5c 30 98 34 f3 36 88 46 23 78 22 f2 20 df 88 9a a7 b0 b2 60 51 d7 c0 6a 63 a9 c4 58 c8	.Q.\0.4.6.F#x"........`Q..jc..X.
01a0	a8 f7 97 0c 40 04 d1 ad 01 38 27 f9 de 41 0e 24 1e 1e 09 78 90 11 d4 44 28 69 a3 d0 12 d5 97 7b	....@....8'..A.$...x...D(i.....{
01c0	96 87 e0 83 09 69 c1 00 a8 c6 58 cd a0 76 9e c3 dc 72 4a ae 61 67 20 25 85 12 f6 0c 5d 62 c9 f3	.....i....X..v...rJ.ag.%....]b..
01e0	9e 4d d3 ca aa 0d ae 85 c0 f4 3e 93 11 bb 1f 71 77 4c 88 a5 11 8b 8d ea 33 93 26 56 ad 1b 66 72	.M........>....qwL......3.&V..fr
0200	c1 c6 d7 c9 00 f4 ee a0 2f 16 38 ad b1 e3 66 ca 70 e4 90 c9 27 24 4f 8f a8 57 ca a8 15 d9 da 89	......../.8...f.p...'$O..W......
0220	66 b4 95 39 44 22 0a a2 95 da 15 8b 12 91 12 22 05 38 f7 c4 02 70 23 b9 e8 68 6e 6b 52 cc 9c e3	f..9D".........".8...p#..hnkR...
0240	9a 78 46 20 9a 56 69 42 3e f4 d7 8c 41 b4 79 02 e6 ad 4d 35 62 b1 1e 8e 3c b3 80 41 80 54 88 cb	.xF..ViB>...A.y...M5b...<..A.T..
0260	44 3b 48 d4 90 28 0d c9 4e 33 ef 6b fa ce 6b c4 f5 51 90 33 0a 55 a4 84 4a 44 d6 1f d5 db d0 0c	D;H..(..N3.k..k..Q.3.U..JD......
0280	21 04 3a d0 73 03 00 dc 45 fc 5b 0c 80 cc a8 4b 03 d0 90 cc 7f 81 73 58 08 64 9e 73 70 e4 c2 4c	!.:.s...E.[....K......sX.d.sp..L
02a0	13 ce a5 5b 30 0b 31 a5 a8 13 98 5c d7 39 6c d4 00 b2 4c 20 29 2e 0c 00 15 d1 5b 46 d5 3d a3 ad	...[0.1....\.9l...L.).....[F.=..
02c0	bb a6 01 90 0c bc 5b 7b 41 37 a1 32 62 f7 23 ee 96 09 65 d4 05 9d ee 0c 80 8c 3b 7d 81 01 94 9a	......[{A7.2b.#...e.......;}....
02e0	4e de b3 01 70 60 a2 58 74 05 30 2f 44 1e 85 9b 29 60 65 81 5c 43 73 ec 73 a0 c2 53 82 08 6d 57	N...p`.Xt.0/D...)`e.\Cs.s..S..mW
0300	71 6e 29 c7 6d f4 a7 01 68 28 12 c3 63 a1 80 94 10 08 5b 72 58 b4 1a 48 28 d4 8d a7 d8 69 d4 39	qn).m...h(..c.....[rX..H(....i.9
0320	36 ac 39 86 49 0c 40 5b f3 90 ca 14 b4 7d 13 4b d8 95 01 c8 70 e6 07 4c 13 fb 46 02 a8 99 46 27	6.9.I.@[.....}.K....p..L..F...F'
0340	89 80 64 bd 6b 4d 5e 0a 2a 0d ef e0 bc 27 ea 31 76 22 8a 53 8f 5b 75 63 92 a2 5a d2 c4 3d 9c d7	..d.kM^.*....'.1v".S.[uc..Z..=..
0360	ae 00 da 4c c0 c0 1a 2f 37 70 ef 61 c8 4b c2 27 02 c4 cf b3 be 1d b1 d2 61 69 d3 51 4d 3d ef 5b	...L.../7p.a.K.'........ai.QM=.[
0380	96 78 f2 2e 91 ec 35 5f f0 d3 f9 47 eb 1a 4f e4 1b 35 7e 0d 35 ea 48 09 9d 42 b0 75 0d 2e 0c 80	.x....5_...G..O..5~.5.H..B.u....
03a0	50 f5 b0 6e ad 0b 51 ad 54 d0 3b 0a 81 3a c2 44 4c cd 65 c0 35 42 49 20 a2 c1 ff 8c 9a 03 82 6b	P..n..Q.T.;..:.DL.e.5BI........k
03c0	47 03 90 a6 aa 73 d8 3a 82 f0 d0 00 68 96 00 f6 4c 34 90 51 75 cf 0a 78 f8 86 0c e8 e0 fa 94 01	G....s.:....h...L4.Qu..x........
03e0	28 68 fb 11 77 cb 7a a5 da 89 02 c8 23 de 1a 00 19 77 f2 ca e2 ec 93 8e ad 07 a6 3e 81 7c 26 6a	(h..w.z.....#....w.........>.|&j
0400	51 1a a3 cf 9b 9d b1 48 c0 b5 01 98 16 0e f7 bb 19 d6 63 e2 f2 3c 91 8b 45 ba 05 63 65 7e cb 87	Q......H..........c..<..E..ce~..
0420	3d c9 73 94 06 e7 60 ca bb 8e d8 75 78 f5 88 ee 88 78 0c 82 9a 73 20 0a bd 87 2d c7 56 ac 51 6d	=.s...`....ux....x...s....-.V.Qm
0440	99 4f c2 2c 0c 78 60 00 d0 88 8e 71 80 51 4d 15 6d 40 93 e0 89 32 30 dc d1 00 24 cc 33 12 e5 96	.O.,.x`....q.QM.m@...20...$.3...
0460	91 7d 26 a2 18 b9 75 5a 9c 98 63 d6 a2 72 7f f2 a2 e5 12 e7 19 9e 26 70 5c bf 4a d8 a6 5f 93 94	.}&...uZ..c..r........&p\.J.._..
0480	63 f3 03 5c 42 3c 6c 01 16 54 53 0f 09 a9 69 bc be a6 ea 9a bd d7 3c 32 55 de 58 94 e3 ba 66 5a	c..\B<l..TS...i.......<2U.X...fZ
04a0	d9 44 9d d7 35 83 28 78 1f 88 16 94 84 2a 66 59 97 7b 90 b5 a6 91 f7 bc e0 b3 86 5f 10 23 16 c2	.D..5.(x.....*fY.{........._.#..
04c0	ca 40 a0 b6 04 78 99 a6 28 eb b3 c3 83 5c 1b ae e9 00 d0 60 c9 48 16 f4 5b 90 3e a6 9d 01 60 bb	.@...x..(....\.....`.H..[.>...`.
04e0	28 25 da a6 a1 37 37 9a 23 72 4b f7 ed c8 00 92 51 75 cf 96 d6 16 22 c2 8c fd 59 0b 2e d8 9d 01	(%...77.#rK.....Qu...."...Y.....
0500	e0 18 87 11 77 cf 2a d8 b0 03 d5 03 b7 06 40 c7 9d 79 a2 e8 d8 da 77 10 d3 d2 08 8e 28 75 9e 8d	....w.*.......@..y....w.....(u..
0520	55 06 ac 0f 04 53 56 b6 00 d6 27 ca a9 3d 78 c5 d6 98 98 67 78 8a 33 fb 8a 04 38 c7 4a f0 d8 1e	U....SV...'..=x....gx.3...8.J...
0540	ab 34 c8 6d 6f 33 a1 86 3e 93 11 cd 5d 47 3d 88 1f 84 65 d1 59 e7 4f 06 e0 b4 23 c6 d5 0a c0 23	.4.mo3..>...]G=...e.Y.O...#....#
0560	9b 1f 10 02 fb d6 61 29 74 09 65 12 37 59 9a 22 a6 c3 54 a1 98 73 24 5a 30 ba f7 59 5f 16 ca ea	......a)t.e.7Y."..T..s$Z0..Y_...
0580	ae a8 1b 03 30 07 98 c6 8f 8c 1b 76 c5 0a 3b d6 38 ec 6c 37 e8 f9 f8 22 1a 68 7d be 30 6b 4b a8	....0......v..;.8.l7...".h}.0kK.
05a0	a8 2d 13 a5 18 13 51 41 ed 91 b4 5a 90 dd a2 1e 6d 4e 68 8e a4 ba 51 3a 6c 25 7b 7b bb 2d 05 21	.-....QA...Z....mNh...Q:l%{{.-.!
05c0	91 c3 6e 05 c0 84 4e c8 76 42 08 50 73 48 41 83 35 e0 40 d6 14 8b 54 78 4f 19 d4 41 cd f7 c5 d1	..n...N.vB.PsHA.5.@...TxO..A....
05e0	81 51 6f 24 a3 ea 9e 85 3a 07 22 87 22 65 7d 76 05 40 87 11 77 cf a8 cb 81 45 73 4f 0c 80 8e 3b	.Qo$....:."."e}v.@..w....EsO...;
0600	7b 81 f9 b6 e8 d8 3a 11 00 ed c3 04 5a 1c ef 02 00 07 6e 16 d9 02 d8 b8 b5 54 cc 97 89 4e 5b 80	{.....:.....Z.....n......T...N[.
0620	8a 64 f5 07 93 4a 4d 5b 2e ae 71 ac 1d 8b 99 a6 16 fb 4c 64 e9 e6 1e 25 2c 6e 2b 80 0a 00 55 13	.d...JM[..q.......Ld...%,n+...U.
0640	df 6f 01 0a 5d 1b 00 f2 91 e8 6c 40 20 6a 5a 6e 26 2d 70 b2 73 c4 d1 00 0c ef 07 91 43 73 31 ce	.o..].....l@.jZn&-p.s.......Cs1.
0660	b2 05 d0 38 c9 dc 44 d4 f3 b5 01 88 48 a7 a9 79 90 9e 1b 80 05 f5 7d 03 40 73 0e 08 c7 5a b5 de	...8..D.....H..y......}.@s...Z..
0680	1b 51 42 6f 1d 4e a7 2e 05 cf 15 9a 50 39 21 74 4d 1e 31 13 2d e4 3c 26 33 00 a6 9d 18 00 30 11	.QBo.N......P9!tM.1.-.<&3.....0.
06a0	a8 63 64 bf db e4 67 40 57 00 66 00 a0 c1 af 18 00 49 74 1c e0 ba 02 60 4b 20 9e 5d a5 1e 13 c9	.cd...g@W.f......It....`K..]....
06c0	a8 ba 65 65 65 85 16 e0 4b b7 00 84 97 b6 00 ba 02 88 18 84 70 6f 00 e4 61 2f b0 02 e8 d8 32 52	..eee...K...........po..a/....2R
06e0	21 ce dc 0d 9d 90 1a fb 3b 50 83 0b dc 8b 0b 1c 39 2c 96 e8 50 91 56 88 0e 87 80 15 55 22 d7 dd	!.......;P......9,..P.V.....U"..
0700	2a 7b 81 a7 0e c7 cb e8 8a 40 b2 f6 e7 28 1d 79 b7 05 b0 9d 19 6f 01 c4 02 2e 73 6c 7a de 26 67	*{.......@...(.y.....o....slz.&g
0720	00 b7 87 80 15 d3 b9 55 46 a1 79 6b 78 87 fc c0 00 0c 3b 92 91 30 93 28 44 a2 91 28 99 b9 93 73	.......UF.ykx.....;..0.(D..(...s
0740	0c 5a 80 85 f8 58 b2 c1 51 5a 93 24 d2 38 e1 4f ad 52 bb 33 00 65 01 ae b6 00 59 b2 11 bf 2b 03	.Z...X..QZ.$.8.O.R.3.e....Y...+.
0760	c0 2d c4 27 6f 07 03 70 b5 05 e0 42 1c 11 22 99 7d 76 db 52 b2 4d ab d8 5c 63 ef 31 22 b7 2b 92	.-.'o..p...B..".}v.R.M..\c.1".+.
0780	cc 9b db 43 c0 c7 5b 00 4b d0 03 8b 76 cc cf 74 38 03 b0 e0 7b 02 52 3a 19 80 73 96 b5 49 a0 eb	...C..[.K...v..t8...{.R:..s..I..
07a0	2a 01 b4 c8 a8 ba 65 4b 24 c2 42 63 d0 d7 1d 02 ee 47 dc 1d d3 33 80 c1 92 0e bc c7 ec 34 28 08	*.....eK$.Bc.....G...3.......4(.
07c0	51 c7 96 91 08 09 14 96 ad 2d e2 4c 72 0e 98 1a 42 f0 44 fa 33 e0 9e 10 37 06 d6 48 7e a7 30 d3	Q........-.Lr...B.D.3...7..H~.0.
07e0	6e 6c 24 9b 5c 88 9d f4 20 8b 02 1b 89 e4 37 09 88 93 ea 79 3a 04 34 65 53 ab 54 b2 fe e2 06 00	nl$.\.........7....y:.4eS.T.....
0800	c1 5d fd 0c a8 bb 1b c4 7e 58 42 cf 01 08 49 d6 54 45 7c 2d 0e 55 c0 2a 44 5a 3d 2f 2a c4 c1 19	.]......~XB...I.TE|-.U.*DZ=/*...
0820	0c 9d dc fa 53 26 25 80 fd 06 75 90 fe 0c c8 71 4e 5a f9 7a 69 00 6a 44 07 ae 0e 01 23 74 c2 db	....S&%...u....qNZ.zi.jD....#t..
0840	21 e0 7e 99 25 5e 71 6c 1d 8a bd 01 b8 3a 04 e4 f9 30 00 7e c9 e6 c8 fb 66 0e d2 5a 8d 46 2d 10	!.~.%^ql.....:...0.~....f..Z.F-.
0860	0d 94 82 21 4b c2 fb 43 40 91 66 0f 53 af 2e 44 4b fd 33 01 39 d0 db a4 45 9f fc 62 ec b2 18 c1	...!K..C@.f.S..DK.3.9...E..b....
0880	6d 52 3d 40 54 69 89 71 91 51 75 cb c2 20 f2 81 da 42 5f fa 33 20 d5 77 7e 06 9c 22 4b 3a f0 1e	mR=@Ti.q.Qu......B_.3..w~.."K:..
08a0	b2 93 01 00 5a d5 b1 75 43 78 f1 43 a0 0a f5 20 ef e8 6b c8 72 be a1 34 80 89 fe 0e 9a 43 fa ba	....Z..uCx.C......k.r..4.....C..
08c0	0f 81 aa df 76 cb 9f a4 84 76 f6 8a af 29 b2 73 be 4d 0e d5 04 31 19 20 20 e6 17 46 95 f9 6f e3	....v....v...).s.M...1.....F..o.
08e0	f2 ab 08 38 7e 5a 34 f7 eb 61 0e 00 26 bd 4d 9a ff 3f 8b 40 af 51 78 bf d7 be 3a e7 5f 02 10 e6	...8~Z4..a..&.M..?.@.Qx...:._...
0900	93 5f ab 7f 81 01 00 fa 1b 83 07 f4 ad 74 5d 93 08 4f 5f 4a df 91 ff 2f fd 12 36 a2 bf 8f 7e e9	._...........t]..O_J.../..6...~.
0920	97 7e e9 97 7e e9 97 32 32 fd 47 13 a0 82 7e 34 72 45 06 98 52 30 d5 d5 ba b5 b4 56 f6 c2 1d e1	.~..~..22.G...~4rE..R0.....V....
0940	4e 05 d0 15 59 c6 a6 d0 7b b9 58 b2 2b 32 7c 99 e9 8a 17 9b 0b cc 3e 56 ec d7 c2 d3 46 bf 6d c3	N...Y...{.X.+2|.......>V....F.m.
0960	4f 0d 92 d1 47 7f bb 68 2b fb 6e 74 dd a7 7b 3f cc fa f2 f9 d0 cf c8 ca 0c 3b 15 23 0b 53 73 30	O...G..h+.nt..{?.........;.#.Ss0
0980	4c 16 58 b8 82 a9 59 42 49 71 1f 46 33 72 73 52 c4 3e a6 46 b5 e2 e9 ae 60 4b 22 71 d5 f3 25 e8	L.X...YBIq.F3rsR.>.F....`K"q..%.
09a0	4b 4c 29 be 88 24 8b f1 72 d0 8f 5a c7 eb 1f ec df ab b0 8f 77 53 4a 8c af e6 e2 da ad 26 e6 a1	KL)..$..r..Z........wSJ......&..
09c0	bd fe b2 ae a0 4b c2 3e 3c c6 27 c9 00 e0 56 1a fe 14 78 e9 11 fa 4d 1b de 6a fe bc d6 65 2c e3	.....K.><.'...V...x...M..j...e,.
09e0	5d f4 a1 15 7e 33 ba 6e 93 dd d2 f0 26 7c b0 2f 21 11 7b 97 12 d5 8c dc ac 00 34 c1 39 e1 f3 b0	]...~3.n....&|./!.{.......4.9...
0a00	92 11 b5 88 7d 4c 89 ba 2f fe be e0 8b 92 81 47 03 1d 80 4a 6a 0d f7 71 05 cb 25 d9 a8 c4 25 a8	....}L../......G...Jj..q..%...%.
0a20	74 8a 19 23 29 86 8b 69 1b af e6 73 02 7b a9 1f 44 05 95 98 ae 24 2e 45 71 8c ac 8f 4a 92 8b 4a	t..#)..i...s.{..D....$.Eq...J..J
0a40	4c 26 f9 ae 55 d4 ff f7 32 60 a5 48 b3 bf a6 2b f0 48 57 62 71 17 be 69 6b 28 cb 6b 84 d2 59 1a	L&..U...2`.H...+.HWbq..ik(.k..Y.
0a60	7e 93 5a dd 05 9e d2 56 41 cf 59 f7 5b 02 91 ac 0d 11 d5 1f 13 e2 4c 4a 1d e8 aa b3 4a 5c 6b 93	~.Z....VA.Y.[.........LJ....J\k.
0a80	46 f1 85 a8 0c 58 ad 0d 0e ca 65 8b 74 0a e4 c2 15 31 ca 31 55 e2 f6 31 89 49 25 49 76 6e 75 93	F....X....e.t....1.1U..1.I%Ivnu.
0aa0	5a 3d 85 12 69 5f 9a 04 98 4b 6a 25 d2 5f bf be 2f 33 c5 e9 c3 2b f8 f9 dd 04 a4 b0 ad e7 92 62	Z=..i_...Kj%._../3...+.........b
0ac0	b9 de 93 0c c3 a5 ce 56 0f 3e 7b 85 3e 26 19 8e f1 4d e9 6c 00 b0 91 79 7c 91 7e 90 c7 39 5c 50	.......V.>{.>&...M.l...y|.~..9\P
0ae0	96 ef 1a 80 56 55 ba 35 00 61 22 60 98 cf ad 64 bf 29 03 ce 7e 33 35 70 dd 53 69 c0 59 76 8a ad	....VU.5.a"`...d.)..~35p.Si.Yv..
0b00	39 49 67 51 11 a3 ef 4a ef 81 8b 00 0b 78 5d 32 50 d0 3d 6b 11 59 d0 68 02 43 7b cc c0 11 1e 33	9IgQ...J.....x]2P.=k.Y.h.C{....3
0b20	f2 00 e6 3d 12 ed 9e a9 9a 03 31 dc 7f ed 68 90 b4 09 2d a9 c4 b0 2d ad e2 9d 24 58 2e a9 e1 eb	...=......1...h...-...-...$X....
0b40	92 62 b8 14 a0 47 74 f4 11 5f 69 9e 0f 4a 52 a8 60 fe de 90 44 03 6d 73 95 cd 43 25 66 1f 96 f8	.b...Gt.._i..JR.`...D.ms..C%f...
0b60	21 a5 59 38 b0 47 59 76 54 63 f7 06 c0 24 02 0e 0e a0 46 a7 e0 7d 41 cf 49 7d 6e a5 50 cd 9f cc	!.Y8.GYvTc...$....F..}A.I}n.P...
0b80	5f c0 75 32 e6 6e a5 b8 69 30 37 f8 80 6c 8d 8b 61 4d 7d 10 55 e2 5e 11 88 e5 eb d2 a3 57 bf 49	_.u2.n..i07..l..aM}.U.^......W.I
0ba0	7b 99 dd 1f 61 /* ** $Id: ltable.c,v 2.32.1.2 2007/12/28 15:32:23 roberto Exp $ ** Lua tables (hash) ** See Copyright Notice in lua.h */ /* ** 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. ** 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 ** to it), then the colliding element is in its own main position. ** Hence even when the load factor reaches 100%, performance remains good. */ #include <math.h> #include <string.h> #define ltable_c #define LUA_CORE #include "lua.h" #include "ldebug.h" #include "ldo.h" #include "lgc.h" #include "lmem.h" #include "lobject.h" #include "lstate.h" #include "ltable.h" /* ** max size of array part is 2^MAXBITS */ #if LUAI_BITSINT > 26 #define MAXBITS 26 #else #define MAXBITS (LUAI_BITSINT-2) #endif #define MAXASIZE (1 << MAXBITS) #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t)))) #define hashstr(t,str) hashpow2(t, (str)->tsv.hash) #define hashboolean(t,p) hashpow2(t, p) /* ** for some types, it is better to avoid modulus by power of 2, as ** they tend to have many 2 factors. */ #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1)))) #define hashpointer(t,p) hashmod(t, IntPoint(p)) /* ** number of ints inside a lua_Number */ #define numints cast_int(sizeof(lua_Number)/sizeof(int)) #define dummynode (&dummynode_) static const Node dummynode_ = { {{NULL}, LUA_TNIL}, /* value */ {{{NULL}, LUA_TNIL, NULL}} /* key */ }; /* ** hash for lua_Numbers */ static Node *hashnum (const Table *t, lua_Number n) { unsigned int a[numints]; int i; if (luai_numeq(n, 0)) /* avoid problems with -0 */ return gnode(t, 0); memcpy(a, &n, sizeof(a)); for (i = 1; i < numints; i++) a[0] += a[i]; return hashmod(t, a[0]); } /* ** returns the `main' position of an element in a table (that is, the index ** of its hash value) */ static Node *mainposition (const Table *t, const TValue *key) { switch (ttype(key)) { case LUA_TNUMBER: return hashnum(t, nvalue(key)); case LUA_TSTRING: return hashstr(t, rawtsvalue(key)); case LUA_TBOOLEAN: return hashboolean(t, bvalue(key)); case LUA_TLIGHTUSERDATA: return hashpointer(t, pvalue(key)); default: return hashpointer(t, gcvalue(key)); } } /* ** returns the index for `key' if `key' is an appropriate key to live in ** the array part of the table, -1 otherwise. */ static int arrayindex (const TValue *key) { if (ttisnumber(key)) { lua_Number n = nvalue(key); int k; lua_number2int(k, n); if (luai_numeq(cast_num(k), n)) return k; } return -1; /* `key' did not match some condition */ } /* ** returns the index of a `key' for table traversals. First goes all ** elements in the array part, then elements in the hash part. The ** beginning of a traversal is signalled by -1. */ static int findindex (lua_State *L, Table *t, StkId key) { int i; if (ttisnil(key)) return -1; /* first iteration */ i = arrayindex(key); if (0 < i && i <= t->sizearray) /* is `key' inside array part? */ return i-1; /* yes; that's the index (corrected to C) */ else { Node *n = mainposition(t, key); do { /* check whether `key' is somewhere in the chain */ /* key may be dead already, but it is ok to use it in `next' */ if (luaO_rawequalObj(key2tval(n), key) || (ttype(gkey(n)) == LUA_TDEADKEY && iscollectable(key) && gcvalue(gkey(n)) == gcvalue(key))) { i = cast_int(n - gnode(t, 0)); /* key index in hash table */ /* hash elements are numbered after array ones */ return i + t->sizearray; } else n = gnext(n); } while (n); luaG_runerror(L, "invalid key to " LUA_QL("next")); /* key not found */ return 0; /* to avoid warnings */ } } int luaH_next (lua_State *L, Table *t, StkId key) { int i = findindex(L, t, key); /* find original element */ for (i++; i < t->sizearray; i++) { /* try first array part */ if (!ttisnil(&t->array[i])) { /* a non-nil value? */ setnvalue(key, cast_num(i+1)); setobj2s(L, key+1, &t->array[i]); return 1; } } for (i -= t->sizearray; i < sizenode(t); i++) { /* then hash part */ if (!ttisnil(gval(gnode(t, i)))) { /* a non-nil value? */ setobj2s(L, key, key2tval(gnode(t, i))); setobj2s(L, key+1, gval(gnode(t, i))); return 1; } } return 0; /* no more elements */ } /* ** {============================================================= ** Rehash ** ============================================================== */ static int computesizes (int nums[], int *narray) { int i; int twotoi; /* 2^i */ int a = 0; /* number of elements smaller than 2^i */ int na = 0; /* number of elements to go to array part */ int n = 0; /* optimal size for array part */ for (i = 0, twotoi = 1; twotoi/2 < *narray; 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 smaller than n will go to array part */ } } if (a == *narray) break; /* all elements already counted */ } *narray = n; lua_assert(*narray/2 <= na && na <= *narray); return na; } static int countint (const TValue *key, int *nums) { int k = arrayindex(key); if (0 < k && k <= MAXASIZE) { /* is `key' an appropriate array index? */ nums[ceillog2(k)]++; /* count as such */ return 1; } else return 0; } static int numusearray (const Table *t, int *nums) { int lg; int ttlg; /* 2^lg */ int ause = 0; /* summation of `nums' */ int i = 1; /* count to traverse all array keys */ for (lg=0, ttlg=1; lg<=MAXBITS; lg++, ttlg*=2) { /* for each slice */ int lc = 0; /* counter */ int lim = ttlg; if (lim > t->sizearray) { lim = t->sizearray; /* adjust upper limit */ if (i > lim) break; /* no more elements to count */ } /* count elements in range (2^(lg-1), 2^lg] */ for (; i <= lim; i++) { if (!ttisnil(&t->array[i-1])) lc++; } nums[lg] += lc; ause += lc; } return ause; } static int numusehash (const Table *t, int *nums, int *pnasize) { int totaluse = 0; /* total number of elements */ int ause = 0; /* summation of `nums' */ int i = sizenode(t); while (i--) { Node *n = &t->node[i]; if (!ttisnil(gval(n))) { ause += countint(key2tval(n), nums); totaluse++; } } *pnasize += ause; return totaluse; } static void setarrayvector (lua_State *L, Table *t, int size) { int i; luaM_reallocvector(L, t->array, t->sizearray, size, TValue); for (i=t->sizearray; i<size; i++) setnilvalue(&t->array[i]); t->sizearray = size; } 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 = ceillog2(size); if (lsize > MAXBITS) luaG_runerror(L, "table overflow"); size = twoto(lsize); t->node = luaM_newvector(L, size, Node); for (i=0; i<size; i++) { Node *n = gnode(t, i); gnext(n) = NULL; setnilvalue(gkey(n)); setnilvalue(gval(n)); } } t->lsizenode = cast_byte(lsize); t->lastfree = gnode(t, size); /* all positions are free */ } static void resize (lua_State *L, Table *t, int nasize, int nhsize) { int i; int oldasize = t->sizearray; int oldhsize = t->lsizenode; Node *nold = t->node; /* save old hash ... */ if (nasize > oldasize) /* array part must grow? */ setarrayvector(L, t, nasize); /* create new hash part with appropriate size */ setnodevector(L, t, nhsize); if (nasize < oldasize) { /* array part must shrink? */ t->sizearray = nasize; /* re-insert elements from vanishing slice */ for (i=nasize; i<oldasize; i++) { if (!ttisnil(&t->array[i])) setobjt2t(L, luaH_setnum(L, t, i+1), &t->array[i]); } /* shrink array */ luaM_reallocvector(L, t->array, oldasize, nasize, TValue); } /* re-insert elements from hash part */ for (i = twoto(oldhsize) - 1; i >= 0; i--) { Node *old = nold+i; if (!ttisnil(gval(old))) setobjt2t(L, luaH_set(L, t, key2tval(old)), gval(old)); } if (nold != dummynode) luaM_freearray(L, nold, twoto(oldhsize), Node); /* free old array */ } void luaH_resizearray (lua_State *L, Table *t, int nasize) { int nsize = (t->node == dummynode) ? 0 : sizenode(t); resize(L, t, nasize, nsize); } static void rehash (lua_State *L, Table *t, const TValue *ek) { int nasize, na; int nums[MAXBITS+1]; /* nums[i] = number of keys between 2^(i-1) and 2^i */ int i; int totaluse; for (i=0; i<=MAXBITS; 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 */ /* count extra key */ nasize += countint(ek, nums); totaluse++; /* compute new size for array part */ na = computesizes(nums, &nasize); /* resize the table to new computed sizes */ resize(L, t, nasize, totaluse - na); } /* ** }============================================================= */ Table *luaH_new (lua_State *L, int narray, int nhash) { Table *t = luaM_new(L, Table); luaC_link(L, obj2gco(t), LUA_TTABLE); t->metatable = NULL; t->flags = cast_byte(~0); /* temporary values (kept only if some malloc fails) */ t->array = NULL; t->sizearray = 0; t->lsizenode = 0; t->node = cast(Node *, dummynode); setarrayvector(L, t, narray); setnodevector(L, t, nhash); return t; } void luaH_free (lua_State *L, Table *t) { if (t->node != dummynode) luaM_freearray(L, t->node, sizenode(t), Node); luaM_freearray(L, t->array, t->sizearray, TValue); luaM_free(L, t); } static Node *getfreepos (Table *t) { while (t->lastfree-- > t->node) { if (ttisnil(gkey(t->lastfree))) return t->lastfree; } return NULL; /* could not find a free place */ } /* ** 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. */ static TValue *newkey (lua_State *L, Table *t, const TValue *key) { Node *mp = mainposition(t, key); if (!ttisnil(gval(mp)) || mp == dummynode) { Node *othern; Node *n = getfreepos(t); /* get a free place */ if (n == NULL) { /* cannot find a free place? */ rehash(L, t, key); /* grow table */ return luaH_set(L, t, key); /* re-insert key into grown table */ } lua_assert(n != dummynode); othern = mainposition(t, key2tval(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)); } else { /* 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; } } gkey(mp)->value = key->value; gkey(mp)->tt = key->tt; luaC_barriert(L, t, key); lua_assert(ttisnil(gval(mp))); return gval(mp); } /* ** search function for integers */ const TValue *luaH_getnum (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; } } /* ** search function for strings */ const TValue *luaH_getstr (Table *t, TString *key) { Node *n = hashstr(t, key); do { /* check whether `key' is somewhere in the chain */ if (ttisstring(gkey(n)) && rawtsvalue(gkey(n)) == key) return gval(n); /* that's it */ else n = gnext(n); } while (n); return luaO_nilobject; } /* ** main search function */ const TValue *luaH_get (Table *t, const TValue *key) { switch (ttype(key)) { case LUA_TNIL: return luaO_nilobject; case LUA_TSTRING: return luaH_getstr(t, rawtsvalue(key)); case LUA_TNUMBER: { int k; lua_Number n = nvalue(key); lua_number2int(k, n); if (luai_numeq(cast_num(k), nvalue(key))) /* index is int? */ return luaH_getnum(t, k); /* use specialized version */ /* else go through */ } default: { Node *n = mainposition(t, key); do { /* check whether `key' is somewhere in the chain */ if (luaO_rawequalObj(key2tval(n), key)) return gval(n); /* that's it */ else n = gnext(n); } while (n); return luaO_nilobject; } } } TValue *luaH_set (lua_State *L, Table *t, const TValue *key) { const TValue *p = luaH_get(t, key); t->flags = 0; if (p != luaO_nilobject) return cast(TValue *, p); else { if (ttisnil(key)) luaG_runerror(L, "table index is nil"); else if (ttisnumber(key) && luai_numisnan(nvalue(key))) luaG_runerror(L, "table index is NaN"); return newkey(L, t, key); } } TValue *luaH_setnum (lua_State *L, Table *t, int key) { const TValue *p = luaH_getnum(t, key); if (p != luaO_nilobject) return cast(TValue *, p); else { TValue k; setnvalue(&k, cast_num(key)); return newkey(L, t, &k); } } TValue *luaH_setstr (lua_State *L, Table *t, TString *key) { const TValue *p = luaH_getstr(t, key); if (p != luaO_nilobject) return cast(TValue *, p); else { TValue k; setsvalue(L, &k, key); return newkey(L, t, &k); } } static int unbound_search (Table *t, unsigned int j) { unsigned int i = j; /* i is zero or a present index */ j++; /* find `i' and `j' such that i is present and j is not */ while (!ttisnil(luaH_getnum(t, j))) { i = j; j *= 2; if (j > cast(unsigned int, MAX_INT)) { /* overflow? */ /* table was built with bad purposes: resort to linear search */ i = 1; while (!ttisnil(luaH_getnum(t, i))) i++; return i - 1; } } /* now do a binary search between them */ while (j - i > 1) { unsigned int m = (i+j)/2; if (ttisnil(luaH_getnum(t, m))) j = m; else i = m; } return i; } /* ** Try to find a boundary in table `t'. A `boundary' is an integer index ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil). */ int luaH_getn (Table *t) { unsigned int j = t->sizearray; if (j > 0 && ttisnil(&t->array[j - 1])) { /* there is a boundary in the array part: (binary) search for it */ unsigned int i = 0; while (j - i > 1) { unsigned int m = (i+j)/2; if (ttisnil(&t->array[m - 1])) j = m; else i = m; } return i; } /* else must find a boundary in hash part */ else if (t->node == dummynode) /* hash part is empty? */ return j; /* that is easy... */ else return unbound_search(t, j); } #if defined(LUA_DEBUG) Node *luaH_mainposition (const Table *t, const TValue *key) { return mainposition(t, key); } int luaH_isdummy (Node *n) { return n == dummynode; } #endif