Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/trunk/src/MLRISC/library/bitset.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/library/bitset.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 412 - (view) (download)

1 : monnier 411 (*
2 :     * Non growable dense set in bitvector format.
3 :     *
4 :     * -- Allen
5 :     *)
6 :    
7 : monnier 245 structure BitSet :> BITSET =
8 :     struct
9 :    
10 :     structure A = Word8Array
11 :     structure W = Word8
12 :     open A
13 :    
14 :     infix << >> & ||
15 :     infix sub
16 :    
17 :     type bitset = array
18 :    
19 :     val word = Word.fromInt
20 :     val int = Word.toInt
21 :     val op & = Word.andb
22 :     val op >> = Word.>>
23 :     val op << = W.<<
24 :    
25 :     fun create n = array((n+7) div 8, 0wx0)
26 :    
27 :     fun size a = length(a) * 8
28 :    
29 :     fun set (a, i) =
30 :     let val byte = int((word i) >> 0w3)
31 :     val mask = W.<< (0w1, (word i) & 0w7)
32 :     in update(a, byte, W.orb(a sub byte, mask)) end
33 :    
34 :     fun reset (a, i) =
35 :     let val byte = int((word i) >> 0w3)
36 :     val mask = W.notb(W.<< (0w1, (word i) & 0w7))
37 :     in update(a, byte, W.andb(a sub byte, mask)) end
38 :    
39 :     fun clear a = modify (fn _ => 0wx0) a
40 :    
41 :     fun copy (a) = tabulate (length a, fn i => a sub i)
42 :    
43 :     fun toString (a) =
44 :     let fun f i = if i < length a then W.toString(a sub i)::f(i+1) else []
45 :     val s = String.concat(f 0)
46 :     in "[" ^ s ^ "]" end
47 :    
48 :     fun contains (a, i) =
49 :     let val byte = int((word i) >> 0w3)
50 :     val mask = W.<<(0w1, (word i) & 0w7)
51 :     in W.andb(A.sub(a, byte), mask) <> 0wx0 end
52 :    
53 :     fun markAndTest (a, i) =
54 :     let val byte = int((word i) >> 0w3)
55 :     val mask = W.<<(0w1, (word i) & 0w7)
56 :     val word = A.sub(a,byte)
57 :     in if W.andb(word, mask) <> 0wx0 then
58 :     true
59 :     else
60 :     (A.update(a, byte, W.orb(word, mask)); false)
61 :     end
62 :    
63 :     fun unmarkAndTest (a, i) =
64 :     let val byte = int(word i >> 0w3)
65 :     val mask = W.<<(0w1, (word i) & 0w7)
66 :     val word = A.sub(a,byte)
67 :     in if W.andb(word, mask) <> 0wx0 then
68 :     (A.update(a, byte, W.andb(word,W.notb mask)); true)
69 :     else
70 :     false
71 :     end
72 :    
73 :     end
74 :    

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0