ltable.c 25 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841
  1. /*
  2. ** $Id: ltable.c,v 2.118.1.4 2018/06/08 16:22:51 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 <string.h>
  24. #include "lua.h"
  25. #include "ldebug.h"
  26. #include "ldo.h"
  27. #include "lgc.h"
  28. #include "lmem.h"
  29. #include "lobject.h"
  30. #include "lstate.h"
  31. #include "lstring.h"
  32. #include "ltable.h"
  33. #include "lvm.h"
  34. /*
  35. ** Maximum size of array part (MAXASIZE) is 2^MAXABITS. MAXABITS is
  36. ** the largest integer such that MAXASIZE fits in an unsigned int.
  37. */
  38. #define MAXABITS cast_int(sizeof(int) * CHAR_BIT - 1)
  39. #define MAXASIZE (1u << MAXABITS)
  40. /*
  41. ** Maximum size of hash part is 2^MAXHBITS. MAXHBITS is the largest
  42. ** integer such that 2^MAXHBITS fits in a signed int. (Note that the
  43. ** maximum number of elements in a table, 2^MAXABITS + 2^MAXHBITS, still
  44. ** fits comfortably in an unsigned int.)
  45. */
  46. #define MAXHBITS (MAXABITS - 1)
  47. #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t))))
  48. #define hashstr(t,str) hashpow2(t, (str)->hash)
  49. #define hashboolean(t,p) hashpow2(t, p)
  50. #define hashint(t,i) hashpow2(t, i)
  51. /*
  52. ** for some types, it is better to avoid modulus by power of 2, as
  53. ** they tend to have many 2 factors.
  54. */
  55. #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1))))
  56. #define hashpointer(t,p) hashmod(t, point2uint(p))
  57. #define dummynode (&dummynode_)
  58. static const Node dummynode_ = {
  59. {NILCONSTANT}, /* value */
  60. {{NILCONSTANT, 0}} /* key */
  61. };
  62. /*
  63. ** Hash for floating-point numbers.
  64. ** The main computation should be just
  65. ** n = frexp(n, &i); return (n * INT_MAX) + i
  66. ** but there are some numerical subtleties.
  67. ** In a two-complement representation, INT_MAX does not has an exact
  68. ** representation as a float, but INT_MIN does; because the absolute
  69. ** value of 'frexp' is smaller than 1 (unless 'n' is inf/NaN), the
  70. ** absolute value of the product 'frexp * -INT_MIN' is smaller or equal
  71. ** to INT_MAX. Next, the use of 'unsigned int' avoids overflows when
  72. ** adding 'i'; the use of '~u' (instead of '-u') avoids problems with
  73. ** INT_MIN.
  74. */
  75. #if !defined(l_hashfloat)
  76. static int l_hashfloat (lua_Number n) {
  77. int i;
  78. lua_Integer ni;
  79. n = l_mathop(frexp)(n, &i) * -cast_num(INT_MIN);
  80. if (!lua_numbertointeger(n, &ni)) { /* is 'n' inf/-inf/NaN? */
  81. lua_assert(luai_numisnan(n) || l_mathop(fabs)(n) == cast_num(HUGE_VAL));
  82. return 0;
  83. }
  84. else { /* normal case */
  85. unsigned int u = cast(unsigned int, i) + cast(unsigned int, ni);
  86. return cast_int(u <= cast(unsigned int, INT_MAX) ? u : ~u);
  87. }
  88. }
  89. #endif
  90. /*
  91. ** returns the 'main' position of an element in a table (that is, the index
  92. ** of its hash value)
  93. */
  94. static Node *mainposition (const Table *t, const TValue *key) {
  95. switch (ttype(key)) {
  96. case LUA_TNUMINT:
  97. return hashint(t, ivalue(key));
  98. case LUA_TNUMFLT:
  99. return hashmod(t, l_hashfloat(fltvalue(key)));
  100. case LUA_TSHRSTR:
  101. return hashstr(t, tsvalue(key));
  102. case LUA_TLNGSTR:
  103. return hashpow2(t, luaS_hashlongstr(tsvalue(key)));
  104. case LUA_TBOOLEAN:
  105. return hashboolean(t, bvalue(key));
  106. case LUA_TLIGHTUSERDATA:
  107. return hashpointer(t, pvalue(key));
  108. case LUA_TLCF:
  109. return hashpointer(t, fvalue(key));
  110. default:
  111. lua_assert(!ttisdeadkey(key));
  112. return hashpointer(t, gcvalue(key));
  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, 0 otherwise.
  118. */
  119. static unsigned int arrayindex (const TValue *key) {
  120. if (ttisinteger(key)) {
  121. lua_Integer k = ivalue(key);
  122. if (0 < k && (lua_Unsigned)k <= MAXASIZE)
  123. return cast(unsigned int, k); /* 'key' is an appropriate array index */
  124. }
  125. return 0; /* 'key' did not match some condition */
  126. }
  127. /*
  128. ** returns the index of a 'key' for table traversals. First goes all
  129. ** elements in the array part, then elements in the hash part. The
  130. ** beginning of a traversal is signaled by 0.
  131. */
  132. static unsigned int findindex (lua_State *L, Table *t, StkId key) {
  133. unsigned int i;
  134. if (ttisnil(key)) return 0; /* first iteration */
  135. i = arrayindex(key);
  136. if (i != 0 && i <= t->sizearray) /* is 'key' inside array part? */
  137. return i; /* yes; that's the index */
  138. else {
  139. int nx;
  140. Node *n = mainposition(t, key);
  141. for (;;) { /* check whether 'key' is somewhere in the chain */
  142. /* key may be dead already, but it is ok to use it in 'next' */
  143. if (luaV_rawequalobj(gkey(n), key) ||
  144. (ttisdeadkey(gkey(n)) && iscollectable(key) &&
  145. deadvalue(gkey(n)) == gcvalue(key))) {
  146. i = cast_int(n - gnode(t, 0)); /* key index in hash table */
  147. /* hash elements are numbered after array ones */
  148. return (i + 1) + t->sizearray;
  149. }
  150. nx = gnext(n);
  151. if (nx == 0)
  152. luaG_runerror(L, "invalid key to 'next'"); /* key not found */
  153. else n += nx;
  154. }
  155. }
  156. }
  157. static void rotable_next(lua_State *L, ROTable *t, TValue *key, TValue *val);
  158. int luaH_next (lua_State *L, Table *t, StkId key) {
  159. unsigned int i;
  160. if (isrotable(t)) {
  161. rotable_next(L, (ROTable *) t, key, key+1);
  162. return ttisnil(key) ? 0 : 1;
  163. }
  164. i = findindex(L, t, key); /* find original element */
  165. for (; i < t->sizearray; i++) { /* try first array part */
  166. if (!ttisnil(&t->array[i])) { /* a non-nil value? */
  167. setivalue(key, i + 1);
  168. setobj2s(L, key+1, &t->array[i]);
  169. return 1;
  170. }
  171. }
  172. for (i -= t->sizearray; cast_int(i) < sizenode(t); i++) { /* hash part */
  173. if (!ttisnil(gval(gnode(t, i)))) { /* a non-nil value? */
  174. setobj2s(L, key, gkey(gnode(t, i)));
  175. setobj2s(L, key+1, gval(gnode(t, i)));
  176. return 1;
  177. }
  178. }
  179. return 0; /* no more elements */
  180. }
  181. /*
  182. ** {=============================================================
  183. ** Rehash
  184. ** ==============================================================
  185. */
  186. /*
  187. ** Compute the optimal size for the array part of table 't'. 'nums' is a
  188. ** "count array" where 'nums[i]' is the number of integers in the table
  189. ** between 2^(i - 1) + 1 and 2^i. 'pna' enters with the total number of
  190. ** integer keys in the table and leaves with the number of keys that
  191. ** will go to the array part; return the optimal size.
  192. */
  193. static unsigned int computesizes (unsigned int nums[], unsigned int *pna) {
  194. int i;
  195. unsigned int twotoi; /* 2^i (candidate for optimal size) */
  196. unsigned int a = 0; /* number of elements smaller than 2^i */
  197. unsigned int na = 0; /* number of elements to go to array part */
  198. unsigned int optimal = 0; /* optimal size for array part */
  199. /* loop while keys can fill more than half of total size */
  200. for (i = 0, twotoi = 1;
  201. twotoi > 0 && *pna > twotoi / 2;
  202. i++, twotoi *= 2) {
  203. if (nums[i] > 0) {
  204. a += nums[i];
  205. if (a > twotoi/2) { /* more than half elements present? */
  206. optimal = twotoi; /* optimal size (till now) */
  207. na = a; /* all elements up to 'optimal' will go to array part */
  208. }
  209. }
  210. }
  211. lua_assert((optimal == 0 || optimal / 2 < na) && na <= optimal);
  212. *pna = na;
  213. return optimal;
  214. }
  215. static int countint (const TValue *key, unsigned int *nums) {
  216. unsigned int k = arrayindex(key);
  217. if (k != 0) { /* is 'key' an appropriate array index? */
  218. nums[luaO_ceillog2(k)]++; /* count as such */
  219. return 1;
  220. }
  221. else
  222. return 0;
  223. }
  224. /*
  225. ** Count keys in array part of table 't': Fill 'nums[i]' with
  226. ** number of keys that will go into corresponding slice and return
  227. ** total number of non-nil keys.
  228. */
  229. static unsigned int numusearray (const Table *t, unsigned int *nums) {
  230. int lg;
  231. unsigned int ttlg; /* 2^lg */
  232. unsigned int ause = 0; /* summation of 'nums' */
  233. unsigned int i = 1; /* count to traverse all array keys */
  234. /* traverse each slice */
  235. for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) {
  236. unsigned int lc = 0; /* counter */
  237. unsigned int lim = ttlg;
  238. if (lim > t->sizearray) {
  239. lim = t->sizearray; /* adjust upper limit */
  240. if (i > lim)
  241. break; /* no more elements to count */
  242. }
  243. /* count elements in range (2^(lg - 1), 2^lg] */
  244. for (; i <= lim; i++) {
  245. if (!ttisnil(&t->array[i-1]))
  246. lc++;
  247. }
  248. nums[lg] += lc;
  249. ause += lc;
  250. }
  251. return ause;
  252. }
  253. static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) {
  254. int totaluse = 0; /* total number of elements */
  255. int ause = 0; /* elements added to 'nums' (can go to array part) */
  256. int i = sizenode(t);
  257. while (i--) {
  258. Node *n = &t->node[i];
  259. if (!ttisnil(gval(n))) {
  260. ause += countint(gkey(n), nums);
  261. totaluse++;
  262. }
  263. }
  264. *pna += ause;
  265. return totaluse;
  266. }
  267. static void setarrayvector (lua_State *L, Table *t, unsigned int size) {
  268. unsigned int i;
  269. luaM_reallocvector(L, t->array, t->sizearray, size, TValue);
  270. for (i=t->sizearray; i<size; i++)
  271. setnilvalue(&t->array[i]);
  272. t->sizearray = size;
  273. }
  274. static void setnodevector (lua_State *L, Table *t, unsigned int size) {
  275. if (size == 0) { /* no elements to hash part? */
  276. t->node = cast(Node *, dummynode); /* use common 'dummynode' */
  277. t->lsizenode = 0;
  278. t->lastfree = NULL; /* signal that it is using dummy node */
  279. }
  280. else {
  281. int i;
  282. int lsize = luaO_ceillog2(size);
  283. if (lsize > MAXHBITS)
  284. luaG_runerror(L, "table overflow");
  285. size = twoto(lsize);
  286. t->node = luaM_newvector(L, size, Node);
  287. for (i = 0; i < (int)size; i++) {
  288. Node *n = gnode(t, i);
  289. gnext(n) = 0;
  290. setnilvalue(wgkey(n));
  291. setnilvalue(gval(n));
  292. }
  293. t->lsizenode = cast_byte(lsize);
  294. t->lastfree = gnode(t, size); /* all positions are free */
  295. }
  296. }
  297. typedef struct {
  298. Table *t;
  299. unsigned int nhsize;
  300. } AuxsetnodeT;
  301. static void auxsetnode (lua_State *L, void *ud) {
  302. AuxsetnodeT *asn = cast(AuxsetnodeT *, ud);
  303. setnodevector(L, asn->t, asn->nhsize);
  304. }
  305. void luaH_resize (lua_State *L, Table *t, unsigned int nasize,
  306. unsigned int nhsize) {
  307. unsigned int i;
  308. int j;
  309. AuxsetnodeT asn;
  310. unsigned int oldasize = t->sizearray;
  311. int oldhsize = allocsizenode(t);
  312. Node *nold = t->node; /* save old hash ... */
  313. if (nasize > oldasize) /* array part must grow? */
  314. setarrayvector(L, t, nasize);
  315. /* create new hash part with appropriate size */
  316. asn.t = t; asn.nhsize = nhsize;
  317. if (luaD_rawrunprotected(L, auxsetnode, &asn) != LUA_OK) { /* mem. error? */
  318. setarrayvector(L, t, oldasize); /* array back to its original size */
  319. luaD_throw(L, LUA_ERRMEM); /* rethrow memory error */
  320. }
  321. if (nasize < oldasize) { /* array part must shrink? */
  322. t->sizearray = nasize;
  323. /* re-insert elements from vanishing slice */
  324. for (i=nasize; i<oldasize; i++) {
  325. if (!ttisnil(&t->array[i]))
  326. luaH_setint(L, t, i + 1, &t->array[i]);
  327. }
  328. /* shrink array */
  329. luaM_reallocvector(L, t->array, oldasize, nasize, TValue);
  330. }
  331. /* re-insert elements from hash part */
  332. for (j = oldhsize - 1; j >= 0; j--) {
  333. Node *old = nold + j;
  334. if (!ttisnil(gval(old))) {
  335. /* doesn't need barrier/invalidate cache, as entry was
  336. already present in the table */
  337. setobjt2t(L, luaH_set(L, t, gkey(old)), gval(old));
  338. }
  339. }
  340. if (oldhsize > 0) /* not the dummy node? */
  341. luaM_freearray(L, nold, cast(size_t, oldhsize)); /* free old hash */
  342. }
  343. void luaH_resizearray (lua_State *L, Table *t, unsigned int nasize) {
  344. int nsize = allocsizenode(t);
  345. luaH_resize(L, t, nasize, nsize);
  346. }
  347. /*
  348. ** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i
  349. */
  350. static void rehash (lua_State *L, Table *t, const TValue *ek) {
  351. unsigned int asize; /* optimal size for array part */
  352. unsigned int na; /* number of keys in the array part */
  353. unsigned int nums[MAXABITS + 1];
  354. int i;
  355. int totaluse;
  356. for (i = 0; i <= MAXABITS; i++) nums[i] = 0; /* reset counts */
  357. na = numusearray(t, nums); /* count keys in array part */
  358. totaluse = na; /* all those keys are integer keys */
  359. totaluse += numusehash(t, nums, &na); /* count keys in hash part */
  360. /* count extra key */
  361. na += countint(ek, nums);
  362. totaluse++;
  363. /* compute new size for array part */
  364. asize = computesizes(nums, &na);
  365. /* resize the table to new computed sizes */
  366. luaH_resize(L, t, asize, totaluse - na);
  367. }
  368. /*
  369. ** }=============================================================
  370. */
  371. Table *luaH_new (lua_State *L) {
  372. GCObject *o = luaC_newobj(L, LUA_TTABLE, sizeof(Table));
  373. Table *t = gco2t(o);
  374. t->metatable = NULL;
  375. t->flags = cast_byte(~0);
  376. t->array = NULL;
  377. t->sizearray = 0;
  378. setnodevector(L, t, 0);
  379. return t;
  380. }
  381. void luaH_free (lua_State *L, Table *t) {
  382. if (!isdummy(t))
  383. luaM_freearray(L, t->node, cast(size_t, sizenode(t)));
  384. luaM_freearray(L, t->array, t->sizearray);
  385. luaM_free(L, t);
  386. }
  387. static Node *getfreepos (Table *t) {
  388. if (!isdummy(t)) {
  389. while (t->lastfree > t->node) {
  390. t->lastfree--;
  391. if (ttisnil(gkey(t->lastfree)))
  392. return t->lastfree;
  393. }
  394. }
  395. return NULL; /* could not find a free place */
  396. }
  397. /*
  398. ** inserts a new key into a hash table; first, check whether key's main
  399. ** position is free. If not, check whether colliding node is in its main
  400. ** position or not: if it is not, move colliding node to an empty place and
  401. ** put new key in its main position; otherwise (colliding node is in its main
  402. ** position), new key goes to an empty position.
  403. */
  404. TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {
  405. Node *mp;
  406. TValue aux;
  407. if(!isrwtable(t)) luaG_runerror(L, "table is Readonly");
  408. if (ttisnil(key)) luaG_runerror(L, "table index is nil");
  409. else if (ttisfloat(key)) {
  410. lua_Integer k;
  411. if (luaV_tointeger(key, &k, 0)) { /* does index fit in an integer? */
  412. setivalue(&aux, k);
  413. key = &aux; /* insert it as an integer */
  414. }
  415. else if (luai_numisnan(fltvalue(key)))
  416. luaG_runerror(L, "table index is NaN");
  417. }
  418. mp = mainposition(t, key);
  419. if (!ttisnil(gval(mp)) || isdummy(t)) { /* main position is taken? */
  420. Node *othern;
  421. Node *f = getfreepos(t); /* get a free place */
  422. if (f == NULL) { /* cannot find a free place? */
  423. rehash(L, t, key); /* grow table */
  424. /* whatever called 'newkey' takes care of TM cache */
  425. return luaH_set(L, t, key); /* insert key into grown table */
  426. }
  427. lua_assert(!isdummy(t));
  428. othern = mainposition(t, gkey(mp));
  429. if (othern != mp) { /* is colliding node out of its main position? */
  430. /* yes; move colliding node into free position */
  431. while (othern + gnext(othern) != mp) /* find previous */
  432. othern += gnext(othern);
  433. gnext(othern) = cast_int(f - othern); /* rechain to point to 'f' */
  434. *f = *mp; /* copy colliding node into free pos. (mp->next also goes) */
  435. if (gnext(mp) != 0) {
  436. gnext(f) += cast_int(mp - f); /* correct 'next' */
  437. gnext(mp) = 0; /* now 'mp' is free */
  438. }
  439. setnilvalue(gval(mp));
  440. }
  441. else { /* colliding node is in its own main position */
  442. /* new node will go into free position */
  443. if (gnext(mp) != 0)
  444. gnext(f) = cast_int((mp + gnext(mp)) - f); /* chain new position */
  445. else lua_assert(gnext(f) == 0);
  446. gnext(mp) = cast_int(f - mp);
  447. mp = f;
  448. }
  449. }
  450. setnodekey(L, &mp->i_key, key);
  451. luaC_barrierback(L, t, key);
  452. lua_assert(ttisnil(gval(mp)));
  453. return gval(mp);
  454. }
  455. /*
  456. ** search function for integers
  457. */
  458. const TValue *luaH_getint (Table *t, lua_Integer key) {
  459. if (isrotable(t))
  460. return luaO_nilobject;
  461. /* (1 <= key && key <= t->sizearray) */
  462. if (l_castS2U(key) - 1 < t->sizearray)
  463. return &t->array[key - 1];
  464. else {
  465. Node *n = hashint(t, key);
  466. for (;;) { /* check whether 'key' is somewhere in the chain */
  467. if (ttisinteger(gkey(n)) && ivalue(gkey(n)) == key)
  468. return gval(n); /* that's it */
  469. else {
  470. int nx = gnext(n);
  471. if (nx == 0) break;
  472. n += nx;
  473. }
  474. }
  475. return luaO_nilobject;
  476. }
  477. }
  478. /*
  479. ** search function for short strings
  480. */
  481. static const TValue* rotable_findentry(ROTable *rotable, TString *key, unsigned *ppos);
  482. const TValue *luaH_getshortstr (Table *t, TString *key) {
  483. Node *n;
  484. if (isrotable(t))
  485. return rotable_findentry((ROTable*) t, key, NULL);
  486. n = hashstr(t, key);
  487. lua_assert(gettt(key) == LUA_TSHRSTR);
  488. for (;;) { /* check whether 'key' is somewhere in the chain */
  489. const TValue *k = gkey(n);
  490. if (ttisshrstring(k) && eqshrstr(tsvalue(k), key))
  491. return gval(n); /* that's it */
  492. else {
  493. int nx = gnext(n);
  494. if (nx == 0)
  495. return luaO_nilobject; /* not found */
  496. n += nx;
  497. }
  498. }
  499. }
  500. /*
  501. ** "Generic" get version. (Not that generic: not valid for integers,
  502. ** which may be in array part, nor for floats with integral values.)
  503. */
  504. static const TValue *getgeneric (Table *t, const TValue *key) {
  505. Node *n;
  506. if (isrotable(t))
  507. return luaO_nilobject;
  508. n = mainposition(t, key);
  509. for (;;) { /* check whether 'key' is somewhere in the chain */
  510. if (luaV_rawequalobj(gkey(n), key))
  511. return gval(n); /* that's it */
  512. else {
  513. int nx = gnext(n);
  514. if (nx == 0)
  515. return luaO_nilobject; /* not found */
  516. n += nx;
  517. }
  518. }
  519. }
  520. const TValue *luaH_getstr (Table *t, TString *key) {
  521. if (gettt(key) == LUA_TSHRSTR)
  522. return luaH_getshortstr(t, key);
  523. else { /* for long strings, use generic case */
  524. TValue ko;
  525. setsvalue(cast(lua_State *, NULL), &ko, key);
  526. return getgeneric(t, &ko);
  527. }
  528. }
  529. /*
  530. ** main search function
  531. */
  532. const TValue *luaH_get (Table *t, const TValue *key) {
  533. switch (ttype(key)) {
  534. case LUA_TSHRSTR: return luaH_getshortstr(t, tsvalue(key));
  535. case LUA_TNUMINT: return luaH_getint(t, ivalue(key));
  536. case LUA_TNIL: return luaO_nilobject;
  537. case LUA_TNUMFLT: {
  538. lua_Integer k;
  539. if (luaV_tointeger(key, &k, 0)) /* index is int? */
  540. return luaH_getint(t, k); /* use specialized version */
  541. /* else... */
  542. } /* FALLTHROUGH */
  543. default:
  544. return getgeneric(t, key);
  545. }
  546. }
  547. /*
  548. ** beware: when using this function you probably need to check a GC
  549. ** barrier and invalidate the TM cache.
  550. */
  551. TValue *luaH_set (lua_State *L, Table *t, const TValue *key) {
  552. const TValue *p;
  553. if (isrotable(t))
  554. luaG_runerror(L, "table is readonly");
  555. p = luaH_get(t, key);
  556. if (p != luaO_nilobject)
  557. return cast(TValue *, p);
  558. else return luaH_newkey(L, t, key);
  559. }
  560. void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) {
  561. const TValue *p;
  562. if (isrotable(t))
  563. luaG_runerror(L, "table is readonly");
  564. p = luaH_getint(t, key);
  565. TValue *cell;
  566. if (p != luaO_nilobject)
  567. cell = cast(TValue *, p);
  568. else {
  569. TValue k;
  570. setivalue(&k, key);
  571. cell = luaH_newkey(L, t, &k);
  572. }
  573. setobj2t(L, cell, value);
  574. }
  575. static lua_Unsigned unbound_search (Table *t, lua_Unsigned j) {
  576. lua_Unsigned i = j; /* i is zero or a present index */
  577. j++;
  578. /* find 'i' and 'j' such that i is present and j is not */
  579. while (!ttisnil(luaH_getint(t, j))) {
  580. i = j;
  581. if (j > l_castS2U(LUA_MAXINTEGER) / 2) { /* overflow? */
  582. /* table was built with bad purposes: resort to linear search */
  583. i = 1;
  584. while (!ttisnil(luaH_getint(t, i))) i++;
  585. return i - 1;
  586. }
  587. j *= 2;
  588. }
  589. /* now do a binary search between them */
  590. while (j - i > 1) {
  591. lua_Unsigned m = (i+j)/2;
  592. if (ttisnil(luaH_getint(t, m))) j = m;
  593. else i = m;
  594. }
  595. return i;
  596. }
  597. /*
  598. ** Try to find a boundary in table 't'. A 'boundary' is an integer index
  599. ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
  600. */
  601. lua_Unsigned luaH_getn (Table *t) {
  602. unsigned int j;
  603. if (isrotable(t))
  604. return 0;
  605. j = t->sizearray;
  606. if (j > 0 && ttisnil(&t->array[j - 1])) {
  607. /* there is a boundary in the array part: (binary) search for it */
  608. unsigned int i = 0;
  609. while (j - i > 1) {
  610. unsigned int m = (i+j)/2;
  611. if (ttisnil(&t->array[m - 1])) j = m;
  612. else i = m;
  613. }
  614. return i;
  615. }
  616. /* else must find a boundary in hash part */
  617. else if (isdummy(t)) /* hash part is empty? */
  618. return j; /* that is easy... */
  619. else return unbound_search(t, j);
  620. }
  621. int luaH_isdummy (const Table *t) { return isdummy(t); }
  622. /*
  623. ** All keyed ROTable access passes through rotable_findentry(). ROTables
  624. ** are simply a list of <key><TValue value> pairs.
  625. **
  626. ** The global KeyCache is used to avoid a relatively expensive Flash memory
  627. ** vector scan. A simple hash on the key's TString addr and the ROTable
  628. ** addr selects the cache line. The line's slots are then scanned for a
  629. ** hit.
  630. **
  631. ** Unlike the standard hash which uses a prime line count therefore requires
  632. ** the use of modulus operation which is expensive on an IoT processor
  633. ** without H/W divide. This hash is power of 2 based which might not be quite
  634. ** so uniform but can be calculated without using H/W-based instructions.
  635. **
  636. ** If a match is found and the table addresses match, then this entry is
  637. ** probed first. In practice the hit-rate here is over 99% so the code
  638. ** rarely fails back to doing the linear scan in ROM.
  639. ** Note that this hash does a couple of prime multiples and a modulus 2^X
  640. ** with is all evaluated in H/W, and adequately randomizes the lookup.
  641. */
  642. #define HASH(a,b) ((((29*(size_t)(a)) ^ (37*((b)->hash)))>>4)&(KEYCACHE_N-1))
  643. #define NDX_SHFT 24
  644. #define ADDR_MASK (((size_t) 1<<24)-1)
  645. /*
  646. * Find a string key entry in a rotable and return it.
  647. */
  648. static const TValue* rotable_findentry(ROTable *t, TString *key, unsigned *ppos) {
  649. const ROTable_entry *e = cast(const ROTable_entry *, t->entry);
  650. const int tl = getlsizenode(t);
  651. const char *strkey = getstr(key);
  652. const int hash = HASH(t, key);
  653. KeyCache *cl = luaE_getcache(hash);
  654. int i, j = 1, l;
  655. if (!e || gettt(key) != LUA_TSHRSTR)
  656. return luaO_nilobject;
  657. l = getshrlen(key);
  658. /* scan the ROTable key cache and return if hit found */
  659. for (i = 0; i < KEYCACHE_M; i++) {
  660. int cl_ndx = cl[i] >> NDX_SHFT;
  661. if ((((size_t)t - cl[i]) & ADDR_MASK) == 0 && cl_ndx < tl &&
  662. strcmp(e[cl_ndx].key, strkey) == 0) {
  663. if (ppos)
  664. *ppos = cl_ndx;
  665. return &e[cl_ndx].value;
  666. }
  667. }
  668. /*
  669. * In practice most table scans are from a table miss due to the key cache
  670. * short-circuiting almost all table hits. ROTable keys can be unsorted
  671. * because of legacy compatibility, so the search must use a sequential
  672. * equality match.
  673. *
  674. * The masked name4 comparison is a safe 4-byte comparison for all supported
  675. * NodeMCU hosts and targets; It generate fast efficient access that avoids
  676. * unaligned exceptions and costly strcmp() except for a last hit validation.
  677. * However, this is ENDIAN SENSITIVE which is validate during initialisation.
  678. *
  679. * The majority of search misses are for metavalues (keys starting with __),
  680. * so all metavalues if any must be at the front of each entry list.
  681. */
  682. lu_int32 name4 = *(lu_int32 *)strkey;
  683. lu_int32 mask4 = l > 2 ? (~0u) : (~0u)>>((3-l)*8);
  684. lua_assert(*(int*)"abcd" == 0x64636261);
  685. #define eq4(s) (((*(lu_int32 *)s ^ name4) & mask4) == 0)
  686. #define ismeta(s) ((*(lu_int32 *)s & 0xffff) == *(lu_int32 *)"__\0")
  687. if (ismeta(&name4)) {
  688. for(i = 0; i < tl && ismeta(e[i].key); i++) {
  689. if (eq4(e[i].key) && !strcmp(e[i].key, strkey)) {
  690. j = 0; break;
  691. }
  692. }
  693. } else {
  694. for(i = 0; i < tl; i++) {
  695. if (eq4(e[i].key) && !strcmp(e[i].key, strkey)) {
  696. j = 0; break;
  697. }
  698. }
  699. }
  700. if (j)
  701. return luaO_nilobject;
  702. if (ppos)
  703. *ppos = i;
  704. /* In the case of a hit, update the lookaside cache */
  705. for (j = KEYCACHE_M-1; j>0; j--)
  706. cl[j] = cl[j-1];
  707. cl[0] = ((size_t)t & ADDR_MASK) + (i << NDX_SHFT);
  708. return &e[i].value;
  709. }
  710. static void rotable_next_helper(lua_State *L, ROTable *t, int pos,
  711. TValue *key, TValue *val) {
  712. const ROTable_entry *e = cast(const ROTable_entry *, t->entry);
  713. if (pos < getlsizenode(t)) {
  714. /* Found an entry */
  715. setsvalue(L, key, luaS_new(L, e[pos].key));
  716. setobj2s(L, val, &e[pos].value);
  717. } else {
  718. setnilvalue(key);
  719. setnilvalue(val);
  720. }
  721. }
  722. /* next (used for iteration) */
  723. static void rotable_next(lua_State *L, ROTable *t, TValue *key, TValue *val) {
  724. unsigned keypos = getlsizenode(t);
  725. /* Special case: if key is nil, return the first element of the rotable */
  726. if (ttisnil(key))
  727. rotable_next_helper(L, t, 0, key, val);
  728. else if (ttisstring(key)) {
  729. /* Find the previous key again */
  730. if (ttisstring(key)) {
  731. rotable_findentry(t, tsvalue(key), &keypos);
  732. }
  733. /* Advance to next key */
  734. rotable_next_helper(L, t, ++keypos, key, val);
  735. }
  736. }
  737. #if defined(LUA_DEBUG)
  738. Node *luaH_mainposition (const Table *t, const TValue *key) {
  739. return mainposition(t, key);
  740. }
  741. #endif