/*
** $Id: ltable.c,v 2.31 2006/01/10 13:13:06 roberto Exp roberto $
** 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>
#include <stdio.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]; // 通常double类型的长度是int的2倍，所以numints = 2
  int i;
  n += 1;  /* normalize number (avoid -0) */
  lua_assert(sizeof(a) <= sizeof(n));

  // 将n的二进制数据复制到a数组中，n的二进制数据被分为了两个int数值
  memcpy(a, &n, sizeof(a));

  // 再将2个int数值相加，加起来
  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.
*/

/*
** 如果key是table的数组部分中的适当键，则返回key的索引，否则返回-1
*/

// 如果key是table的数组部分中的适当键，则返回key的索引，否则返回-1
static int arrayindex (const TValue *key) {
  if (ttisnumber(key)) {
    lua_Number n = nvalue(key);
    int k;
    lua_number2int(k, n); // 把Node.key的value域强转成int
    if (luai_numeq(cast_num(k), n)) // 再比对数值是否与强转之前相等
      return k;
    // 因为lua_Number对应的C基础类型是double，lua_Number类型的数值未必是个整数
  }
  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;
  // 实参key为nil值，返回-1，表示从table中的第一个元素开始迭代
  if (ttisnil(key)) return -1;  /* first iteration */

  i = arrayindex(key);
  if (0 < i && i <= t->sizearray)  /* is `key' inside array part? */
    // C数组部分的下标从0开始，比如tbl[1]是放在C array[0]的位置上，所以要-1
    return i - 1;  /* yes; that's the index (corrected to C) */
  else {
    // 在hash部分中，则先用key值算mainpos，然后顺着哈希冲突链往下找；key值可能已经在gc阶段里属于死亡状态，但是可以用在next()的逻辑里它依旧可以被使用
    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 `findindex' */
      // key可能是LUA_TDEADKEY类型，key依旧存在于Table所对应的内存块中，findindex()是基于内存位置去寻找的，
      // 所以在findindex()中还能找到对应的key，而luaH_next()会判断value是否为nil，为nil就继续基于内存布局往后找实际存在并有效的key-value
      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; // 外部调用要根据返回值的大小判定实参key对应的元素在array部分还是hash部分
      }
      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) {
  // table的array部分和hash部分是两段不同的内存块，findindex会找到目标key值在对应内存块中的index序号
  int i = findindex(L, t, key);  /* find original element */

  // 下面的2个for都是从key的位置开始，按内存布局的顺序，往后找第一个不为nil的元素，拷贝它的key-value值（TValue）到虚拟栈上

  // key在array部分的范围内，0 <= index序号 < sizearray
  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;
    }
  }
  // key在hash部分的范围内，0 <= index序号 < 2 ^ lsizenode
  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;
    }
  }
  // key的位置往后已经没有不为nil的元素
  return 0;  /* no more elements */
}


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

static int computesizes (int nums[], int *narray) {
  int i; // 遍历nums时使用的下标
  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];

      // 这里需要开启一下脑内的幻想，twotoi是一块呈2倍增长的区域，a是当前统计的累计数
      // 如果当前统计的累计数a > twotoi所代表的那块区域的一半
      // 那么就调整一下未来array part的大小（= twotoi）
      // 目的是为了避免空间浪费，让未来的array part至少一半的空间都被使用
      if (a > twotoi/2) {  /* more than half elements present? */
        n = twotoi;  /* optimal size (till now) */
        na = a;  /* all elements smaller than n will go to array part */
      }

      // 如果tbl内只有几个key，但这些key都是数值较大的整数，代码会如何执行？
      // 大概率n、na = 0，数组部分空间为0

      // 如果tbl内一个整数都没有，代码如何执行？
      // 会无法进入for循环，数组部分空间为0，因为for那层有 twotoi/2 < *narray 的限制，
    }
    if (a == *narray) break;  /* all elements already counted */
  }

  // 所以，新的数组大小确定后（特殊情形，可能是0），数组部分一半以上的空间都会被占用
  // 最终目标就是让new array part，空间利用率 >= 50%
  *narray = n;
  lua_assert(*narray/2 <= na && na <= *narray);
  return na;
}


static int countint (const TValue *key, int *nums) {
  // 检查key的value域是一个整数，若不是整数，返回-1，若是，返回整数值
  int k = arrayindex(key);
  // 检查k是否在合法的正整数范围内
  if (0 < k && k <= MAXASIZE) {  /* is `key' an appropriate array index? */
    // ceillog2(k)用于计算出k在( 2^(i-1), 2^i ] 的哪个细分区间上，然后计数
    nums[ceillog2(k)]++;  /* count as such */
    return 1;
  }
  else
    return 0;
}


static int numusearray (const Table *t, int *nums) {
  int lg;
  int ttlg;  /* 2^lg */
  int ause = 0;  /* summation of `nums' */
  int i = 1;  /* count to traverse all array keys (i等同于array的下标，要遍历整个array部分，它是统计区间的头部index)*/
  for (lg=0, ttlg=1; lg<=MAXBITS; lg++, ttlg*=2) {  /* for each slice */
    int lc = 0;  /* counter */

    // lim相当于目前统计区间的尾部index，限制其 <= t->sizearray
    int lim = ttlg;
    if (lim > t->sizearray) {
      lim = t->sizearray;  /* adjust upper limit */
      if (i > lim)
        break;  /* no more elements to count */
    }

    /* count elements in range (2^(lg-1), 2^lg] */
    for (; i <= lim; i++) {
      if (!ttisnil(&t->array[i-1])) // 取数组部分上的各个元素（TValue），判断其类型不为nil就增加计数
        lc++;
    }

    nums[lg] += lc;
    ause += lc;
  }
  return ause; // return 数组部分的总使用计数
}


static int numusehash (const Table *t, int *nums, int *pnasize) {
  int totaluse = 0;  /* total number of elements */
  int ause = 0;  /* summation of `nums' */

  // 遍历tbl的哈希部分
  int i = sizenode(t);
  while (i--) {
    // Node的value不为nil则加入计数
    Node *n = &t->node[i];
    if (!ttisnil(gval(n))) {
      // 检查Node的key是否为正整数，若是，并入nums的计数
      ause += countint(key2tval(n), nums);

      totaluse++;
    }
  }
  *pnasize += ause;
  return totaluse;
}


static void setarrayvector (lua_State *L, Table *t, int size) {
  int i;
  luaM_reallocvector(L, t->array, t->sizearray, size, TValue);
  for (i=t->sizearray; i<size; i++)
     setnilvalue(&t->array[i]);
  t->sizearray = size;
}


static void setnodevector (lua_State *L, Table *t, int size) {
  int lsize;
  if (size == 0) {  /* no elements to hash part? */
    t->node = cast(Node *, dummynode);  /* use common `dummynode' */
    lsize = 0;
  }
  else {
    int i;

    // size不变 或 增大、缩小至2的次方
    lsize = ceillog2(size);
    if (lsize > MAXBITS)
      luaG_runerror(L, "table overflow");
    size = twoto(lsize);
    // printf("hashsize = %d \n", size);

    // 不同于array，如果要调整hash部分的大小，必定重新另申请一块内存块，然后对它进行置nil初始化
    t->node = luaM_newvector(L, size, Node);
    for (i=0; i<size; i++) {
      Node *n = gnode(t, i);
      gnext(n) = NULL;
      setnilvalue(gkey(n));
      setnilvalue(gval(n));
    }
  }

  t->lsizenode = cast_byte(lsize);
  // lastfree指针移动到内存块最右边
  t->lastfree = gnode(t, size);  /* all positions are free */
}


static void resize (lua_State *L, Table *t, int nasize, int nhsize) {
  int i;
  int oldasize = t->sizearray;
  int oldhsize = t->lsizenode;
  Node *nold = t->node;  /* save old hash ... */

  // 数组部分增大，很好处理，在原来的内存块尾部追加空间即可
  if (nasize > oldasize)  /* array part must grow? */
    setarrayvector(L, t, nasize);

  /* create new hash part with appropriate size */
  // 直接释放掉旧的hash部分，或申请新的hash内存区域
  setnodevector(L, t, nhsize);

  // 数组部分减小，减小的差集区域里，如果有不为nil的key-value对，则需要把它扔到hash部分中
  if (nasize < oldasize) {  /* array part must shrink? */
    t->sizearray = nasize;
    /* re-insert elements from vanishing slice */
    for (i=nasize; i<oldasize; i++) {
      if (!ttisnil(&t->array[i]))
        setobjt2t(L, luaH_setnum(L, t, i+1), &t->array[i]);
    }

    /* shrink array */
    // 收缩array part，lua默认的内存分配函数是realloc()，它其实并不需要用到oldasize
    luaM_reallocvector(L, t->array, oldasize, nasize, TValue);
  }

  /* re-insert elements from hash part */
  // 将原hash部分中不为nil的key-value对，重新hash到新的内存块中
  for (i = twoto(oldhsize) - 1; i >= 0; i--) {
    Node *old = nold+i;
    if (!ttisnil(gval(old)))
      setobjt2t(L, luaH_set(L, t, key2tval(old)), gval(old));
  }

  // 释放原先hash部分所对应的内存块
  if (nold != dummynode)
    luaM_freearray(L, nold, twoto(oldhsize), Node);  /* free old array */
}


void luaH_resizearray (lua_State *L, Table *t, int nasize) {
  int nsize = (t->node == dummynode) ? 0 : sizenode(t);
  resize(L, t, nasize, nsize);
}


// ek为触发rehash的，新插入的key值，const修饰，禁止通过ek修改源实例
static void rehash (lua_State *L, Table *t, const TValue *ek) {
  int nasize, na; // nasize = 可以被放到array部分的key计数

  // nums作为后续resize table数组部分的依据，统计的是table里的key值
  // 每个nums[i]都是一个计数，表示key值在区间( 2^(i-1), 2^i ]范围内的key值个数
  int nums[MAXBITS+1];  /* nums[i] = number of keys between 2^(i-1) and 2^i */
  int i;
  int totaluse;
  for (i=0; i<=MAXBITS; i++) nums[i] = 0;  /* reset counts */

  // 统计数组部分中目前仍有效的key-value，将key值的区间计数结果注入到nums
  nasize = numusearray(t, nums);  /* count keys in array part */
  totaluse = nasize;  /* all those keys are integer keys */

  // 返回hash部分中目前仍有效的Node个数，并对nums和nasize作注入修改（如果key为正整数，则可以纳入nums和nasize的计数中）
  totaluse += numusehash(t, nums, &nasize);  /* count keys in hash part */

  /* count extra key */
  // 检查新插入的key的value域是否为整数，是否需要并入nums的计数中
  nasize += countint(ek, nums);
  totaluse++;

  // 截止到目前
  // nasize = 原array + hash部分，有多少个元素是正整数
  // nums = 这些正整数的数值分布
  // totaluse = 原array + hash部分，不为nil的元素总数

  /* compute new size for array part */
  // 根据nums，计算出合适的new array part大小
  // nasize会被修改为：new array part的大小
  // na被赋值为：会有多少个元素被放到new array part
  na = computesizes(nums, &nasize);

  /* resize the table to new computed sizes */
  // (totaluse - na)新的hash part会有多少个元素

  // printf("rehash run nasize=%d hashsize=%d ", nasize, totaluse - na);
  resize(L, t, nasize, totaluse - na);
}



/*
** }=============================================================
*/

// 创建新的lua table，array部分和hash部分的初始大小由外部传入
Table *luaH_new (lua_State *L, int narray, int nhash) {
  Table *t = luaM_new(L, Table);
  luaC_link(L, obj2gco(t), LUA_TTABLE);
  t->metatable = NULL;
  t->flags = cast_byte(~0); // ~0是将0按位取反，即所有位上都为1
  /* temporary values (kept only if some malloc fails) */
  t->array = NULL;
  t->sizearray = 0;
  t->lsizenode = 0;
  t->node = cast(Node *, dummynode);
  setarrayvector(L, t, narray); // narray直接作为数组部分的槽位数
  setnodevector(L, t, nhash); // hash部分的槽位数必定 >= nhash
  return t;
}


void luaH_free (lua_State *L, Table *t) {
  if (t->node != dummynode)
    luaM_freearray(L, t->node, sizenode(t), Node);
  luaM_freearray(L, t->array, t->sizearray, TValue);
  luaM_free(L, t);
}


static Node *getfreepos (Table *t) {
  while (t->lastfree-- > t->node) {
    if (ttisnil(gkey(t->lastfree)))
      return t->lastfree;
  }
  return NULL;  /* could not find a free place */
}



/*
** inserts a new key into a hash table; first, check whether key's main 
** position is free. If not, check whether colliding node is in its main 
** position or not: if it is not, move colliding node to an empty place and 
** put new key in its main position; otherwise (colliding node is in its main 
** position), new key goes to an empty position. 
*/

/*
** 将一个key插入哈希部分; 首先，检查 key值 -> hash值 索引到的mainpos（Node）是否空闲，空闲则直接用这个Node；
** 
** 若不空闲，转而计算冲突Node的mainpos，如果冲突Node的mainpos表明它本就该放在这个位置，
** 那么它们属于同一个哈希值下的哈希冲突，将新插入的key-value扔到freepos
** 
** 若冲突Node的mainpos表明该Node本不该放在这个位置上，那么意味着冲突Node，
** 是在插入时发生了hash冲突，才被放到这个位置上的，所以应该将冲突Node挪到freepos，
** 并调整前缀Node的next指针，最后将新插入key-value放到空出来的位置上（它本该放在这里）
*/
static TValue *newkey (lua_State *L, Table *t, const TValue *key) {
  // 根据key值计算mainpos，得到mainpos对应的Node
  Node *mp = mainposition(t, key);
  // mp的value域非nil 或 mp是dummynode（table的hash部分未构建）
  if (!ttisnil(gval(mp)) || mp == dummynode) { 
    Node *othern;

    // 尝试找到一个空闲Node，找不到就rehash，rehash后肯定有合适的位置了
    Node *n = getfreepos(t);  /* get a free place */
    if (n == NULL) {  /* cannot find a free place? */
      rehash(L, t, key);  /* grow table */
      return luaH_set(L, t, key);  /* re-insert key into grown table */
    }

    // 断言n不是虚拟Node
    lua_assert(n != dummynode);

    // mp为占用了mainpos的key-value，转而计算它的mainpos
    othern = mainposition(t, key2tval(mp));
    // 冲突的key-value，它本来不该被放在这里？
    if (othern != mp) {  /* is colliding node out of its main position? */
      // 那就把colliding node扔到freepos，尽可能地让所有的key-value放在它们的mainpos里，这样后续索引的时候会更快
      /* yes; move colliding node into free position */

      // colliding node不在它的mainpos上，说明colliding node是因为hash冲突才被挪到现在这个位置上的
      // 那么othern为哈希冲突链的头节点，顺着它往下找，找colliding node的前缀节点
      while (gnext(othern) != mp) othern = gnext(othern);  /* find previous */

      // 令前缀节点的next指向free pos
      gnext(othern) = n;  /* redo the chain with `n' in place of `mp' */
      // colliding node 的内容copy到free pos
      *n = *mp;  /* copy colliding node into free pos. (mp->next also goes) */

      // Node mp就空了出来，清理一下它的next指针和value域
      gnext(mp) = NULL;  /* now `mp' is free */
      setnilvalue(gval(mp));
    }
    else {  /* colliding node is in its own main position */
    // 冲突的key-value，它在自己的mainpos里
      // 那就得把新的key-value扔到freepos里了
      /* new node will go into free position */

      // 把free pos链到colliding node后面就行了，不需要链到冲突链的末尾，反正由next链出来的所有节点都是属于这个hash冲突的
      gnext(n) = gnext(mp);  /* chain new position */
      gnext(mp) = n;
      mp = n;
    }
  }

  // mp为新key的插入目标Node，key域赋值
  gkey(mp)->value = key->value; gkey(mp)->tt = key->tt;
  // gc相关操作
  luaC_barriert(L, t, key);
  // 断言Node的value域为nil
  lua_assert(ttisnil(gval(mp)));
  // 返回Node的value域指针
  return gval(mp);
}


/*
** search function for integers
*/
const TValue *luaH_getnum (Table *t, int key) {
  /* (1 <= key && key <= t->sizearray) */
  if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray))
    return &t->array[key-1];
    // 如果key是个负数，会不会执行到这一分支？应该是不会的，那么为什么？

    // 首先回看一下c++关于unsigned的笔记
    // 然后这里的情况是 int key, int t->sizearray
    // 在key和sizearray都趋近于MAX int的数值时，key-1可以让判断正确通过

    // int key = 0时，unsigned int (key-1)，其数值会变为MAX int + 1，因为int首个符号位的1被当做了数值，
    // 那么在这种情况下，MAX int + 1 < MAX int是不可能成立的，所以会执行else分支，key是越来越小的负数时，
    // 推论也是如此

    // 当int key = MIN int时，key-1，二进制表示由`1000 0000 0000 0000 0000 0000 0000 0000`
    // 变为`0111 1111 1111 1111 1111 1111 1111 1111`，key-1 = MAX int
    // 那么MAX int < MAX int也是不可能成立的，会执行else分支

    // 所以 key <= 0 时，不可能执行到这一分支，官方注释是正确的
  else {
    lua_Number nk = cast_num(key);
    Node *n = hashnum(t, nk);
    do {  /* check whether `key' is somewhere in the chain */
      if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)), nk))
        return gval(n);  /* that's it */
      else n = gnext(n);
    } while (n);
    return luaO_nilobject;
  }
}


/*
** search function for strings
*/
const TValue *luaH_getstr (Table *t, TString *key) {
  Node *n = hashstr(t, key);
  do {  /* check whether `key' is somewhere in the chain */
    if (ttisstring(gkey(n)) && rawtsvalue(gkey(n)) == key)
      return gval(n);  /* that's it */
    else n = gnext(n);
  } while (n);
  return luaO_nilobject;
}


/*
** main search function
*/
const TValue *luaH_get (Table *t, const TValue *key) {
  switch (ttype(key)) {
    case LUA_TNIL: return luaO_nilobject;
    case LUA_TSTRING: return luaH_getstr(t, rawtsvalue(key));
    case LUA_TNUMBER: {
      int k;
      lua_Number n = nvalue(key);
      lua_number2int(k, n);
      if (luai_numeq(cast_num(k), nvalue(key))) /* index is int? */
        return luaH_getnum(t, k);  /* use specialized version */
      /* else go through */
    }
    default: {
      Node *n = mainposition(t, key);
      do {  /* check whether `key' is somewhere in the chain */
        if (luaO_rawequalObj(key2tval(n), key))
          return gval(n);  /* that's it */
        else n = gnext(n);
      } while (n);
      return luaO_nilobject;
    }
  }
}


TValue *luaH_set (lua_State *L, Table *t, const TValue *key) {
  const TValue *p = luaH_get(t, key);
  t->flags = 0; // flags缓存重置
  // “Node的key部分 == TValue *key”的Node，是否在t中实际存在？
  if (p != luaO_nilobject)
    return cast(TValue *, p); // 找得到，update操作，返回(TValue *) Node.value 供外部调用修改
  else {
    if (ttisnil(key)) // key值是nil，t[nil] = -22，这种lua语句会报错
      luaG_runerror(L, "table index is nil");
    else if (ttisnumber(key) && luai_numisnan(nvalue(key))) // 检查key值是nan，nan会在把0当成除数时生成（Not A Numbewr），t[NaN] = -22，这种lua语句会报错
      luaG_runerror(L, "table index is NaN");
    return newkey(L, t, key); // 找不到，insert操作，table增加新的key-value
  }
}


TValue *luaH_setnum (lua_State *L, Table *t, int key) {
  const TValue *p = luaH_getnum(t, key);
  if (p != luaO_nilobject)
    return cast(TValue *, p);
  else {
    TValue k;
    setnvalue(&k, cast_num(key));
    return newkey(L, t, &k);
  }
}


TValue *luaH_setstr (lua_State *L, Table *t, TString *key) {
  const TValue *p = luaH_getstr(t, key);
  if (p != luaO_nilobject)
    return cast(TValue *, p);
  else {
    TValue k;
    setsvalue(L, &k, key);
    return newkey(L, t, &k);
  }
}

// 在table的hash部分查找
static int unbound_search (Table *t, unsigned int j) {
  unsigned int i = j;  /* i is zero or a present index */
  j++;

  /* find `i' and `j' such that i is present and j is not */
  // 找到符合 (t[i] ~= nil) and (j == nil) 的i和j，目的是确定一个大概的范围
  while (!ttisnil(luaH_getnum(t, j))) {
    // 2倍增长
    i = j;
    j *= 2;

    if (j > cast(unsigned int, MAX_INT)) {  /* overflow? */
      /* table was built with bad purposes: resort to linear search */
      // j已经超过整数上限，表构建得不够好，回归线性查找，从下标1开始找table中的第一个nil值
      i = 1;
      while (!ttisnil(luaH_getnum(t, i))) i++;
      return i - 1;
    }
  }

  /* now do a binary search between them */
  // 在i和j之间以二分形式查找边界
  while (j - i > 1) {
    unsigned int m = (i+j)/2;
    if (ttisnil(luaH_getnum(t, m))) j = m;
    else i = m;
  }

  return i;
}


/*
** Try to find a boundary in table `t'. A `boundary' is an integer index
** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
** 
** 尝试在table t中查找边界，boundary是一个整数索引，
** 使得t[i]不是nil，t[i+1]是nil（如果t[1]是nil，则为0）
*/
int luaH_getn (Table *t) {
  unsigned int j = t->sizearray;
  // arraysize > 0 且 array部分的最后一个元素为nil，意味着table的array部分没被塞满，
  // 而且boundary在array部分中，采用二分方式查找它
  if (j > 0 && ttisnil(&t->array[j - 1])) {
    /* there is a boundary in the array part: (binary) search for it */
    unsigned int i = 0;
    while (j - i > 1) {
      unsigned int m = (i+j)/2;
      if (ttisnil(&t->array[m - 1]))
        j = m;
      else
        i = m;
    }
    return i;
  }
  /* else must find a boundary in hash part */
  else if (t->node == dummynode)  /* hash part is empty? */
    // ((arraysize <= 0 或 array部分的最后一个元素不为nil) 且 table没有hash部分)，那么sizearray就是table的长度
    return j;  /* that is easy... */
  else
    // 转而去table的hash部分查找符合条件的t[i]
    return unbound_search(t, j);
}



#if defined(LUA_DEBUG)

Node *luaH_mainposition (const Table *t, const TValue *key) {
  return mainposition(t, key);
}

int luaH_isdummy (Node *n) { return n == dummynode; }

#endif