2

我问这个问题是因为这不是我第一次看到这种编码实践，但从未看到任何关于其原因的评论：我正在浏览 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)))

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

4

3 回答 3

1

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

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

于 2009-08-05T01:15:15.280 回答
1

当您看到在这种类型的上下文中使用的颜色时，通常是由于实现了一个基本算法，该算法本身是根据颜色定义的。Meredith 提到了一个例子。另一个是红黑树。

于 2009-08-05T01:21:13.437 回答
1

我面前没有 Lua 源代码，但是位定义名称似乎与垃圾收集有关。请参阅维基百科条目中有关三色标记的部分。

于 2009-08-05T03:59:54.033 回答