Bitmap.hsc

{-# LANGUAGE CApiFFI #-}

{-| Raw bindings to @roaring/roaring.h@ for 32-bit Roaring bitmaps, @roaring_bitmap_t@.

Each binding is the C function without its @roaring_bitmap_@ (or @roaring_@) prefix, camelCased.
The @_safe@ loaders only bound how far they read, so they are named @*Bounded@ here.
The @*Validated@ loaders also run 'internalValidate'.
Use them for bytes from outside the program.
Handles carry no ownership.
Release the bitmaps that C returns with 'free' or 'finalizerFree'.
A bitmap is not synchronised.
Concurrent use needs external locking.
-}
module Data.Bitmap.Roaring.FFI.Bitmap
  ( Bitmap (..)
  , size
  , alignment
  , create
  , createWithCapacity
  , initWithCapacity
  , initCleared
  , free
  , finalizerFree
  , with
  , fromRange
  , ofPtr
  , copy
  , overwrite
  , clear
  , getCopyOnWrite
  , setCopyOnWrite
  , containsShared
  , unshareAll
  , add
  , addChecked
  , addMany
  , addBulk
  , addRange
  , addRangeClosed
  , remove
  , removeChecked
  , removeMany
  , removeRange
  , removeRangeClosed
  , contains
  , containsBulk
  , containsRange
  , containsRangeClosed
  , getCardinality
  , rangeCardinality
  , rangeCardinalityClosed
  , isEmpty
  , minimum
  , maximum
  , select
  , rank
  , rankMany
  , getIndex
  , equals
  , isSubset
  , isStrictSubset
  , intersect
  , intersectWithRange
  , jaccardIndex
  , and
  , andInplace
  , andCardinality
  , or
  , orInplace
  , orCardinality
  , orMany
  , orManyHeap
  , xor
  , xorInplace
  , xorCardinality
  , xorMany
  , andnot
  , andnotInplace
  , andnotCardinality
  , lazyOr
  , lazyOrInplace
  , lazyXor
  , lazyXorInplace
  , repairAfterLazy
  , flip
  , flipClosed
  , flipInplace
  , flipInplaceClosed
  , addOffset
  , toUint32Array
  , rangeUint32Array
  , toBitset
  , wordRangeToBitset
  , runOptimize
  , removeRunCompression
  , shrinkToFit
  , statistics
  , getStatistics
  , internalValidate
  , sizeInBytes
  , serialize
  , deserialize
  , deserializeBounded
  , deserializeValidated
  , portableSizeInBytes
  , portableSerialize
  , portableDeserialize
  , portableDeserializeBounded
  , portableDeserializeValidated
  , portableDeserializeSize
  , portableDeserializeFrozen
  , frozenSizeInBytes
  , frozenSerialize
  , frozenView
  , withPortableFrozen
  , withFrozenView
  , Callback
  , wrapCallback
  , iterate
  , iterateWith
  , Callback64
  , wrapCallback64
  , iterate64
  , iterate64With
  , printf
  , printfDescribe
  ) where

#include <roaring/roaring.h>
#include <roaring/roaring_array.h>

import Prelude hiding (and, flip, iterate, maximum, minimum, or)

import Control.Exception (bracket)
import Data.Bitmap.Roaring.FFI.Bitmap.BulkContext (BulkContext (..))
import Data.Bitmap.Roaring.FFI.Bitmap.Statistics (Statistics)
import Data.Bitmap.Roaring.FFI.Bitset (Bitset (..))
import Data.Bitmap.Roaring.FFI.Callback qualified as Callback
import Data.Bitmap.Roaring.FFI.NullHandle qualified as NullHandle
import Data.Bits (shiftL, shiftR, testBit, (.&.), (.|.))
import Data.Int (Int64)
import Data.Word (Word32, Word64, Word8)
import Foreign.C.ConstPtr (ConstPtr (..))
import Foreign.C.Types (CChar, CSize (..))
import Foreign.ForeignPtr (FinalizerPtr)
import Foreign.Marshal.Alloc (alloca)
import Foreign.Marshal.Array (peekArray)
import Foreign.Ptr (FunPtr, Ptr, nullPtr, plusPtr)
import Foreign.Storable (Storable, peek)

{- | @roaring_bitmap_t@.

Its 'Storable' instance stores the pointer itself, so a @'Ptr' t'Bitmap'@ is a C array of bitmaps, as taken by 'orMany'.
-}
newtype Bitmap = Bitmap (Ptr Bitmap)
  deriving (Eq, Ord, Show, Storable)

-- | @sizeof(roaring_bitmap_t)@
size :: Int
size = #{size roaring_bitmap_t}
{-# INLINE size #-}

-- | @alignof(roaring_bitmap_t)@
alignment :: Int
alignment = #{alignment roaring_bitmap_t}
{-# INLINE alignment #-}

-- | @roaring_bitmap_create@: NULL on allocation failure.
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_create"
  create :: IO Bitmap

-- | @roaring_bitmap_create_with_capacity@: the capacity is a number of containers. NULL on allocation failure.
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_create_with_capacity"
  createWithCapacity :: Word32 -> IO Bitmap

{- | @roaring_bitmap_init_with_capacity@: initialises a bitmap in caller memory of 'size' bytes.
'False' if allocating the container array failed.

Such a bitmap must be released with 'clear', never with 'free'.
-}
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_init_with_capacity"
  initWithCapacity :: Bitmap -> Word32 -> IO Bool

-- | @roaring_bitmap_init_cleared@: initialises a bitmap in caller memory without allocating. Release it with 'clear', never with 'free'.
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_init_cleared"
  initCleared :: Bitmap -> IO ()

-- | @roaring_bitmap_free@: also releases read-only views.
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_free"
  free :: Bitmap -> IO ()

-- | @&roaring_bitmap_free@
foreign import capi unsafe "roaring/roaring.h &roaring_bitmap_free"
  finalizerFree :: FinalizerPtr Bitmap

-- | Frees the bitmap when the action ends. Throws t'NullHandle.NullHandle' if the constructor returns NULL.
with :: IO Bitmap -> (Bitmap -> IO a) -> IO a
with = NullHandle.bracket "Data.Bitmap.Roaring.FFI.Bitmap.with" free
{-# INLINE with #-}

{- | @roaring_bitmap_from_range@: @[min, max)@ every @step@ from @min@, @max@ capped at @2^32@.
NULL on failure, when @step@ is 0, and when the range is empty.
-}
foreign import capi safe "roaring/roaring.h roaring_bitmap_from_range"
  fromRange :: Word64 -> Word64 -> Word32 -> IO Bitmap

-- | @roaring_bitmap_of_ptr@: NULL on failure.
foreign import capi safe "roaring/roaring.h roaring_bitmap_of_ptr"
  ofPtr :: CSize -> Ptr Word32 -> IO Bitmap

-- | @roaring_bitmap_copy@: NULL on failure. With copy-on-write enabled, containers are shared rather than copied.
foreign import capi safe "roaring/roaring.h roaring_bitmap_copy"
  copy :: Bitmap -> IO Bitmap

{- | @roaring_bitmap_overwrite@: makes the first bitmap a copy of the second, copy-on-write flag included.
'False' on allocation failure.

After 'False', the first bitmap must not be used, cleared or freed.
C releases the first bitmap's containers before it allocates anything.
If growing its container array then fails, the bitmap keeps its old size over the released containers.

Passing the same bitmap twice leaves it unchanged and returns 'True'.
The C function would read the containers it has just released, so this binding does not call it.
-}
overwrite :: Bitmap -> Bitmap -> IO Bool
overwrite target source
  | target == source = pure True
  | otherwise = overwriteDistinct target source
{-# INLINE overwrite #-}

foreign import capi safe "roaring/roaring.h roaring_bitmap_overwrite"
  overwriteDistinct :: Bitmap -> Bitmap -> IO Bool

-- | @roaring_bitmap_clear@: also releases every container.
foreign import capi safe "roaring/roaring.h roaring_bitmap_clear"
  clear :: Bitmap -> IO ()

-- | @roaring_bitmap_get_copy_on_write@
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_get_copy_on_write"
  getCopyOnWrite :: Bitmap -> IO Bool

{- | @roaring_bitmap_set_copy_on_write@: enables or disables copy-on-write.
Disabling it unshares (copies) any shared containers.

Bitmaps that share containers must all have it enabled.
Such bitmaps look independent but touch the same memory, which matters across threads.
-}
foreign import capi safe "roaring/roaring.h roaring_bitmap_set_copy_on_write"
  setCopyOnWrite :: Bitmap -> Bool -> IO ()

-- | @roaring_contains_shared@
foreign import capi unsafe "roaring/roaring.h roaring_contains_shared"
  containsShared :: Bitmap -> IO Bool

-- | @roaring_unshare_all@: 'True' if anything was unshared.
foreign import capi safe "roaring/roaring.h roaring_unshare_all"
  unshareAll :: Bitmap -> IO Bool

-- | @roaring_bitmap_add@
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_add"
  add :: Bitmap -> Word32 -> IO ()

-- | @roaring_bitmap_add_checked@: 'True' if the value was absent.
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_add_checked"
  addChecked :: Bitmap -> Word32 -> IO Bool

-- | @roaring_bitmap_add_many@
foreign import capi safe "roaring/roaring.h roaring_bitmap_add_many"
  addMany :: Bitmap -> CSize -> Ptr Word32 -> IO ()

-- | @roaring_bitmap_add_bulk@: see "Data.Bitmap.Roaring.FFI.Bitmap.BulkContext" for the context's rules.
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_add_bulk"
  addBulk :: Bitmap -> BulkContext -> Word32 -> IO ()

-- | @roaring_bitmap_add_range@: @[min, max)@, @max@ capped at @2^32@.
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_add_range"
  addRange :: Bitmap -> Word64 -> Word64 -> IO ()

-- | @roaring_bitmap_add_range_closed@
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_add_range_closed"
  addRangeClosed :: Bitmap -> Word32 -> Word32 -> IO ()

-- | @roaring_bitmap_remove@
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_remove"
  remove :: Bitmap -> Word32 -> IO ()

-- | @roaring_bitmap_remove_checked@: 'True' if the value was present.
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_remove_checked"
  removeChecked :: Bitmap -> Word32 -> IO Bool

-- | @roaring_bitmap_remove_many@
foreign import capi safe "roaring/roaring.h roaring_bitmap_remove_many"
  removeMany :: Bitmap -> CSize -> Ptr Word32 -> IO ()

-- | @roaring_bitmap_remove_range@: @[min, max)@, @max@ capped at @2^32@.
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_remove_range"
  removeRange :: Bitmap -> Word64 -> Word64 -> IO ()

-- | @roaring_bitmap_remove_range_closed@
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_remove_range_closed"
  removeRangeClosed :: Bitmap -> Word32 -> Word32 -> IO ()

-- | @roaring_bitmap_contains@
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_contains"
  contains :: Bitmap -> Word32 -> IO Bool

-- | @roaring_bitmap_contains_bulk@: see "Data.Bitmap.Roaring.FFI.Bitmap.BulkContext" for the context's rules.
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_contains_bulk"
  containsBulk :: Bitmap -> BulkContext -> Word32 -> IO Bool

-- | @roaring_bitmap_contains_range@: @[start, end)@, @end@ capped at @2^32@.
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_contains_range"
  containsRange :: Bitmap -> Word64 -> Word64 -> IO Bool

-- | @roaring_bitmap_contains_range_closed@
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_contains_range_closed"
  containsRangeClosed :: Bitmap -> Word32 -> Word32 -> IO Bool

-- | @roaring_bitmap_get_cardinality@
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_get_cardinality"
  getCardinality :: Bitmap -> IO Word64

-- | @roaring_bitmap_range_cardinality@: @[start, end)@, @end@ capped at @2^32@.
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_range_cardinality"
  rangeCardinality :: Bitmap -> Word64 -> Word64 -> IO Word64

-- | @roaring_bitmap_range_cardinality_closed@
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_range_cardinality_closed"
  rangeCardinalityClosed :: Bitmap -> Word32 -> Word32 -> IO Word64

-- | @roaring_bitmap_is_empty@
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_is_empty"
  isEmpty :: Bitmap -> IO Bool

-- | @roaring_bitmap_minimum@: @UINT32_MAX@ when empty.
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_minimum"
  minimum :: Bitmap -> IO Word32

-- | @roaring_bitmap_maximum@: 0 when empty.
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_maximum"
  maximum :: Bitmap -> IO Word32

-- | @roaring_bitmap_select@: the rank is 0-based. 'False' when it is not below the cardinality.
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_select"
  select :: Bitmap -> Word32 -> Ptr Word32 -> IO Bool

-- | @roaring_bitmap_rank@: the number of values less than or equal to the given one.
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_rank"
  rank :: Bitmap -> Word32 -> IO Word64

-- | @roaring_bitmap_rank_many@: 'rank' of each value in the ascending array @[begin, end)@, written to the output array.
foreign import capi safe "roaring/roaring.h roaring_bitmap_rank_many"
  rankMany :: Bitmap -> Ptr Word32 -> Ptr Word32 -> Ptr Word64 -> IO ()

-- | @roaring_bitmap_get_index@: 0-based, or -1 when the value is absent.
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_get_index"
  getIndex :: Bitmap -> Word32 -> IO Int64

-- | @roaring_bitmap_equals@
foreign import capi safe "roaring/roaring.h roaring_bitmap_equals"
  equals :: Bitmap -> Bitmap -> IO Bool

-- | @roaring_bitmap_is_subset@: whether the first is a subset of the second.
foreign import capi safe "roaring/roaring.h roaring_bitmap_is_subset"
  isSubset :: Bitmap -> Bitmap -> IO Bool

-- | @roaring_bitmap_is_strict_subset@: whether the first is a strict subset of the second.
foreign import capi safe "roaring/roaring.h roaring_bitmap_is_strict_subset"
  isStrictSubset :: Bitmap -> Bitmap -> IO Bool

-- | @roaring_bitmap_intersect@
foreign import capi safe "roaring/roaring.h roaring_bitmap_intersect"
  intersect :: Bitmap -> Bitmap -> IO Bool

-- | @roaring_bitmap_intersect_with_range@: @[x, y)@, @y@ capped at @2^32@.
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_intersect_with_range"
  intersectWithRange :: Bitmap -> Word64 -> Word64 -> IO Bool

-- | @roaring_bitmap_jaccard_index@: NaN when both are empty.
foreign import capi safe "roaring/roaring.h roaring_bitmap_jaccard_index"
  jaccardIndex :: Bitmap -> Bitmap -> IO Double

-- | @roaring_bitmap_and@: NULL on failure.
foreign import capi safe "roaring/roaring.h roaring_bitmap_and"
  and :: Bitmap -> Bitmap -> IO Bitmap

-- | @roaring_bitmap_and_inplace@: the two may be the same bitmap.
foreign import capi safe "roaring/roaring.h roaring_bitmap_and_inplace"
  andInplace :: Bitmap -> Bitmap -> IO ()

-- | @roaring_bitmap_and_cardinality@
foreign import capi safe "roaring/roaring.h roaring_bitmap_and_cardinality"
  andCardinality :: Bitmap -> Bitmap -> IO Word64

-- | @roaring_bitmap_or@: NULL on failure.
foreign import capi safe "roaring/roaring.h roaring_bitmap_or"
  or :: Bitmap -> Bitmap -> IO Bitmap

-- | @roaring_bitmap_or_inplace@: passing the same bitmap twice leaves it unchanged.
orInplace :: Bitmap -> Bitmap -> IO ()
orInplace target other
  | target == other = pure ()
  | otherwise = orInplaceDistinct target other
{-# INLINE orInplace #-}

foreign import capi safe "roaring/roaring.h roaring_bitmap_or_inplace"
  orInplaceDistinct :: Bitmap -> Bitmap -> IO ()

-- | @roaring_bitmap_or_cardinality@
foreign import capi safe "roaring/roaring.h roaring_bitmap_or_cardinality"
  orCardinality :: Bitmap -> Bitmap -> IO Word64

-- | @roaring_bitmap_or_many@: NULL on failure.
foreign import capi safe "roaring/roaring.h roaring_bitmap_or_many"
  orMany :: CSize -> Ptr Bitmap -> IO Bitmap

-- | @roaring_bitmap_or_many_heap@: NULL on failure.
foreign import capi safe "roaring/roaring.h roaring_bitmap_or_many_heap"
  orManyHeap :: Word32 -> Ptr Bitmap -> IO Bitmap

-- | @roaring_bitmap_xor@: NULL on failure.
foreign import capi safe "roaring/roaring.h roaring_bitmap_xor"
  xor :: Bitmap -> Bitmap -> IO Bitmap

-- | @roaring_bitmap_xor_inplace@: passing the same bitmap twice clears it.
xorInplace :: Bitmap -> Bitmap -> IO ()
xorInplace target other
  | target == other = clear target
  | otherwise = xorInplaceDistinct target other
{-# INLINE xorInplace #-}

foreign import capi safe "roaring/roaring.h roaring_bitmap_xor_inplace"
  xorInplaceDistinct :: Bitmap -> Bitmap -> IO ()

-- | @roaring_bitmap_xor_cardinality@
foreign import capi safe "roaring/roaring.h roaring_bitmap_xor_cardinality"
  xorCardinality :: Bitmap -> Bitmap -> IO Word64

-- | @roaring_bitmap_xor_many@: NULL on failure.
foreign import capi safe "roaring/roaring.h roaring_bitmap_xor_many"
  xorMany :: CSize -> Ptr Bitmap -> IO Bitmap

-- | @roaring_bitmap_andnot@: first minus second. NULL on failure.
foreign import capi safe "roaring/roaring.h roaring_bitmap_andnot"
  andnot :: Bitmap -> Bitmap -> IO Bitmap

-- | @roaring_bitmap_andnot_inplace@: first minus second. Passing the same bitmap twice clears it.
andnotInplace :: Bitmap -> Bitmap -> IO ()
andnotInplace target other
  | target == other = clear target
  | otherwise = andnotInplaceDistinct target other
{-# INLINE andnotInplace #-}

foreign import capi safe "roaring/roaring.h roaring_bitmap_andnot_inplace"
  andnotInplaceDistinct :: Bitmap -> Bitmap -> IO ()

-- | @roaring_bitmap_andnot_cardinality@: the size of first minus second.
foreign import capi safe "roaring/roaring.h roaring_bitmap_andnot_cardinality"
  andnotCardinality :: Bitmap -> Bitmap -> IO Word64

{- | @roaring_bitmap_lazy_or@: NULL on failure.
The flag forces container results into bitsets.

The result is inconsistent until 'repairAfterLazy'.
Until then, pass it only to the lazy functions.
-}
foreign import capi safe "roaring/roaring.h roaring_bitmap_lazy_or"
  lazyOr :: Bitmap -> Bitmap -> Bool -> IO Bitmap

-- | @roaring_bitmap_lazy_or_inplace@: the first bitmap is inconsistent until 'repairAfterLazy'. Passing the same bitmap twice leaves it unchanged.
lazyOrInplace :: Bitmap -> Bitmap -> Bool -> IO ()
lazyOrInplace target other bitsetConversion
  | target == other = pure ()
  | otherwise = lazyOrInplaceDistinct target other bitsetConversion
{-# INLINE lazyOrInplace #-}

foreign import capi safe "roaring/roaring.h roaring_bitmap_lazy_or_inplace"
  lazyOrInplaceDistinct :: Bitmap -> Bitmap -> Bool -> IO ()

-- | @roaring_bitmap_lazy_xor@: NULL on failure. The result is inconsistent until 'repairAfterLazy'.
foreign import capi safe "roaring/roaring.h roaring_bitmap_lazy_xor"
  lazyXor :: Bitmap -> Bitmap -> IO Bitmap

-- | @roaring_bitmap_lazy_xor_inplace@: the first bitmap is inconsistent until 'repairAfterLazy'. Passing the same bitmap twice clears it.
lazyXorInplace :: Bitmap -> Bitmap -> IO ()
lazyXorInplace target other
  | target == other = clear target
  | otherwise = lazyXorInplaceDistinct target other
{-# INLINE lazyXorInplace #-}

foreign import capi safe "roaring/roaring.h roaring_bitmap_lazy_xor_inplace"
  lazyXorInplaceDistinct :: Bitmap -> Bitmap -> IO ()

-- | @roaring_bitmap_repair_after_lazy@
foreign import capi safe "roaring/roaring.h roaring_bitmap_repair_after_lazy"
  repairAfterLazy :: Bitmap -> IO ()

-- | @roaring_bitmap_flip@: @[start, end)@, @end@ capped at @2^32@. NULL on failure.
foreign import capi safe "roaring/roaring.h roaring_bitmap_flip"
  flip :: Bitmap -> Word64 -> Word64 -> IO Bitmap

-- | @roaring_bitmap_flip_closed@: NULL on failure.
foreign import capi safe "roaring/roaring.h roaring_bitmap_flip_closed"
  flipClosed :: Bitmap -> Word32 -> Word32 -> IO Bitmap

-- | @roaring_bitmap_flip_inplace@: @[start, end)@, @end@ capped at @2^32@.
foreign import capi safe "roaring/roaring.h roaring_bitmap_flip_inplace"
  flipInplace :: Bitmap -> Word64 -> Word64 -> IO ()

-- | @roaring_bitmap_flip_inplace_closed@
foreign import capi safe "roaring/roaring.h roaring_bitmap_flip_inplace_closed"
  flipInplaceClosed :: Bitmap -> Word32 -> Word32 -> IO ()

-- | @roaring_bitmap_add_offset@: NULL on failure. Values shifted outside @[0, 2^32)@ are dropped.
foreign import capi safe "roaring/roaring.h roaring_bitmap_add_offset"
  addOffset :: Bitmap -> Int64 -> IO Bitmap

-- | @roaring_bitmap_to_uint32_array@: the output must hold 'getCardinality' values.
foreign import capi safe "roaring/roaring.h roaring_bitmap_to_uint32_array"
  toUint32Array :: Bitmap -> Ptr Word32 -> IO ()

-- | @roaring_bitmap_range_uint32_array@: up to @limit@ values from the 0-based @offset@, both truncated to 32 bits. Always returns 'True', so it does not tell how many values it wrote.
foreign import capi safe "roaring/roaring.h roaring_bitmap_range_uint32_array"
  rangeUint32Array :: Bitmap -> CSize -> CSize -> Ptr Word32 -> IO Bool

-- | @roaring_bitmap_to_bitset@: the bitset must be empty. 'False' on allocation failure.
foreign import capi safe "roaring/roaring.h roaring_bitmap_to_bitset"
  toBitset :: Bitmap -> Bitset -> IO Bool

{- | @roaring_bitmap_word_range_to_bitset@: writes @n_words@ 64-bit words, starting at word @first_word@.
Value @64 * (first_word + k) + i@ sets bit @i@ of word @k@.
All words are overwritten.
The sum @first_word + n_words@ must not exceed @2^26@.
-}
foreign import capi safe "roaring/roaring.h roaring_bitmap_word_range_to_bitset"
  wordRangeToBitset :: Bitmap -> Word32 -> Word32 -> Ptr Word64 -> IO ()

{- | @roaring_bitmap_run_optimize@: converts containers to or from runs, whichever is smaller.
'True' if the result has a run container.

Adding or removing single values never converts a run container to another kind.
Call it again after many such edits to recover the space.
-}
foreign import capi safe "roaring/roaring.h roaring_bitmap_run_optimize"
  runOptimize :: Bitmap -> IO Bool

-- | @roaring_bitmap_remove_run_compression@: 'True' if anything changed.
foreign import capi safe "roaring/roaring.h roaring_bitmap_remove_run_compression"
  removeRunCompression :: Bitmap -> IO Bool

-- | @roaring_bitmap_shrink_to_fit@: returns the bytes saved.
foreign import capi safe "roaring/roaring.h roaring_bitmap_shrink_to_fit"
  shrinkToFit :: Bitmap -> IO CSize

-- | @roaring_bitmap_statistics@
foreign import capi safe "roaring/roaring.h roaring_bitmap_statistics"
  statistics :: Bitmap -> Ptr Statistics -> IO ()

getStatistics :: Bitmap -> IO Statistics
getStatistics bitmap =
  alloca $ \ptr -> do
    statistics bitmap ptr
    peek ptr

{- | @roaring_bitmap_internal_validate@: checks the internal invariants.
'True' if the bitmap is consistent.
If a check fails and the pointer is not NULL, the pointer receives a static C string that names the first problem.
The caller does not free that string.

Unless the bytes are known to come from a serialised bitmap, the loaded bitmap must pass this before any other use.
Lazy results fail it until 'repairAfterLazy'.
-}
foreign import capi safe "roaring/roaring.h roaring_bitmap_internal_validate"
  internalValidate :: Bitmap -> Ptr (ConstPtr CChar) -> IO Bool

-- | @roaring_bitmap_size_in_bytes@
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_size_in_bytes"
  sizeInBytes :: Bitmap -> IO CSize

-- | @roaring_bitmap_serialize@: CRoaring's own format, which other Roaring implementations cannot read. The buffer must hold 'sizeInBytes'.
foreign import capi safe "roaring/roaring.h roaring_bitmap_serialize"
  serialize :: Bitmap -> Ptr CChar -> IO CSize

{- | @roaring_bitmap_deserialize@: NULL on failure.

It takes no length, so a malformed or truncated buffer can make it read past the end.
-}
foreign import capi safe "roaring/roaring.h roaring_bitmap_deserialize"
  deserialize :: Ptr () -> IO Bitmap

{- | @roaring_bitmap_deserialize_safe@: reads at most the given number of bytes.
NULL on failure.

Only the reads are bounded.
Bytes that did not come from 'serialize' can still yield a broken bitmap.
Until 'internalValidate' accepts it, such a bitmap can give wrong answers, crash or corrupt memory.
-}
foreign import capi safe "roaring/roaring.h roaring_bitmap_deserialize_safe"
  deserializeBounded :: Ptr () -> CSize -> IO Bitmap

{- | Runs 'deserializeBounded', then 'internalValidate'.
'Nothing' when the bytes are truncated, malformed or fail validation.
After 'Nothing', there is nothing to free.
-}
deserializeValidated :: Ptr () -> CSize -> IO (Maybe Bitmap)
deserializeValidated buffer limit = deserializeBounded buffer limit >>= validated

-- | @roaring_bitmap_portable_size_in_bytes@
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_portable_size_in_bytes"
  portableSizeInBytes :: Bitmap -> IO CSize

-- | @roaring_bitmap_portable_serialize@: the buffer must hold 'portableSizeInBytes'.
foreign import capi safe "roaring/roaring.h roaring_bitmap_portable_serialize"
  portableSerialize :: Bitmap -> Ptr CChar -> IO CSize

{- | @roaring_bitmap_portable_deserialize@: NULL on failure.

It takes no length, so a malformed or truncated buffer can make it read past the end.
-}
foreign import capi safe "roaring/roaring.h roaring_bitmap_portable_deserialize"
  portableDeserialize :: Ptr CChar -> IO Bitmap

{- | @roaring_bitmap_portable_deserialize_safe@: reads at most the given number of bytes.
NULL on failure.

Only the reads are bounded.
Bytes that did not come from a portable serialiser can still yield a broken bitmap.
Until 'internalValidate' accepts it, such a bitmap can give wrong answers, crash or corrupt memory.
-}
foreign import capi safe "roaring/roaring.h roaring_bitmap_portable_deserialize_safe"
  portableDeserializeBounded :: Ptr CChar -> CSize -> IO Bitmap

{- | Runs 'portableDeserializeBounded', then 'internalValidate'.
'Nothing' when the bytes are truncated, malformed or fail validation.
After 'Nothing', there is nothing to free.
-}
portableDeserializeValidated :: Ptr CChar -> CSize -> IO (Maybe Bitmap)
portableDeserializeValidated buffer limit = portableDeserializeBounded buffer limit >>= validated

validated :: Bitmap -> IO (Maybe Bitmap)
validated bitmap
  | bitmap == Bitmap nullPtr = pure Nothing
  | otherwise = do
      valid <- internalValidate bitmap nullPtr
      if valid then pure $ Just bitmap else Nothing <$ free bitmap

-- | @roaring_bitmap_portable_deserialize_size@: reads at most the given number of bytes. Returns 0 if the whole bitmap does not fit in them or is malformed.
foreign import capi safe "roaring/roaring.h roaring_bitmap_portable_deserialize_size"
  portableDeserializeSize :: Ptr CChar -> CSize -> IO CSize

{- | @roaring_bitmap_portable_deserialize_frozen@: a read-only view into the portable-format buffer.
NULL on failure and on big-endian hosts.

It takes no length, so a malformed or truncated buffer can make it read past the end.
The buffer must stay alive and unmodified until 'free' releases the view.
The view must not be modified.
-}
foreign import capi safe "roaring/roaring.h roaring_bitmap_portable_deserialize_frozen"
  portableDeserializeFrozen :: Ptr CChar -> IO Bitmap

-- | @roaring_bitmap_frozen_size_in_bytes@
foreign import capi unsafe "roaring/roaring.h roaring_bitmap_frozen_size_in_bytes"
  frozenSizeInBytes :: Bitmap -> IO CSize

{- | @roaring_bitmap_frozen_serialize@: the format mirrors the in-memory layout, so it depends on the CRoaring version and host endianness.
The buffer must hold 'frozenSizeInBytes'.
-}
foreign import capi safe "roaring/roaring.h roaring_bitmap_frozen_serialize"
  frozenSerialize :: Bitmap -> Ptr CChar -> IO ()

{- | @roaring_bitmap_frozen_view@: a @const@ bitmap viewing a 'frozenSerialize' buffer of exactly the given length.
NULL on failure, including when the buffer is not 32-byte aligned.

Only the header is checked, so a buffer that did not come from 'frozenSerialize' can yield a bitmap that misbehaves.
Pass @v'Bitmap' ('unConstPtr' view)@ to read-only functions and to 'free'.
Modifying the view is undefined behaviour.
The buffer must stay alive and unmodified until 'free' releases the view.
-}
foreign import capi safe "roaring/roaring.h roaring_bitmap_frozen_view"
  frozenView :: Ptr CChar -> CSize -> IO (ConstPtr Bitmap)

{- | Validates a 'portableDeserializeFrozen' view of a whole bitmap within the given number of bytes, and frees it when the action ends.
'Nothing' when the bytes do not hold a valid bitmap, and on big-endian hosts.

Before it makes the view, it checks that the container offsets in the header stay within those bytes.
C follows these offsets without checks.

The buffer must stay unmodified during the action.
The view must not be modified, and must not escape the action.
-}
withPortableFrozen :: Ptr CChar -> CSize -> (Bitmap -> IO a) -> IO (Maybe a)
withPortableFrozen buffer limit action = do
  whole <- portableDeserializeSize buffer limit
  contained <- if whole == 0 then pure False else payloadsWithin buffer $ fromIntegral whole
  if contained then viewing (portableDeserializeFrozen buffer) action else pure Nothing

payloadsWithin :: Ptr CChar -> Word64 -> IO Bool
payloadsWithin buffer whole = do
  cookie <- littleEndian buffer 0 4
  let runFlagged = cookie .&. 0xFFFF == #{const SERIAL_COOKIE}
  count <- if runFlagged then pure $ cookie `shiftR` 16 + 1 else littleEndian buffer 4 4
  let
    descriptors = if runFlagged then 4 + (count + 7) `div` 8 else 8
    offsets = descriptors + 4 * count
    containersFrom index
      | index == count = pure True
      | otherwise = do
          within <- payloadWithin index
          if within then containersFrom $ index + 1 else pure False
    payloadWithin index = do
      cardinality <- (+ 1) <$> littleEndian buffer (descriptors + 4 * index + 2) 2
      offset <- littleEndian buffer (offsets + 4 * index) 4
      run <- isRun index
      if run then runsWithin offset else pure $ offset + arrayOrBitsetBytes cardinality <= whole
    isRun index
      | runFlagged = (`testBit` fromIntegral (index `mod` 8)) <$> littleEndian buffer (4 + index `div` 8) 1
      | otherwise = pure False
    runsWithin offset
      | offset + 2 > whole = pure False
      | otherwise = do
          runs <- littleEndian buffer offset 2
          pure $ offset + 2 + 4 * runs <= whole
  if runFlagged && count < #{const NO_OFFSET_THRESHOLD} then pure True else containersFrom 0
  where
    arrayOrBitsetBytes cardinality
      | cardinality > #{const DEFAULT_MAX_SIZE} = 8 * #{const BITSET_CONTAINER_SIZE_IN_WORDS}
      | otherwise = 2 * cardinality

littleEndian :: Ptr CChar -> Word64 -> Int -> IO Word64
littleEndian buffer at width = foldr prepend 0 <$> peekArray width (buffer `plusPtr` fromIntegral at :: Ptr Word8)
  where
    prepend byte rest = rest `shiftL` 8 .|. fromIntegral byte

{- | Validates a 'frozenView' of a buffer of exactly the given length, and frees it when the action ends.

'Nothing' when the bytes do not hold a valid bitmap or the buffer is not 32-byte aligned.
The buffer must stay unmodified during the action.
The view must not be modified, and must not escape the action.
-}
withFrozenView :: Ptr CChar -> CSize -> (Bitmap -> IO a) -> IO (Maybe a)
withFrozenView buffer bytes = viewing $ Bitmap . unConstPtr <$> frozenView buffer bytes

viewing :: IO Bitmap -> (Bitmap -> IO a) -> IO (Maybe a)
viewing construct action = bracket (construct >>= validated) (mapM_ free) $ traverse action

-- | @roaring_iterator@: returning 'False' stops the iteration.
type Callback = Word32 -> Ptr () -> IO Bool

-- | Release the result with 'Foreign.Ptr.freeHaskellFunPtr'.
foreign import ccall "wrapper"
  wrapCallback :: Callback -> IO (FunPtr Callback)

-- | @roaring_iterate@: 'True' if the callback never stopped the iteration.
foreign import capi safe "roaring/roaring.h roaring_iterate"
  iterate :: Bitmap -> FunPtr Callback -> Ptr () -> IO Bool

-- | @roaring_iterator64@: returning 'False' stops the iteration.
type Callback64 = Word64 -> Ptr () -> IO Bool

-- | Release the result with 'Foreign.Ptr.freeHaskellFunPtr'.
foreign import ccall "wrapper"
  wrapCallback64 :: Callback64 -> IO (FunPtr Callback64)

{- | @roaring_iterate64@: each value is widened and OR-ed with the given word.
The word is not shifted.
To place a key in the upper half, pass @key * 2^32@.
-}
foreign import capi safe "roaring/roaring.h roaring_iterate64"
  iterate64 :: Bitmap -> FunPtr Callback64 -> Word64 -> Ptr () -> IO Bool

{- | Runs 'iterate' with a Haskell function.
'True' if the function never returned 'False'.

An exception from the function stops the iteration and is rethrown after it, instead of unwinding through C.
Each value costs a call into Haskell, about 100 ns.
For reading in bulk, 'Data.Bitmap.Roaring.FFI.Bitmap.Iterator.read' is much faster.
-}
iterateWith :: Bitmap -> (Word32 -> IO Bool) -> IO Bool
iterateWith bitmap visit = Callback.with wrapCallback visit $ \callback -> iterate bitmap callback nullPtr

-- | Like 'iterateWith', but for 'iterate64'. Each value is OR-ed with the given word.
iterate64With :: Bitmap -> Word64 -> (Word64 -> IO Bool) -> IO Bool
iterate64With bitmap highBits visit = Callback.with wrapCallback64 visit $ \callback -> iterate64 bitmap callback highBits nullPtr

-- | @roaring_bitmap_printf@: writes to C's @stdout@.
foreign import capi safe "roaring/roaring.h roaring_bitmap_printf"
  printf :: Bitmap -> IO ()

-- | @roaring_bitmap_printf_describe@: writes to C's @stdout@.
foreign import capi safe "roaring/roaring.h roaring_bitmap_printf_describe"
  printfDescribe :: Bitmap -> IO ()