Проблемы с переносимостью: выравнивание данных, проблемы с порядком байтов и т. Д. - PullRequest
2 голосов
/ 24 апреля 2011

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

Во-первых, позвольте мне объяснить, какие данные хранятся и где они хранятся.Итак, сначала несколько определений.Структура записи разбита на Каталог записей и Данные записи .

[Field count=N] [Field offset[0]] [...] [Field offset[N-1]] [Data for fields 0 to N]
  • Количество полей и смещения объединеныназывается каталогом записей.

  • Данные называются данными записи.

  • Число полей имеет тип uint16_t.

  • Смещение поля имеет тип uint16_t.

  • Поля данных могут обрабатываться как байтовый буфер переменной длины, на который указывает (uint8_t *) сдлина не менее N байтов.

  • Число полей не может превышать: 4095 или 0x0FFF (в старшем порядке).

Записихранится на странице:

  • Страницы имеют размер: 4096 байт.

  • На страницах необходимо хранить 2 байта данных для каждой записи.

  • Последние 6 байтов страницы хранят текущее смещение свободного пространства и данные для каталога слотов.Метаданные не имеют отношения к вопросу, поэтому я не буду никому утомлять подробностями.

Мы храним записи на странице, добавляя к смещению свободного места и добавляяк этому.Записи могут быть позже изменены и удалены.Это оставит неиспользуемые фрагменты пространства на странице.Эти данные не используются повторно до момента сжатия.

В данный момент мы сохраняем фрагментный байт 0x80 в неиспользуемом пространстве (поскольку свободное пространство не может превышать 0x0FFF, первый байт никогда не будет 0x80).

Однако это становится проблемой во время уплотнения.В итоге мы сканируем все, пока не получим первый байт, который не равен 0x80.Мы считаем это началом свободного пространства.К сожалению, это не переносимо и будет работать только на машинах с прямым порядком байтов.

Но просто для повторения этой проблемы проблема заключается в различении: 0x808000 и 0x800080, где первые два байта (читайсправа налево) два допустимых поля количества полей в зависимости от порядкового номера платформы.

Я хочу попробовать выровнять записи по четным байтам.У меня просто нет предвидения, чтобы увидеть, будет ли это правильным решением этой проблемы.

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

Затем возникает проблема маркировки фрагментов.Фрагменты создаются при удалении или изменении записи (увеличение / уменьшение на некоторое количество байтов).Я хотел сохранить то, что я бы назвал 2-байтовыми маркерами фрагмента: 0xFFFF.Но это кажется невозможным при изменении.

Вот где я застрял.Извините за многословное объяснение проблемы.Мы (мой партнер, это академическое задание) несколько раз боролись с проблемой неоднозначности данных, и она продолжает маскироваться под разные решения.

Любое понимание поможет.Я надеюсь, что постановка проблемы может быть выполнена.

1 Ответ

2 голосов
/ 24 апреля 2011

Я бы попробовал это:

  1. Выравнивание записей по крайней мере по 2-байтовым границам.
  2. Сканирование списка на наличие свободного места в виде списка uint16_t, а не символа, тогда ищи length & 0x8000.

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

...