ltable.c 21 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759
  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. ** Implementation of tables (aka arrays, objects, or hash tables).
  8. ** Tables keep its elements in two parts: an array part and a hash part.
  9. ** Non-negative integer keys are all candidates to be kept in the array
  10. ** part. The actual size of the array is the largest `n' such that at
  11. ** least half the slots between 0 and n are in use.
  12. ** Hash uses a mix of chained scatter table with Brent's variation.
  13. ** A main invariant of these tables is that, if an element is not
  14. ** in its main position (i.e. the `original' position that its hash gives
  15. ** to it), then the colliding element is in its own main position.
  16. ** Hence even when the load factor reaches 100%, performance remains good.
  17. */
  18. #define ltable_c
  19. #define LUA_CORE
  20. #define LUAC_CROSS_FILE
  21. #include "lua.h"
  22. #include C_HEADER_MATH
  23. #include C_HEADER_STRING
  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 "ltable.h"
  31. #include "lrotable.h"
  32. /*
  33. ** max size of array part is 2^MAXBITS
  34. */
  35. #if LUAI_BITSINT > 26
  36. #define MAXBITS 26
  37. #else
  38. #define MAXBITS (LUAI_BITSINT-2)
  39. #endif
  40. #define MAXASIZE (1 << MAXBITS)
  41. #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t))))
  42. #define hashstr(t,str) hashpow2(t, (str)->tsv.hash)
  43. #define hashboolean(t,p) hashpow2(t, p)
  44. /*
  45. ** for some types, it is better to avoid modulus by power of 2, as
  46. ** they tend to have many 2 factors.
  47. */
  48. #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1))))
  49. #define hashpointer(t,p) hashmod(t, IntPoint(p))
  50. /*
  51. ** number of ints inside a lua_Number
  52. */
  53. #define numints cast_int(sizeof(lua_Number)/sizeof(int))
  54. #define dummynode (&dummynode_)
  55. static const Node dummynode_ = {
  56. {LUA_TVALUE_NIL}, /* value */
  57. {LUA_TKEY_NIL} /* key */
  58. };
  59. /*
  60. ** hash for lua_Numbers
  61. */
  62. static Node *hashnum (const Table *t, lua_Number n) {
  63. unsigned int a[numints];
  64. int i;
  65. if (luai_numeq(n, 0)) /* avoid problems with -0 */
  66. return gnode(t, 0);
  67. c_memcpy(a, &n, sizeof(a));
  68. for (i = 1; i < numints; i++) a[0] += a[i];
  69. return hashmod(t, a[0]);
  70. }
  71. /*
  72. ** returns the `main' position of an element in a table (that is, the index
  73. ** of its hash value)
  74. */
  75. static Node *mainposition (const Table *t, const TValue *key) {
  76. switch (ttype(key)) {
  77. case LUA_TNUMBER:
  78. return hashnum(t, nvalue(key));
  79. case LUA_TSTRING:
  80. return hashstr(t, rawtsvalue(key));
  81. case LUA_TBOOLEAN:
  82. return hashboolean(t, bvalue(key));
  83. case LUA_TLIGHTUSERDATA:
  84. case LUA_TROTABLE:
  85. case LUA_TLIGHTFUNCTION:
  86. return hashpointer(t, pvalue(key));
  87. default:
  88. return hashpointer(t, gcvalue(key));
  89. }
  90. }
  91. /*
  92. ** returns the index for `key' if `key' is an appropriate key to live in
  93. ** the array part of the table, -1 otherwise.
  94. */
  95. static int arrayindex (const TValue *key) {
  96. if (ttisnumber(key)) {
  97. lua_Number n = nvalue(key);
  98. int k;
  99. lua_number2int(k, n);
  100. if (luai_numeq(cast_num(k), n))
  101. return k;
  102. }
  103. return -1; /* `key' did not match some condition */
  104. }
  105. /*
  106. ** returns the index of a `key' for table traversals. First goes all
  107. ** elements in the array part, then elements in the hash part. The
  108. ** beginning of a traversal is signalled by -1.
  109. */
  110. static int findindex (lua_State *L, Table *t, StkId key) {
  111. int i;
  112. if (ttisnil(key)) return -1; /* first iteration */
  113. i = arrayindex(key);
  114. if (0 < i && i <= t->sizearray) /* is `key' inside array part? */
  115. return i-1; /* yes; that's the index (corrected to C) */
  116. else {
  117. Node *n = mainposition(t, key);
  118. do { /* check whether `key' is somewhere in the chain */
  119. /* key may be dead already, but it is ok to use it in `next' */
  120. if (luaO_rawequalObj(key2tval(n), key) ||
  121. (ttype(gkey(n)) == LUA_TDEADKEY && iscollectable(key) &&
  122. gcvalue(gkey(n)) == gcvalue(key))) {
  123. i = cast_int(n - gnode(t, 0)); /* key index in hash table */
  124. /* hash elements are numbered after array ones */
  125. return i + t->sizearray;
  126. }
  127. else n = gnext(n);
  128. } while (n);
  129. luaG_runerror(L, "invalid key to " LUA_QL("next")); /* key not found */
  130. return 0; /* to avoid warnings */
  131. }
  132. }
  133. int luaH_next (lua_State *L, Table *t, StkId key) {
  134. int i = findindex(L, t, key); /* find original element */
  135. for (i++; i < t->sizearray; i++) { /* try first array part */
  136. if (!ttisnil(&t->array[i])) { /* a non-nil value? */
  137. setnvalue(key, cast_num(i+1));
  138. setobj2s(L, key+1, &t->array[i]);
  139. return 1;
  140. }
  141. }
  142. for (i -= t->sizearray; i < sizenode(t); i++) { /* then hash part */
  143. if (!ttisnil(gval(gnode(t, i)))) { /* a non-nil value? */
  144. setobj2s(L, key, key2tval(gnode(t, i)));
  145. setobj2s(L, key+1, gval(gnode(t, i)));
  146. return 1;
  147. }
  148. }
  149. return 0; /* no more elements */
  150. }
  151. int luaH_next_ro (lua_State *L, void *t, StkId key) {
  152. luaR_next(L, t, key, key+1);
  153. return ttisnil(key) ? 0 : 1;
  154. }
  155. /*
  156. ** {=============================================================
  157. ** Rehash
  158. ** ==============================================================
  159. */
  160. static int computesizes (int nums[], int *narray) {
  161. int i;
  162. int twotoi; /* 2^i */
  163. int a = 0; /* number of elements smaller than 2^i */
  164. int na = 0; /* number of elements to go to array part */
  165. int n = 0; /* optimal size for array part */
  166. for (i = 0, twotoi = 1; twotoi/2 < *narray; i++, twotoi *= 2) {
  167. if (nums[i] > 0) {
  168. a += nums[i];
  169. if (a > twotoi/2) { /* more than half elements present? */
  170. n = twotoi; /* optimal size (till now) */
  171. na = a; /* all elements smaller than n will go to array part */
  172. }
  173. }
  174. if (a == *narray) break; /* all elements already counted */
  175. }
  176. *narray = n;
  177. lua_assert(*narray/2 <= na && na <= *narray);
  178. return na;
  179. }
  180. static int countint (const TValue *key, int *nums) {
  181. int k = arrayindex(key);
  182. if (0 < k && k <= MAXASIZE) { /* is `key' an appropriate array index? */
  183. nums[ceillog2(k)]++; /* count as such */
  184. return 1;
  185. }
  186. else
  187. return 0;
  188. }
  189. static int numusearray (const Table *t, int *nums) {
  190. int lg;
  191. int ttlg; /* 2^lg */
  192. int ause = 0; /* summation of `nums' */
  193. int i = 1; /* count to traverse all array keys */
  194. for (lg=0, ttlg=1; lg<=MAXBITS; lg++, ttlg*=2) { /* for each slice */
  195. int lc = 0; /* counter */
  196. int lim = ttlg;
  197. if (lim > t->sizearray) {
  198. lim = t->sizearray; /* adjust upper limit */
  199. if (i > lim)
  200. break; /* no more elements to count */
  201. }
  202. /* count elements in range (2^(lg-1), 2^lg] */
  203. for (; i <= lim; i++) {
  204. if (!ttisnil(&t->array[i-1]))
  205. lc++;
  206. }
  207. nums[lg] += lc;
  208. ause += lc;
  209. }
  210. return ause;
  211. }
  212. static int numusehash (const Table *t, int *nums, int *pnasize) {
  213. int totaluse = 0; /* total number of elements */
  214. int ause = 0; /* summation of `nums' */
  215. int i = sizenode(t);
  216. while (i--) {
  217. Node *n = &t->node[i];
  218. if (!ttisnil(gval(n))) {
  219. ause += countint(key2tval(n), nums);
  220. totaluse++;
  221. }
  222. }
  223. *pnasize += ause;
  224. return totaluse;
  225. }
  226. static void setarrayvector (lua_State *L, Table *t, int size) {
  227. int i;
  228. luaM_reallocvector(L, t->array, t->sizearray, size, TValue);
  229. for (i=t->sizearray; i<size; i++)
  230. setnilvalue(&t->array[i]);
  231. t->sizearray = size;
  232. }
  233. static Node *getfreepos (Table *t) {
  234. while (t->lastfree-- > t->node) {
  235. if (ttisnil(gkey(t->lastfree)))
  236. return t->lastfree;
  237. }
  238. return NULL; /* could not find a free place */
  239. }
  240. static void resizenodevector (lua_State *L, Table *t, int oldsize, int newsize) {
  241. int lsize;
  242. if (newsize == 0) { /* no elements to hash part? */
  243. t->node = cast(Node *, dummynode); /* use common `dummynode' */
  244. lsize = 0;
  245. }
  246. else {
  247. Node *node = t->node;
  248. int i;
  249. lsize = ceillog2(newsize);
  250. if (lsize > MAXBITS)
  251. luaG_runerror(L, "table overflow");
  252. newsize = twoto(lsize);
  253. if (node == dummynode) {
  254. oldsize = 0;
  255. node = NULL; /* don't try to realloc `dummynode' pointer. */
  256. }
  257. luaM_reallocvector(L, node, oldsize, newsize, Node);
  258. t->node = node;
  259. for (i=oldsize; i<newsize; i++) {
  260. Node *n = gnode(t, i);
  261. gnext(n) = NULL;
  262. setnilvalue(gkey(n));
  263. setnilvalue(gval(n));
  264. }
  265. }
  266. t->lsizenode = cast_byte(lsize);
  267. t->lastfree = gnode(t, newsize); /* reset lastfree to end of table. */
  268. }
  269. static Node *find_prev_node(Node *mp, Node *next) {
  270. Node *prev = mp;
  271. while (prev != NULL && gnext(prev) != next) prev = gnext(prev);
  272. return prev;
  273. }
  274. /*
  275. ** move a node from it's old position to it's new position during a rehash;
  276. ** first, check whether the moving node's main position is free. If not, check whether
  277. ** colliding node is in its main position or not: if it is not, move colliding
  278. ** node to an empty place and put moving node in its main position; otherwise
  279. ** (colliding node is in its main position), moving node goes to an empty position.
  280. */
  281. static int move_node (lua_State *L, Table *t, Node *node) {
  282. Node *mp = mainposition(t, key2tval(node));
  283. /* if node is in it's main position, don't need to move node. */
  284. if (mp == node) return 1;
  285. /* if node is in it's main position's chain, don't need to move node. */
  286. if (find_prev_node(mp, node) != NULL) return 1;
  287. /* is main position is free? */
  288. if (!ttisnil(gval(mp)) || mp == dummynode) {
  289. /* no; move main position node if it is out of its main position */
  290. Node *othermp;
  291. othermp = mainposition(t, key2tval(mp));
  292. if (othermp != mp) { /* is colliding node out of its main position? */
  293. /* yes; swap colliding node with the node that is being moved. */
  294. Node *prev;
  295. Node tmp;
  296. tmp = *node;
  297. prev = find_prev_node(othermp, mp); /* find previous */
  298. if (prev != NULL) gnext(prev) = node; /* redo the chain with `n' in place of `mp' */
  299. *node = *mp; /* copy colliding node into free pos. (mp->next also goes) */
  300. *mp = tmp;
  301. return (prev != NULL) ? 1 : 0; /* is colliding node part of its main position chain? */
  302. }
  303. else { /* colliding node is in its own main position */
  304. /* add node to main position's chain. */
  305. gnext(node) = gnext(mp); /* chain new position */
  306. gnext(mp) = node;
  307. }
  308. }
  309. else { /* main position is free, move node */
  310. *mp = *node;
  311. gnext(node) = NULL;
  312. setnilvalue(gkey(node));
  313. setnilvalue(gval(node));
  314. }
  315. return 1;
  316. }
  317. static int move_number (lua_State *L, Table *t, Node *node) {
  318. int key;
  319. lua_Number n = nvalue(key2tval(node));
  320. lua_number2int(key, n);
  321. if (luai_numeq(cast_num(key), nvalue(key2tval(node)))) {/* index is int? */
  322. /* (1 <= key && key <= t->sizearray) */
  323. if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray)) {
  324. setobjt2t(L, &t->array[key-1], gval(node));
  325. setnilvalue(gkey(node));
  326. setnilvalue(gval(node));
  327. return 1;
  328. }
  329. }
  330. return 0;
  331. }
  332. static void resize_hashpart (lua_State *L, Table *t, int nhsize) {
  333. int i;
  334. int lsize=0;
  335. int oldhsize = (t->node != dummynode) ? twoto(t->lsizenode) : 0;
  336. if (nhsize > 0) { /* round new hashpart size up to next power of two. */
  337. lsize=ceillog2(nhsize);
  338. if (lsize > MAXBITS)
  339. luaG_runerror(L, "table overflow");
  340. }
  341. nhsize = twoto(lsize);
  342. /* grow hash part to new size. */
  343. if (oldhsize < nhsize)
  344. resizenodevector(L, t, oldhsize, nhsize);
  345. else { /* hash part might be shrinking */
  346. if (nhsize > 0) {
  347. t->lsizenode = cast_byte(lsize);
  348. t->lastfree = gnode(t, nhsize); /* reset lastfree back to end of table. */
  349. }
  350. else { /* new hashpart size is zero. */
  351. resizenodevector(L, t, oldhsize, nhsize);
  352. return;
  353. }
  354. }
  355. /* break old chains, try moving int keys to array part and compact keys into new hashpart */
  356. for (i = 0; i < oldhsize; i++) {
  357. Node *old = gnode(t, i);
  358. gnext(old) = NULL;
  359. if (ttisnil(gval(old))) { /* clear nodes with nil values. */
  360. setnilvalue(gkey(old));
  361. continue;
  362. }
  363. if (ttisnumber(key2tval(old))) { /* try moving the int keys into array part. */
  364. if(move_number(L, t, old))
  365. continue;
  366. }
  367. if (i >= nhsize) { /* move all valid keys to indices < nhsize. */
  368. Node *n = getfreepos(t); /* get a free place */
  369. lua_assert(n != dummynode && n != NULL);
  370. *n = *old;
  371. }
  372. }
  373. /* shrink hash part */
  374. if (oldhsize > nhsize)
  375. resizenodevector(L, t, oldhsize, nhsize);
  376. /* move nodes to their new mainposition and re-create node chains */
  377. for (i = 0; i < nhsize; i++) {
  378. Node *curr = gnode(t, i);
  379. if (!ttisnil(gval(curr)))
  380. while (move_node(L, t, curr) == 0);
  381. }
  382. }
  383. static void resize (lua_State *L, Table *t, int nasize, int nhsize) {
  384. int i;
  385. int oldasize = t->sizearray;
  386. if (nasize > oldasize) /* array part must grow? */
  387. setarrayvector(L, t, nasize);
  388. resize_hashpart(L, t, nhsize);
  389. if (nasize < oldasize) { /* array part must shrink? */
  390. t->sizearray = nasize;
  391. /* re-insert elements from vanishing slice */
  392. for (i=nasize; i<oldasize; i++) {
  393. if (!ttisnil(&t->array[i]))
  394. setobjt2t(L, luaH_setnum(L, t, i+1), &t->array[i]);
  395. }
  396. /* shrink array */
  397. luaM_reallocvector(L, t->array, oldasize, nasize, TValue);
  398. }
  399. }
  400. void luaH_resizearray (lua_State *L, Table *t, int nasize) {
  401. int nsize = (t->node == dummynode) ? 0 : sizenode(t);
  402. resize(L, t, nasize, nsize);
  403. }
  404. static void rehash (lua_State *L, Table *t, const TValue *ek) {
  405. int nasize, na;
  406. int nums[MAXBITS+1]; /* nums[i] = number of keys between 2^(i-1) and 2^i */
  407. int i;
  408. int totaluse;
  409. for (i=0; i<=MAXBITS; i++) nums[i] = 0; /* reset counts */
  410. nasize = numusearray(t, nums); /* count keys in array part */
  411. totaluse = nasize; /* all those keys are integer keys */
  412. totaluse += numusehash(t, nums, &nasize); /* count keys in hash part */
  413. /* count extra key */
  414. nasize += countint(ek, nums);
  415. totaluse++;
  416. /* compute new size for array part */
  417. na = computesizes(nums, &nasize);
  418. /* resize the table to new computed sizes */
  419. resize(L, t, nasize, totaluse - na);
  420. }
  421. /*
  422. ** }=============================================================
  423. */
  424. Table *luaH_new (lua_State *L, int narray, int nhash) {
  425. Table *t = luaM_new(L, Table);
  426. luaC_link(L, obj2gco(t), LUA_TTABLE);
  427. sethvalue2s(L, L->top, t); /* put table on stack */
  428. incr_top(L);
  429. t->metatable = NULL;
  430. t->flags = cast_byte(~0);
  431. /* temporary values (kept only if some malloc fails) */
  432. t->array = NULL;
  433. t->sizearray = 0;
  434. t->lsizenode = 0;
  435. t->node = cast(Node *, dummynode);
  436. setarrayvector(L, t, narray);
  437. resizenodevector(L, t, 0, nhash);
  438. L->top--; /* remove table from stack */
  439. return t;
  440. }
  441. void luaH_free (lua_State *L, Table *t) {
  442. if (t->node != dummynode)
  443. luaM_freearray(L, t->node, sizenode(t), Node);
  444. luaM_freearray(L, t->array, t->sizearray, TValue);
  445. luaM_free(L, t);
  446. }
  447. /*
  448. ** inserts a new key into a hash table; first, check whether key's main
  449. ** position is free. If not, check whether colliding node is in its main
  450. ** position or not: if it is not, move colliding node to an empty place and
  451. ** put new key in its main position; otherwise (colliding node is in its main
  452. ** position), new key goes to an empty position.
  453. */
  454. static TValue *newkey (lua_State *L, Table *t, const TValue *key) {
  455. Node *mp = mainposition(t, key);
  456. if (!ttisnil(gval(mp)) || mp == dummynode) {
  457. Node *othern;
  458. Node *n = getfreepos(t); /* get a free place */
  459. if (n == NULL) { /* cannot find a free place? */
  460. rehash(L, t, key); /* grow table */
  461. return luaH_set(L, t, key); /* re-insert key into grown table */
  462. }
  463. lua_assert(n != dummynode);
  464. othern = mainposition(t, key2tval(mp));
  465. if (othern != mp) { /* is colliding node out of its main position? */
  466. /* yes; move colliding node into free position */
  467. while (gnext(othern) != mp) othern = gnext(othern); /* find previous */
  468. gnext(othern) = n; /* redo the chain with `n' in place of `mp' */
  469. *n = *mp; /* copy colliding node into free pos. (mp->next also goes) */
  470. gnext(mp) = NULL; /* now `mp' is free */
  471. setnilvalue(gval(mp));
  472. }
  473. else { /* colliding node is in its own main position */
  474. /* new node will go into free position */
  475. gnext(n) = gnext(mp); /* chain new position */
  476. gnext(mp) = n;
  477. mp = n;
  478. }
  479. }
  480. setobj2t(L, gkey(mp), key);
  481. luaC_barriert(L, t, key);
  482. lua_assert(ttisnil(gval(mp)));
  483. return gval(mp);
  484. }
  485. /*
  486. ** search function for integers
  487. */
  488. const TValue *luaH_getnum (Table *t, int key) {
  489. /* (1 <= key && key <= t->sizearray) */
  490. if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray))
  491. return &t->array[key-1];
  492. else {
  493. lua_Number nk = cast_num(key);
  494. Node *n = hashnum(t, nk);
  495. do { /* check whether `key' is somewhere in the chain */
  496. if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)), nk))
  497. return gval(n); /* that's it */
  498. else n = gnext(n);
  499. } while (n);
  500. return luaO_nilobject;
  501. }
  502. }
  503. /* same thing for rotables */
  504. const TValue *luaH_getnum_ro (void *t, int key) {
  505. const TValue *res = luaR_findentry(t, NULL, key, NULL);
  506. return res ? res : luaO_nilobject;
  507. }
  508. /*
  509. ** search function for strings
  510. */
  511. const TValue *luaH_getstr (Table *t, TString *key) {
  512. Node *n = hashstr(t, key);
  513. do { /* check whether `key' is somewhere in the chain */
  514. if (ttisstring(gkey(n)) && rawtsvalue(gkey(n)) == key)
  515. return gval(n); /* that's it */
  516. else n = gnext(n);
  517. } while (n);
  518. return luaO_nilobject;
  519. }
  520. /* same thing for rotables */
  521. const TValue *luaH_getstr_ro (void *t, TString *key) {
  522. char keyname[LUA_MAX_ROTABLE_NAME + 1];
  523. const TValue *res;
  524. if (!t)
  525. return luaO_nilobject;
  526. luaR_getcstr(keyname, key, LUA_MAX_ROTABLE_NAME);
  527. res = luaR_findentry(t, keyname, 0, NULL);
  528. return res ? res : luaO_nilobject;
  529. }
  530. /*
  531. ** main search function
  532. */
  533. const TValue *luaH_get (Table *t, const TValue *key) {
  534. switch (ttype(key)) {
  535. case LUA_TNIL: return luaO_nilobject;
  536. case LUA_TSTRING: return luaH_getstr(t, rawtsvalue(key));
  537. case LUA_TNUMBER: {
  538. int k;
  539. lua_Number n = nvalue(key);
  540. lua_number2int(k, n);
  541. if (luai_numeq(cast_num(k), nvalue(key))) /* index is int? */
  542. return luaH_getnum(t, k); /* use specialized version */
  543. /* else go through */
  544. }
  545. default: {
  546. Node *n = mainposition(t, key);
  547. do { /* check whether `key' is somewhere in the chain */
  548. if (luaO_rawequalObj(key2tval(n), key))
  549. return gval(n); /* that's it */
  550. else n = gnext(n);
  551. } while (n);
  552. return luaO_nilobject;
  553. }
  554. }
  555. }
  556. /* same thing for rotables */
  557. const TValue *luaH_get_ro (void *t, const TValue *key) {
  558. switch (ttype(key)) {
  559. case LUA_TNIL: return luaO_nilobject;
  560. case LUA_TSTRING: return luaH_getstr_ro(t, rawtsvalue(key));
  561. case LUA_TNUMBER: {
  562. int k;
  563. lua_Number n = nvalue(key);
  564. lua_number2int(k, n);
  565. if (luai_numeq(cast_num(k), nvalue(key))) /* index is int? */
  566. return luaH_getnum_ro(t, k); /* use specialized version */
  567. /* else go through */
  568. }
  569. default: {
  570. return luaO_nilobject;
  571. }
  572. }
  573. }
  574. TValue *luaH_set (lua_State *L, Table *t, const TValue *key) {
  575. const TValue *p = luaH_get(t, key);
  576. t->flags = 0;
  577. if (p != luaO_nilobject)
  578. return cast(TValue *, p);
  579. else {
  580. if (ttisnil(key)) luaG_runerror(L, "table index is nil");
  581. else if (ttisnumber(key) && luai_numisnan(nvalue(key)))
  582. luaG_runerror(L, "table index is NaN");
  583. return newkey(L, t, key);
  584. }
  585. }
  586. TValue *luaH_setnum (lua_State *L, Table *t, int key) {
  587. const TValue *p = luaH_getnum(t, key);
  588. if (p != luaO_nilobject)
  589. return cast(TValue *, p);
  590. else {
  591. TValue k;
  592. setnvalue(&k, cast_num(key));
  593. return newkey(L, t, &k);
  594. }
  595. }
  596. TValue *luaH_setstr (lua_State *L, Table *t, TString *key) {
  597. const TValue *p = luaH_getstr(t, key);
  598. if (p != luaO_nilobject)
  599. return cast(TValue *, p);
  600. else {
  601. TValue k;
  602. setsvalue(L, &k, key);
  603. return newkey(L, t, &k);
  604. }
  605. }
  606. static int unbound_search (Table *t, unsigned int j) {
  607. unsigned int i = j; /* i is zero or a present index */
  608. j++;
  609. /* find `i' and `j' such that i is present and j is not */
  610. while (!ttisnil(luaH_getnum(t, j))) {
  611. i = j;
  612. j *= 2;
  613. if (j > cast(unsigned int, MAX_INT)) { /* overflow? */
  614. /* table was built with bad purposes: resort to linear search */
  615. i = 1;
  616. while (!ttisnil(luaH_getnum(t, i))) i++;
  617. return i - 1;
  618. }
  619. }
  620. /* now do a binary search between them */
  621. while (j - i > 1) {
  622. unsigned int m = (i+j)/2;
  623. if (ttisnil(luaH_getnum(t, m))) j = m;
  624. else i = m;
  625. }
  626. return i;
  627. }
  628. /*
  629. ** Try to find a boundary in table `t'. A `boundary' is an integer index
  630. ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
  631. */
  632. int luaH_getn (Table *t) {
  633. unsigned int j = t->sizearray;
  634. if (j > 0 && ttisnil(&t->array[j - 1])) {
  635. /* there is a boundary in the array part: (binary) search for it */
  636. unsigned int i = 0;
  637. while (j - i > 1) {
  638. unsigned int m = (i+j)/2;
  639. if (ttisnil(&t->array[m - 1])) j = m;
  640. else i = m;
  641. }
  642. return i;
  643. }
  644. /* else must find a boundary in hash part */
  645. else if (t->node == dummynode) /* hash part is empty? */
  646. return j; /* that is easy... */
  647. else return unbound_search(t, j);
  648. }
  649. /* same thing for rotables */
  650. int luaH_getn_ro (void *t) {
  651. int i = 1, len=0;
  652. while(luaR_findentry(t, NULL, i ++, NULL))
  653. len ++;
  654. return len;
  655. }
  656. #if defined(LUA_DEBUG)
  657. Node *luaH_mainposition (const Table *t, const TValue *key) {
  658. return mainposition(t, key);
  659. }
  660. int luaH_isdummy (Node *n) { return n == dummynode; }
  661. #endif