Haskell – use the O (1) function to write a storable instance of CString to get the total byte length
I'm trying to write an instance of storable vector for CString (in my example, C characters ending in null) The storable instance will store the pointer referred to by CString (PTR cchar) Therefore, the length of the vector is the number of CString pointers Now, the reason why I write this storable instance is that it will be used for zero copy from FFI CString, and then use unsafecreate for fast bytestring construction (after some transformations - so we use fast vectors here for intermediate operations) In order to quickly build bytestring, storable instances need three things:
>Total length (in bytes) – storable instances need to have a bookkeeping allocation to store the length of each CString when adding each CString to the vector and the total length of cstrings stored so far Let's say that the total length of C string cannot exceed 2 ^ 31 Therefore, int32 / word32 will be used to store the length and total length of each CString. > The function that stores CString and its length - O (n) time This function will traverse the CString, store its length, and increase the total length by the length of the CString. > Functon returns length - O (1) time in total bytes This function will only retrieve the value from the field that stores the total length
Although I know how to write custom storable instances, I don't know how to deal with this situation A simple code (which can be a simple toy example) showing how to customize bookkeeping and write the function of storing / obtaining bookkeeping results will be appreciated
Update 1 (clarification)
There are two reasons for using storable vector instances in my case: using fast calculation / conversion of unboxed types (real-time data received through C FFI) and fast conversion to bytestring (sending data in real time) IPC to another program) Unsafecreate is very good for fast byte string conversion However, we must know how much to allocate and pass a conversion function Given a storable vector instance (using mixed types – I'll simplify the above problem to CString type), I can easily build a fast conversion function that can traverse each element of the vector and convert it to bytestring Then we pass it to unsafecreate However, we must also pass the number of bytes it wants to allocate O (n) recursive byte length calculation function is too slow and can double the overhead of constructing byte string
Solution
Sounds like you want to write something like this Note that this code has not been tested
-- 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)
After that, you can add any other functions you may need according to the application Just make sure that each function retains invariants