data/textures/cobble.png

/*
** $Id: ltable.c,v 2.32.1.2 2007/12/28 15:32:23 roberto Exp $
** Lua tables (hash)
** See Copyright Notice in lua.h
*/


/*
** Implementation of tables (aka arrays, objects, or hash tables).
** Tables keep its elements in two parts: an array part and a hash part.
** Non-negative integer keys are all candidates to be kept in the array
** part. The actual size of the array is the largest `n' such that at
** least half the slots between 0 and n are in use.
** Hash uses a mix of chained scatter table with Brent's variation.
** A main invariant of these tables is that, if an element is not
** in its main position (i.e. the `original' position that its hash gives
** to it), then the colliding element is in its own main position.
** Hence even when the load factor reaches 100%, performance remains good.
*/

#include <math.h>
#include <string.h>

#define ltable_c
#define LUA_CORE

#include "lua.h"

#include "ldebug.h"
#include "ldo.h"
#include "lgc.h"
#include "lmem.h"
#include "lobject.h"
#include "lstate.h"
#include "ltable.h"


/*
** max size of array part is 2^MAXBITS
*/
#if LUAI_BITSINT > 26
#define MAXBITS		26
#else
#define MAXBITS		(LUAI_BITSINT-2)
#endif

#define MAXASIZE	(1 << MAXBITS)


#define hashpow2(t,n)      (gnode(t, lmod((n), sizenode(t))))
  
#define hashstr(t,str)  hashpow2(t, (str)->tsv.hash)
#define hashboolean(t,p)        hashpow2(t, p)


/*
** for some types, it is better to avoid modulus by power of 2, as
** they tend to have many 2 factors.
*/
#define hashmod(t,n)	(gnode(t, ((n) % ((sizenode(t)-1)|1))))


#define hashpointer(t,p)	hashmod(t, IntPoint(p))


/*
** number of ints inside a lua_Number
*/
#define numints		cast_int(sizeof(lua_Number)/sizeof(int))


#define dummynode		(&dummynode_)

static const Node dummynode_ = {
  {{NULL}, LUA_TNIL},  /* value */
  {{{NULL}, LUA_TNIL, NULL}}  /* key */
};


/*
** hash for lua_Numbers
*/
static Node *hashnum (const Table *t, lua_Number n) {
  unsigned int a[numints];
  int i;
  if (luai_numeq(n, 0))  /* avoid problems with -0 */
    return gnode(t, 0);
  memcpy(a, &n, sizeof(a));
  for (i = 1; i < numints; i++) a[0] += a[i];
  return hashmod(t, a[0]);
}


/*
** returns the `main' position of an element in a table (that is, the index
** of its hash value)
*/
static Node *mainposition (const Table *t, const TValue *key) {
  switch (ttype(key)) {
    case LUA_TNUMBER:
      return hashnum(t, nvalue(key));
    case LUA_TSTRING:
      return hashstr(t, rawtsvalue(key));
    case LUA_TBOOLEAN:
      return hashboolean(t, bvalue(key));
    case LUA_TLIGHTUSERDATA:
      return hashpointer(t, pvalue(key));
    default:
      return hashpointer(t, gcvalue(key));
  }
}


/*
** returns the index for `key' if `key' is an appropriate key to live in
** the array part of the table, -1 otherwise.
*/
static int arrayindex (const TValue *key) {
  if (ttisnumber(key)) {
    lua_Number n = nvalue(key);
    int k;
    lua_number2int(k, n);
    if (luai_numeq(cast_num(k), n))
      return k;
  }
  return -1;  /* `key' did not match some condition */
}


/*
** returns the index of a `key' for table traversals. First goes all
** elements in the array part, then elements in the hash part. The
** beginning of a traversal is signalled by -1.
*/
static int findindex (lua_State *L, Table *t, StkId key) {
  int i;
  if (ttisnil(key)) return -1;  /* first iteration */
  i = arrayindex(key);
  if (0 < i && i <= t->sizearray)  /* is `key' inside array part? */
    return i-1;  /* yes; that's the index (corrected to C) */
  else {
    Node *n = mainposition(t, key);
    do {  /* check whether `key' is somewhere in the chain */
      /* key may be dead already, but it is ok to use it in `next' */
      if (luaO_rawequalObj(key2tval(n), key) ||
            (ttype(gkey(n)) == LUA_TDEADKEY && iscollectable(key) &&
             gcvalue(gkey(n)) == gcvalue(key))) {
        i = cast_int(n - gnode(t, 0));  /* key index in hash table */
        /* hash elements are numbered after array ones */
        return i + t->sizearray;
      }
      else n = gnext(n);
    } while (n);
    luaG_runerror(L, "invalid key to " LUA_QL("next"));  /* key not found */
    return 0;  /* to avoid warnings */
  }
}


int luaH_next (lua_State *L, Table *t, StkId key) {
  int i = findindex(L, t, key);  /* find original element */
  for (i++; i < t->sizearray; i++) {  /* try first array part */
    if (!ttisnil(&t->array[i])) {  /* a non-nil value? */
      setnvalue(key, cast_num(i+1));
      setobj2s(L, key+1, &t->array[i]);
      return 1;
    }
  }
  for (i -= t->sizearray; i < sizenode(t); i++) {  /* then hash part */
    if (!ttisnil(gval(gnode(t, i)))) {  /* a non-nil value? */
      setobj2s(L, key, key2tval(gnode(t, i)));
      setobj2s(L, key+1, gval(gnode(t, i)));
      return 1;
    }
  }
  return 0;  /* no more elements */
}


/*
** {=============================================================
** Rehash
** ==============================================================
*/


static int computesizes (int nums[], int *narray) {
  int i;
  int twotoi;  /* 2^i */
  int a = 0;  /* number of elements smaller than 2^i */
  int na = 0;  /* number of elements to go to array part */
  int n = 0;  /* optimal size for array part */
  for (i = 0, twotoi = 1; twotoi/2 < *narray; i++, twotoi *= 2) {
    if (nums[i] > 0) {
      a += nums[i];
      if (a > twotoi/2) {  /* more than half elements present? */
ofs	hex dump	ascii
0000	89 50 4e 47 0d 0a 1a 0a 00 00 00 0d 49 48 44 52 00 00 00 10 00 00 00 10 08 02 00 00 00 90 91 68	.PNG........IHDR...............h
0020	36 00 00 00 03 73 42 49 54 08 08 08 db e1 4f e0 00 00 00 09 70 48 59 73 00 00 0e c4 00 00 0e c4	6....sBIT.....O.....pHYs........
0040	01 95 2b 0e 1b 00 00 02 e1 49 44 41 54 28 91 25 d0 4d 4b fa 70 00 00 e0 fd f6 e2 1b 6e ad b5 28	..+......IDAT(.%.MK.p.......n..(
0060	b7 e5 46 cc b1 83 25 43 e8 85 2e 15 78 ac 5b 97 e8 50 97 3e 40 dd ba 74 09 3a 05 9d 3b 0b 5d 3d	..F...%C....x.[..P.>@..t.:..;.]=
0080	85 a7 24 92 a5 90 24 cd 0c 2c a4 d2 1c 4d b4 46 1b 6d 43 dd ff f0 7f 3e c2 03 56 56 56 48 92 ac	..$...$..,...M.F.mC....>..VVVH..
00a0	d7 eb c3 e1 50 96 e5 e5 e5 e5 6a b5 ba ba ba 1a 8b c5 3a 9d 4e 3e 9f 37 0c 63 6b 6b cb f7 7d 51	....P.....j.......:.N>.7.ckk..}Q
00c0	14 1b 8d 06 38 3c 3c 5c 5c 5c ec f5 7a b6 6d 93 24 d9 ef f7 39 8e bb b8 b8 00 00 ec ed ed 99 a6	....8<<\\\..z.m.$...9...........
00e0	d9 ef f7 3f 3e 3e 52 a9 14 0c c3 a6 69 a2 be ef eb ba 3e 35 35 c5 30 4c b9 5c 16 04 21 1a 8d 4e	...?>>R.....i.....>55.0L.\..!..N
0100	4f 4f 93 24 f9 f5 f5 95 48 24 48 92 44 51 b4 d1 68 84 c3 e1 df df 5f 84 e7 79 45 51 34 4d eb f5	OO.$....H$H.DQ..h....._..yEQ4M..
0120	7a 92 24 01 00 82 c1 e0 cf cf 4f 28 14 6a 34 1a 2c cb 8e 8d 8d 05 83 41 1c c7 05 41 d0 34 0d 71	z.$.......O(.j4.,......A...A.4.q
0140	1c 47 92 a4 74 3a 5d 28 14 8a c5 a2 e3 38 8a a2 64 b3 d9 dd dd dd f7 f7 77 df f7 63 b1 18 04 41	.G..t:](.....8..d.......w..c...A
0160	bd 5e cf 30 0c 14 45 11 96 65 09 82 f0 7d 5f 92 24 45 51 4a a5 92 e7 79 aa aa f2 3c df 6e b7 55	.^.0..E..e...}_.$EQJ...y...<.n.U
0180	55 bd bc bc d4 34 6d 67 67 a7 dd 6e df dc dc a0 eb eb eb e9 74 da 34 cd e1 70 48 10 44 a1 50 f0	U....4mgg..n........t.4..pH.D.P.
01a0	7d 3f 1e 8f 87 c3 61 db b6 8f 8e 8e ba dd ee d9 d9 59 a5 52 01 00 1c 1f 1f a3 c9 64 52 d7 75 0c	}?....a..........Y.R.......dR.u.
01c0	c3 68 9a d6 75 3d 12 89 cc cd cd 0d 06 03 d3 34 33 99 8c 61 18 96 65 8d 46 a3 62 b1 18 8d 46 51	.h..u=.........43..a..e.F.b...FQ
01e0	14 45 d6 d6 d6 28 8a ea 74 3a a6 69 c6 e3 f1 a5 a5 a5 db db db 6e b7 cb 71 9c 28 8a 04 41 f0 3c	.E...(..t:.i.........n..q.(..A.<
0200	df e9 74 42 a1 90 2c cb 2f 2f 2f a8 ef fb 0c c3 60 18 e6 ba 6e 3e 9f bf be be 3e 3f 3f b7 6d db	..tB..,.///.....`...n>....>??.m.
0220	75 dd ab ab ab f1 f1 f1 99 99 99 c7 c7 c7 93 93 93 c1 60 30 3f 3f 0f 68 9a 0e 04 02 ae eb 62 18	u.................`0??.h......b.
0240	96 48 24 ba dd ee e9 e9 e9 d3 d3 93 e3 38 93 93 93 d5 6a 15 82 a0 56 ab 45 92 a4 ae eb fd 7e 1f	.H$..........8....j...V.E.....~.
0260	68 9a b6 b9 b9 79 70 70 20 08 c2 68 34 42 10 a4 56 ab bd be be e6 72 39 cf f3 b2 d9 2c 4d d3 04	h....ypp...h4B..V.....r9....,M..
0280	41 58 96 f5 3f 17 59 58 58 48 26 93 38 8e c3 30 8c e3 b8 aa aa 2c cb 42 10 b4 bd bd 4d 10 04 0c	AX..?.YXXH&.8..0.....,.B....M...
02a0	c3 00 80 4a a5 52 af d7 df de de 38 8e 43 44 51 54 55 b5 dd 6e 73 1c 17 89 44 58 96 2d 95 4a 8a	...J.R.....8.CDQTU..ns...DX.-.J.
02c0	a2 7c 7f 7f 97 cb e5 54 2a a5 69 1a 00 20 10 08 fc fd fd 11 04 81 4c 4c 4c d8 b6 bd b1 b1 61 18	.\|.....T*.i...........LLL.....a.
02e0	c6 fd fd bd 6d db b3 b3 b3 cf cf cf 96 65 3d 3c 3c 88 a2 28 cb 32 8e e3 b9 5c 8e a6 69 4d d3 90	....m........e=<<..(.2...\..iM..
0300	fd fd fd 66 b3 99 c9 64 28 8a 62 59 d6 30 8c bb bb bb 56 ab 45 51 d4 e7 e7 67 ad 56 f3 3c af d9	...f...d(.bY.0....V.EQ...g.V.<..
0320	6c 32 0c 63 18 86 69 9a ff 00 e7 ab 79 f4 08 69 75 28 00 00 00 00 49 45 4e 44 ae 42 60 82	l2.c..i.....y..iu(....IEND.B`.