使用'颜色'来定义对象的标志状态？

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

我已经看到了在其他项目类似的东西（它甚至用“红”），但永远无法理解（也不关心）什么是颜色和物体之间的概念连接州。有什么样的约定规定'白色'应该表示'好'和'黑'，'坏'或类似的东西？任何人都知道这种做法的起源是什么？

来源

2009-08-05 ogoid

您可能在红黑树的实现中看到了“红色”。那里的颜色并不重要，除了图表看起来比橙色粉红色的树更可敬。 – 2009-08-05 01:22:51

难道它起源于white-gray-black深度优先搜索？在该版本的算法中，白色顶点未被访问，灰色顶点在树下方被访问，并且灰色顶点在返回的路上变为黑色。

我从评论中认为这与垃圾收集有关？

来源

2009-08-05 01:15:15

是的，这是垃圾收集机制。我会读一个数据结构/算法书。但在我看来，由于这些算法的通用性，颜色关联本质上是不合适的。我对吗？ – ogoid 2009-08-06 14:38:28

当您看到这种类型的上下文中使用的颜色时，通常是由于基本算法的实现本身是根据颜色定义的。梅雷迪思提到了一个例子。另一个是Red-Black Trees。

来源

2009-08-05 01:21:13 caf

还有红 - 绿 - 黑混合（http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.1477），但我相信这不是来自哪里。 :) – 2009-08-05 01:24:50

我没有在我面前的Lua源代码，但位定义名称似乎是有关garbage collection。请参阅维基百科关于三色标记的条目。

来源

2009-08-05 03:59:54 themis

使用'颜色'来定义对象的标志状态？

回答

相关问题