使用'顏色'來定義對象的標誌狀態？

我在問這個問題，因爲這不是我第一次看到這種編碼習慣，但從來沒有看到任何關於這個原因的評論：我在瀏覽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

使用'顏色'來定義對象的標誌狀態？

回答

相關問題