diff options
-rw-r--r-- | word64-map/src/Data/Word64Map.hs | 71 | ||||
-rw-r--r-- | word64-map/word64-map.cabal | 21 |
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 #-} |
4 | module 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 | -- | ||
17 | module Data.Word64Map | ||
18 | ( Word64Map | ||
19 | , fitsInInt | ||
20 | , Data.Word64Map.lookup | ||
21 | , insert | ||
22 | , delete | ||
23 | , size | ||
24 | , empty | ||
25 | ) where | ||
5 | 26 | ||
6 | import Data.Bits | 27 | import Data.Bits |
7 | import qualified Data.IntMap as IntMap | 28 | import qualified Data.IntMap as IntMap |
@@ -10,20 +31,44 @@ import Data.Monoid | |||
10 | import Data.Typeable | 31 | import Data.Typeable |
11 | import Data.Word | 32 | import 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'. | ||
19 | fitsInInt :: forall proxy word. (Bounded word, Integral word) => proxy word -> Bool | 42 | fitsInInt :: forall proxy word. (Bounded word, Integral word) => proxy word -> Bool |
20 | fitsInInt proxy = (original == casted) | 43 | fitsInInt 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 | ||
49 | newtype Word64Map a = Word64Map (IntMap a) | ||
50 | #else | ||
25 | newtype Word64Map a = Word64Map (IntMap (IntMap a)) | 51 | newtype Word64Map a = Word64Map (IntMap (IntMap a)) |
52 | #endif | ||
53 | |||
26 | 54 | ||
55 | #if KNOWN64 | ||
56 | size :: Word64Map a -> Int | ||
57 | size (Word64Map mp) = IntMap.size mp | ||
58 | {-# INLINE size #-} | ||
59 | empty :: Word64Map a | ||
60 | empty = Word64Map (IntMap.empty) | ||
61 | {-# INLINE empty #-} | ||
62 | lookup :: Word64 -> Word64Map b -> Maybe b | ||
63 | lookup key (Word64Map mp) = IntMap.lookup (fromIntegral key) mp | ||
64 | {-# INLINE lookup #-} | ||
65 | insert :: Word64 -> b -> Word64Map b -> Word64Map b | ||
66 | insert key val (Word64Map mp) = Word64Map (IntMap.insert (fromIntegral key) val mp) | ||
67 | {-# INLINE insert #-} | ||
68 | delete :: Word64 -> Word64Map b -> Word64Map b | ||
69 | delete key (Word64Map m) = Word64Map (IntMap.delete (fromIntegral key) m) | ||
70 | {-# INLINE delete #-} | ||
71 | #else | ||
27 | size :: Word64Map a -> Int | 72 | size :: Word64Map a -> Int |
28 | size (Word64Map m) = getSum $ foldMap (\n -> Sum (IntMap.size n)) m | 73 | size (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. |
34 | keyFrom64 :: Word64 -> (# Int,Int #) | 79 | keyFrom64 :: Word64 -> (# Int,Int #) |
35 | keyFrom64 w8 = | 80 | keyFrom64 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 | ||
41 | lookup :: Word64 -> Word64Map b -> Maybe b | 86 | lookup :: Word64 -> Word64Map b -> Maybe b |
42 | lookup w8 (Word64Map m) | (# hi,lo #) <- keyFrom64 w8 = do | 87 | lookup 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 | ||
47 | insert :: Word64 -> b -> Word64Map b -> Word64Map b | 92 | insert :: Word64 -> b -> Word64Map b -> Word64Map b |
48 | insert w8 b (Word64Map m) | (# hi,lo #) <- keyFrom64 w8 | 93 | insert 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 | ||
55 | delete :: Word64 -> Word64Map b -> Word64Map b | 100 | delete :: Word64 -> Word64Map b -> Word64Map b |
56 | delete w8 (Word64Map m) | (# hi,lo #) <- keyFrom64 w8 | 101 | delete 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 | ||
4 | name: word64-map | 4 | name: word64-map |
5 | version: 0.1.0.0 | 5 | version: 0.1.0.0 |
6 | -- synopsis: | 6 | synopsis: 64-bit Version of IntMap |
7 | -- description: | 7 | description: 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. | ||
8 | license: BSD3 | 14 | license: BSD3 |
9 | license-file: LICENSE | 15 | license-file: LICENSE |
10 | author: James Crayne | 16 | author: James Crayne |
11 | maintainer: jim.crayne@gmail.com | 17 | maintainer: James Crayne <jim.crayne@gmail.com> |
12 | -- copyright: | 18 | -- copyright: |
13 | -- category: | 19 | -- category: |
14 | build-type: Simple | 20 | build-type: Simple |
15 | extra-source-files: CHANGELOG.md | 21 | extra-source-files: CHANGELOG.md |
16 | cabal-version: >=1.10 | 22 | cabal-version: >=1.10 |
17 | 23 | ||
24 | |||
18 | library | 25 | library |
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 | ||