c - 使用 'color' 定义对象的标志状态？

Question

我问这个问题是因为这不是我第一次看到这种编码实践，但从未看到任何关于其原因的评论:我正在浏览 Lua 的源代码，看到他们使用“颜色”(白色、黑色)来描述对象的状态。这是头文件 lgc.h 中的代码:

/*
** Layout for bit use in `marked' field:
** bit 0 - object is white (type 0)
** bit 1 - object is white (type 1)
** bit 2 - object is black
** bit 3 - for userdata: has been finalized
** bit 3 - for tables: has weak keys
** bit 4 - for tables: has weak values
** bit 5 - object is fixed (should not be collected)
** bit 6 - object is "super" fixed (only the main thread)
*/

#define WHITE0BIT   0
#define WHITE1BIT   1
#define BLACKBIT    2
#define FINALIZEDBIT    3
#define KEYWEAKBIT  3
#define VALUEWEAKBIT    4
#define FIXEDBIT    5
#define SFIXEDBIT   6
#define WHITEBITS   bit2mask(WHITE0BIT, WHITE1BIT)

#define iswhite(x)      test2bits((x)->gch.marked, WHITE0BIT, WHITE1BIT)
#define isblack(x)      testbit((x)->gch.marked, BLACKBIT)
#define isgray(x)   (!isblack(x) && !iswhite(x))

#define otherwhite(g)   (g->currentwhite ^ WHITEBITS)
#define isdead(g,v) ((v)->gch.marked & otherwhite(g) & WHITEBITS)

#define changewhite(x)  ((x)->gch.marked ^= WHITEBITS)
#define gray2black(x)   l_setbit((x)->gch.marked, BLACKBIT)

#define valiswhite(x)   (iscollectable(x) && iswhite(gcvalue(x)))

我已经在其他项目中看到了类似的东西(甚至使用了“红色”)，但从未理解(也不关心)颜色和对象状态之间的概念联系是什么。有任何约定指定“白色”应该表示“好”和“黑色”、“坏”或类似的东西？有谁知道这种做法的起源是什么？

Answer 1

它可能起源于white-gray-black深度优先搜索？在这个版本的算法中，白色顶点未被访问，灰色顶点在树向下的过程中被访问过，灰色顶点在返回的过程中变为黑色。

我从评论中假设这与垃圾收集有关？