2

I'm asking this question because it isn't the first time I saw this coding practice, but never saw any commentary about the reason for this: I was browsing the Lua's source and saw that they use 'colors' (white, black) to describe the state of an object. Here is the code from header 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)))

I already saw something similar in other projects (which used even 'red'), but never understood (nor cared) what's the conceptual connection between color and objects' state. There is any sort of convention specifying that 'white' should mean 'good' and 'black', 'bad' or something similar? Anyone knows what's the origin of this practice?

4

3 に答える 3

1

目の前にLuaソースコードはありませんが、ビット定義名はガベージコレクションに関連しているようです。ウィキペディアのエントリの3色マーキングに関するセクションを参照してください。

于 2009-08-05T03:59:54.033 に答える
1

白黒の深さ優先検索に起源があるのでしょうか? このバージョンのアルゴリズムでは、白い頂点は未訪問であり、灰色の頂点はツリーを下る途中で訪問され、灰色の頂点は戻る途中で黒に変わります。

コメントから、これはガベージコレクションと関係があると思いますか?

于 2009-08-05T01:15:15.280 に答える
1

このタイプのコンテキストで色が使用されている場合、それは通常、それ自体が色に関して定義されている基本的なアルゴリズムの実装によるものです。メレディスはこの一例を挙げました。もう一つは赤黒木です。

于 2009-08-05T01:21:13.437 に答える