Using 'color' to define object's flag status?

Question

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?

Answer 1

Could it have its origins in white-gray-black depth-first search? In this version of the algorithm, white vertices are unvisited, gray vertices have been visited on the way down the tree, and a gray vertex gets changed to black on the way back up.

I assume from the comments that this has something to do with garbage collection?

Answer 2

When you see colours used in this type of context, it's usually due to an implementation of a basic algorithm that is itself defined in terms of colours. Meredith mentioned one example of this; another is Red-Black Trees.

Answer 3

I don't have the Lua source code in front of me, but the bit definition names seem to be related to garbage collection. See the section in the Wikipedia entry on tri-colour marking.