ltable.c 25 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869
  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. #include "lua.h"
  21. #include <math.h>
  22. #include <string.h>
  23. #include "ldebug.h"
  24. #include "ldo.h"
  25. #include "lgc.h"
  26. #include "lmem.h"
  27. #include "lobject.h"
  28. #include "lstate.h"
  29. #include "ltable.h"
  30. #include "lstring.h"
  31. /*
  32. ** max size of array part is 2^MAXBITS
  33. */
  34. #if LUAI_BITSINT > 26
  35. #define MAXBITS 26
  36. #else
  37. #define MAXBITS (LUAI_BITSINT-2)
  38. #endif
  39. #define MAXASIZE (1 << MAXBITS)
  40. #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t))))
  41. #define hashstr(t,str) hashpow2(t, (str)->tsv.hash)
  42. #define hashboolean(t,p) hashpow2(t, p)
  43. /*
  44. ** for some types, it is better to avoid modulus by power of 2, as
  45. ** they tend to have many 2 factors.
  46. */
  47. #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1))))
  48. #define hashpointer(t,p) hashmod(t, IntPoint(p))
  49. /*
  50. ** number of ints inside a lua_Number
  51. */
  52. #define numints cast_int(sizeof(lua_Number)/sizeof(int))
  53. static const TValue* rotable_findentry(ROTable *rotable, TString *key, unsigned *ppos);
  54. static void rotable_next_helper(lua_State *L, ROTable *pentries, int pos,
  55. TValue *key, TValue *val);
  56. static void rotable_next(lua_State *L, ROTable *rotable, TValue *key, TValue *val);
  57. #define dummynode (&dummynode_)
  58. static const Node dummynode_ = {
  59. {LUA_TVALUE_NIL}, /* value */
  60. {LUA_TKEY_NIL} /* key */
  61. };
  62. /*
  63. ** hash for lua_Numbers
  64. */
  65. static Node *hashnum (const Table *t, lua_Number n) {
  66. unsigned int a[numints];
  67. int i;
  68. if (luai_numeq(n, 0)) /* avoid problems with -0 */
  69. return gnode(t, 0);
  70. memcpy(a, &n, sizeof(a));
  71. for (i = 1; i < numints; i++) a[0] += a[i];
  72. return hashmod(t, a[0]);
  73. }
  74. /*
  75. ** returns the `main' position of an element in a table (that is, the index
  76. ** of its hash value)
  77. */
  78. static Node *mainposition (const Table *t, const TValue *key) {
  79. switch (ttype(key)) {
  80. case LUA_TNUMBER:
  81. return hashnum(t, nvalue(key));
  82. case LUA_TSTRING:
  83. return hashstr(t, rawtsvalue(key));
  84. case LUA_TBOOLEAN:
  85. return hashboolean(t, bvalue(key));
  86. case LUA_TLIGHTUSERDATA:
  87. case LUA_TLIGHTFUNCTION:
  88. return hashpointer(t, pvalue(key));
  89. case LUA_TROTABLE:
  90. return hashpointer(t, hvalue(key));
  91. default:
  92. return hashpointer(t, gcvalue(key));
  93. }
  94. }
  95. /*
  96. ** returns the index for `key' if `key' is an appropriate key to live in
  97. ** the array part of the table, -1 otherwise.
  98. */
  99. static int arrayindex (const TValue *key) {
  100. if (ttisnumber(key)) {
  101. lua_Number n = nvalue(key);
  102. int k;
  103. lua_number2int(k, n);
  104. if (luai_numeq(cast_num(k), n))
  105. return k;
  106. }
  107. return -1; /* `key' did not match some condition */
  108. }
  109. /*
  110. ** returns the index of a `key' for table traversals. First goes all
  111. ** elements in the array part, then elements in the hash part. The
  112. ** beginning of a traversal is signalled by -1.
  113. */
  114. static int findindex (lua_State *L, Table *t, StkId key) {
  115. int i;
  116. if (ttisnil(key)) return -1; /* first iteration */
  117. i = arrayindex(key);
  118. if (0 < i && i <= t->sizearray) /* is `key' inside array part? */
  119. return i-1; /* yes; that's the index (corrected to C) */
  120. else {
  121. Node *n = mainposition(t, key);
  122. do { /* check whether `key' is somewhere in the chain */
  123. /* key may be dead already, but it is ok to use it in `next' */
  124. if (luaO_rawequalObj(key2tval(n), key) ||
  125. (ttype(gkey(n)) == LUA_TDEADKEY && iscollectable(key) &&
  126. gcvalue(gkey(n)) == gcvalue(key))) {
  127. i = cast_int(n - gnode(t, 0)); /* key index in hash table */
  128. /* hash elements are numbered after array ones */
  129. return i + t->sizearray;
  130. }
  131. else n = gnext(n);
  132. } while (n);
  133. luaG_runerror(L, "invalid key to " LUA_QL("next")); /* key not found */
  134. return 0; /* to avoid warnings */
  135. }
  136. }
  137. int luaH_next (lua_State *L, Table *t, StkId key) {
  138. int i;
  139. if (isrotable(t)) {
  140. rotable_next(L, (ROTable *) t, key, key+1);
  141. return ttisnil(key) ? 0 : 1;
  142. }
  143. i = findindex(L, t, key); /* find original element */
  144. for (i++; i < t->sizearray; i++) { /* try first array part */
  145. if (!ttisnil(&t->array[i])) { /* a non-nil value? */
  146. setnvalue(key, cast_num(i+1));
  147. setobj2s(L, key+1, &t->array[i]);
  148. return 1;
  149. }
  150. }
  151. for (i -= t->sizearray; i < sizenode(t); i++) { /* then hash part */
  152. if (!ttisnil(gval(gnode(t, i)))) { /* a non-nil value? */
  153. setobj2s(L, key, key2tval(gnode(t, i)));
  154. setobj2s(L, key+1, gval(gnode(t, i)));
  155. return 1;
  156. }
  157. }
  158. return 0; /* no more elements */
  159. }
  160. /*
  161. ** {=============================================================
  162. ** Rehash
  163. ** ==============================================================
  164. */
  165. static int computesizes (int nums[], int *narray) {
  166. int i;
  167. int twotoi; /* 2^i */
  168. int a = 0; /* number of elements smaller than 2^i */
  169. int na = 0; /* number of elements to go to array part */
  170. int n = 0; /* optimal size for array part */
  171. for (i = 0, twotoi = 1; twotoi/2 < *narray; i++, twotoi *= 2) {
  172. if (nums[i] > 0) {
  173. a += nums[i];
  174. if (a > twotoi/2) { /* more than half elements present? */
  175. n = twotoi; /* optimal size (till now) */
  176. na = a; /* all elements smaller than n will go to array part */
  177. }
  178. }
  179. if (a == *narray) break; /* all elements already counted */
  180. }
  181. *narray = n;
  182. lua_assert(*narray/2 <= na && na <= *narray);
  183. return na;
  184. }
  185. static int countint (const TValue *key, int *nums) {
  186. int k = arrayindex(key);
  187. if (0 < k && k <= MAXASIZE) { /* is `key' an appropriate array index? */
  188. nums[ceillog2(k)]++; /* count as such */
  189. return 1;
  190. }
  191. else
  192. return 0;
  193. }
  194. static int numusearray (const Table *t, int *nums) {
  195. int lg;
  196. int ttlg; /* 2^lg */
  197. int ause = 0; /* summation of `nums' */
  198. int i = 1; /* count to traverse all array keys */
  199. for (lg=0, ttlg=1; lg<=MAXBITS; lg++, ttlg*=2) { /* for each slice */
  200. int lc = 0; /* counter */
  201. int lim = ttlg;
  202. if (lim > t->sizearray) {
  203. lim = t->sizearray; /* adjust upper limit */
  204. if (i > lim)
  205. break; /* no more elements to count */
  206. }
  207. /* count elements in range (2^(lg-1), 2^lg] */
  208. for (; i <= lim; i++) {
  209. if (!ttisnil(&t->array[i-1]))
  210. lc++;
  211. }
  212. nums[lg] += lc;
  213. ause += lc;
  214. }
  215. return ause;
  216. }
  217. static int numusehash (const Table *t, int *nums, int *pnasize) {
  218. int totaluse = 0; /* total number of elements */
  219. int ause = 0; /* summation of `nums' */
  220. int i = sizenode(t);
  221. while (i--) {
  222. Node *n = &t->node[i];
  223. if (!ttisnil(gval(n))) {
  224. ause += countint(key2tval(n), nums);
  225. totaluse++;
  226. }
  227. }
  228. *pnasize += ause;
  229. return totaluse;
  230. }
  231. static void setarrayvector (lua_State *L, Table *t, int size) {
  232. int i;
  233. luaM_reallocvector(L, t->array, t->sizearray, size, TValue);
  234. for (i=t->sizearray; i<size; i++)
  235. setnilvalue(&t->array[i]);
  236. t->sizearray = size;
  237. }
  238. static Node *getfreepos (Table *t) {
  239. while (t->lastfree-- > t->node) {
  240. if (ttisnil(gkey(t->lastfree)))
  241. return t->lastfree;
  242. }
  243. return NULL; /* could not find a free place */
  244. }
  245. static void resizenodevector (lua_State *L, Table *t, int oldsize, int newsize) {
  246. int lsize;
  247. if (newsize == 0) { /* no elements to hash part? */
  248. t->node = cast(Node *, dummynode); /* use common `dummynode' */
  249. lsize = 0;
  250. }
  251. else {
  252. Node *node = t->node;
  253. int i;
  254. lsize = ceillog2(newsize);
  255. if (lsize > MAXBITS)
  256. luaG_runerror(L, "table overflow");
  257. newsize = twoto(lsize);
  258. if (node == dummynode) {
  259. oldsize = 0;
  260. node = NULL; /* don't try to realloc `dummynode' pointer. */
  261. }
  262. luaM_reallocvector(L, node, oldsize, newsize, Node);
  263. t->node = node;
  264. for (i=oldsize; i<newsize; i++) {
  265. Node *n = gnode(t, i);
  266. gnext(n) = NULL;
  267. setnilvalue(gkey(n));
  268. setnilvalue(gval(n));
  269. }
  270. }
  271. t->lsizenode = cast_byte(lsize);
  272. t->lastfree = gnode(t, newsize); /* reset lastfree to end of table. */
  273. }
  274. static Node *find_prev_node(Node *mp, Node *next) {
  275. Node *prev = mp;
  276. while (prev != NULL && gnext(prev) != next) prev = gnext(prev);
  277. return prev;
  278. }
  279. /*
  280. ** move a node from it's old position to it's new position during a rehash;
  281. ** first, check whether the moving node's main position is free. If not, check whether
  282. ** colliding node is in its main position or not: if it is not, move colliding
  283. ** node to an empty place and put moving node in its main position; otherwise
  284. ** (colliding node is in its main position), moving node goes to an empty position.
  285. */
  286. static int move_node (lua_State *L, Table *t, Node *node) {
  287. Node *mp = mainposition(t, key2tval(node));
  288. /* if node is in it's main position, don't need to move node. */
  289. if (mp == node) return 1;
  290. /* if node is in it's main position's chain, don't need to move node. */
  291. if (find_prev_node(mp, node) != NULL) return 1;
  292. /* is main position is free? */
  293. if (!ttisnil(gval(mp)) || mp == dummynode) {
  294. /* no; move main position node if it is out of its main position */
  295. Node *othermp;
  296. othermp = mainposition(t, key2tval(mp));
  297. if (othermp != mp) { /* is colliding node out of its main position? */
  298. /* yes; swap colliding node with the node that is being moved. */
  299. Node *prev;
  300. Node tmp;
  301. tmp = *node;
  302. prev = find_prev_node(othermp, mp); /* find previous */
  303. if (prev != NULL) gnext(prev) = node; /* redo the chain with `n' in place of `mp' */
  304. *node = *mp; /* copy colliding node into free pos. (mp->next also goes) */
  305. *mp = tmp;
  306. return (prev != NULL) ? 1 : 0; /* is colliding node part of its main position chain? */
  307. }
  308. else { /* colliding node is in its own main position */
  309. /* add node to main position's chain. */
  310. gnext(node) = gnext(mp); /* chain new position */
  311. gnext(mp) = node;
  312. }
  313. }
  314. else { /* main position is free, move node */
  315. *mp = *node;
  316. gnext(node) = NULL;
  317. setnilvalue(gkey(node));
  318. setnilvalue(gval(node));
  319. }
  320. return 1;
  321. }
  322. static int move_number (lua_State *L, Table *t, Node *node) {
  323. int key;
  324. lua_Number n = nvalue(key2tval(node));
  325. lua_number2int(key, n);
  326. if (luai_numeq(cast_num(key), nvalue(key2tval(node)))) {/* index is int? */
  327. /* (1 <= key && key <= t->sizearray) */
  328. if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray)) {
  329. setobjt2t(L, &t->array[key-1], gval(node));
  330. setnilvalue(gkey(node));
  331. setnilvalue(gval(node));
  332. return 1;
  333. }
  334. }
  335. return 0;
  336. }
  337. static void resize_hashpart (lua_State *L, Table *t, int nhsize) {
  338. int i;
  339. int lsize=0;
  340. int oldhsize = (t->node != dummynode) ? twoto(t->lsizenode) : 0;
  341. if (nhsize > 0) { /* round new hashpart size up to next power of two. */
  342. lsize=ceillog2(nhsize);
  343. if (lsize > MAXBITS)
  344. luaG_runerror(L, "table overflow");
  345. }
  346. nhsize = twoto(lsize);
  347. /* grow hash part to new size. */
  348. if (oldhsize < nhsize)
  349. resizenodevector(L, t, oldhsize, nhsize);
  350. else { /* hash part might be shrinking */
  351. if (nhsize > 0) {
  352. t->lsizenode = cast_byte(lsize);
  353. t->lastfree = gnode(t, nhsize); /* reset lastfree back to end of table. */
  354. }
  355. else { /* new hashpart size is zero. */
  356. resizenodevector(L, t, oldhsize, nhsize);
  357. return;
  358. }
  359. }
  360. /* break old chains, try moving int keys to array part and compact keys into new hashpart */
  361. for (i = 0; i < oldhsize; i++) {
  362. Node *old = gnode(t, i);
  363. gnext(old) = NULL;
  364. if (ttisnil(gval(old))) { /* clear nodes with nil values. */
  365. setnilvalue(gkey(old));
  366. continue;
  367. }
  368. if (ttisnumber(key2tval(old))) { /* try moving the int keys into array part. */
  369. if(move_number(L, t, old))
  370. continue;
  371. }
  372. if (i >= nhsize) { /* move all valid keys to indices < nhsize. */
  373. Node *n = getfreepos(t); /* get a free place */
  374. lua_assert(n != dummynode && n != NULL);
  375. *n = *old;
  376. }
  377. }
  378. /* shrink hash part */
  379. if (oldhsize > nhsize)
  380. resizenodevector(L, t, oldhsize, nhsize);
  381. /* move nodes to their new mainposition and re-create node chains */
  382. for (i = 0; i < nhsize; i++) {
  383. Node *curr = gnode(t, i);
  384. if (!ttisnil(gval(curr)))
  385. while (move_node(L, t, curr) == 0);
  386. }
  387. }
  388. static void resize (lua_State *L, Table *t, int nasize, int nhsize) {
  389. int i;
  390. int oldasize = t->sizearray;
  391. if (nasize > oldasize) /* array part must grow? */
  392. setarrayvector(L, t, nasize);
  393. if (t->node != dummynode || nhsize>0)
  394. resize_hashpart(L, t, nhsize);
  395. if (nasize < oldasize) { /* array part must shrink? */
  396. t->sizearray = nasize;
  397. /* re-insert elements from vanishing slice */
  398. for (i=nasize; i<oldasize; i++) {
  399. if (!ttisnil(&t->array[i]))
  400. setobjt2t(L, luaH_setnum(L, t, i+1), &t->array[i]);
  401. }
  402. /* shrink array */
  403. luaM_reallocvector(L, t->array, oldasize, nasize, TValue);
  404. }
  405. }
  406. void luaH_resizearray (lua_State *L, Table *t, int nasize) {
  407. int nsize = (t->node == dummynode) ? 0 : sizenode(t);
  408. resize(L, t, nasize, nsize);
  409. }
  410. static void rehash (lua_State *L, Table *t, const TValue *ek) {
  411. int nasize, na;
  412. int nums[MAXBITS+1]; /* nums[i] = number of keys between 2^(i-1) and 2^i */
  413. int i;
  414. int totaluse;
  415. for (i=0; i<=MAXBITS; i++) nums[i] = 0; /* reset counts */
  416. nasize = numusearray(t, nums); /* count keys in array part */
  417. totaluse = nasize; /* all those keys are integer keys */
  418. totaluse += numusehash(t, nums, &nasize); /* count keys in hash part */
  419. /* count extra key */
  420. nasize += countint(ek, nums);
  421. totaluse++;
  422. /* compute new size for array part */
  423. na = computesizes(nums, &nasize);
  424. /* resize the table to new computed sizes */
  425. resize(L, t, nasize, totaluse - na);
  426. }
  427. /*
  428. ** }=============================================================
  429. */
  430. Table *luaH_new (lua_State *L, int narray, int nhash) {
  431. Table *t = luaM_new(L, Table);
  432. luaC_link(L, obj2gco(t), LUA_TTABLE);
  433. sethvalue2s(L, L->top, t); /* put table on stack */
  434. incr_top(L);
  435. t->metatable = NULL;
  436. t->flags = cast_byte(~0);
  437. /* temporary values (kept only if some malloc fails) */
  438. t->array = NULL;
  439. t->sizearray = 0;
  440. t->lsizenode = 0;
  441. t->node = cast(Node *, dummynode);
  442. setarrayvector(L, t, narray);
  443. resizenodevector(L, t, 0, nhash);
  444. L->top--; /* remove table from stack */
  445. return t;
  446. }
  447. void luaH_free (lua_State *L, Table *t) {
  448. if (t->node != dummynode)
  449. luaM_freearray(L, t->node, sizenode(t), Node);
  450. luaM_freearray(L, t->array, t->sizearray, TValue);
  451. luaM_free(L, t);
  452. }
  453. /*
  454. ** inserts a new key into a hash table; first, check whether key's main
  455. ** position is free. If not, check whether colliding node is in its main
  456. ** position or not: if it is not, move colliding node to an empty place and
  457. ** put new key in its main position; otherwise (colliding node is in its main
  458. ** position), new key goes to an empty position.
  459. */
  460. static TValue *newkey (lua_State *L, Table *t, const TValue *key) {
  461. Node *mp = mainposition(t, key);
  462. if (!ttisnil(gval(mp)) || mp == dummynode) {
  463. Node *othern;
  464. Node *n = getfreepos(t); /* get a free place */
  465. if (n == NULL) { /* cannot find a free place? */
  466. rehash(L, t, key); /* grow table */
  467. return luaH_set(L, t, key); /* re-insert key into grown table */
  468. }
  469. lua_assert(n != dummynode);
  470. othern = mainposition(t, key2tval(mp));
  471. if (othern != mp) { /* is colliding node out of its main position? */
  472. /* yes; move colliding node into free position */
  473. while (gnext(othern) != mp) othern = gnext(othern); /* find previous */
  474. gnext(othern) = n; /* redo the chain with `n' in place of `mp' */
  475. *n = *mp; /* copy colliding node into free pos. (mp->next also goes) */
  476. gnext(mp) = NULL; /* now `mp' is free */
  477. setnilvalue(gval(mp));
  478. }
  479. else { /* colliding node is in its own main position */
  480. /* new node will go into free position */
  481. gnext(n) = gnext(mp); /* chain new position */
  482. gnext(mp) = n;
  483. mp = n;
  484. }
  485. }
  486. setobj2t(L, gkey(mp), key);
  487. luaC_barriert(L, t, key);
  488. lua_assert(ttisnil(gval(mp)));
  489. return gval(mp);
  490. }
  491. /*
  492. ** search function for integers
  493. */
  494. const TValue *luaH_getnum (Table *t, int key) {
  495. if (isrotable(t))
  496. return luaO_nilobject;
  497. /* (1 <= key && key <= t->sizearray) */
  498. if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray))
  499. return &t->array[key-1];
  500. else {
  501. lua_Number nk = cast_num(key);
  502. Node *n = hashnum(t, nk);
  503. do { /* check whether `key' is somewhere in the chain */
  504. if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)), nk))
  505. return gval(n); /* that's it */
  506. else n = gnext(n);
  507. } while (n);
  508. return luaO_nilobject;
  509. }
  510. }
  511. /*
  512. ** search function for strings
  513. */
  514. const TValue *luaH_getstr (Table *t, TString *key) {
  515. if (isrotable(t)) {
  516. if (key->tsv.len>LUA_MAX_ROTABLE_NAME)
  517. return luaO_nilobject;
  518. return rotable_findentry((ROTable*) t, key, NULL);
  519. }
  520. Node *n = hashstr(t, key);
  521. do { /* check whether `key' is somewhere in the chain */
  522. if (ttisstring(gkey(n)) && rawtsvalue(gkey(n)) == key)
  523. return gval(n); /* that's it */
  524. else n = gnext(n);
  525. } while (n);
  526. return luaO_nilobject;
  527. }
  528. /*
  529. ** main search function
  530. */
  531. const TValue *luaH_get (Table *t, const TValue *key) {
  532. int type = ttype(key);
  533. if (type == LUA_TNIL)
  534. return luaO_nilobject;
  535. if (type == LUA_TSTRING)
  536. return luaH_getstr(t, rawtsvalue(key));
  537. if (isrotable(t))
  538. return luaO_nilobject;
  539. if (type == LUA_TNUMBER) {
  540. int k;
  541. lua_Number n = nvalue(key);
  542. lua_number2int(k, n);
  543. if (luai_numeq(cast_num(k), nvalue(key))) /* index is int? */
  544. return luaH_getnum(t, k); /* use specialized version */
  545. }
  546. /* default */
  547. Node *n = mainposition(t, key);
  548. do { /* check whether `key' is somewhere in the chain */
  549. if (luaO_rawequalObj(key2tval(n), key))
  550. return gval(n); /* that's it */
  551. else n = gnext(n);
  552. } while (n);
  553. return luaO_nilobject;
  554. }
  555. TValue *luaH_set (lua_State *L, Table *t, const TValue *key) {
  556. const TValue *p;
  557. if (isrotable(t))
  558. luaG_runerror(L, "table is readonly");
  559. p = luaH_get(t, key);
  560. t->flags = 0;
  561. if (p != luaO_nilobject)
  562. return cast(TValue *, p);
  563. else {
  564. if (ttisnil(key)) luaG_runerror(L, "table index is nil");
  565. else if (ttisnumber(key) && luai_numisnan(nvalue(key)))
  566. luaG_runerror(L, "table index is NaN");
  567. return newkey(L, t, key);
  568. }
  569. }
  570. TValue *luaH_setnum (lua_State *L, Table *t, int key) {
  571. const TValue *p;
  572. if (isrotable(t))
  573. luaG_runerror(L, "table is readonly");
  574. p = luaH_getnum(t, key);
  575. if (p != luaO_nilobject)
  576. return cast(TValue *, p);
  577. else {
  578. TValue k;
  579. setnvalue(&k, cast_num(key));
  580. return newkey(L, t, &k);
  581. }
  582. }
  583. TValue *luaH_setstr (lua_State *L, Table *t, TString *key) {
  584. const TValue *p;
  585. if (isrotable(t))
  586. luaG_runerror(L, "table is readonly");
  587. p = luaH_getstr(t, key);
  588. if (p != luaO_nilobject)
  589. return cast(TValue *, p);
  590. else {
  591. TValue k;
  592. setsvalue(L, &k, key);
  593. return newkey(L, t, &k);
  594. }
  595. }
  596. static int unbound_search (Table *t, unsigned int j) {
  597. unsigned int i = j; /* i is zero or a present index */
  598. j++;
  599. /* find `i' and `j' such that i is present and j is not */
  600. while (!ttisnil(luaH_getnum(t, j))) {
  601. i = j;
  602. j *= 2;
  603. if (j > cast(unsigned int, MAX_INT)) { /* overflow? */
  604. /* table was built with bad purposes: resort to linear search */
  605. i = 1;
  606. while (!ttisnil(luaH_getnum(t, i))) i++;
  607. return i - 1;
  608. }
  609. }
  610. /* now do a binary search between them */
  611. while (j - i > 1) {
  612. unsigned int m = (i+j)/2;
  613. if (ttisnil(luaH_getnum(t, m))) j = m;
  614. else i = m;
  615. }
  616. return i;
  617. }
  618. /*
  619. ** Try to find a boundary in table `t'. A `boundary' is an integer index
  620. ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
  621. */
  622. int luaH_getn (Table *t) {
  623. unsigned int j;
  624. if(isrotable(t))
  625. return 0;
  626. j = t->sizearray;
  627. if (j > 0 && ttisnil(&t->array[j - 1])) {
  628. /* there is a boundary in the array part: (binary) search for it */
  629. unsigned int i = 0;
  630. while (j - i > 1) {
  631. unsigned int m = (i+j)/2;
  632. if (ttisnil(&t->array[m - 1])) j = m;
  633. else i = m;
  634. }
  635. return i;
  636. }
  637. /* else must find a boundary in hash part */
  638. else if (t->node == dummynode) /* hash part is empty? */
  639. return j; /* that is easy... */
  640. else return unbound_search(t, j);
  641. }
  642. int luaH_isdummy (Node *n) { return n == dummynode; }
  643. /*
  644. ** All keyed ROTable access passes through rotable_findentry(). ROTables
  645. ** are simply a list of <key><TValue value> pairs.
  646. **
  647. ** The global KeyCache is used to avoid a relatively expensive Flash memory
  648. ** vector scan. A simple hash on the key's TString addr and the ROTable
  649. ** addr selects the cache line. The line's slots are then scanned for a
  650. ** hit.
  651. **
  652. ** Unlike the standard hast which uses a prime line count therefore requires
  653. ** the use of modulus operation which is expensive on an IoT processor
  654. ** without H/W divide. This hash is power of 2 based which might not be
  655. ** quite so uniform but can be calcuated without using H/W-based instructions.
  656. **
  657. ** If a match is found and the table addresses match, then this entry is
  658. ** probed first. In practice the hit-rate here is over 99% so the code
  659. ** rarely fails back to doing the linear scan in ROM.
  660. ** Note that this hash does a couple of prime multiples and a modulus 2^X
  661. ** with is all evaluated in H/W, and adequately randomizes the lookup.
  662. */
  663. #define LA_LINES 32
  664. #define LA_SLOTS 4
  665. static size_t cache [LA_LINES][LA_SLOTS];
  666. #define HASH(a,b) ((((29*(size_t)(a)) ^ (37*((b)->tsv.hash)))>>4) % LA_LINES)
  667. #define NDX_SHFT 24
  668. #define ADDR_MASK (((size_t) 1<<24)-1)
  669. /*
  670. * Find a string key entry in a rotable and return it. Note that this internally
  671. * uses a null key to denote a metatable search.
  672. */
  673. static const TValue* rotable_findentry(ROTable *t, TString *key, unsigned *ppos) {
  674. const ROTable_entry *e = cast(const ROTable_entry *, t->entry);
  675. const int tl = getlsizenode(t);
  676. const char *strkey = getstr(key);
  677. size_t *cl = cache[HASH(t, key)];
  678. int i, j = 1, l;
  679. if (!e || gettt(key) != LUA_TSTRING)
  680. return luaO_nilobject;
  681. l = key->tsv.len;
  682. /* scan the ROTable lookaside cache and return if hit found */
  683. for (i=0; i<LA_SLOTS; i++) {
  684. int cl_ndx = cl[i] >> NDX_SHFT;
  685. if ((((size_t)t - cl[i]) & ADDR_MASK) == 0 && cl_ndx < tl &&
  686. strcmp(e[cl_ndx].key, strkey) == 0) {
  687. if (ppos)
  688. *ppos = cl_ndx;
  689. return &e[cl_ndx].value;
  690. }
  691. }
  692. /*
  693. * A lot of search misses are metavalues, but tables typically only have at
  694. * most a couple of them, so these are always put at the front of the table
  695. * in ascending order and the metavalue scan short circuits using a straight
  696. * strcmp()
  697. */
  698. lu_int32 name4 = *(lu_int32 *) strkey;
  699. if (*(char*)&name4 == '_') {
  700. for(i = 0; i < tl; i++) {
  701. j = strcmp(e[i].key, strkey);
  702. if (j>=0)
  703. break;
  704. }
  705. } else {
  706. /*
  707. * Ordinary (non-meta) keys can be unsorted. This is for legacy compatiblity,
  708. * plus misses are pretty rare in this case. The masked name4 comparison is
  709. * safe 4-byte comparison that nearly always avoids the more costly strcmp()
  710. * for an actual hit validation.
  711. */
  712. lu_int32 mask4 = l > 2 ? (~0u) : (~0u)>>((3-l)*8);
  713. for(i = 0; i < tl; i++) {
  714. if (((*(lu_int32 *)e[i].key ^ name4) & mask4) != 0)
  715. continue;
  716. j = strcmp(e[i].key, strkey);
  717. if (j==0)
  718. break;
  719. }
  720. }
  721. if (j)
  722. return luaO_nilobject;
  723. if (ppos)
  724. *ppos = i;
  725. /* In the case of a hit, update the lookaside cache */
  726. for (j = LA_SLOTS-1; j>0; j--)
  727. cl[j] = cl[j-1];
  728. cl[0] = ((size_t)t & ADDR_MASK) + (i << NDX_SHFT);
  729. return &e[i].value;
  730. }
  731. static void rotable_next_helper(lua_State *L, ROTable *t, int pos,
  732. TValue *key, TValue *val) {
  733. const ROTable_entry *e = cast(const ROTable_entry *, t->entry);
  734. if (pos < getlsizenode(t)) {
  735. /* Found an entry */
  736. setsvalue(L, key, luaS_new(L, e[pos].key));
  737. setobj2s(L, val, &e[pos].value);
  738. } else {
  739. setnilvalue(key);
  740. setnilvalue(val);
  741. }
  742. }
  743. /* next (used for iteration) */
  744. static void rotable_next(lua_State *L, ROTable *t, TValue *key, TValue *val) {
  745. unsigned keypos = getlsizenode(t);
  746. /* Special case: if key is nil, return the first element of the rotable */
  747. if (ttisnil(key))
  748. rotable_next_helper(L, t, 0, key, val);
  749. else if (ttisstring(key)) {
  750. /* Find the previous key again */
  751. if (ttisstring(key)) {
  752. rotable_findentry(t, rawtsvalue(key), &keypos);
  753. }
  754. /* Advance to next key */
  755. rotable_next_helper(L, t, ++keypos, key, val);
  756. }
  757. }
  758. #if defined(LUA_DEBUG)
  759. Node *luaH_mainposition (const Table *t, const TValue *key) {
  760. return mainposition(t, key);
  761. }
  762. #endif