/*
** barrier that moves collector forward, that is, mark the white object
** being pointed by a black object. (If in sweep phase, clear the black
** object to white [sweep it] to avoid other barrier calls for this
** same object.)
*/
void luaC_barrier_ (lua_State *L, GCObject *o, GCObject *v) {
  global_State *g = G(L);
  lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o));
  if (keepinvariant(g))  /* must keep invariant? */
    reallymarkobject(g, v);  /* restore invariant */
  else {  /* sweep phase */
    lua_assert(issweepphase(g));
    makewhite(g, o);  /* mark main obj. as white to avoid other barriers */
  }
}

static void marktmu (global_State *g) {
  GCObject *u = g->tmudata;
  if (u) {
    do {
      u = u->gch.next;
      makewhite(g, u);  /* may be marked, if left from previous GC */
      reallymarkobject(g, u);
    } while (u != g->tmudata);
  }
}

void luaC_barrierf (lua_State *L, GCObject *o, GCObject *v) {
  global_State *g = G(L);
  lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o));
  lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
  lua_assert(ttype(&o->gch) != LUA_TTABLE);
  /* must keep invariant? */
  if (g->gcstate == GCSpropagate)
    reallymarkobject(g, v);  /* restore invariant */
  else  /* don't mind */
    makewhite(g, o);  /* mark as white just to avoid other barriers */
}

/*
** barrier that moves collector forward, that is, mark the white object
** being pointed by a black object.
*/
void luaC_barrier_ (lua_State *L, GCObject *o, GCObject *v) {
  global_State *g = G(L);
  lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o));
  lua_assert(isgenerational(g) || g->gcstate != GCSpause);
  lua_assert(gch(o)->tt != LUA_TTABLE);
  if (keepinvariant(g))  /* must keep invariant? */
    reallymarkobject(g, v);  /* restore invariant */
  else {  /* sweep phase */
    lua_assert(issweepphase(g));
    makewhite(g, o);  /* mark main obj. as white to avoid other barriers */
  }
}

/*
** Traverse an ephemeron table and link it to proper list. Returns true
** iff any object was marked during this traversal (which implies that
** convergence has to continue). During propagation phase, keep table
** in 'grayagain' list, to be visited again in the atomic phase. In
** the atomic phase, if table has any white->white entry, it has to
** be revisited during ephemeron convergence (as that key may turn
** black). Otherwise, if it has any white key, table has to be cleared
** (in the atomic phase).
*/
static int traverseephemeron (global_State *g, Table *h) {
  int marked = 0;  /* true if an object is marked in this traversal */
  int hasclears = 0;  /* true if table has white keys */
  int hasww = 0;  /* true if table has entry "white-key -> white-value" */
  Node *n, *limit = gnodelast(h);
  unsigned int i;
  /* traverse array part */
  for (i = 0; i < h->sizearray; i++) {
    if (valiswhite(&h->array[i])) {
      marked = 1;
      reallymarkobject(g, gcvalue(&h->array[i]));
    }
  }
  /* traverse hash part */
  for (n = gnode(h, 0); n < limit; n++) {
    checkdeadkey(n);
    if (ttisnil(gval(n)))  /* entry is empty? */
      removeentry(n);  /* remove it */
    else if (iscleared(g, gkey(n))) {  /* key is not marked (yet)? */
      hasclears = 1;  /* table must be cleared */
      if (valiswhite(gval(n)))  /* value not marked yet? */
        hasww = 1;  /* white-white entry */
    }
    else if (valiswhite(gval(n))) {  /* value not marked yet? */
      marked = 1;
      reallymarkobject(g, gcvalue(gval(n)));  /* mark it now */
    }
  }
  /* link table into proper list */
  if (g->gcstate == GCSpropagate)
    linkgclist(h, g->grayagain);  /* must retraverse it in atomic phase */
  else if (hasww)  /* table has white->white entries? */
    linkgclist(h, g->ephemeron);  /* have to propagate again */
  else if (hasclears)  /* table has white keys? */
    linkgclist(h, g->allweak);  /* may have to clean white keys */
  return marked;
}

static int traverseephemeron (global_State *g, Table *h) {
	int marked = 0;  /* true if an object is marked in this traversal */
	int hasclears = 0;  /* true if table has white keys */
	int prop = 0;  /* true if table has entry "white-key -> white-value" */
	Node *n, *limit = gnodelast(h);
	int i;
	/* traverse array part (numeric keys are 'strong') */
	for (i = 0; i < h->sizearray; i++) {
	if (valiswhite(&h->array[i])) {
		marked = 1;
		reallymarkobject(g, gcvalue(&h->array[i]));
	}
	}
	/* traverse hash part */
	for (n = gnode(h, 0); n < limit; n++) {
	checkdeadkey(n);
	if (ttisnil(gval(n)))  /* entry is empty? */
		removeentry(n);  /* remove it */
	else if (iscleared(g, gkey(n))) {  /* key is not marked (yet)? */
		hasclears = 1;  /* table must be cleared */
		if (valiswhite(gval(n)))  /* value not marked yet? */
		prop = 1;  /* must propagate again */
	}
	else if (valiswhite(gval(n))) {  /* value not marked yet? */
		marked = 1;
		reallymarkobject(g, gcvalue(gval(n)));  /* mark it now */
	}
	}
	if (prop)
	linktable(h, &g->ephemeron);  /* have to propagate again */
	else if (hasclears)  /* does table have white keys? */
	linktable(h, &g->allweak);  /* may have to clean white keys */
	else  /* no white keys */
	linktable(h, &g->grayagain);  /* no need to clean */
	return marked;
}

static void marktmu (GCState *st) {
  GCObject *u;
#if LUA_REFCOUNT
  for (u = st->g->tmudata_head.next; u != (GCObject*)&st->g->tmudata_tail; u = u->gch.next) {
#else !LUA_REFCOUNT
  for (u = st->g->tmudata; u; u = u->gch.next) {
#endif LUA_REFCOUNT
    unmark(u);  /* may be marked, if left from previous GC */
    reallymarkobject(st, u);
  }
}


/* move `dead' udata that need finalization to list `tmudata' */
size_t luaC_separateudata (lua_State *L) {
  size_t deadmem = 0;
#if LUA_REFCOUNT
  GCObject **p = &G(L)->rootudata_head.next;
#else !LUA_REFCOUNT
  GCObject **p = &G(L)->rootudata;
#endif LUA_REFCOUNT
  GCObject *curr;
  GCObject *collected = NULL;  /* to collect udata with gc event */
#if !LUA_REFCOUNT
  GCObject **lastcollected = &collected;
  while ((curr = *p) != NULL) {
    lua_assert(curr->gch.tt == LUA_TUSERDATA);
#else LUA_REFCOUNT
  while ((curr = *p) != (GCObject*)&G(L)->rootudata_tail) {
#endif LUA_REFCOUNT
    if (ismarked(curr) || isfinalized(gcotou(curr)))
      p = &curr->gch.next;  /* don't bother with them */

    else if (fasttm(L, gcotou(curr)->uv.metatable, TM_GC) == NULL) {
      markfinalized(gcotou(curr));  /* don't need finalization */
      p = &curr->gch.next;
    }
    else {  /* must call its gc method */
      deadmem += sizeudata(gcotou(curr)->uv.len);
      *p = curr->gch.next;
#if LUA_REFCOUNT
	  Unlink(curr);
	  curr->gch.next = (GCObject*)&G(L)->tmudata_tail;  /* link `curr' at the end of `collected' list */
	  curr->gch.prev = G(L)->tmudata_tail.prev;
	  G(L)->tmudata_tail.prev->gch.next = curr;
      G(L)->tmudata_tail.prev = curr;
#else !LUA_REFCOUNT
	  curr->gch.next = NULL;  /* link `curr' at the end of `collected' list */
      *lastcollected = curr;
      lastcollected = &curr->gch.next;
#endif LUA_REFCOUNT
    }
  }
  /* insert collected udata with gc event into `tmudata' list */
#if LUA_REFCOUNT
//  *lastcollected = G(L)->tmudata_head.next;
//  G(L)->tmudata_head.next = collected;
#else !LUA_REFCOUNT
  *lastcollected = G(L)->tmudata;
  G(L)->tmudata = collected;
#endif LUA_REFCOUNT
  return deadmem;
}


static void removekey (lua_State *L, Node *n) {
  (void)L;
  setnilvalue(gval(n));  /* remove corresponding value ... */
  if (iscollectable(gkey(n)))
    setttype(gkey(n), LUA_TNONE);  /* dead key; remove it */
}

void luaC_marknew (lua_State *L, GCObject *o) {
  global_State *g = G(L);
  o->gch.marked = luaC_white(g);
  if (g->gcstate == GCSpropagate)
    reallymarkobject(g, o);  /* mark new objects as gray during propagate state. */
}