diff options
author | David Walter Seikel | 2012-01-23 23:36:30 +1000 |
---|---|---|
committer | David Walter Seikel | 2012-01-23 23:36:30 +1000 |
commit | 6523585c66c04cea54df50013df8886b589847d8 (patch) | |
tree | 0b22aee7064166d88595eda260ca2d17c0773da5 /libraries/LuaJIT-1.1.7/src/ltable.c | |
parent | Update the EFL to what I'm actually using, coz I'm using some stuff not yet r... (diff) | |
download | SledjHamr-6523585c66c04cea54df50013df8886b589847d8.zip SledjHamr-6523585c66c04cea54df50013df8886b589847d8.tar.gz SledjHamr-6523585c66c04cea54df50013df8886b589847d8.tar.bz2 SledjHamr-6523585c66c04cea54df50013df8886b589847d8.tar.xz |
Add luaproc and LuaJIT libraries.
Two versions of LuaJIT, the stable release, and the dev version. Try the dev version first, until ih fails badly.
Diffstat (limited to '')
-rw-r--r-- | libraries/LuaJIT-1.1.7/src/ltable.c | 588 |
1 files changed, 588 insertions, 0 deletions
diff --git a/libraries/LuaJIT-1.1.7/src/ltable.c b/libraries/LuaJIT-1.1.7/src/ltable.c new file mode 100644 index 0000000..6b226ad --- /dev/null +++ b/libraries/LuaJIT-1.1.7/src/ltable.c | |||
@@ -0,0 +1,588 @@ | |||
1 | /* | ||
2 | ** $Id: ltable.c,v 2.32.1.2 2007/12/28 15:32:23 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 | ** 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. | ||
19 | */ | ||
20 | |||
21 | #include <math.h> | ||
22 | #include <string.h> | ||
23 | |||
24 | #define ltable_c | ||
25 | #define LUA_CORE | ||
26 | |||
27 | #include "lua.h" | ||
28 | |||
29 | #include "ldebug.h" | ||
30 | #include "ldo.h" | ||
31 | #include "lgc.h" | ||
32 | #include "lmem.h" | ||
33 | #include "lobject.h" | ||
34 | #include "lstate.h" | ||
35 | #include "ltable.h" | ||
36 | |||
37 | |||
38 | /* | ||
39 | ** max size of array part is 2^MAXBITS | ||
40 | */ | ||
41 | #if LUAI_BITSINT > 26 | ||
42 | #define MAXBITS 26 | ||
43 | #else | ||
44 | #define MAXBITS (LUAI_BITSINT-2) | ||
45 | #endif | ||
46 | |||
47 | #define MAXASIZE (1 << MAXBITS) | ||
48 | |||
49 | |||
50 | #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t)))) | ||
51 | |||
52 | #define hashstr(t,str) hashpow2(t, (str)->tsv.hash) | ||
53 | #define hashboolean(t,p) hashpow2(t, p) | ||
54 | |||
55 | |||
56 | /* | ||
57 | ** for some types, it is better to avoid modulus by power of 2, as | ||
58 | ** they tend to have many 2 factors. | ||
59 | */ | ||
60 | #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1)))) | ||
61 | |||
62 | |||
63 | #define hashpointer(t,p) hashmod(t, IntPoint(p)) | ||
64 | |||
65 | |||
66 | /* | ||
67 | ** number of ints inside a lua_Number | ||
68 | */ | ||
69 | #define numints cast_int(sizeof(lua_Number)/sizeof(int)) | ||
70 | |||
71 | |||
72 | |||
73 | #define dummynode (&dummynode_) | ||
74 | |||
75 | static const Node dummynode_ = { | ||
76 | {{NULL}, LUA_TNIL}, /* value */ | ||
77 | {{{NULL}, LUA_TNIL, NULL}} /* key */ | ||
78 | }; | ||
79 | |||
80 | |||
81 | /* | ||
82 | ** hash for lua_Numbers | ||
83 | */ | ||
84 | static Node *hashnum (const Table *t, lua_Number n) { | ||
85 | unsigned int a[numints]; | ||
86 | int i; | ||
87 | if (luai_numeq(n, 0)) /* avoid problems with -0 */ | ||
88 | return gnode(t, 0); | ||
89 | memcpy(a, &n, sizeof(a)); | ||
90 | for (i = 1; i < numints; i++) a[0] += a[i]; | ||
91 | return hashmod(t, a[0]); | ||
92 | } | ||
93 | |||
94 | |||
95 | |||
96 | /* | ||
97 | ** returns the `main' position of an element in a table (that is, the index | ||
98 | ** of its hash value) | ||
99 | */ | ||
100 | static Node *mainposition (const Table *t, const TValue *key) { | ||
101 | switch (ttype(key)) { | ||
102 | case LUA_TNUMBER: | ||
103 | return hashnum(t, nvalue(key)); | ||
104 | case LUA_TSTRING: | ||
105 | return hashstr(t, rawtsvalue(key)); | ||
106 | case LUA_TBOOLEAN: | ||
107 | return hashboolean(t, bvalue(key)); | ||
108 | case LUA_TLIGHTUSERDATA: | ||
109 | return hashpointer(t, pvalue(key)); | ||
110 | default: | ||
111 | return hashpointer(t, gcvalue(key)); | ||
112 | } | ||
113 | } | ||
114 | |||
115 | |||
116 | /* | ||
117 | ** returns the index for `key' if `key' is an appropriate key to live in | ||
118 | ** the array part of the table, -1 otherwise. | ||
119 | */ | ||
120 | static int arrayindex (const TValue *key) { | ||
121 | if (ttisnumber(key)) { | ||
122 | lua_Number n = nvalue(key); | ||
123 | int k; | ||
124 | lua_number2int(k, n); | ||
125 | if (luai_numeq(cast_num(k), n)) | ||
126 | return k; | ||
127 | } | ||
128 | return -1; /* `key' did not match some condition */ | ||
129 | } | ||
130 | |||
131 | |||
132 | /* | ||
133 | ** returns the index of a `key' for table traversals. First goes all | ||
134 | ** elements in the array part, then elements in the hash part. The | ||
135 | ** beginning of a traversal is signalled by -1. | ||
136 | */ | ||
137 | static int findindex (lua_State *L, Table *t, StkId key) { | ||
138 | int i; | ||
139 | if (ttisnil(key)) return -1; /* first iteration */ | ||
140 | i = arrayindex(key); | ||
141 | if (0 < i && i <= t->sizearray) /* is `key' inside array part? */ | ||
142 | return i-1; /* yes; that's the index (corrected to C) */ | ||
143 | else { | ||
144 | Node *n = mainposition(t, key); | ||
145 | do { /* check whether `key' is somewhere in the chain */ | ||
146 | /* key may be dead already, but it is ok to use it in `next' */ | ||
147 | if (luaO_rawequalObj(key2tval(n), key) || | ||
148 | (ttype(gkey(n)) == LUA_TDEADKEY && iscollectable(key) && | ||
149 | gcvalue(gkey(n)) == gcvalue(key))) { | ||
150 | i = cast_int(n - gnode(t, 0)); /* key index in hash table */ | ||
151 | /* hash elements are numbered after array ones */ | ||
152 | return i + t->sizearray; | ||
153 | } | ||
154 | else n = gnext(n); | ||
155 | } while (n); | ||
156 | luaG_runerror(L, "invalid key to " LUA_QL("next")); /* key not found */ | ||
157 | return 0; /* to avoid warnings */ | ||
158 | } | ||
159 | } | ||
160 | |||
161 | |||
162 | int luaH_next (lua_State *L, Table *t, StkId key) { | ||
163 | int i = findindex(L, t, key); /* find original element */ | ||
164 | for (i++; i < t->sizearray; i++) { /* try first array part */ | ||
165 | if (!ttisnil(&t->array[i])) { /* a non-nil value? */ | ||
166 | setnvalue(key, cast_num(i+1)); | ||
167 | setobj2s(L, key+1, &t->array[i]); | ||
168 | return 1; | ||
169 | } | ||
170 | } | ||
171 | for (i -= t->sizearray; i < sizenode(t); i++) { /* then hash part */ | ||
172 | if (!ttisnil(gval(gnode(t, i)))) { /* a non-nil value? */ | ||
173 | setobj2s(L, key, key2tval(gnode(t, i))); | ||
174 | setobj2s(L, key+1, gval(gnode(t, i))); | ||
175 | return 1; | ||
176 | } | ||
177 | } | ||
178 | return 0; /* no more elements */ | ||
179 | } | ||
180 | |||
181 | |||
182 | /* | ||
183 | ** {============================================================= | ||
184 | ** Rehash | ||
185 | ** ============================================================== | ||
186 | */ | ||
187 | |||
188 | |||
189 | static int computesizes (int nums[], int *narray) { | ||
190 | int i; | ||
191 | int twotoi; /* 2^i */ | ||
192 | int a = 0; /* number of elements smaller than 2^i */ | ||
193 | int na = 0; /* number of elements to go to array part */ | ||
194 | int n = 0; /* optimal size for array part */ | ||
195 | for (i = 0, twotoi = 1; twotoi/2 < *narray; i++, twotoi *= 2) { | ||
196 | if (nums[i] > 0) { | ||
197 | a += nums[i]; | ||
198 | if (a > twotoi/2) { /* more than half elements present? */ | ||
199 | n = twotoi; /* optimal size (till now) */ | ||
200 | na = a; /* all elements smaller than n will go to array part */ | ||
201 | } | ||
202 | } | ||
203 | if (a == *narray) break; /* all elements already counted */ | ||
204 | } | ||
205 | *narray = n; | ||
206 | lua_assert(*narray/2 <= na && na <= *narray); | ||
207 | return na; | ||
208 | } | ||
209 | |||
210 | |||
211 | static int countint (const TValue *key, int *nums) { | ||
212 | int k = arrayindex(key); | ||
213 | if (0 < k && k <= MAXASIZE) { /* is `key' an appropriate array index? */ | ||
214 | nums[ceillog2(k)]++; /* count as such */ | ||
215 | return 1; | ||
216 | } | ||
217 | else | ||
218 | return 0; | ||
219 | } | ||
220 | |||
221 | |||
222 | static int numusearray (const Table *t, int *nums) { | ||
223 | int lg; | ||
224 | int ttlg; /* 2^lg */ | ||
225 | int ause = 0; /* summation of `nums' */ | ||
226 | int i = 1; /* count to traverse all array keys */ | ||
227 | for (lg=0, ttlg=1; lg<=MAXBITS; lg++, ttlg*=2) { /* for each slice */ | ||
228 | int lc = 0; /* counter */ | ||
229 | int lim = ttlg; | ||
230 | if (lim > t->sizearray) { | ||
231 | lim = t->sizearray; /* adjust upper limit */ | ||
232 | if (i > lim) | ||
233 | break; /* no more elements to count */ | ||
234 | } | ||
235 | /* count elements in range (2^(lg-1), 2^lg] */ | ||
236 | for (; i <= lim; i++) { | ||
237 | if (!ttisnil(&t->array[i-1])) | ||
238 | lc++; | ||
239 | } | ||
240 | nums[lg] += lc; | ||
241 | ause += lc; | ||
242 | } | ||
243 | return ause; | ||
244 | } | ||
245 | |||
246 | |||
247 | static int numusehash (const Table *t, int *nums, int *pnasize) { | ||
248 | int totaluse = 0; /* total number of elements */ | ||
249 | int ause = 0; /* summation of `nums' */ | ||
250 | int i = sizenode(t); | ||
251 | while (i--) { | ||
252 | Node *n = &t->node[i]; | ||
253 | if (!ttisnil(gval(n))) { | ||
254 | ause += countint(key2tval(n), nums); | ||
255 | totaluse++; | ||
256 | } | ||
257 | } | ||
258 | *pnasize += ause; | ||
259 | return totaluse; | ||
260 | } | ||
261 | |||
262 | |||
263 | static void setarrayvector (lua_State *L, Table *t, int size) { | ||
264 | int i; | ||
265 | luaM_reallocvector(L, t->array, t->sizearray, size, TValue); | ||
266 | for (i=t->sizearray; i<size; i++) | ||
267 | setnilvalue(&t->array[i]); | ||
268 | t->sizearray = size; | ||
269 | } | ||
270 | |||
271 | |||
272 | static void setnodevector (lua_State *L, Table *t, int size) { | ||
273 | int lsize; | ||
274 | if (size == 0) { /* no elements to hash part? */ | ||
275 | t->node = cast(Node *, dummynode); /* use common `dummynode' */ | ||
276 | lsize = 0; | ||
277 | } | ||
278 | else { | ||
279 | int i; | ||
280 | lsize = ceillog2(size); | ||
281 | if (lsize > MAXBITS) | ||
282 | luaG_runerror(L, "table overflow"); | ||
283 | size = twoto(lsize); | ||
284 | t->node = luaM_newvector(L, size, Node); | ||
285 | for (i=0; i<size; i++) { | ||
286 | Node *n = gnode(t, i); | ||
287 | gnext(n) = NULL; | ||
288 | setnilvalue(gkey(n)); | ||
289 | setnilvalue(gval(n)); | ||
290 | } | ||
291 | } | ||
292 | t->lsizenode = cast_byte(lsize); | ||
293 | t->lastfree = gnode(t, size); /* all positions are free */ | ||
294 | } | ||
295 | |||
296 | |||
297 | static void resize (lua_State *L, Table *t, int nasize, int nhsize) { | ||
298 | int i; | ||
299 | int oldasize = t->sizearray; | ||
300 | int oldhsize = t->lsizenode; | ||
301 | Node *nold = t->node; /* save old hash ... */ | ||
302 | if (nasize > oldasize) /* array part must grow? */ | ||
303 | setarrayvector(L, t, nasize); | ||
304 | /* create new hash part with appropriate size */ | ||
305 | setnodevector(L, t, nhsize); | ||
306 | if (nasize < oldasize) { /* array part must shrink? */ | ||
307 | t->sizearray = nasize; | ||
308 | /* re-insert elements from vanishing slice */ | ||
309 | for (i=nasize; i<oldasize; i++) { | ||
310 | if (!ttisnil(&t->array[i])) | ||
311 | setobjt2t(L, luaH_setnum(L, t, i+1), &t->array[i]); | ||
312 | } | ||
313 | /* shrink array */ | ||
314 | luaM_reallocvector(L, t->array, oldasize, nasize, TValue); | ||
315 | } | ||
316 | /* re-insert elements from hash part */ | ||
317 | for (i = twoto(oldhsize) - 1; i >= 0; i--) { | ||
318 | Node *old = nold+i; | ||
319 | if (!ttisnil(gval(old))) | ||
320 | setobjt2t(L, luaH_set(L, t, key2tval(old)), gval(old)); | ||
321 | } | ||
322 | if (nold != dummynode) | ||
323 | luaM_freearray(L, nold, twoto(oldhsize), Node); /* free old array */ | ||
324 | } | ||
325 | |||
326 | |||
327 | void luaH_resizearray (lua_State *L, Table *t, int nasize) { | ||
328 | int nsize = (t->node == dummynode) ? 0 : sizenode(t); | ||
329 | resize(L, t, nasize, nsize); | ||
330 | } | ||
331 | |||
332 | |||
333 | static void rehash (lua_State *L, Table *t, const TValue *ek) { | ||
334 | int nasize, na; | ||
335 | int nums[MAXBITS+1]; /* nums[i] = number of keys between 2^(i-1) and 2^i */ | ||
336 | int i; | ||
337 | int totaluse; | ||
338 | for (i=0; i<=MAXBITS; i++) nums[i] = 0; /* reset counts */ | ||
339 | nasize = numusearray(t, nums); /* count keys in array part */ | ||
340 | totaluse = nasize; /* all those keys are integer keys */ | ||
341 | totaluse += numusehash(t, nums, &nasize); /* count keys in hash part */ | ||
342 | /* count extra key */ | ||
343 | nasize += countint(ek, nums); | ||
344 | totaluse++; | ||
345 | /* compute new size for array part */ | ||
346 | na = computesizes(nums, &nasize); | ||
347 | /* resize the table to new computed sizes */ | ||
348 | resize(L, t, nasize, totaluse - na); | ||
349 | } | ||
350 | |||
351 | |||
352 | |||
353 | /* | ||
354 | ** }============================================================= | ||
355 | */ | ||
356 | |||
357 | |||
358 | Table *luaH_new (lua_State *L, int narray, int nhash) { | ||
359 | Table *t = luaM_new(L, Table); | ||
360 | luaC_link(L, obj2gco(t), LUA_TTABLE); | ||
361 | t->metatable = NULL; | ||
362 | t->flags = cast_byte(~0); | ||
363 | /* temporary values (kept only if some malloc fails) */ | ||
364 | t->array = NULL; | ||
365 | t->sizearray = 0; | ||
366 | t->lsizenode = 0; | ||
367 | t->node = cast(Node *, dummynode); | ||
368 | setarrayvector(L, t, narray); | ||
369 | setnodevector(L, t, nhash); | ||
370 | return t; | ||
371 | } | ||
372 | |||
373 | |||
374 | void luaH_free (lua_State *L, Table *t) { | ||
375 | if (t->node != dummynode) | ||
376 | luaM_freearray(L, t->node, sizenode(t), Node); | ||
377 | luaM_freearray(L, t->array, t->sizearray, TValue); | ||
378 | luaM_free(L, t); | ||
379 | } | ||
380 | |||
381 | |||
382 | static Node *getfreepos (Table *t) { | ||
383 | while (t->lastfree-- > t->node) { | ||
384 | if (ttisnil(gkey(t->lastfree))) | ||
385 | return t->lastfree; | ||
386 | } | ||
387 | return NULL; /* could not find a free place */ | ||
388 | } | ||
389 | |||
390 | |||
391 | |||
392 | /* | ||
393 | ** inserts a new key into a hash table; first, check whether key's main | ||
394 | ** position is free. If not, check whether colliding node is in its main | ||
395 | ** position or not: if it is not, move colliding node to an empty place and | ||
396 | ** put new key in its main position; otherwise (colliding node is in its main | ||
397 | ** position), new key goes to an empty position. | ||
398 | */ | ||
399 | TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) { | ||
400 | Node *mp = mainposition(t, key); | ||
401 | if (!ttisnil(gval(mp)) || mp == dummynode) { | ||
402 | Node *othern; | ||
403 | Node *n = getfreepos(t); /* get a free place */ | ||
404 | if (n == NULL) { /* cannot find a free place? */ | ||
405 | rehash(L, t, key); /* grow table */ | ||
406 | return luaH_set(L, t, key); /* re-insert key into grown table */ | ||
407 | } | ||
408 | lua_assert(n != dummynode); | ||
409 | othern = mainposition(t, key2tval(mp)); | ||
410 | if (othern != mp) { /* is colliding node out of its main position? */ | ||
411 | /* yes; move colliding node into free position */ | ||
412 | while (gnext(othern) != mp) othern = gnext(othern); /* find previous */ | ||
413 | gnext(othern) = n; /* redo the chain with `n' in place of `mp' */ | ||
414 | *n = *mp; /* copy colliding node into free pos. (mp->next also goes) */ | ||
415 | gnext(mp) = NULL; /* now `mp' is free */ | ||
416 | setnilvalue(gval(mp)); | ||
417 | } | ||
418 | else { /* colliding node is in its own main position */ | ||
419 | /* new node will go into free position */ | ||
420 | gnext(n) = gnext(mp); /* chain new position */ | ||
421 | gnext(mp) = n; | ||
422 | mp = n; | ||
423 | } | ||
424 | } | ||
425 | gkey(mp)->value = key->value; gkey(mp)->tt = key->tt; | ||
426 | luaC_barriert(L, t, key); | ||
427 | lua_assert(ttisnil(gval(mp))); | ||
428 | return gval(mp); | ||
429 | } | ||
430 | |||
431 | |||
432 | /* | ||
433 | ** search function for integers | ||
434 | */ | ||
435 | const TValue *luaH_getnum (Table *t, int key) { | ||
436 | /* (1 <= key && key <= t->sizearray) */ | ||
437 | if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray)) | ||
438 | return &t->array[key-1]; | ||
439 | else { | ||
440 | lua_Number nk = cast_num(key); | ||
441 | Node *n = hashnum(t, nk); | ||
442 | do { /* check whether `key' is somewhere in the chain */ | ||
443 | if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)), nk)) | ||
444 | return gval(n); /* that's it */ | ||
445 | else n = gnext(n); | ||
446 | } while (n); | ||
447 | return luaO_nilobject; | ||
448 | } | ||
449 | } | ||
450 | |||
451 | |||
452 | /* | ||
453 | ** search function for strings | ||
454 | */ | ||
455 | const TValue *luaH_getstr (Table *t, TString *key) { | ||
456 | Node *n = hashstr(t, key); | ||
457 | do { /* check whether `key' is somewhere in the chain */ | ||
458 | if (ttisstring(gkey(n)) && rawtsvalue(gkey(n)) == key) | ||
459 | return gval(n); /* that's it */ | ||
460 | else n = gnext(n); | ||
461 | } while (n); | ||
462 | return luaO_nilobject; | ||
463 | } | ||
464 | |||
465 | |||
466 | /* | ||
467 | ** main search function | ||
468 | */ | ||
469 | const TValue *luaH_get (Table *t, const TValue *key) { | ||
470 | switch (ttype(key)) { | ||
471 | case LUA_TNIL: return luaO_nilobject; | ||
472 | case LUA_TSTRING: return luaH_getstr(t, rawtsvalue(key)); | ||
473 | case LUA_TNUMBER: { | ||
474 | int k; | ||
475 | lua_Number n = nvalue(key); | ||
476 | lua_number2int(k, n); | ||
477 | if (luai_numeq(cast_num(k), nvalue(key))) /* index is int? */ | ||
478 | return luaH_getnum(t, k); /* use specialized version */ | ||
479 | /* else go through */ | ||
480 | } | ||
481 | default: { | ||
482 | Node *n = mainposition(t, key); | ||
483 | do { /* check whether `key' is somewhere in the chain */ | ||
484 | if (luaO_rawequalObj(key2tval(n), key)) | ||
485 | return gval(n); /* that's it */ | ||
486 | else n = gnext(n); | ||
487 | } while (n); | ||
488 | return luaO_nilobject; | ||
489 | } | ||
490 | } | ||
491 | } | ||
492 | |||
493 | |||
494 | TValue *luaH_set (lua_State *L, Table *t, const TValue *key) { | ||
495 | const TValue *p = luaH_get(t, key); | ||
496 | t->flags = 0; | ||
497 | if (p != luaO_nilobject) | ||
498 | return cast(TValue *, p); | ||
499 | else { | ||
500 | if (ttisnil(key)) luaG_runerror(L, "table index is nil"); | ||
501 | else if (ttisnumber(key) && luai_numisnan(nvalue(key))) | ||
502 | luaG_runerror(L, "table index is NaN"); | ||
503 | return luaH_newkey(L, t, key); | ||
504 | } | ||
505 | } | ||
506 | |||
507 | |||
508 | TValue *luaH_setnum (lua_State *L, Table *t, int key) { | ||
509 | const TValue *p = luaH_getnum(t, key); | ||
510 | if (p != luaO_nilobject) | ||
511 | return cast(TValue *, p); | ||
512 | else { | ||
513 | TValue k; | ||
514 | setnvalue(&k, cast_num(key)); | ||
515 | return luaH_newkey(L, t, &k); | ||
516 | } | ||
517 | } | ||
518 | |||
519 | |||
520 | TValue *luaH_setstr (lua_State *L, Table *t, TString *key) { | ||
521 | const TValue *p = luaH_getstr(t, key); | ||
522 | if (p != luaO_nilobject) | ||
523 | return cast(TValue *, p); | ||
524 | else { | ||
525 | TValue k; | ||
526 | setsvalue(L, &k, key); | ||
527 | return luaH_newkey(L, t, &k); | ||
528 | } | ||
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_getnum(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_getnum(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_getnum(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 non-nil 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 (t->node == dummynode) /* 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 n == dummynode; } | ||
587 | |||
588 | #endif | ||