Блог

Существует ли идиоматический способ C резервировать и перерабатывать идентификаторы, которые гарантированно уникальны? Мои требования таковы:

1. Предполагая, что существует идентификатор, который в данный момент не зарезервирован, reserve_id(void) возвращает мне этот идентификатор.
2. В непрерывной последовательности вызовов reserve_id() ни один идентификатор не будет возвращен дважды
3. Существует функция recycle(id_type), которая возвращает идентификатор доступному пулу.

Я, например, видел Boost::Uuid, но а) я не вижу документации, которая утверждает гарантированную уникальность двух UUID и б) на данный момент я ограничен более ранней версией Boost (1.40). Я мог бы нажать на обновление, если бы это было особенно идеально для задачи.

Я думаю, вы уже решили эту проблему для большинства практических целей, найдя Boost::Uuid , за исключением вашего требования перерабатывать уже сгенерированные идентификаторы.

Из документации, на которую вы ссылались в вопросе:

Когда идентификаторы UUID генерируются одним из определенных механизмов, они либо гарантированно уникальны, отличаются от всех других сгенерированных идентификаторов UUID (то есть они никогда не генерировались ранее и никогда не будут сгенерированы снова), либо с высокой вероятностью будут уникальными (в зависимости от механизма).

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

РЕДАКТИРОВАТЬ: Вы отметили, что вам нужна гарантия уникальности. На самом деле, вы никогда не получите его при программной генерации уникального идентификатора. На практике вы собираетесь сохранить сгенерированный идентификатор в типе данных, который имеет конечный размер, и поэтому возможный набор идентификаторов, которые вы можете сгенерировать, тоже конечен. ИМХО, лучшее, чего вы можете достичь, — это имитировать уникальность в пределах порога допуска.

Вы могли бы сделать это с помощью

• Использование метода, который делает шансы на получение дубликата UUID очень незначительными (это то, что будет делать Boost::UUID);

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

• Если вам нужно действительно огромное количество уникальных идентификаторов, больше, чем поместилось бы в собственный тип, вы могли бы реализовать тип, который управляет памятью и выполняет необходимую математику, и просто создавать последовательные идентификаторы, или вы могли бы, возможно, использовать что-то вроде библиотеки GNU Bignum, чтобы сделать это за вас.

Как долго живут идентификаторы? Вам ДЕЙСТВИТЕЛЬНО нужно их перерабатывать или вы можете жить с тем, что они будут уникальными вечно? Сколько вам нужно сгенерировать всех сразу? Сколько битов вы можете выделить для идентификатора?

Вот простой рецепт: возьмите mac-адрес вашей карты Ethernet (который является уникальным во всем мире, исключая аппаратные проблемы), добавьте время / дату (с разрешением в миллисекунду) и счетчик увеличивающихся целых чисел (увеличивается один раз на каждый сгенерированный идентификатор), и у вас будет идентификатор, уникальный в пределах вашего диапазона времени / дат, при условии, что вы не генерируете MAXINT из них за одну миллисекунду на этом компьютере. Теперь это НЕ выглядит случайным образом, и злоумышленнику легко предсказать, поэтому не используйте его для обеспечения безопасности, и это, конечно, не самое эффективное использование битов, но оно уникально во всем мире.

Какого рода уникальность вам требуется?
Просто уникальные на протяжении всего срока службы программы или уникальные при нескольких запусках / межпроцессном взаимодействии?

Если это первое, то вы могли бы просто new выделить байт памяти, а затем использовать адрес этой памяти в качестве своего идентификатора. Это будет гарантированно уникальным до тех пор, пока вы delete не освободите память, после чего она может быть переработана.

Это можно легко обернуть в класс, подобный этому:

 #include <stdint.h>

class UID
{
public:
        typedef uint64_t id_type;

        static const id_type reserve_id()
        {
                uint8_t* idBlock = new uint8_t;
                *idBlock = validId;
                return (id_type)idBlock;
        }

        static void recycle(id_type id)
        {
                uint8_t* idBlock = (uint8_t*)id;
                if (*idBlock == validId)
                {
                        *idBlock = 0;
                        delete idBlock;
                }
        }
private:
        static const uint8_t validId = 0x1D;
};
  

Возможно, это немного необычно, но это соответствует вашим требованиям, если вам нужна уникальность только для каждого процесса 🙂

Да, это просто.

1. reserve_id Функция является operator new(0) .
2. При этом выделяется ноль байт, но с уникальным адресом.
3. recycle Функция, конечно operator delete

Проблема, похоже, не связана с C , это скорее фундаментальная проблема. Ожидается, что сколько идентификаторов будут действительными в любой момент времени? Если вы ожидаете, что в любой момент времени у вас будет несколько допустимых идентификаторов, просто поместите их в контейнер, такой как связанный список, вектор или набор, в зависимости от ваших требований к производительности и относительной частоты повторного использования / резервирования. Вероятно, лучшим вариантом является отсортированный связанный список, поскольку у вас будут операции как по переработке, так и по резервированию в O (n). Вектор имеет O (n), O (n log n), а набор имеет O (n log n), O (n) соответственно (может быть, я ошибаюсь, я очень быстро сообразил).

 void recycle(ID) {
    container.remove(ID);
    // abort if unsuccessiful (= invalid ID)
}

ID reserve() {
    static ID last = 0;
    while(container.find(last)) {
        last  ;
    }
    return last;
}