AnimeSlave Jun 26 at 16:41

Контейнер ConditionalBitset — небольшое хранилище для условий выполнения

Easy

8 min

1.1K

Tutorial

Вводное слово

У каждого программиста бывает желание велосипедостроения. Это случилось и у меня. Решил зарефакторить кусочек кода в приложении на текущей работе. Было приложение, которое выполняло работу в бесконечном цикле. И в этом цикле работа выполнялась, когда приложение было активно. То, что приложение активно в данный момент определялось через группу булевых значений. То есть каждую итерацию цикла приложение проверяла все эти булевы условия. Я подумал, что не лучше ли будет проверять одно значение вместо пачки. Так родился простой велосипед небольшого хранилища булевых условий в битах целочисленного типа.

В статье все примеры взяты из головы. Все совпадения случаны

Проблема и решение

Так вот. Как-то столкнулся я с кодом

bool hasFocus     { false };
bool hasWindow    { false };
bool isInitialized{ false };
bool isVisible    { false };

Который дальше имел такую конструкцию:

bool isActive() const
{
    return isInitialized && hasFocus && isVisible && hasWindow;
}

Отсутствие constexpr не имеет значения для статьи. Это просто пример.

И подумалось мне, а почему так? Для чего проверять каждый раз пачку булевых значений, когда в принципе можно только одно. isActive например. И тоже булево. С точки зрения оптимизации, если isActive используется для проверки в цикле, где задержки нежелательны, проверить одно значение быстрее, чем 4. Да и те, что я предоставил в пример, это лишь пример. Условий может быть куда больше. Я видел как-то код с 12 условиями.

Так вот, почему бы не использовать одно значение? Запретов как бы нет. Но возникает другой вопрос. А как удостовериться, что все условия соблюдены? И полученная истина в isActive явно указывает на то, что и hasFocus, и hasWindow, и isInitialized, и isVisible истины? То есть можно написать методы setHasFocus, setHasWindow, seIsVisible и setIsInitialized. И в каждом из них проверять наличие всех условий. Например:

void setHasFocus(bool value)
{
    hasFocus = value;
    isActive = isInitialized && hasFocus && isVisible && hasWindow;
}

Но это лишние проверки, и потенциальные ошибки, если надо добавить ещё условия. И кто-то легко может для своего удобства не через метод «погасит» условие, а напрямую, через переменную.

Я решил, что здесь хорошо подойдут битовые поля. Но использовать std::bitset я не хотел, так как это немного не то. Вот что внутри у std::bitset clang'а:

__storage_type __first_[_N_words];

Работа с массивом. И вот это вот всё. Старые добрый битовые операции - всё, что нужно. Почему нет? Берём целочисленный тип, и принимаем, что 0 - это истина. То есть, если все биты памяти этого типа стоят в 0, то значит все условия соблюдены. Если есть хотя бы один бит, то не все условия соблюдены. Логично? Логично. Выставляя биты - устанавливаются условия. Убирая биты - условия выполняются. Даже текстом выглядит просто.

Теперь вопрос в том, как выставлять биты? Здесь поможет степень двойки, битовый сдвиг и перечисления.

enum class AppIsActiveConditions : uint8_t
{
    NONE        = 0,
    INITIALIZED = (1 << 0),
    HAS_FOCUS   = (1 << 1),
    HAS_WINDOW  = (1 << 2),
    IS_VISIBLE  = (1 << 3),
};

Пример простой, но уже надеюсь понятно что к чему. Внутренний тип перечисления uint8_t нужен для создания числа, в котором поместятся все условия. По умолчанию у перечислений в C++ внутренний тип int. Можно по сути использовать любой целочисленный. Со знаком или без - это не важно. Главное, чтобы все условия имели положительные и не повторяющиеся значения степени двойки. Условие NONE с нулём вспомогательное. Оно никак не используется. Но применение и ему можно найти, если захотеть.

Объявление переменной хранилища выглядит так:

ConditionalBitset <AppIsActiveConditions> isActive {
    AppIsActiveConditions::INITIALIZED,
    AppIsActiveConditions::HAS_FOCUS,
    AppIsActiveConditions::HAS_WINDOW,
    AppIsActiveConditions::IS_VISIBLE
};

Переменная isActive хранит в себе биты условий. И не равно 0. Далее остаётся только указывать, какие условия выполнились. Или заново установить условия, если условие перестало быть истинным. Делается это через методы

isActive.reach(AppIsActiveConditions::INITIALIZED); // достигли условия
isActive.lose(AppIsActiveConditions::INITIALIZED);  // условие потеряли

Оба метода возвращают булево для того, чтобы проинформировать. true возвращается, когда методы выполнили работу. false же означает:

для метода reach, что при достижении условия - условие либо уже было достигнуто, либо не устанавливалось изначально.
для метода lose, что при потере условия - условие либо ещё не было достигнуто, либо было установлено ранее.

Немного заумно, но так проще понять.

Проверить наличие условия можно через метод

isActive.isReached(AppIsActiveConditions::INITIALIZED);

Через него можно заменить и запросы к старым булевым значениям.

Осталось только показать код класса.
(Спойлер в markdown почему-то не работает. Оставлю так, портянкой - для объёму)

Код класса

// Предварительное проверочное объявление класса,
// чтобы случайно не ввести другие типы. 
// Потому что нам нужны только перечисления
template <typename Type, bool = std::is_enum<Type>::value>
class ConditionalBitset;

// Основное тело класса
template <typename EnumType>
class ConditionalBitset <EnumType, true> final
{
    // Выделяется внутренний тип перечисления
    using EnumUnderlyingType = typename std::underlying_type<EnumType>::type;

public:
    // Указываю, что нужно использовать только этот конструктор 
    template <typename...Args>
    explicit constexpr ConditionalBitset (Args&&...args) noexcept
    {
        ((add(std::forward<Args>(args))),...);
    }

    // Преведение типа к булеву для простоты проверки
    // Сравнение с нулём для наглядности, можно указать `!value`
    constexpr operator bool() const noexcept { return value == 0; }

    constexpr bool isReached(EnumType condition) const noexcept
    {
        return !has(condition);
    }

    constexpr bool lose(EnumType condition) noexcept
    {
        if (has(condition))
        {
            return false;
        }

        add(condition);
        return true;
    }

    constexpr bool reach(EnumType condition) noexcept
    {
        if (!has(condition))
        {
            return false;
        }

        remove(condition);
        return true;
    }

private:
    // Вспомогательные приватные методы тоже для наглядности

    constexpr void add(EnumType condition) noexcept
    {
        value |= static_cast<EnumUnderlyingType>(condition);
    }

    constexpr bool has(EnumType condition) const noexcept
    {
        return (value & static_cast<EnumUnderlyingType>(condition));
    }

    constexpr void remove(EnumType condition) noexcept
    {
        value ^= static_cast<EnumUnderlyingType>(condition);
    }

    // Целое число, как битовое поле
    EnumUnderlyingType value; 

};

Просто и наглядно.

Минусы решения

И в при таком решении есть свои минусы.

Основной минус, что нельзя динамически добавлять условия. Но мне это и не было нужно.

Так же нет проверки на одинаковые значения условий. Поэтому важным критерием является не повторяющиеся значения для условий.

Не менее значительный минус в том, что теперь в дебаге сложнее смотреть какие условия уже выполнились, а какие ещё нет. Требуется складывать значения условий в уме.

И ещё - нельзя «выключить» условие, можно только либо «погасить» его в переменной где-то в коде, либо удалить его из списка инициализации переменной.

На самом деле минусов куда больше. Я указал только часть

upd.
В методе remove используется оператор XOR (^), который имеет особенность - он возвращает разницу между двумя операндами. Он может как удалить бит, если он был, так и установить его, если его не было. Это может стать проблемами в будущем, если вызывать метод remove повторно на одно и тоже значение.

Более идиоматическое «удаление» выглядит так

constexpr void remove(EnumType condition) noexcept
{
    value &= ~(static_cast<EnumUnderlyingType>(condition));
}

Оно всегда выполняет удаление без непредвиденных эффектов при неправильном использовании. Но здесь уже две операции: логическое отрицание и логическое умножение вместо одной.

Benchmarks

Их нет. Этот велосипед - это велосипед. И не рассматривался, как конечное решение для прода. А для статьи для Хабра - самое то.

upd.

Чуть более детальное описание и немного теории

Не вдаваясь в более детальные подробности укажу, что память храниться, как набор битов. В обычной переменной типа int для 32-битной системы 4 байта, или 32 бита, так как в одном байте 8 бит.
Тип int в памяти можно представить так

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Число 3 будет выглядеть так (это всё те же 4 байта)

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1

Выше в статье было указано такое выражение (1 << 0). Это выражение - битовый сдвиг влево (оператор <<), относящийся к битовым операция с памятью. В более общем виде, это выражение будет выглядеть так n << m. С помощь него можно сдвинуть некую память n на некое число битов m влево. В примере 1 << 0 число 1 сдвигается на 0 битов. И по сути результат выражения равен 1. Почему тогда не написать просто 1 вместо 1 << 0? Это сделано специально для наглядности. Ведь далее в коде статьи показаны и другие выражения смещения 1 << 1, 1 << 2, 1 << 3. И вместе они уже наглядно показывают, что производится смещение числа 1 на некоторое число битов.

enum class AppIsActiveConditions : uint8_t
{
    NONE        = 0,
    INITIALIZED = (1 << 0),
    HAS_FOCUS   = (1 << 1),
    HAS_WINDOW  = (1 << 2),
    IS_VISIBLE  = (1 << 3),
};

Таким образов формируется перечисление, которое используется как набор Условий, который будут «храниться» в Контейнере.

Каждое Условие, по задумке, это целочисленное не повторяющееся положительное число равное числу, полученному из степень двойки, то есть 2^x. А почему нужно число именно степени двойки? Потому что особенность всех чисел степени двойки в том, что их представление в двоичной системе исчисления содержит только 1 бит равный 1.

Например число 4 в одном байте выглядит так

0 0 0 0 0 1 0 0

А число 32 - так

0 0 1 0 0 0 0 0

Число 1, тоже степени двойки, только степень равно нулю (2⁰ = 1). И представляется в памяти так

0 0 0 0 0 0 0 1

И если сдвинуть память занимаемую числом 1 влево на два бита (1 << 2), то получим

0 0 0 0 0 1 0 0

А это уже число 4. Таким образом, сдвигая память числа 1 влево, можно получать нужное число степени двойки.

Добавление Условий в Контейнер

И теперь представьте, что каждый бит хранимого в Контейнере числа можно использовать, как отдельное булево значение, где 1 это true (ИСТИНА), а 0 это false (ЛОЖЬ). Что, собствено, и есть на самом деле. Тип bool в языке C++ - это синтаксический сахар, чтобы удобнее было работать с таким типом. В языке C, к примеру, нет типа bool. Его «эмулирую» через целочисленный тип (обычно int).

Примем, что каждое Условие - это не повторяющееся число степени двойки. Остаётся только Условия «вложить» в Контейнер. Для этого используется битовый оператор | (логическое сложение, OR, ИЛИ). Выражение будет иметь вид n | m. Для примера «сложим» числа 32 и 4

0 0 1 0 0 0 0 0  // 32
                 // |
0 0 0 0 0 1 0 0  // 4
                 // =
0 0 1 0 0 1 0 0  // 36

Получится число 36.

В статье в коде класса оператор | применяется в приватном методе add. Метод add, как бы добавляет проверяемое Условие в Контейнер. Метод приватный и применяется в публичных конструкторе и методе lose. Конструктор указан как «явный» (explicit)., чтобы при объявлении переменной сразу выставить нужные Условия для проверки. Такова задумка изначально. Других конструкторов не предусмотрено. В методе 'lose', по задумке, выставляется Условие, которое перестало быть истинным. То есть «потеряли» его. Отсюда и название lose.

«Удаление» Условий из Контейнера

Для «отключения» битов в числе, хранимом в классе, применяется оператор ^ (логическое вычитание, исключающее ИЛИ, XOR). Выражение будет иметь вид n ^ m. Оператор ставит в 0 похожие биты числа, а не похожие в 1. «Вычтем» число 32 из числа 36.

0 0 1 0 0 1 0 0  // 36
                 // ^
0 0 1 0 0 0 0 0  // 32
                 // =
0 0 0 0 0 1 0 0  // 4

Получим число 4.

В статье в коде класса оператор ^ применяется в приватном методе remove. Метод remove, удаляет проверяемое Условие из числа, хранимого в классе. Метод приватный и применяется только в публичном методе reach. Название reach выбрано для описание того, что мы как бы «достигли» проверяемого Условия.

Результат работы

В итоге, после того, как все Условия были «достигнуты», в Контейнере должно остаться число 0. И именно оно принято за конечный результат. Для того, чтобы оставить логику булево значения, то есть, чтобы можно было объект класса использовать в ветвениях и циклах, в классе был определён оператор operator bool() для неявного приведения хранимого в классе числа к булеву значению.

На этом всё. Спасибо за внимание!

Tags:

Hubs: