Запись сохраняемого экземпляра для CString с функцией O (1) для получения общей длины байта


Я пытаюсь написать хранимый вектор экземпляр для CString (в моем случае c-символы с нулевым окончанием). Хранимый экземпляр будет хранить указатели, которыми является строка CString (Ptr CChar). Таким образом, длина вектора-это число указателей CString. Теперь причина, по которой я пишу этот хранимый экземпляр, заключается в том, что он будет использоваться для выполнения нулевого копирования из FFI CString, а затем быстрого построения ByteString с использованием unsafeCreate (после некоторого преобразования-поэтому мы используем быстрые векторы здесь для промежуточных оперативный). Для быстрого построения ByteString необходимы три вещи для хранения экземпляра:

  • Total length in bytes-хранимый экземпляр должен иметь Book-Keeping выделение для хранения длины каждой CString при добавлении его к вектору, и общая длина CString хранится до сих пор. Допустим, общая длина строк C не может превышать 2^31. Таким образом, Int32/Word32 будет хранить длину каждой строки C и общую длину.
  • функция для хранения CString и его длина-O (n) время. Эта функция будет ходить по CString и хранить его длину, а также увеличивать общую длину на длину CString.
  • функция для возврата длины в общем количестве байт-O (1) раз. Эта функция просто извлекает значение из поля, в котором хранится общая длина

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

Обновление 1 (Уточнение)

Причина использования storable vector instance в моем случае двоякая: быстрое вычисление/преобразование с использованием распакованных типов (на данных реального времени, полученных через C FFI), и быстрое преобразование в bytestring (для отправки данных в реальном времени через IPC в другую программу). Для быстрого преобразования bytestring, unsafeCreate превосходно. Но, мы должны знать, сколько нужно выделите, а также, передайте ему функцию для преобразования. Учитывая экземпляр вектора с возможностью хранения (со смешанными типами - я упростил свой вопрос выше до типа CString), мне легко построить функцию быстрого преобразования, которая обходит каждый элемент вектора и преобразует его в bytestring. Затем мы просто передаем его unsafeCreate. Но, мы должны также передать ему количество байт, чтобы выделить. Функция вычисления рекурсивной длины байта O(n) слишком медленна и может удвоить накладные расходы на построение bytestring.

1   4   2011-12-11 18:39:54

1 ответ:

Похоже, вы хотите написать что-то вроде этого. Обратите внимание, что этот код не тестируется.

-- The basic type.  Export the type but not the constructors or 
-- accessors from the module.
data StringVector {
   strVecLength :: Word32,               -- Total length
   strVecContents [(Word32, Ptr CChar)]  -- (Length, value) pairs
}

-- Invariants: forall (StringVector len contents), 
--    len == sum (map fst) contents
--    all (\p -> fst p == c_strlen (snd p)) contents


-- The null case.
emptyStrVec :: StringVector
emptyStrVec = StringVector 0 []


-- Put a new Cstring at the head of the vector.  Analogous to ":".
stringVectorCons :: Ptr CChar -> StringVector -> StringVector
stringVectorCons ptr (StringVector len pairs) = 
   StringVector (len + n) $ (n, ptr) : pairs
   where
      n = c_strlen ptr   -- Or whatever the right function name is


-- Extract the head of the vector and the remaining vector.
stringVectorUncons :: StringVector -> ((Word32, Ptr CChar), StringVector)
stringVectorUncons (StringVector len (h:t)) =
   (h, StringVector (len - fst h) t)

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