Теги / кодирование указателей

Question

Мне нужен способ пометить указатель как часть набора x или часть набора y (т. Е. Тег имеет только 2 «состояния»), это означает, что можно предположить untagged = x и tagged =y.

В настоящее время я смотрю на использование побитового xor для этого:

ptr ^ magic = encoded_ptr
encoded_ptr ^ magic = ptr

, но я озадачен тем, как определить, помечен ли указатель в первую очередь.Я использую это, чтобы пометить, откуда берутся узлы пула в связанном списке, чтобы при отсоединении они могли вернуться к правильным perant.

Обновление

Просто чтобы всем тем, кто предлагает сохранить флаг в дополнительных элементах данных, было ясно, что я ограничен sizeof(void*), поэтому я не могу добавлять новых участников, иначе я бы это сделал.Кроме того, пулы не являются смежными, они состоят из множества страниц, отслеживание диапазонов добавит слишком много накладных расходов (мне нужно быстрое и простое решение , если можно так назвать).

Answer 1

Большинство решений будет зависеть от платформы. вот несколько из них:

1) Указатель, возвращаемый malloc или new, будет выровнен (вы называете его 4, 8, 16, 32 байта). Таким образом, на большинстве архитектур несколько битов LSB адреса всегда будут равны 0.

2) И конкретный способ для Win32: если ваша программа не использует переключатель 3 ГБ, значения всех указателей пользовательского режима будут меньше 0x80000000, поэтому в качестве флага можно использовать старший бит. В качестве бонуса он также падает, когда помеченный указатель разыменовывается без ремонта.

Answer 2

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

Гораздо лучший способ сделать это - сохранить идентификатор в структуре, на которую указывает указатель.

Answer 3

Конечно, если у вас есть только два пула, когда вы выделяете память для каждого пула, вы знаете возможный диапазон адресов - так почему бы не проверить, находится ли заданный вами указатель в одном или другом диапазоне адресов с простой арифметикой указателей?

Answer 4

У вас может быть ptr1 ^ magic = ptr2 с ptr1 в наборе X и ptr2 в наборе Y (если вы не докажете обратное).Поскольку (я полагаю) у вас нет контроля над указанными адресами указателей, ваша техника кажется неадекватной.

Альтернативой решению Vinay является сохранение тегов в виде битов предварительно выделенного буфера(особенно легко, если размер списка ограничен, так как вам не нужно увеличивать или уменьшать буфер).Это очень компактное и эффективное решение, для которого не требуется изменять указанную структуру данных.

Cheers,

-stan

Answer 5

Если производительность не является большой проблемой, можно использовать два std :: set.

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