Используя 'цвет', чтобы определить статус флага объекта?

Question

Я задаю этот вопрос, потому что это не первый раз, когда я видел эту практику кодирования, но никогда не видел никаких комментариев о причине этого: я просматривал источник 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)))

Я уже видел нечто подобное в других проектах (которые использовали даже «красный»), но никогда не понимал (и не заботился), какова концептуальная связь между цветом и состоянием объектов. Существует какое-то соглашение, определяющее, что «белый» должен означать «хороший» и «черный», «плохой» или что-то подобное? Кто-нибудь знает, каково происхождение этой практики?

Answer 1

Когда вы видите цвета, используемые в этом типе контекста, это обычно происходит из-за реализации базового алгоритма, который сам определяется в терминах цветов. Мередит упомянула один пример этого; другой - красно-черные деревья .

Answer 2

У меня нет исходного кода Lua передо мной, но имена определений битов, кажется, связанный с сборкой мусора . Смотрите раздел в Википедии запись на трехцветную маркировку.

Answer 3

Может ли он иметь происхождение в бело-серо-черном поиске в глубину? В этой версии алгоритма белые вершины не посещаются, серые вершины посещаются на пути вниз по дереву, а серая вершина изменяется на черный при возврате вверх.

Я предполагаю из комментариев, что это как-то связано со сборкой мусора?