Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
5205 | clevermous | 1 | /* |
2 | ** $Id: ltable.c,v 2.67 2011/11/30 12:41:45 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 |
||
22 | |||
23 | #define ltable_c |
||
24 | #define LUA_CORE |
||
25 | |||
26 | #include "lua.h" |
||
27 | |||
28 | #include "ldebug.h" |
||
29 | #include "ldo.h" |
||
30 | #include "lgc.h" |
||
31 | #include "lmem.h" |
||
32 | #include "lobject.h" |
||
33 | #include "lstate.h" |
||
34 | #include "lstring.h" |
||
35 | #include "ltable.h" |
||
36 | #include "lvm.h" |
||
37 | |||
38 | |||
39 | /* |
||
40 | ** max size of array part is 2^MAXBITS |
||
41 | */ |
||
42 | #if LUAI_BITSINT >= 32 |
||
43 | #define MAXBITS 30 |
||
44 | #else |
||
45 | #define MAXBITS (LUAI_BITSINT-2) |
||
46 | #endif |
||
47 | |||
48 | #define MAXASIZE (1 << MAXBITS) |
||
49 | |||
50 | |||
51 | #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t)))) |
||
52 | |||
53 | #define hashstr(t,str) hashpow2(t, (str)->tsv.hash) |
||
54 | #define hashboolean(t,p) hashpow2(t, p) |
||
55 | |||
56 | |||
57 | /* |
||
58 | ** for some types, it is better to avoid modulus by power of 2, as |
||
59 | ** they tend to have many 2 factors. |
||
60 | */ |
||
61 | #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1)))) |
||
62 | |||
63 | |||
64 | #define hashpointer(t,p) hashmod(t, IntPoint(p)) |
||
65 | |||
66 | |||
67 | #define dummynode (&dummynode_) |
||
68 | |||
69 | #define isdummy(n) ((n) == dummynode) |
||
70 | |||
71 | static const Node dummynode_ = { |
||
72 | {NILCONSTANT}, /* value */ |
||
73 | {{NILCONSTANT, NULL}} /* key */ |
||
74 | }; |
||
75 | |||
76 | |||
77 | /* |
||
78 | ** hash for lua_Numbers |
||
79 | */ |
||
80 | static Node *hashnum (const Table *t, lua_Number n) { |
||
81 | int i; |
||
82 | luai_hashnum(i, n); |
||
83 | if (i < 0) { |
||
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 */ |
||
87 | } |
||
88 | return hashmod(t, i); |
||
89 | } |
||
90 | |||
91 | |||
92 | |||
93 | /* |
||
94 | ** returns the `main' position of an element in a table (that is, the index |
||
95 | ** of its hash value) |
||
96 | */ |
||
97 | static Node *mainposition (const Table *t, const TValue *key) { |
||
98 | switch (ttype(key)) { |
||
99 | case LUA_TNUMBER: |
||
100 | return hashnum(t, nvalue(key)); |
||
101 | case LUA_TSTRING: |
||
102 | return hashstr(t, rawtsvalue(key)); |
||
103 | case LUA_TBOOLEAN: |
||
104 | return hashboolean(t, bvalue(key)); |
||
105 | case LUA_TLIGHTUSERDATA: |
||
106 | return hashpointer(t, pvalue(key)); |
||
107 | case LUA_TLCF: |
||
108 | return hashpointer(t, fvalue(key)); |
||
109 | default: |
||
110 | return hashpointer(t, gcvalue(key)); |
||
111 | } |
||
112 | } |
||
113 | |||
114 | |||
115 | /* |
||
116 | ** returns the index for `key' if `key' is an appropriate key to live in |
||
117 | ** the array part of the table, -1 otherwise. |
||
118 | */ |
||
119 | static int arrayindex (const TValue *key) { |
||
120 | if (ttisnumber(key)) { |
||
121 | lua_Number n = nvalue(key); |
||
122 | int k; |
||
123 | lua_number2int(k, n); |
||
124 | if (luai_numeq(cast_num(k), n)) |
||
125 | return k; |
||
126 | } |
||
127 | return -1; /* `key' did not match some condition */ |
||
128 | } |
||
129 | |||
130 | |||
131 | /* |
||
132 | ** returns the index of a `key' for table traversals. First goes all |
||
133 | ** elements in the array part, then elements in the hash part. The |
||
134 | ** beginning of a traversal is signaled by -1. |
||
135 | */ |
||
136 | static int findindex (lua_State *L, Table *t, StkId key) { |
||
137 | int i; |
||
138 | if (ttisnil(key)) return -1; /* first iteration */ |
||
139 | i = arrayindex(key); |
||
140 | if (0 < i && i <= t->sizearray) /* is `key' inside array part? */ |
||
141 | return i-1; /* yes; that's the index (corrected to C) */ |
||
142 | else { |
||
143 | Node *n = mainposition(t, key); |
||
144 | for (;;) { /* check whether `key' is somewhere in the chain */ |
||
145 | /* key may be dead already, but it is ok to use it in `next' */ |
||
146 | if (luaV_rawequalobj(gkey(n), key) || |
||
147 | (ttisdeadkey(gkey(n)) && iscollectable(key) && |
||
148 | deadvalue(gkey(n)) == gcvalue(key))) { |
||
149 | i = cast_int(n - gnode(t, 0)); /* key index in hash table */ |
||
150 | /* hash elements are numbered after array ones */ |
||
151 | return i + t->sizearray; |
||
152 | } |
||
153 | else n = gnext(n); |
||
154 | if (n == NULL) |
||
155 | luaG_runerror(L, "invalid key to " LUA_QL("next")); /* key not found */ |
||
156 | } |
||
157 | } |
||
158 | } |
||
159 | |||
160 | |||
161 | int luaH_next (lua_State *L, Table *t, StkId key) { |
||
162 | int i = findindex(L, t, key); /* find original element */ |
||
163 | for (i++; i < t->sizearray; i++) { /* try first array part */ |
||
164 | if (!ttisnil(&t->array[i])) { /* a non-nil value? */ |
||
165 | setnvalue(key, cast_num(i+1)); |
||
166 | setobj2s(L, key+1, &t->array[i]); |
||
167 | return 1; |
||
168 | } |
||
169 | } |
||
170 | for (i -= t->sizearray; i < sizenode(t); i++) { /* then hash part */ |
||
171 | if (!ttisnil(gval(gnode(t, i)))) { /* a non-nil value? */ |
||
172 | setobj2s(L, key, gkey(gnode(t, i))); |
||
173 | setobj2s(L, key+1, gval(gnode(t, i))); |
||
174 | return 1; |
||
175 | } |
||
176 | } |
||
177 | return 0; /* no more elements */ |
||
178 | } |
||
179 | |||
180 | |||
181 | /* |
||
182 | ** {============================================================= |
||
183 | ** Rehash |
||
184 | ** ============================================================== |
||
185 | */ |
||
186 | |||
187 | |||
188 | static int computesizes (int nums[], int *narray) { |
||
189 | int i; |
||
190 | int twotoi; /* 2^i */ |
||
191 | int a = 0; /* number of elements smaller than 2^i */ |
||
192 | int na = 0; /* number of elements to go to array part */ |
||
193 | int n = 0; /* optimal size for array part */ |
||
194 | for (i = 0, twotoi = 1; twotoi/2 < *narray; i++, twotoi *= 2) { |
||
195 | if (nums[i] > 0) { |
||
196 | a += nums[i]; |
||
197 | if (a > twotoi/2) { /* more than half elements present? */ |
||
198 | n = twotoi; /* optimal size (till now) */ |
||
199 | na = a; /* all elements smaller than n will go to array part */ |
||
200 | } |
||
201 | } |
||
202 | if (a == *narray) break; /* all elements already counted */ |
||
203 | } |
||
204 | *narray = n; |
||
205 | lua_assert(*narray/2 <= na && na <= *narray); |
||
206 | return na; |
||
207 | } |
||
208 | |||
209 | |||
210 | static int countint (const TValue *key, int *nums) { |
||
211 | int k = arrayindex(key); |
||
212 | if (0 < k && k <= MAXASIZE) { /* is `key' an appropriate array index? */ |
||
213 | nums[luaO_ceillog2(k)]++; /* count as such */ |
||
214 | return 1; |
||
215 | } |
||
216 | else |
||
217 | return 0; |
||
218 | } |
||
219 | |||
220 | |||
221 | static int numusearray (const Table *t, int *nums) { |
||
222 | int lg; |
||
223 | int ttlg; /* 2^lg */ |
||
224 | int ause = 0; /* summation of `nums' */ |
||
225 | int i = 1; /* count to traverse all array keys */ |
||
226 | for (lg=0, ttlg=1; lg<=MAXBITS; lg++, ttlg*=2) { /* for each slice */ |
||
227 | int lc = 0; /* counter */ |
||
228 | int lim = ttlg; |
||
229 | if (lim > t->sizearray) { |
||
230 | lim = t->sizearray; /* adjust upper limit */ |
||
231 | if (i > lim) |
||
232 | break; /* no more elements to count */ |
||
233 | } |
||
234 | /* count elements in range (2^(lg-1), 2^lg] */ |
||
235 | for (; i <= lim; i++) { |
||
236 | if (!ttisnil(&t->array[i-1])) |
||
237 | lc++; |
||
238 | } |
||
239 | nums[lg] += lc; |
||
240 | ause += lc; |
||
241 | } |
||
242 | return ause; |
||
243 | } |
||
244 | |||
245 | |||
246 | static int numusehash (const Table *t, int *nums, int *pnasize) { |
||
247 | int totaluse = 0; /* total number of elements */ |
||
248 | int ause = 0; /* summation of `nums' */ |
||
249 | int i = sizenode(t); |
||
250 | while (i--) { |
||
251 | Node *n = &t->node[i]; |
||
252 | if (!ttisnil(gval(n))) { |
||
253 | ause += countint(gkey(n), nums); |
||
254 | totaluse++; |
||
255 | } |
||
256 | } |
||
257 | *pnasize += ause; |
||
258 | return totaluse; |
||
259 | } |
||
260 | |||
261 | |||
262 | static void setarrayvector (lua_State *L, Table *t, int size) { |
||
263 | int i; |
||
264 | luaM_reallocvector(L, t->array, t->sizearray, size, TValue); |
||
265 | for (i=t->sizearray; i |
||
266 | setnilvalue(&t->array[i]); |
||
267 | t->sizearray = size; |
||
268 | } |
||
269 | |||
270 | |||
271 | static void setnodevector (lua_State *L, Table *t, int size) { |
||
272 | int lsize; |
||
273 | if (size == 0) { /* no elements to hash part? */ |
||
274 | t->node = cast(Node *, dummynode); /* use common `dummynode' */ |
||
275 | lsize = 0; |
||
276 | } |
||
277 | else { |
||
278 | int i; |
||
279 | lsize = luaO_ceillog2(size); |
||
280 | if (lsize > MAXBITS) |
||
281 | luaG_runerror(L, "table overflow"); |
||
282 | size = twoto(lsize); |
||
283 | t->node = luaM_newvector(L, size, Node); |
||
284 | for (i=0; i |
||
285 | Node *n = gnode(t, i); |
||
286 | gnext(n) = NULL; |
||
287 | setnilvalue(gkey(n)); |
||
288 | setnilvalue(gval(n)); |
||
289 | } |
||
290 | } |
||
291 | t->lsizenode = cast_byte(lsize); |
||
292 | t->lastfree = gnode(t, size); /* all positions are free */ |
||
293 | } |
||
294 | |||
295 | |||
296 | void luaH_resize (lua_State *L, Table *t, int nasize, int nhsize) { |
||
297 | int i; |
||
298 | int oldasize = t->sizearray; |
||
299 | int oldhsize = t->lsizenode; |
||
300 | Node *nold = t->node; /* save old hash ... */ |
||
301 | if (nasize > oldasize) /* array part must grow? */ |
||
302 | setarrayvector(L, t, nasize); |
||
303 | /* create new hash part with appropriate size */ |
||
304 | setnodevector(L, t, nhsize); |
||
305 | if (nasize < oldasize) { /* array part must shrink? */ |
||
306 | t->sizearray = nasize; |
||
307 | /* re-insert elements from vanishing slice */ |
||
308 | for (i=nasize; i |
||
309 | if (!ttisnil(&t->array[i])) |
||
310 | luaH_setint(L, t, i + 1, &t->array[i]); |
||
311 | } |
||
312 | /* shrink array */ |
||
313 | luaM_reallocvector(L, t->array, oldasize, nasize, TValue); |
||
314 | } |
||
315 | /* re-insert elements from hash part */ |
||
316 | for (i = twoto(oldhsize) - 1; i >= 0; i--) { |
||
317 | Node *old = nold+i; |
||
318 | if (!ttisnil(gval(old))) { |
||
319 | /* doesn't need barrier/invalidate cache, as entry was |
||
320 | already present in the table */ |
||
321 | setobjt2t(L, luaH_set(L, t, gkey(old)), gval(old)); |
||
322 | } |
||
323 | } |
||
324 | if (!isdummy(nold)) |
||
325 | luaM_freearray(L, nold, cast(size_t, twoto(oldhsize))); /* free old array */ |
||
326 | } |
||
327 | |||
328 | |||
329 | void luaH_resizearray (lua_State *L, Table *t, int nasize) { |
||
330 | int nsize = isdummy(t->node) ? 0 : sizenode(t); |
||
331 | luaH_resize(L, t, nasize, nsize); |
||
332 | } |
||
333 | |||
334 | |||
335 | static void rehash (lua_State *L, Table *t, const TValue *ek) { |
||
336 | int nasize, na; |
||
337 | int nums[MAXBITS+1]; /* nums[i] = number of keys with 2^(i-1) < k <= 2^i */ |
||
338 | int i; |
||
339 | int totaluse; |
||
340 | for (i=0; i<=MAXBITS; i++) nums[i] = 0; /* reset counts */ |
||
341 | nasize = numusearray(t, nums); /* count keys in array part */ |
||
342 | totaluse = nasize; /* all those keys are integer keys */ |
||
343 | totaluse += numusehash(t, nums, &nasize); /* count keys in hash part */ |
||
344 | /* count extra key */ |
||
345 | nasize += countint(ek, nums); |
||
346 | totaluse++; |
||
347 | /* compute new size for array part */ |
||
348 | na = computesizes(nums, &nasize); |
||
349 | /* resize the table to new computed sizes */ |
||
350 | luaH_resize(L, t, nasize, totaluse - na); |
||
351 | } |
||
352 | |||
353 | |||
354 | |||
355 | /* |
||
356 | ** }============================================================= |
||
357 | */ |
||
358 | |||
359 | |||
360 | Table *luaH_new (lua_State *L) { |
||
361 | Table *t = &luaC_newobj(L, LUA_TTABLE, sizeof(Table), NULL, 0)->h; |
||
362 | t->metatable = NULL; |
||
363 | t->flags = cast_byte(~0); |
||
364 | t->array = NULL; |
||
365 | t->sizearray = 0; |
||
366 | setnodevector(L, t, 0); |
||
367 | return t; |
||
368 | } |
||
369 | |||
370 | |||
371 | void luaH_free (lua_State *L, Table *t) { |
||
372 | if (!isdummy(t->node)) |
||
373 | luaM_freearray(L, t->node, cast(size_t, sizenode(t))); |
||
374 | luaM_freearray(L, t->array, t->sizearray); |
||
375 | luaM_free(L, t); |
||
376 | } |
||
377 | |||
378 | |||
379 | static Node *getfreepos (Table *t) { |
||
380 | while (t->lastfree > t->node) { |
||
381 | t->lastfree--; |
||
382 | if (ttisnil(gkey(t->lastfree))) |
||
383 | return t->lastfree; |
||
384 | } |
||
385 | return NULL; /* could not find a free place */ |
||
386 | } |
||
387 | |||
388 | |||
389 | |||
390 | /* |
||
391 | ** inserts a new key into a hash table; first, check whether key's main |
||
392 | ** position is free. If not, check whether colliding node is in its main |
||
393 | ** position or not: if it is not, move colliding node to an empty place and |
||
394 | ** put new key in its main position; otherwise (colliding node is in its main |
||
395 | ** position), new key goes to an empty position. |
||
396 | */ |
||
397 | TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) { |
||
398 | Node *mp; |
||
399 | if (ttisnil(key)) luaG_runerror(L, "table index is nil"); |
||
400 | else if (ttisnumber(key) && luai_numisnan(L, nvalue(key))) |
||
401 | luaG_runerror(L, "table index is NaN"); |
||
402 | mp = mainposition(t, key); |
||
403 | if (!ttisnil(gval(mp)) || isdummy(mp)) { /* main position is taken? */ |
||
404 | Node *othern; |
||
405 | Node *n = getfreepos(t); /* get a free place */ |
||
406 | if (n == NULL) { /* cannot find a free place? */ |
||
407 | rehash(L, t, key); /* grow table */ |
||
408 | /* whatever called 'newkey' take care of TM cache and GC barrier */ |
||
409 | return luaH_set(L, t, key); /* insert key into grown table */ |
||
410 | } |
||
411 | lua_assert(!isdummy(n)); |
||
412 | othern = mainposition(t, gkey(mp)); |
||
413 | if (othern != mp) { /* is colliding node out of its main position? */ |
||
414 | /* yes; move colliding node into free position */ |
||
415 | while (gnext(othern) != mp) othern = gnext(othern); /* find previous */ |
||
416 | gnext(othern) = n; /* redo the chain with `n' in place of `mp' */ |
||
417 | *n = *mp; /* copy colliding node into free pos. (mp->next also goes) */ |
||
418 | gnext(mp) = NULL; /* now `mp' is free */ |
||
419 | setnilvalue(gval(mp)); |
||
420 | } |
||
421 | else { /* colliding node is in its own main position */ |
||
422 | /* new node will go into free position */ |
||
423 | gnext(n) = gnext(mp); /* chain new position */ |
||
424 | gnext(mp) = n; |
||
425 | mp = n; |
||
426 | } |
||
427 | } |
||
428 | setobj2t(L, gkey(mp), key); |
||
429 | luaC_barrierback(L, obj2gco(t), key); |
||
430 | lua_assert(ttisnil(gval(mp))); |
||
431 | return gval(mp); |
||
432 | } |
||
433 | |||
434 | |||
435 | /* |
||
436 | ** search function for integers |
||
437 | */ |
||
438 | const TValue *luaH_getint (Table *t, int key) { |
||
439 | /* (1 <= key && key <= t->sizearray) */ |
||
440 | if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray)) |
||
441 | return &t->array[key-1]; |
||
442 | else { |
||
443 | lua_Number nk = cast_num(key); |
||
444 | Node *n = hashnum(t, nk); |
||
445 | do { /* check whether `key' is somewhere in the chain */ |
||
446 | if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)), nk)) |
||
447 | return gval(n); /* that's it */ |
||
448 | else n = gnext(n); |
||
449 | } while (n); |
||
450 | return luaO_nilobject; |
||
451 | } |
||
452 | } |
||
453 | |||
454 | |||
455 | /* |
||
456 | ** search function for strings |
||
457 | */ |
||
458 | const TValue *luaH_getstr (Table *t, TString *key) { |
||
459 | Node *n = hashstr(t, key); |
||
460 | do { /* check whether `key' is somewhere in the chain */ |
||
461 | if (ttisstring(gkey(n)) && eqstr(rawtsvalue(gkey(n)), key)) |
||
462 | return gval(n); /* that's it */ |
||
463 | else n = gnext(n); |
||
464 | } while (n); |
||
465 | return luaO_nilobject; |
||
466 | } |
||
467 | |||
468 | |||
469 | /* |
||
470 | ** main search function |
||
471 | */ |
||
472 | const TValue *luaH_get (Table *t, const TValue *key) { |
||
473 | switch (ttypenv(key)) { |
||
474 | case LUA_TNIL: return luaO_nilobject; |
||
475 | case LUA_TSTRING: return luaH_getstr(t, rawtsvalue(key)); |
||
476 | case LUA_TNUMBER: { |
||
477 | int k; |
||
478 | lua_Number n = nvalue(key); |
||
479 | lua_number2int(k, n); |
||
480 | if (luai_numeq(cast_num(k), nvalue(key))) /* index is int? */ |
||
481 | return luaH_getint(t, k); /* use specialized version */ |
||
482 | /* else go through */ |
||
483 | } |
||
484 | default: { |
||
485 | Node *n = mainposition(t, key); |
||
486 | do { /* check whether `key' is somewhere in the chain */ |
||
487 | if (luaV_rawequalobj(gkey(n), key)) |
||
488 | return gval(n); /* that's it */ |
||
489 | else n = gnext(n); |
||
490 | } while (n); |
||
491 | return luaO_nilobject; |
||
492 | } |
||
493 | } |
||
494 | } |
||
495 | |||
496 | |||
497 | /* |
||
498 | ** beware: when using this function you probably need to check a GC |
||
499 | ** barrier and invalidate the TM cache. |
||
500 | */ |
||
501 | TValue *luaH_set (lua_State *L, Table *t, const TValue *key) { |
||
502 | const TValue *p = luaH_get(t, key); |
||
503 | if (p != luaO_nilobject) |
||
504 | return cast(TValue *, p); |
||
505 | else return luaH_newkey(L, t, key); |
||
506 | } |
||
507 | |||
508 | |||
509 | void luaH_setint (lua_State *L, Table *t, int key, TValue *value) { |
||
510 | const TValue *p = luaH_getint(t, key); |
||
511 | TValue *cell; |
||
512 | if (p != luaO_nilobject) |
||
513 | cell = cast(TValue *, p); |
||
514 | else { |
||
515 | TValue k; |
||
516 | setnvalue(&k, cast_num(key)); |
||
517 | cell = luaH_newkey(L, t, &k); |
||
518 | } |
||
519 | setobj2t(L, cell, value); |
||
520 | } |
||
521 | |||
522 | |||
523 | static int unbound_search (Table *t, unsigned int j) { |
||
524 | unsigned int i = j; /* i is zero or a present index */ |
||
525 | j++; |
||
526 | /* find `i' and `j' such that i is present and j is not */ |
||
527 | while (!ttisnil(luaH_getint(t, j))) { |
||
528 | i = j; |
||
529 | j *= 2; |
||
530 | if (j > cast(unsigned int, MAX_INT)) { /* overflow? */ |
||
531 | /* table was built with bad purposes: resort to linear search */ |
||
532 | i = 1; |
||
533 | while (!ttisnil(luaH_getint(t, i))) i++; |
||
534 | return i - 1; |
||
535 | } |
||
536 | } |
||
537 | /* now do a binary search between them */ |
||
538 | while (j - i > 1) { |
||
539 | unsigned int m = (i+j)/2; |
||
540 | if (ttisnil(luaH_getint(t, m))) j = m; |
||
541 | else i = m; |
||
542 | } |
||
543 | return i; |
||
544 | } |
||
545 | |||
546 | |||
547 | /* |
||
548 | ** Try to find a boundary in table `t'. A `boundary' is an integer index |
||
549 | ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil). |
||
550 | */ |
||
551 | int luaH_getn (Table *t) { |
||
552 | unsigned int j = t->sizearray; |
||
553 | if (j > 0 && ttisnil(&t->array[j - 1])) { |
||
554 | /* there is a boundary in the array part: (binary) search for it */ |
||
555 | unsigned int i = 0; |
||
556 | while (j - i > 1) { |
||
557 | unsigned int m = (i+j)/2; |
||
558 | if (ttisnil(&t->array[m - 1])) j = m; |
||
559 | else i = m; |
||
560 | } |
||
561 | return i; |
||
562 | } |
||
563 | /* else must find a boundary in hash part */ |
||
564 | else if (isdummy(t->node)) /* hash part is empty? */ |
||
565 | return j; /* that is easy... */ |
||
566 | else return unbound_search(t, j); |
||
567 | } |
||
568 | |||
569 | |||
570 | |||
571 | #if defined(LUA_DEBUG) |
||
572 | |||
573 | Node *luaH_mainposition (const Table *t, const TValue *key) { |
||
574 | return mainposition(t, key); |
||
575 | } |
||
576 | |||
577 | int luaH_isdummy (Node *n) { return isdummy(n); } |
||
578 | |||
579 | #endif>=>=>=MAXBITS;>=>>>=>=MAXBITS;>=>>=>=>>>>=>>>><> |