9
3

ltable.c 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669
  1. /*
  2. ** $Id: ltable.c,v 2.118 2016/11/07 12:38:35 roberto Exp $
  3. ** Lua tables (hash)
  4. ** See Copyright Notice in lua.h
  5. */
  6. #define ltable_c
  7. #define LUA_CORE
  8. #include "lprefix.h"
  9. /*
  10. ** Implementation of tables (aka arrays, objects, or hash tables).
  11. ** Tables keep its elements in two parts: an array part and a hash part.
  12. ** Non-negative integer keys are all candidates to be kept in the array
  13. ** part. The actual size of the array is the largest 'n' such that
  14. ** more than half the slots between 1 and n are in use.
  15. ** Hash uses a mix of chained scatter table with Brent's variation.
  16. ** A main invariant of these tables is that, if an element is not
  17. ** in its main position (i.e. the 'original' position that its hash gives
  18. ** to it), then the colliding element is in its own main position.
  19. ** Hence even when the load factor reaches 100%, performance remains good.
  20. */
  21. #include <math.h>
  22. #include <limits.h>
  23. #include "lua.h"
  24. #include "ldebug.h"
  25. #include "ldo.h"
  26. #include "lgc.h"
  27. #include "lmem.h"
  28. #include "lobject.h"
  29. #include "lstate.h"
  30. #include "lstring.h"
  31. #include "ltable.h"
  32. #include "lvm.h"
  33. /*
  34. ** Maximum size of array part (MAXASIZE) is 2^MAXABITS. MAXABITS is
  35. ** the largest integer such that MAXASIZE fits in an unsigned int.
  36. */
  37. #define MAXABITS cast_int(sizeof(int) * CHAR_BIT - 1)
  38. #define MAXASIZE (1u << MAXABITS)
  39. /*
  40. ** Maximum size of hash part is 2^MAXHBITS. MAXHBITS is the largest
  41. ** integer such that 2^MAXHBITS fits in a signed int. (Note that the
  42. ** maximum number of elements in a table, 2^MAXABITS + 2^MAXHBITS, still
  43. ** fits comfortably in an unsigned int.)
  44. */
  45. #define MAXHBITS (MAXABITS - 1)
  46. #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t))))
  47. #define hashstr(t,str) hashpow2(t, (str)->hash)
  48. #define hashboolean(t,p) hashpow2(t, p)
  49. #define hashint(t,i) hashpow2(t, i)
  50. /*
  51. ** for some types, it is better to avoid modulus by power of 2, as
  52. ** they tend to have many 2 factors.
  53. */
  54. #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1))))
  55. #define hashpointer(t,p) hashmod(t, point2uint(p))
  56. #define dummynode (&dummynode_)
  57. static const Node dummynode_ = {
  58. {NILCONSTANT}, /* value */
  59. {{NILCONSTANT, 0}} /* key */
  60. };
  61. /*
  62. ** Hash for floating-point numbers.
  63. ** The main computation should be just
  64. ** n = frexp(n, &i); return (n * INT_MAX) + i
  65. ** but there are some numerical subtleties.
  66. ** In a two-complement representation, INT_MAX does not has an exact
  67. ** representation as a float, but INT_MIN does; because the absolute
  68. ** value of 'frexp' is smaller than 1 (unless 'n' is inf/NaN), the
  69. ** absolute value of the product 'frexp * -INT_MIN' is smaller or equal
  70. ** to INT_MAX. Next, the use of 'unsigned int' avoids overflows when
  71. ** adding 'i'; the use of '~u' (instead of '-u') avoids problems with
  72. ** INT_MIN.
  73. */
  74. #if !defined(l_hashfloat)
  75. static int l_hashfloat (lua_Number n) {
  76. int i;
  77. lua_Integer ni;
  78. n = l_mathop(frexp)(n, &i) * -cast_num(INT_MIN);
  79. if (!lua_numbertointeger(n, &ni)) { /* is 'n' inf/-inf/NaN? */
  80. lua_assert(luai_numisnan(n) || l_mathop(fabs)(n) == cast_num(HUGE_VAL));
  81. return 0;
  82. }
  83. else { /* normal case */
  84. unsigned int u = cast(unsigned int, i) + cast(unsigned int, ni);
  85. return cast_int(u <= cast(unsigned int, INT_MAX) ? u : ~u);
  86. }
  87. }
  88. #endif
  89. /*
  90. ** returns the 'main' position of an element in a table (that is, the index
  91. ** of its hash value)
  92. */
  93. static Node *mainposition (const Table *t, const TValue *key) {
  94. switch (ttype(key)) {
  95. case LUA_TNUMINT:
  96. return hashint(t, ivalue(key));
  97. case LUA_TNUMFLT:
  98. return hashmod(t, l_hashfloat(fltvalue(key)));
  99. case LUA_TSHRSTR:
  100. return hashstr(t, tsvalue(key));
  101. case LUA_TLNGSTR:
  102. return hashpow2(t, luaS_hashlongstr(tsvalue(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. lua_assert(!ttisdeadkey(key));
  111. return hashpointer(t, gcvalue(key));
  112. }
  113. }
  114. /*
  115. ** returns the index for 'key' if 'key' is an appropriate key to live in
  116. ** the array part of the table, 0 otherwise.
  117. */
  118. static unsigned int arrayindex (const TValue *key) {
  119. if (ttisinteger(key)) {
  120. lua_Integer k = ivalue(key);
  121. if (0 < k && (lua_Unsigned)k <= MAXASIZE)
  122. return cast(unsigned int, k); /* 'key' is an appropriate array index */
  123. }
  124. return 0; /* 'key' did not match some condition */
  125. }
  126. /*
  127. ** returns the index of a 'key' for table traversals. First goes all
  128. ** elements in the array part, then elements in the hash part. The
  129. ** beginning of a traversal is signaled by 0.
  130. */
  131. static unsigned int findindex (lua_State *L, Table *t, StkId key) {
  132. unsigned int i;
  133. if (ttisnil(key)) return 0; /* first iteration */
  134. i = arrayindex(key);
  135. if (i != 0 && i <= t->sizearray) /* is 'key' inside array part? */
  136. return i; /* yes; that's the index */
  137. else {
  138. int nx;
  139. Node *n = mainposition(t, key);
  140. for (;;) { /* check whether 'key' is somewhere in the chain */
  141. /* key may be dead already, but it is ok to use it in 'next' */
  142. if (luaV_rawequalobj(gkey(n), key) ||
  143. (ttisdeadkey(gkey(n)) && iscollectable(key) &&
  144. deadvalue(gkey(n)) == gcvalue(key))) {
  145. i = cast_int(n - gnode(t, 0)); /* key index in hash table */
  146. /* hash elements are numbered after array ones */
  147. return (i + 1) + t->sizearray;
  148. }
  149. nx = gnext(n);
  150. if (nx == 0)
  151. luaG_runerror(L, "invalid key to 'next'"); /* key not found */
  152. else n += nx;
  153. }
  154. }
  155. }
  156. int luaH_next (lua_State *L, Table *t, StkId key) {
  157. unsigned int i = findindex(L, t, key); /* find original element */
  158. for (; i < t->sizearray; i++) { /* try first array part */
  159. if (!ttisnil(&t->array[i])) { /* a non-nil value? */
  160. setivalue(key, i + 1);
  161. setobj2s(L, key+1, &t->array[i]);
  162. return 1;
  163. }
  164. }
  165. for (i -= t->sizearray; cast_int(i) < sizenode(t); i++) { /* hash part */
  166. if (!ttisnil(gval(gnode(t, i)))) { /* a non-nil value? */
  167. setobj2s(L, key, gkey(gnode(t, i)));
  168. setobj2s(L, key+1, gval(gnode(t, i)));
  169. return 1;
  170. }
  171. }
  172. return 0; /* no more elements */
  173. }
  174. /*
  175. ** {=============================================================
  176. ** Rehash
  177. ** ==============================================================
  178. */
  179. /*
  180. ** Compute the optimal size for the array part of table 't'. 'nums' is a
  181. ** "count array" where 'nums[i]' is the number of integers in the table
  182. ** between 2^(i - 1) + 1 and 2^i. 'pna' enters with the total number of
  183. ** integer keys in the table and leaves with the number of keys that
  184. ** will go to the array part; return the optimal size.
  185. */
  186. static unsigned int computesizes (unsigned int nums[], unsigned int *pna) {
  187. int i;
  188. unsigned int twotoi; /* 2^i (candidate for optimal size) */
  189. unsigned int a = 0; /* number of elements smaller than 2^i */
  190. unsigned int na = 0; /* number of elements to go to array part */
  191. unsigned int optimal = 0; /* optimal size for array part */
  192. /* loop while keys can fill more than half of total size */
  193. for (i = 0, twotoi = 1; *pna > twotoi / 2; i++, twotoi *= 2) {
  194. if (nums[i] > 0) {
  195. a += nums[i];
  196. if (a > twotoi/2) { /* more than half elements present? */
  197. optimal = twotoi; /* optimal size (till now) */
  198. na = a; /* all elements up to 'optimal' will go to array part */
  199. }
  200. }
  201. }
  202. lua_assert((optimal == 0 || optimal / 2 < na) && na <= optimal);
  203. *pna = na;
  204. return optimal;
  205. }
  206. static int countint (const TValue *key, unsigned int *nums) {
  207. unsigned int k = arrayindex(key);
  208. if (k != 0) { /* is 'key' an appropriate array index? */
  209. nums[luaO_ceillog2(k)]++; /* count as such */
  210. return 1;
  211. }
  212. else
  213. return 0;
  214. }
  215. /*
  216. ** Count keys in array part of table 't': Fill 'nums[i]' with
  217. ** number of keys that will go into corresponding slice and return
  218. ** total number of non-nil keys.
  219. */
  220. static unsigned int numusearray (const Table *t, unsigned int *nums) {
  221. int lg;
  222. unsigned int ttlg; /* 2^lg */
  223. unsigned int ause = 0; /* summation of 'nums' */
  224. unsigned int i = 1; /* count to traverse all array keys */
  225. /* traverse each slice */
  226. for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) {
  227. unsigned int lc = 0; /* counter */
  228. unsigned 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. static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) {
  245. int totaluse = 0; /* total number of elements */
  246. int ause = 0; /* elements added to 'nums' (can go to array part) */
  247. int i = sizenode(t);
  248. while (i--) {
  249. Node *n = &t->node[i];
  250. if (!ttisnil(gval(n))) {
  251. ause += countint(gkey(n), nums);
  252. totaluse++;
  253. }
  254. }
  255. *pna += ause;
  256. return totaluse;
  257. }
  258. static void setarrayvector (lua_State *L, Table *t, unsigned int size) {
  259. unsigned int i;
  260. luaM_reallocvector(L, t->array, t->sizearray, size, TValue);
  261. for (i=t->sizearray; i<size; i++)
  262. setnilvalue(&t->array[i]);
  263. t->sizearray = size;
  264. }
  265. static void setnodevector (lua_State *L, Table *t, unsigned int size) {
  266. if (size == 0) { /* no elements to hash part? */
  267. t->node = cast(Node *, dummynode); /* use common 'dummynode' */
  268. t->lsizenode = 0;
  269. t->lastfree = NULL; /* signal that it is using dummy node */
  270. }
  271. else {
  272. int i;
  273. int lsize = luaO_ceillog2(size);
  274. if (lsize > MAXHBITS)
  275. luaG_runerror(L, "table overflow");
  276. size = twoto(lsize);
  277. t->node = luaM_newvector(L, size, Node);
  278. for (i = 0; i < (int)size; i++) {
  279. Node *n = gnode(t, i);
  280. gnext(n) = 0;
  281. setnilvalue(wgkey(n));
  282. setnilvalue(gval(n));
  283. }
  284. t->lsizenode = cast_byte(lsize);
  285. t->lastfree = gnode(t, size); /* all positions are free */
  286. }
  287. }
  288. void luaH_resize (lua_State *L, Table *t, unsigned int nasize,
  289. unsigned int nhsize) {
  290. unsigned int i;
  291. int j;
  292. unsigned int oldasize = t->sizearray;
  293. int oldhsize = allocsizenode(t);
  294. Node *nold = t->node; /* save old hash ... */
  295. if (nasize > oldasize) /* array part must grow? */
  296. setarrayvector(L, t, nasize);
  297. /* create new hash part with appropriate size */
  298. setnodevector(L, t, nhsize);
  299. if (nasize < oldasize) { /* array part must shrink? */
  300. t->sizearray = nasize;
  301. /* re-insert elements from vanishing slice */
  302. for (i=nasize; i<oldasize; i++) {
  303. if (!ttisnil(&t->array[i]))
  304. luaH_setint(L, t, i + 1, &t->array[i]);
  305. }
  306. /* shrink array */
  307. luaM_reallocvector(L, t->array, oldasize, nasize, TValue);
  308. }
  309. /* re-insert elements from hash part */
  310. for (j = oldhsize - 1; j >= 0; j--) {
  311. Node *old = nold + j;
  312. if (!ttisnil(gval(old))) {
  313. /* doesn't need barrier/invalidate cache, as entry was
  314. already present in the table */
  315. setobjt2t(L, luaH_set(L, t, gkey(old)), gval(old));
  316. }
  317. }
  318. if (oldhsize > 0) /* not the dummy node? */
  319. luaM_freearray(L, nold, cast(size_t, oldhsize)); /* free old hash */
  320. }
  321. void luaH_resizearray (lua_State *L, Table *t, unsigned int nasize) {
  322. int nsize = allocsizenode(t);
  323. luaH_resize(L, t, nasize, nsize);
  324. }
  325. /*
  326. ** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i
  327. */
  328. static void rehash (lua_State *L, Table *t, const TValue *ek) {
  329. unsigned int asize; /* optimal size for array part */
  330. unsigned int na; /* number of keys in the array part */
  331. unsigned int nums[MAXABITS + 1];
  332. int i;
  333. int totaluse;
  334. for (i = 0; i <= MAXABITS; i++) nums[i] = 0; /* reset counts */
  335. na = numusearray(t, nums); /* count keys in array part */
  336. totaluse = na; /* all those keys are integer keys */
  337. totaluse += numusehash(t, nums, &na); /* count keys in hash part */
  338. /* count extra key */
  339. na += countint(ek, nums);
  340. totaluse++;
  341. /* compute new size for array part */
  342. asize = computesizes(nums, &na);
  343. /* resize the table to new computed sizes */
  344. luaH_resize(L, t, asize, totaluse - na);
  345. }
  346. /*
  347. ** }=============================================================
  348. */
  349. Table *luaH_new (lua_State *L) {
  350. GCObject *o = luaC_newobj(L, LUA_TTABLE, sizeof(Table));
  351. Table *t = gco2t(o);
  352. t->metatable = NULL;
  353. t->flags = cast_byte(~0);
  354. t->array = NULL;
  355. t->sizearray = 0;
  356. setnodevector(L, t, 0);
  357. return t;
  358. }
  359. void luaH_free (lua_State *L, Table *t) {
  360. if (!isdummy(t))
  361. luaM_freearray(L, t->node, cast(size_t, sizenode(t)));
  362. luaM_freearray(L, t->array, t->sizearray);
  363. luaM_free(L, t);
  364. }
  365. static Node *getfreepos (Table *t) {
  366. if (!isdummy(t)) {
  367. while (t->lastfree > t->node) {
  368. t->lastfree--;
  369. if (ttisnil(gkey(t->lastfree)))
  370. return t->lastfree;
  371. }
  372. }
  373. return NULL; /* could not find a free place */
  374. }
  375. /*
  376. ** inserts a new key into a hash table; first, check whether key's main
  377. ** position is free. If not, check whether colliding node is in its main
  378. ** position or not: if it is not, move colliding node to an empty place and
  379. ** put new key in its main position; otherwise (colliding node is in its main
  380. ** position), new key goes to an empty position.
  381. */
  382. TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {
  383. Node *mp;
  384. TValue aux;
  385. if (ttisnil(key)) luaG_runerror(L, "table index is nil");
  386. else if (ttisfloat(key)) {
  387. lua_Integer k;
  388. if (luaV_tointeger(key, &k, 0)) { /* does index fit in an integer? */
  389. setivalue(&aux, k);
  390. key = &aux; /* insert it as an integer */
  391. }
  392. else if (luai_numisnan(fltvalue(key)))
  393. luaG_runerror(L, "table index is NaN");
  394. }
  395. mp = mainposition(t, key);
  396. if (!ttisnil(gval(mp)) || isdummy(t)) { /* main position is taken? */
  397. Node *othern;
  398. Node *f = getfreepos(t); /* get a free place */
  399. if (f == NULL) { /* cannot find a free place? */
  400. rehash(L, t, key); /* grow table */
  401. /* whatever called 'newkey' takes care of TM cache */
  402. return luaH_set(L, t, key); /* insert key into grown table */
  403. }
  404. lua_assert(!isdummy(t));
  405. othern = mainposition(t, gkey(mp));
  406. if (othern != mp) { /* is colliding node out of its main position? */
  407. /* yes; move colliding node into free position */
  408. while (othern + gnext(othern) != mp) /* find previous */
  409. othern += gnext(othern);
  410. gnext(othern) = cast_int(f - othern); /* rechain to point to 'f' */
  411. *f = *mp; /* copy colliding node into free pos. (mp->next also goes) */
  412. if (gnext(mp) != 0) {
  413. gnext(f) += cast_int(mp - f); /* correct 'next' */
  414. gnext(mp) = 0; /* now 'mp' is free */
  415. }
  416. setnilvalue(gval(mp));
  417. }
  418. else { /* colliding node is in its own main position */
  419. /* new node will go into free position */
  420. if (gnext(mp) != 0)
  421. gnext(f) = cast_int((mp + gnext(mp)) - f); /* chain new position */
  422. else lua_assert(gnext(f) == 0);
  423. gnext(mp) = cast_int(f - mp);
  424. mp = f;
  425. }
  426. }
  427. setnodekey(L, &mp->i_key, key);
  428. luaC_barrierback(L, t, key);
  429. lua_assert(ttisnil(gval(mp)));
  430. return gval(mp);
  431. }
  432. /*
  433. ** search function for integers
  434. */
  435. const TValue *luaH_getint (Table *t, lua_Integer key) {
  436. /* (1 <= key && key <= t->sizearray) */
  437. if (l_castS2U(key) - 1 < t->sizearray)
  438. return &t->array[key - 1];
  439. else {
  440. Node *n = hashint(t, key);
  441. for (;;) { /* check whether 'key' is somewhere in the chain */
  442. if (ttisinteger(gkey(n)) && ivalue(gkey(n)) == key)
  443. return gval(n); /* that's it */
  444. else {
  445. int nx = gnext(n);
  446. if (nx == 0) break;
  447. n += nx;
  448. }
  449. }
  450. return luaO_nilobject;
  451. }
  452. }
  453. /*
  454. ** search function for short strings
  455. */
  456. const TValue *luaH_getshortstr (Table *t, TString *key) {
  457. Node *n = hashstr(t, key);
  458. lua_assert(key->tt == LUA_TSHRSTR);
  459. for (;;) { /* check whether 'key' is somewhere in the chain */
  460. const TValue *k = gkey(n);
  461. if (ttisshrstring(k) && eqshrstr(tsvalue(k), key))
  462. return gval(n); /* that's it */
  463. else {
  464. int nx = gnext(n);
  465. if (nx == 0)
  466. return luaO_nilobject; /* not found */
  467. n += nx;
  468. }
  469. }
  470. }
  471. /*
  472. ** "Generic" get version. (Not that generic: not valid for integers,
  473. ** which may be in array part, nor for floats with integral values.)
  474. */
  475. static const TValue *getgeneric (Table *t, const TValue *key) {
  476. Node *n = mainposition(t, key);
  477. for (;;) { /* check whether 'key' is somewhere in the chain */
  478. if (luaV_rawequalobj(gkey(n), key))
  479. return gval(n); /* that's it */
  480. else {
  481. int nx = gnext(n);
  482. if (nx == 0)
  483. return luaO_nilobject; /* not found */
  484. n += nx;
  485. }
  486. }
  487. }
  488. const TValue *luaH_getstr (Table *t, TString *key) {
  489. if (key->tt == LUA_TSHRSTR)
  490. return luaH_getshortstr(t, key);
  491. else { /* for long strings, use generic case */
  492. TValue ko;
  493. setsvalue(cast(lua_State *, NULL), &ko, key);
  494. return getgeneric(t, &ko);
  495. }
  496. }
  497. /*
  498. ** main search function
  499. */
  500. const TValue *luaH_get (Table *t, const TValue *key) {
  501. switch (ttype(key)) {
  502. case LUA_TSHRSTR: return luaH_getshortstr(t, tsvalue(key));
  503. case LUA_TNUMINT: return luaH_getint(t, ivalue(key));
  504. case LUA_TNIL: return luaO_nilobject;
  505. case LUA_TNUMFLT: {
  506. lua_Integer k;
  507. if (luaV_tointeger(key, &k, 0)) /* index is int? */
  508. return luaH_getint(t, k); /* use specialized version */
  509. /* else... */
  510. } /* FALLTHROUGH */
  511. default:
  512. return getgeneric(t, key);
  513. }
  514. }
  515. /*
  516. ** beware: when using this function you probably need to check a GC
  517. ** barrier and invalidate the TM cache.
  518. */
  519. TValue *luaH_set (lua_State *L, Table *t, const TValue *key) {
  520. const TValue *p = luaH_get(t, key);
  521. if (p != luaO_nilobject)
  522. return cast(TValue *, p);
  523. else return luaH_newkey(L, t, key);
  524. }
  525. void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) {
  526. const TValue *p = luaH_getint(t, key);
  527. TValue *cell;
  528. if (p != luaO_nilobject)
  529. cell = cast(TValue *, p);
  530. else {
  531. TValue k;
  532. setivalue(&k, key);
  533. cell = luaH_newkey(L, t, &k);
  534. }
  535. setobj2t(L, cell, value);
  536. }
  537. static int unbound_search (Table *t, unsigned int j) {
  538. unsigned int i = j; /* i is zero or a present index */
  539. j++;
  540. /* find 'i' and 'j' such that i is present and j is not */
  541. while (!ttisnil(luaH_getint(t, j))) {
  542. i = j;
  543. if (j > cast(unsigned int, MAX_INT)/2) { /* overflow? */
  544. /* table was built with bad purposes: resort to linear search */
  545. i = 1;
  546. while (!ttisnil(luaH_getint(t, i))) i++;
  547. return i - 1;
  548. }
  549. j *= 2;
  550. }
  551. /* now do a binary search between them */
  552. while (j - i > 1) {
  553. unsigned int m = (i+j)/2;
  554. if (ttisnil(luaH_getint(t, m))) j = m;
  555. else i = m;
  556. }
  557. return i;
  558. }
  559. /*
  560. ** Try to find a boundary in table 't'. A 'boundary' is an integer index
  561. ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
  562. */
  563. int luaH_getn (Table *t) {
  564. unsigned int j = t->sizearray;
  565. if (j > 0 && ttisnil(&t->array[j - 1])) {
  566. /* there is a boundary in the array part: (binary) search for it */
  567. unsigned int i = 0;
  568. while (j - i > 1) {
  569. unsigned int m = (i+j)/2;
  570. if (ttisnil(&t->array[m - 1])) j = m;
  571. else i = m;
  572. }
  573. return i;
  574. }
  575. /* else must find a boundary in hash part */
  576. else if (isdummy(t)) /* hash part is empty? */
  577. return j; /* that is easy... */
  578. else return unbound_search(t, j);
  579. }
  580. #if defined(LUA_DEBUG)
  581. Node *luaH_mainposition (const Table *t, const TValue *key) {
  582. return mainposition(t, key);
  583. }
  584. int luaH_isdummy (const Table *t) { return isdummy(t); }
  585. #endif