/*
** clear collected entries from weaktables
*/
static void cleartable (GCObject *l) {
  while (l) {
    Table *h = gco2h(l);
    int i = h->sizearray;
    lua_assert(testbit(h->marked, VALUEWEAKBIT) ||
               testbit(h->marked, KEYWEAKBIT));
    if (testbit(h->marked, VALUEWEAKBIT)) {
      while (i--) {
        TValue *o = &h->array[i];
        if (iscleared(o, 0))  /* value was collected? */
          setnilvalue(o);  /* remove value */
      }
    }
    i = sizenode(h);
    while (i--) {
      Node *n = gnode(h, i);
      if (!ttisnil(gval(n)) &&  /* non-empty entry? */
          (iscleared(key2tval(n), 1) || iscleared(gval(n), 0))) {
        setnilvalue(gval(n));  /* remove value ... */
        removeentry(n);  /* remove entry from table */
      }
    }
    l = h->gclist;
  }
}

LUA_API int lua_getn (lua_State *L, int index) {
  StkId t;
  const TValue *value;
  int n;
  lua_lock(L);
  t = index2adr(L, index);
  api_check(L, ttype(t) == LUA_TTABLE);
  value = luaH_getstr(hvalue(t), luaS_newliteral(L, "n"));  /* = t.n */
  if (ttype(value) == LUA_TNUMBER) {
    n = (int)value;
  } else {
    Node *nd;
    Table *a = hvalue(t);
    lua_Number max = 0;
    int i;
    i = a->sizearray;
    while (i--) {
      if (ttype(&a->array[i]) != LUA_TNIL)
        break;
    }
    max = i+1;
    i = sizenode(a);
    nd = a->node;
    while (i--) {
      if (ttype(gkey(nd)) == LUA_TNUMBER &&
          ttype(gval(nd)) != LUA_TNIL &&
          nvalue(gkey(nd)) > max)
        max = nvalue(gkey(nd));
      nd++;
    }
    lua_number2int(n, max);
  }
  lua_unlock(L);
  return n;
}

int debug_getsize(lua_State* L)
{
  TValue* o = L->base;
  switch (o->tt) {
    /* Container types */
    case LUA_TTABLE: {
      Table *h = hvalue(o);
      lua_pushinteger(L, sizeof(Table) + sizeof(TValue) * h->sizearray +
                             sizeof(Node) * sizenode(h));
      break;
    }
    case LUA_TFUNCTION: {
      Closure *cl = clvalue(o);
      lua_pushinteger(L, (cl->c.isC) ? sizeCclosure(cl->c.nupvalues) :
                           sizeLclosure(cl->l.nupvalues));
      break;
    }
    case LUA_TTHREAD: {
      lua_State *th = thvalue(o);
      lua_pushinteger(L, sizeof(lua_State) + sizeof(TValue) * th->stacksize +
                                 sizeof(CallInfo) * th->size_ci);
      break;
    }
    case LUA_TPROTO: {
      Proto *p = pvalue(o);
      lua_pushinteger(L, sizeof(Proto) + sizeof(Instruction) * p->sizecode +
                             sizeof(Proto *) * p->sizep +
                             sizeof(TValue) * p->sizek + 
                             sizeof(int) * p->sizelineinfo +
                             sizeof(LocVar) * p->sizelocvars +
                             sizeof(TString *) * p->sizeupvalues);
     break;
    }
    /* Non-containers */
    case LUA_TUSERDATA: {
      lua_pushnumber(L, uvalue(o)->len);
      break;
    }
    case LUA_TLIGHTUSERDATA: {
      lua_pushnumber(L, sizeof(void*));
      break;
    }
    case LUA_TSTRING: {
      TString *s = rawtsvalue(o);
      lua_pushinteger(L, sizeof(TString) + s->tsv.len + 1);
      break;
    }
    case LUA_TNUMBER: {
      lua_pushinteger(L, sizeof(lua_Number));
      break;
    }
    case LUA_TBOOLEAN: {
      lua_pushinteger(L, sizeof(int));
      break;
    }
    default: return 0;
  }
  return 1;
}

static const char *travglobals (lua_State *L, const TObject *o) {
  Table *g = hvalue(gt(L));
  int i = sizenode(g);
  while (i--) {
    Node *n = gnode(g, i);
    if (luaO_rawequalObj(o, gval(n)) && ttisstring(gkey(n)))
      return getstr(tsvalue(gkey(n)));
  }
  return NULL;
}

void fleece_size_hash_part (insp_ctrl *ctrl, const Table *t, size_t *count, int *pure) {

  int i = sizenode(t);
  while (i--) {
	Node *node = &t->node[i];
	if(!ttisnil(key2tval(node)) && !ttisnil(gval(node))) {
		FLEECE_SIZE(ctrl, (const TValue *)key2tval(node));
		FLEECE_SIZE(ctrl, (const TValue *)gval(node));
		ctrl->total_len += 2; // : , or (rsp closing bracket!)
	}
  } 
}

/*
** clear collected keys from weaktables
*/
static void cleartablekeys (lua_State *L, GCObject *l) {
  while (l) {
    Table *h = gcotoh(l);
    int i = sizenode(h);
    lua_assert(h->marked & KEYWEAK);
    while (i--) {
      Node *n = gnode(h, i);
      if (!valismarked(gkey(n)))  /* key was collected? */
        removekey(L, n);  /* remove entry from table */
    }
    l = h->gclist;
  }
}

static int numusehash (const Table *t, int *nums, int *pnasize) {
    int totaluse = 0;  /* total number of elements */
    int ause = 0;  /* summation of `nums' */
    int i = sizenode(t);
    while (i--) {
        Node *n = &t->node[i];
        if (!ttisnil(gval(n))) {
            ause += countint(key2tval(n), nums);
            totaluse++;
        }
    }
    *pnasize += ause;
    return totaluse;
}

static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) {
  int totaluse = 0;  /* total number of elements */
  int ause = 0;  /* elements added to 'nums' (can go to array part) */
  int i = sizenode(t);
  while (i--) {
    Node *n = &t->node[i];
    if (!isempty(gval(n))) {
      if (keyisinteger(n))
        ause += countint(keyival(n), nums);
      totaluse++;
    }
  }
  *pna += ause;
  return totaluse;
}

int lvH_next (lv_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 */
}

/*
** traverse one gray object, turning it to black.
** Returns `quantity' traversed.
*/
static l_mem propagatemark (global_State *g) {
  GCObject *o = g->gray;
  lua_assert(isgray(o));
  gray2black(o);
  switch (o->gch.tt) {
    case LUA_TTABLE: {
      Table *h = gco2h(o);
      g->gray = h->gclist;
      if (traversetable(g, h))  /* table is weak? */
        black2gray(o);  /* keep it gray */
      return sizeof(Table) + sizeof(TValue) * h->sizearray +
                             sizeof(Node) * sizenode(h);
    }
    case LUA_TFUNCTION: {
      Closure *cl = gco2cl(o);
      g->gray = cl->c.gclist;
      traverseclosure(g, cl);
      return (cl->c.isC) ? sizeCclosure(cl->c.nupvalues) :
                           sizeLclosure(cl->l.nupvalues);
    }
    case LUA_TTHREAD: {
      lua_State *th = gco2th(o);
      g->gray = th->gclist;
      th->gclist = g->grayagain;
      g->grayagain = o;
      black2gray(o);
      traversestack(g, th);
      return sizeof(lua_State) + sizeof(TValue) * th->stacksize +
                                 sizeof(CallInfo) * th->size_ci;
    }
    case LUA_TPROTO: {
      Proto *p = gco2p(o);
      g->gray = p->gclist;
      traverseproto(g, p);
      return sizeof(Proto) + sizeof(Instruction) * p->sizecode +
                             sizeof(Proto *) * p->sizep +
                             sizeof(TValue) * p->sizek + 
                             sizeof(int) * p->sizelineinfo +
                             sizeof(LocVar) * p->sizelocvars +
                             sizeof(TString *) * p->sizeupvalues;
    }
    default: lua_assert(0); return 0;
  }
}

/*
** clear collected values from weaktables
*/
static void cleartablevalues (lua_State *L, GCObject *l) {
  while (l) {
    Table *h = gcotoh(l);
    int i = h->sizearray;
    lua_assert(h->marked & VALUEWEAK);
    while (i--) {
      TObject *o = &h->array[i];
      if (!valismarked(o))  /* value was collected? */
        setnilvalue(o);  /* remove value */
    }
    i = sizenode(h);
    while (i--) {
      Node *n = gnode(h, i);
      if (!valismarked(gval(n)))  /* value was collected? */
        removekey(L, n);  /* remove entry from table */
    }
    l = h->gclist;
  }
}

static int traversetable(global_State *g, Table *h) {
    int i;
    int weakkey = 0;
    int weakvalue = 0;
    const TValue *mode;
    if (h->metatable)
        markobject(g, h->metatable);
    mode = gfasttm(g, h->metatable, TM_MODE);
    if (mode && ttisstring(mode)) { /* is there a weak mode? */
        weakkey = (strchr(svalue(mode), 'k') != NULL);
        weakvalue = (strchr(svalue(mode), 'v') != NULL);
        if (weakkey || weakvalue) { /* is really weak? */
            h->marked &= ~(KEYWEAK | VALUEWEAK); /* clear bits */
            h->marked |= cast_byte((weakkey << KEYWEAKBIT) |
                                   (weakvalue << VALUEWEAKBIT));
            h->gclist = g->weak; /* must be cleared after GC, ... */
            g->weak = obj2gco(h); /* ... so put in the appropriate list */
        }
    }
    if (weakkey && weakvalue)
        return 1;
    if (!weakvalue) {
        i = h->sizearray;
        while (i--)
            markvalue(g, &h->array[i]);
    }
    i = sizenode(h);
    while (i--) {
        Node *n = gnode(h, i);
        lua_assert(ttype(gkey(n)) != LUA_TDEADKEY || ttisnil(gval(n)));
        if (ttisnil(gval(n)))
            removeentry(n); /* remove empty entries */
        else {
            lua_assert(!ttisnil(gkey(n)));
            if (!weakkey)
                markvalue(g, gkey(n));
            if (!weakvalue)
                markvalue(g, gval(n));
        }
    }
    return weakkey || weakvalue;
}

int luaH_next (lua_State *L, Table *t, StkId key) {
  unsigned int asize = luaH_realasize(t);
  unsigned int i = findindex(L, t, s2v(key), asize);  /* find original key */
  for (; i < asize; i++) {  /* try first array part */
    if (!isempty(&t->array[i])) {  /* a non-empty entry? */
      setivalue(s2v(key), i + 1);
      setobj2s(L, key + 1, &t->array[i]);
      return 1;
    }
  }
  for (i -= asize; cast_int(i) < sizenode(t); i++) {  /* hash part */
    if (!isempty(gval(gnode(t, i)))) {  /* a non-empty entry? */
      Node *n = gnode(t, i);
      getnodekey(L, s2v(key), n);
      setobj2s(L, key + 1, gval(n));
      return 1;
    }
  }
  return 0;  /* no more elements */
}

LUAPLUS_API bool LuaPlusH_next(LuaState* state, LuaObject* table, LuaObject* key, LuaObject* value)
{
	Table* t = hvalue(table->GetTObject());
	int i = luaH_findindex(*state, t, key->GetTObject());  /* find original element */
    for (i++; i < t->sizearray; i++) {  /* try first array part */
      if (!ttisnil(&t->array[i])) {  /* a non-nil value? */
        key->AssignInteger(state, i + 1);
        value->AssignTObject(state, &t->array[i]);
        return true;
	  }
	}
    for (i -= t->sizearray; i < sizenode(t); i++) {  /* then hash part */
      if (!ttisnil(gval(gnode(t, i)))) {  /* a non-nil value? */
        key->AssignTObject(state, key2tval(gnode(t, i)));
        value->AssignTObject(state, gval(gnode(t, i)));
        return true;
      }
	}
	return false;  /* no more elements */
}

static lu_mem traversetable (global_State *g, Table *h) {
  const char *weakkey, *weakvalue;
  const TValue *mode = gfasttm(g, h->metatable, TM_MODE);
  markobjectN(g, h->metatable);
  if (mode && ttisstring(mode) &&  /* is there a weak mode? */
      ((weakkey = strchr(svalue(mode), 'k')),
       (weakvalue = strchr(svalue(mode), 'v')),
       (weakkey || weakvalue))) {  /* is really weak? */
    black2gray(h);  /* keep table gray */
    if (!weakkey)  /* strong keys? */
      traverseweakvalue(g, h);
    else if (!weakvalue)  /* strong values? */
      traverseephemeron(g, h);
    else  /* all weak */
      linkgclist(h, g->allweak);  /* nothing to traverse now */
  }
  else  /* not weak */
    traversestrongtable(g, h);
  return sizeof(Table) + sizeof(TValue) * h->sizearray +
                         sizeof(Node) * cast(size_t, sizenode(h));
}

int kp_table_next(ktap_State *ks, Table *t, StkId key)
{
	int i = findindex(ks, 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, i+1);
			setobj(ks, 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? */
			setobj(ks, key, gkey(gnode(t, i)));
			setobj(ks, key+1, gval(gnode(t, i)));
			return 1;
		}
	}

	return 0;  /* no more elements */
}

void kp_table_dump(ktap_State *ks, Table *t)
{
	int i, count = 0;

	kp_printf(ks, "{");
	for (i = 0; i < t->sizearray; i++) {
		Tvalue *v = &t->array[i];

		if (isnil(v))
			continue;

		if (count)
			kp_printf(ks, ", ");

		kp_printf(ks, "(%d: ", i + 1);
		kp_showobj(ks, v);
		kp_printf(ks, ")");
		count++;
	}

	for (i = 0; i < sizenode(t); i++) {
		Node *n = &t->node[i];

		if (isnil(gkey(n)))
			continue;

		if (count)
			kp_printf(ks, ", ");

		kp_printf(ks, "(");
		kp_showobj(ks, gkey(n));
		kp_printf(ks, ": ");
		kp_showobj(ks, gval(n));
		kp_printf(ks, ")");
		count++;
	}
	kp_printf(ks, "}");
}

static void traversetable (GCState *st, Table *h) {
  int i;
  int weakkey = 0;
  int weakvalue = 0;
  const TObject *mode;
  markvalue(st, h->metatable);
  lua_assert(h->lsizenode || h->node == st->g->dummynode);
  mode = gfasttm(st->g, h->metatable, TM_MODE);
  if (mode && ttisstring(mode)) {  /* is there a weak mode? */
    weakkey = (strchr(svalue(mode), 'k') != NULL);
    weakvalue = (strchr(svalue(mode), 'v') != NULL);
    if (weakkey || weakvalue) {  /* is really weak? */
      GCObject **weaklist;
      h->marked &= ~(KEYWEAK | VALUEWEAK);  /* clear bits */
      h->marked |= cast(lu_byte, (weakkey << KEYWEAKBIT) |
                                 (weakvalue << VALUEWEAKBIT));
      weaklist = (weakkey && weakvalue) ? &st->wkv :
                              (weakkey) ? &st->wk :
                                          &st->wv;
      h->gclist = *weaklist;  /* must be cleared after GC, ... */
      *weaklist = valtogco(h);  /* ... so put in the appropriate list */
    }
  }
  if (!weakvalue) {
    i = h->sizearray;
    while (i--)
      markobject(st, &h->array[i]);
  }
  i = sizenode(h);
  while (i--) {
    Node *n = gnode(h, i);
    if (!ttisnil(gval(n))) {
      lua_assert(!ttisnil(gkey(n)));
      condmarkobject(st, gkey(n), !weakkey);
      condmarkobject(st, gval(n), !weakvalue);
    }
  }
}

int kp_table_length(ktap_State *ks, Table *t)
{
	int i, len = 0;

	for (i = 0; i < t->sizearray; i++) {
		Tvalue *v = &t->array[i];

		if (isnil(v))
			continue;
		len++;
	}

	for (i = 0; i < sizenode(t); i++) {
		Node *n = &t->node[i];

		if (isnil(gkey(n)))
			continue;

		len++;
	}
	
	return len;
}

/* histogram: key should be number or string, value must be number */
void kp_table_histogram(ktap_State *ks, Table *t)
{
	struct table_hist_record *thr;
	char dist_str[40];
	int i, ratio, total = 0, count = 0;

	thr = kp_malloc(ks, sizeof(*thr) * (t->sizearray + sizenode(t)));

	for (i = 0; i < t->sizearray; i++) {
		Tvalue *v = &t->array[i];

		if (isnil(v))
			continue;

		if (!ttisnumber(v))
			goto error;

		setnvalue(&thr[count++].key, i + 1);
		total += nvalue(v);
	}

	for (i = 0; i < sizenode(t); i++) {
		Node *n = &t->node[i];
		int num;

		if (isnil(gkey(n)))
			continue;

		if (!ttisnumber(gval(n)))
			goto error;

		num = nvalue(gval(n));
		setobj(ks, &thr[count].key, gkey(n));
		setobj(ks, &thr[count].val, gval(n));
		count++;
		total += nvalue(gval(n));
	}

	sort(thr, count, sizeof(struct table_hist_record), hist_record_cmp, NULL);

	kp_printf(ks, "%32s%s%s\n", "value ", DISTRIBUTION_STR, " count");
	dist_str[sizeof(dist_str) - 1] = '\0';
	for (i = 0; i < count; i++) {
		Tvalue *key = &thr[i].key;
		Tvalue *val = &thr[i].val;

		memset(dist_str, ' ', sizeof(dist_str) - 1);
		ratio = (nvalue(val) * (sizeof(dist_str) - 1)) / total;
		memset(dist_str, '@', ratio);

		if (ttisstring(key)) {
			char buf[32 + 1] = {0};
			char *keystr;

			if (strlen(svalue(key)) > 32) {
				strncpy(buf, svalue(key), 32-4);
				memset(buf + 32-4, '.', 3);
				keystr = buf;
			} else
				keystr = svalue(key);

			kp_printf(ks, "%32s |%s%-10d\n", keystr, dist_str,
					nvalue(val));
		} else
			kp_printf(ks, "%32d | %s%-10d\n", nvalue(key),
					dist_str, nvalue(val));
	}

	goto out;

 error:
	kp_printf(ks, "error: table histogram only handle "
			" (key: string/number val: number)\n");
 out:
	kp_free(ks, thr);
}