1--[[
2--*****************************************************************************
3--* Copyright (C) 1994-2016 Lua.org, PUC-Rio.
4--*
5--* Permission is hereby granted, free of charge, to any person obtaining
6--* a copy of this software and associated documentation files (the
7--* "Software"), to deal in the Software without restriction, including
8--* without limitation the rights to use, copy, modify, merge, publish,
9--* distribute, sublicense, and/or sell copies of the Software, and to
10--* permit persons to whom the Software is furnished to do so, subject to
11--* the following conditions:
12--*
13--* The above copyright notice and this permission notice shall be
14--* included in all copies or substantial portions of the Software.
15--*
16--* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17--* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18--* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
19--* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
20--* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
21--* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
22--* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23--*****************************************************************************
24--]]
25
26-- testing table library
27
28-- workaround missing pcall in zfs lua implementation
29local function tuple(...)
30  return {n=select('#', ...), ...}
31end
32
33function pcall(f, ...)
34  local co = coroutine.create(f)
35  local res = tuple(coroutine.resume(co, ...))
36  if res[1] and coroutine.status(co) == "suspended" then
37    res[1] = false
38  end
39  return table.unpack(res, 1, res.n)
40end
41
42
43-- workaround missing math lib in zfs lua implementation
44local A1, A2 = 727595, 798405  -- 5^17=D20*A1+A2
45local D20, D40 = 1048576, 1099511627776  -- 2^20, 2^40
46local X1, X2 = 0, 1
47function rand()
48    local U = X2*A2
49    local V = (X1*A2 + X2*A1) % D20
50    V = (V*D20 + U) % D40
51    X1 = V/D20
52    X2 = V - X1*D20
53    return V*100/D40
54end
55
56
57-- testing unpack
58
59local unpack = table.unpack
60
61local x,y,z,a,n
62a = {}; lim = 2000
63for i=1, lim do a[i]=i end
64assert(select(lim, unpack(a)) == lim and select('#', unpack(a)) == lim)
65x = unpack(a)
66assert(x == 1)
67x = {unpack(a)}
68assert(#x == lim and x[1] == 1 and x[lim] == lim)
69x = {unpack(a, lim-2)}
70assert(#x == 3 and x[1] == lim-2 and x[3] == lim)
71x = {unpack(a, 10, 6)}
72assert(next(x) == nil)   -- no elements
73x = {unpack(a, 11, 10)}
74assert(next(x) == nil)   -- no elements
75x,y = unpack(a, 10, 10)
76assert(x == 10 and y == nil)
77x,y,z = unpack(a, 10, 11)
78assert(x == 10 and y == 11 and z == nil)
79a,x = unpack{1}
80assert(a==1 and x==nil)
81a,x = unpack({1,2}, 1, 1)
82assert(a==1 and x==nil)
83
84if not _no32 then
85  assert(not pcall(unpack, {}, 0, 2^31-1))
86  assert(not pcall(unpack, {}, 1, 2^31-1))
87  assert(not pcall(unpack, {}, -(2^31), 2^31-1))
88  assert(not pcall(unpack, {}, -(2^31 - 1), 2^31-1))
89  assert(pcall(unpack, {}, 2^31-1, 0))
90  assert(pcall(unpack, {}, 2^31-1, 1))
91  pcall(unpack, {}, 1, 2^31)
92  a, b = unpack({[2^31-1] = 20}, 2^31-1, 2^31-1)
93  assert(a == 20 and b == nil)
94  a, b = unpack({[2^31-1] = 20}, 2^31-2, 2^31-1)
95  assert(a == nil and b == 20)
96end
97
98-- testing pack
99
100a = table.pack()
101assert(a[1] == nil and a.n == 0)
102
103a = table.pack(table)
104assert(a[1] == table and a.n == 1)
105
106a = table.pack(nil, nil, nil, nil)
107assert(a[1] == nil and a.n == 4)
108
109
110-- testing sort
111
112
113-- test checks for invalid order functions
114local function check (t)
115  local function f(a, b) assert(a and b); return true end
116  local s, e = pcall(table.sort, t, f)
117  assert(not s and e:find("invalid order function"))
118end
119
120check{1,2,3,4}
121check{1,2,3,4,5}
122check{1,2,3,4,5,6}
123
124
125function check (a, f)
126  f = f or function (x,y) return x<y end;
127  for n = #a, 2, -1 do
128    assert(not f(a[n], a[n-1]))
129  end
130end
131
132a = {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep",
133     "Oct", "Nov", "Dec"}
134
135table.sort(a)
136check(a)
137
138function perm (s, n)
139  n = n or #s
140  if n == 1 then
141    local t = {unpack(s)}
142    table.sort(t)
143    check(t)
144  else
145    for i = 1, n do
146      s[i], s[n] = s[n], s[i]
147      perm(s, n - 1)
148      s[i], s[n] = s[n], s[i]
149    end
150  end
151end
152
153perm{}
154perm{1}
155perm{1,2}
156perm{1,2,3}
157perm{1,2,3,4}
158perm{2,2,3,4}
159perm{1,2,3,4,5}
160perm{1,2,3,3,5}
161perm{1,2,3,4,5,6}
162perm{2,2,3,3,5,6}
163
164limit = 5000
165
166a = {}
167for i=1,limit do
168  a[i] = rand()
169end
170
171table.sort(a)
172check(a)
173
174table.sort(a)
175check(a)
176
177a = {}
178for i=1,limit do
179  a[i] = rand()
180end
181
182i=0
183table.sort(a, function(x,y) i=i+1; return y<x end)
184check(a, function(x,y) return y<x end)
185
186
187table.sort{}  -- empty array
188
189for i=1,limit do a[i] = false end
190table.sort(a, function(x,y) return nil end)
191check(a, function(x,y) return nil end)
192for i,v in pairs(a) do assert(not v or i=='n' and v==limit) end
193
194A = {"�lo", "\0first :-)", "alo", "then this one", "45", "and a new"}
195table.sort(A)
196check(A)
197
198tt = {__lt = function (a,b) return a.val < b.val end}
199a = {}
200for i=1,10 do  a[i] = {val=rand(100)}; setmetatable(a[i], tt); end
201table.sort(a)
202check(a, tt.__lt)
203check(a)
204
205
206-- test remove
207local function test (a)
208  table.insert(a, 10); table.insert(a, 2, 20);
209  table.insert(a, 1, -1); table.insert(a, 40);
210  table.insert(a, #a+1, 50)
211  table.insert(a, 2, -2)
212  assert(table.remove(a,1) == -1)
213  assert(table.remove(a,1) == -2)
214  assert(table.remove(a,1) == 10)
215  assert(table.remove(a,1) == 20)
216  assert(table.remove(a,1) == 40)
217  assert(table.remove(a,1) == 50)
218  assert(table.remove(a,1) == nil)
219end
220
221a = {n=0, [-7] = "ban"}
222test(a)
223assert(a.n == 0 and a[-7] == "ban")
224
225a = {[-7] = "ban"};
226test(a)
227assert(a.n == nil and #a == 0 and a[-7] == "ban")
228
229
230table.insert(a, 1, 10); table.insert(a, 1, 20); table.insert(a, 1, -1)
231assert(table.remove(a) == 10)
232assert(table.remove(a) == 20)
233assert(table.remove(a) == -1)
234
235a = {'c', 'd'}
236table.insert(a, 3, 'a')
237table.insert(a, 'b')
238assert(table.remove(a, 1) == 'c')
239assert(table.remove(a, 1) == 'd')
240assert(table.remove(a, 1) == 'a')
241assert(table.remove(a, 1) == 'b')
242assert(#a == 0 and a.n == nil)
243
244a = {10,20,30,40}
245assert(a[#a] == 40)
246assert(table.remove(a, #a) == 40)
247assert(a[#a] == 30)
248assert(table.remove(a, 2) == 20)
249assert(a[#a] == 30 and #a == 2)
250
251
252return "OK"
253