summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--word64-map/src/Data/Word64Map.hs71
-rw-r--r--word64-map/word64-map.cabal21
2 files changed, 75 insertions, 17 deletions
diff --git a/word64-map/src/Data/Word64Map.hs b/word64-map/src/Data/Word64Map.hs
index adc9c27e..4437ca05 100644
--- a/word64-map/src/Data/Word64Map.hs
+++ b/word64-map/src/Data/Word64Map.hs
@@ -1,7 +1,28 @@
1{-# LANGUAGE RankNTypes #-} 1{-# LANGUAGE RankNTypes #-}
2{-# LANGUAGE ScopedTypeVariables #-} 2{-# LANGUAGE ScopedTypeVariables #-}
3{-# LANGUAGE UnboxedTuples #-} 3{-# LANGUAGE UnboxedTuples #-}
4module Data.Word64Map where 4{-# LANGUAGE CPP #-}
5-- | This is a wrapper around 'Data.IntMap', from the containers package, but with a
6-- guaranteed bitwidth of 64 bits.
7--
8-- On 32 bit platforms, this is currently accomplished simply by composing two IntMaps.
9--
10-- On obvious 64 bit platforms(platform name as shown by System.Info.arch ends in 64), CPP
11-- is used and it is simply a newtype around IntMap.
12--
13-- If the CPP is not defined, the Word64Map will be a composition of two IntMaps, but it should
14-- work anyway provided Int is either 32 or 64 bits. Nevertheless, for highest guaranteed efficiency,
15-- report your platform so it can be detected and the CPP defined accordingly.
16--
17module Data.Word64Map
18 ( Word64Map
19 , fitsInInt
20 , Data.Word64Map.lookup
21 , insert
22 , delete
23 , size
24 , empty
25 ) where
5 26
6import Data.Bits 27import Data.Bits
7import qualified Data.IntMap as IntMap 28import qualified Data.IntMap as IntMap
@@ -10,20 +31,44 @@ import Data.Monoid
10import Data.Typeable 31import Data.Typeable
11import Data.Word 32import Data.Word
12 33
13-- | Since 'Int' may be 32 or 64 bits, this function is provided as a 34-- | Returns 'True' if the proxied type can be losslessly converted to 'Int' using
35-- 'fromIntegral'.
36--
37-- Since 'Int' may be 32 or 64 bits, this function is provided as a
14-- convenience to test if an integral type, such as 'Data.Word.Word64', can be 38-- convenience to test if an integral type, such as 'Data.Word.Word64', can be
15-- safely transformed into an 'Int' for use with 'IntMap'. 39-- safely transformed into an 'Int'.
16-- 40--
17-- Returns 'True' if the proxied type can be losslessly converted to 'Int' using 41-- It should be optimized away at runtime.
18-- 'fromIntegral'.
19fitsInInt :: forall proxy word. (Bounded word, Integral word) => proxy word -> Bool 42fitsInInt :: forall proxy word. (Bounded word, Integral word) => proxy word -> Bool
20fitsInInt proxy = (original == casted) 43fitsInInt proxy = (original == casted)
21 where 44 where
22 original = div maxBound 2 :: word 45 original = div maxBound 2 :: word
23 casted = fromIntegral (fromIntegral original :: Int) :: word 46 casted = fromIntegral (fromIntegral original :: Int) :: word
24 47
48#if KNOWN64
49newtype Word64Map a = Word64Map (IntMap a)
50#else
25newtype Word64Map a = Word64Map (IntMap (IntMap a)) 51newtype Word64Map a = Word64Map (IntMap (IntMap a))
52#endif
53
26 54
55#if KNOWN64
56size :: Word64Map a -> Int
57size (Word64Map mp) = IntMap.size mp
58{-# INLINE size #-}
59empty :: Word64Map a
60empty = Word64Map (IntMap.empty)
61{-# INLINE empty #-}
62lookup :: Word64 -> Word64Map b -> Maybe b
63lookup key (Word64Map mp) = IntMap.lookup (fromIntegral key) mp
64{-# INLINE lookup #-}
65insert :: Word64 -> b -> Word64Map b -> Word64Map b
66insert key val (Word64Map mp) = Word64Map (IntMap.insert (fromIntegral key) val mp)
67{-# INLINE insert #-}
68delete :: Word64 -> Word64Map b -> Word64Map b
69delete key (Word64Map m) = Word64Map (IntMap.delete (fromIntegral key) m)
70{-# INLINE delete #-}
71#else
27size :: Word64Map a -> Int 72size :: Word64Map a -> Int
28size (Word64Map m) = getSum $ foldMap (\n -> Sum (IntMap.size n)) m 73size (Word64Map m) = getSum $ foldMap (\n -> Sum (IntMap.size n)) m
29 74
@@ -32,20 +77,20 @@ empty = Word64Map IntMap.empty
32 77
33-- Warning: This function assumes an 'Int' is either 64 or 32 bits. 78-- Warning: This function assumes an 'Int' is either 64 or 32 bits.
34keyFrom64 :: Word64 -> (# Int,Int #) 79keyFrom64 :: Word64 -> (# Int,Int #)
35keyFrom64 w8 = 80keyFrom64 key =
36 if fitsInInt (Proxy :: Proxy Word64) 81 if fitsInInt (Proxy :: Proxy Word64)
37 then (# fromIntegral w8 , 0 #) 82 then (# fromIntegral key , 0 #)
38 else (# fromIntegral (w8 `shiftR` 32), fromIntegral w8 #) 83 else (# fromIntegral (key `shiftR` 32), fromIntegral key #)
39{-# INLINE keyFrom64 #-} 84{-# INLINE keyFrom64 #-}
40 85
41lookup :: Word64 -> Word64Map b -> Maybe b 86lookup :: Word64 -> Word64Map b -> Maybe b
42lookup w8 (Word64Map m) | (# hi,lo #) <- keyFrom64 w8 = do 87lookup key (Word64Map m) | (# hi,lo #) <- keyFrom64 key = do
43 m' <- IntMap.lookup hi m 88 m' <- IntMap.lookup hi m
44 IntMap.lookup lo m' 89 IntMap.lookup lo m'
45{-# INLINE lookup #-} 90{-# INLINE lookup #-}
46 91
47insert :: Word64 -> b -> Word64Map b -> Word64Map b 92insert :: Word64 -> b -> Word64Map b -> Word64Map b
48insert w8 b (Word64Map m) | (# hi,lo #) <- keyFrom64 w8 93insert key b (Word64Map m) | (# hi,lo #) <- keyFrom64 key
49 = Word64Map $ IntMap.alter (Just . maybe (IntMap.singleton lo b) 94 = Word64Map $ IntMap.alter (Just . maybe (IntMap.singleton lo b)
50 (IntMap.insert lo b)) 95 (IntMap.insert lo b))
51 hi 96 hi
@@ -53,7 +98,7 @@ insert w8 b (Word64Map m) | (# hi,lo #) <- keyFrom64 w8
53{-# INLINE insert #-} 98{-# INLINE insert #-}
54 99
55delete :: Word64 -> Word64Map b -> Word64Map b 100delete :: Word64 -> Word64Map b -> Word64Map b
56delete w8 (Word64Map m) | (# hi,lo #) <- keyFrom64 w8 101delete key (Word64Map m) | (# hi,lo #) <- keyFrom64 key
57 = Word64Map $ IntMap.alter (maybe Nothing 102 = Word64Map $ IntMap.alter (maybe Nothing
58 (\m' -> case IntMap.delete lo m' of 103 (\m' -> case IntMap.delete lo m' of
59 m'' | IntMap.null m'' -> Nothing 104 m'' | IntMap.null m'' -> Nothing
@@ -61,6 +106,4 @@ delete w8 (Word64Map m) | (# hi,lo #) <- keyFrom64 w8
61 hi 106 hi
62 m 107 m
63{-# INLINE delete #-} 108{-# INLINE delete #-}
64 109#endif
65
66
diff --git a/word64-map/word64-map.cabal b/word64-map/word64-map.cabal
index 938d2e22..576046e8 100644
--- a/word64-map/word64-map.cabal
+++ b/word64-map/word64-map.cabal
@@ -3,18 +3,25 @@
3 3
4name: word64-map 4name: word64-map
5version: 0.1.0.0 5version: 0.1.0.0
6-- synopsis: 6synopsis: 64-bit Version of IntMap
7-- description: 7description: This is a wrapper around 'Data.IntMap', from the containers package, but with a
8 guaranteed bitwidth of 64 bits.
9
10 On 32 bit platforms, this is currently accomplished simply by composing two IntMaps.
11
12 On obvious 64 bit platforms(platform name as shown by System.Info.arch ends in 64)
13 it is simply a newtype of IntMap.
8license: BSD3 14license: BSD3
9license-file: LICENSE 15license-file: LICENSE
10author: James Crayne 16author: James Crayne
11maintainer: jim.crayne@gmail.com 17maintainer: James Crayne <jim.crayne@gmail.com>
12-- copyright: 18-- copyright:
13-- category: 19-- category:
14build-type: Simple 20build-type: Simple
15extra-source-files: CHANGELOG.md 21extra-source-files: CHANGELOG.md
16cabal-version: >=1.10 22cabal-version: >=1.10
17 23
24
18library 25library
19 exposed-modules: Data.Word64Map 26 exposed-modules: Data.Word64Map
20 -- other-modules: 27 -- other-modules:
@@ -24,3 +31,11 @@ library
24 , containers 31 , containers
25 hs-source-dirs: src 32 hs-source-dirs: src
26 default-language: Haskell2010 33 default-language: Haskell2010
34 if arch(x86_64)
35 Cpp-options: -DKNOWN64
36 if arch(ppc64)
37 Cpp-options: -DKNOWN64
38 if arch(ia64)
39 Cpp-options: -DKNOWN64
40 if arch(arm64)
41 Cpp-options: -DKNOWN64