Changeset 11831 for third-party

Timestamp:

07/31/06 08:11:22 (2 years ago)

Author:

cmarcelo

Message:

* Judy.Map2: toRevList. And TODO updates.

Location:

third-party/HsJudy

Files:

• Judy/Map2.hs (modified) (5 diffs)
• TODO (modified) (3 diffs)
• tests/CheckDup.results (modified) (1 diff)
• tests/TestMap2.hs (modified) (6 diffs)

third-party/HsJudy/Judy/Map2.hs

@@ -3 +3 @@
 module Judy.Map2 (
     Map2 (..),
-    swapMaps, freeze
+    swapMaps, freeze, toRevList
 ) where
 
@@ -160 +160 @@
 --    return $ r
 
+
+internalMap' :: (Ptr Value -> Ptr Value -> IO b) -> Map2 k a -> IO [b]
+internalMap' f (Map2 j) = do
+    jj <- withForeignPtr j peek
+    alloca $ \vp -> do
+        poke vp (0 :: Value)
+        let loop act xs = do
+            r <- act jj vp judyError
+            if r == nullPtr
+                then return xs
+                else do x <- f r vp
+                        loop judyLNext (x:xs)
+        loop judyLFirst []
+
 internalMap :: (Ptr Value -> Ptr Value -> IO b) -> Map2 k a -> IO [b]
 internalMap f (Map2 j) = do
@@ -171 +185 @@
                 else do x <- f r vp
                         loop judyLPrev (x:xs)
-        loop judyLLast []
+        loop judyLLast [] -- Because of list concat we go backwards
+                          -- to get ordered list right.
 
 mapToList_ :: (ReversibleHashIO k, Refeable a) => (k -> a -> b) -> Map2 k a -> IO [b]
@@ -181 +196 @@
     return $ f k' v'
 
+mapToRevList_ :: (ReversibleHashIO k, Refeable a) => (k -> a -> b) -> Map2 k a -> IO [b]
+mapToRevList_ f = internalMap' $ \r vp -> do
+    k <- peek vp
+    k' <- unHashIO k
+    v <- peek r
+    v' <- fromRef v
+    return $ f k' v'
+
 toList_ :: (ReversibleHashIO k, Refeable a) => Map2 k a -> IO [(k,a)]
 toList_ = mapToList_ $ \k a -> (k,a)
+
+toRevList :: (ReversibleHashIO k, Refeable a) => Map2 k a -> IO [(k,a)]
+toRevList = mapToRevList_ $ \k a -> (k,a)
 
 keys_ :: ReversibleHashIO k => Map2 k a -> IO [k]
@@ -201 +227 @@
         poke p1 v2
         poke p2 v1
-
-
-
-
-

third-party/HsJudy/TODO

@@ -1 +1 @@
 # TODO
-- Use Judy to implement Pugs IHash substitute. (First patch done, but it's old by now)
+- Use Judy for Hash and Array in Pugs. Maybe creating some special
+  operators for Judy.Map2 to be used for Array (think shift and pop).
 - CollectionsM: complete the subset of MapM and uncomment/complete CollectionM.
 - See if needGC hack can be improved. It seems its eating CPU time.
 
 - First RBR test: 1/3 running time when using MapL (via Map2). Not sure
-if the results are correct (they seem to be).
-- Should I call MapSL and Map2 just Map?
+  if the results are correct (they seem to be). Check with Ketil about usage
+  of Map2, if its enough.
+
+- Names names names
+  - Idea: Map2 -> IntMap
+  - Should I call MapSL just Map too?
+
 - Other missing malloc error checking
 - Tests that stress MiniGC (w/ two maps at same time would be nice too)
+
 - Check how GHC do interning
+- Check how's sparse array implementation of Parrot.
 
-# "CRAZY" BUGS
-- Dummy/Refeable Bug: need to ask in #haskell and reply Simon's email.
-X Bug on HSIter stuff when use a lot of memory. (One of them is solved. Need to GC now.)
+# "CRAZY" BUGS (X means "solved")
+X Dummy/Refeable Bug: need to ask in #haskell and reply Simon's email.
+  It dissapeared recently. Dunno the reason.
+X Bug on HSIter stuff when use a lot of memory.
 X Finalizer may be not working right => test with sequencing a lot of operations
-  causes error in GHC runtime. (seems to be fixed by having ONLY ONE gc for everyone)
+  causes error in GHC runtime. (seems to be fixed by having ONLY ONE gc
+  for everyone)
 
 
@@ -25 +35 @@
   on the page (are they updated?).
 - Implementations specific to unboxed values like Int and Double: Int seems to
-  be ok now, but Double and other unboxed still need to check
+  be ok now, but Double and other unboxable still need to check
 
 - Discuss APIs
--- Unbounded arrays: see Bulat work on this
+-- Unbounded arrays: see Bulat work on this.
 
 - Refeable vs. HashIO => unify?
@@ -70 +80 @@
 Bulat says "sorry, i don't think so. especially for Arrays ;)"
 
+Judy is useful for applications for (very-)sparse Arrays, which is Pugs' case.
+

third-party/HsJudy/tests/CheckDup.results

@@ -17 +17 @@
 6 Judy.MapSL     ByteString Int     0.642
 7 Data.HashTable String Int         2.790
-8 Data.HashTable String Int         3.809 
+8 Data.HashTable ByteString Int     3.809 
 

third-party/HsJudy/tests/TestMap2.hs

@@ -20 +20 @@
     testSwapMaps
     testAlter
+    testRevList
 
 testSimple = do
@@ -62 +63 @@
     say "Elems"
     s <- new :: IO (Map2 Int Int)
-    elems s .-= []
+    elems s .=> []
     insert 3 42 s
     insert 37 1 s
     insert 0 2 s
-    elems s .-= [1,2,42]
+    elems s .=> [2,42,1]
 
 testKeys = do
@@ -75 +76 @@
     insert 37 1 s
     insert 0 2 s
-    keys s .-= [0,3,37]
+    keys s .=> [0,3,37]
     delete 37 s
     delete 15 s
-    keys s .-= [0,3]
+    keys s .=> [0,3]
 
 testStringValue = do
@@ -87 +88 @@
     insert 22 "string" s
     insert 59 "i am not a number" s
-    toList s    .-= [(22, "string"), (59,"i am not a number")] 
+    toList s    .=> [(22, "string"), (59,"i am not a number")] 
     member 22 s .=> True
 
@@ -102 +103 @@
     insert 23 "string" s
     insert 59 "i am not a number" s
-    toList s    .-= [(22, "string"), (23, "string"), (59,"i am not a number")] 
+    toList s .=> [(22, "string"), (23, "string"), (59,"i am not a number")] 
     member 22 s .=> True
 
@@ -138 +139 @@
     lookup 1 m .=> Nothing
 
+testRevList = do
+    say "RevList"
+    let l = [(1,2), (2,3), (4,5)]
+    m <- fromList l :: IO (J.Map2 Int Int)
+    J.toRevList m .=> reverse l
+
+    insert 3 10 m
+    J.toRevList m .=> reverse (sort $ (3,10):l)
+
 -- TODO: test some crazy haskell type as value (to check stableptrs)