Написание хранимого экземпляра для CString с функцией O (1) для получения полной длины байта - PullRequest
Новая
       34

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

4 голосов
/ 11 декабря 2011

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

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

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

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

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

1 Ответ

1 голос
/ 11 декабря 2011

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

-- 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)

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

...