Left: | ||
Right: |
LEFT | RIGHT |
---|---|
1 // Copyright 2013 The Go Authors. All rights reserved. | 1 // Copyright 2013 The Go Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style | 2 // Use of this source code is governed by a BSD-style |
3 // license that can be found in the LICENSE file. | 3 // license that can be found in the LICENSE file. |
4 | 4 |
5 #include <u.h> | 5 #include <u.h> |
6 #include <libc.h> | 6 #include <libc.h> |
7 #include "go.h" | 7 #include "go.h" |
8 | 8 |
9 enum { | 9 enum { |
10 WORDSIZE = sizeof(uint32), | 10 WORDSIZE = sizeof(uint32), |
11 » WORDSIZELOG2 = 2, | 11 » WORDBITS = 32, |
12 » WORDBITS = WORDSIZE << WORDSIZELOG2, | |
iant
2013/05/22 00:41:00
I may be misreading, but WORDSIZE == 4, so this ma
cshapiro1
2013/05/22 06:35:21
You are right. I have revised these definitions.
| |
13 }; | 12 }; |
14 | 13 |
15 static uintptr | 14 uintptr |
16 size(uintptr n) | 15 bvsize(uintptr n) |
iant
2013/05/22 00:41:00
s/size/bvsize/
cshapiro1
2013/05/22 06:35:21
Sure, renamed.
| |
17 { | 16 { |
18 return ((n + WORDBITS - 1) / WORDBITS) * WORDSIZE; | 17 return ((n + WORDBITS - 1) / WORDBITS) * WORDSIZE; |
19 } | 18 } |
20 | 19 |
21 Bvec* | 20 Bvec* |
22 bvalloc(int32 n) | 21 bvalloc(int32 n) |
23 { | 22 { |
24 Bvec *bv; | 23 Bvec *bv; |
25 uintptr nbytes; | 24 uintptr nbytes; |
26 | 25 |
27 if(n < 0) | 26 if(n < 0) |
28 fatal("bvalloc: initial size is negative\n"); | 27 fatal("bvalloc: initial size is negative\n"); |
29 » nbytes = sizeof(Bvec) + size(n); | 28 » nbytes = sizeof(Bvec) + bvsize(n); |
30 bv = malloc(nbytes); | 29 bv = malloc(nbytes); |
31 if(bv == nil) | 30 if(bv == nil) |
32 fatal("bvalloc: malloc failed\n"); | 31 fatal("bvalloc: malloc failed\n"); |
33 memset(bv, 0, nbytes); | 32 memset(bv, 0, nbytes); |
34 bv->n = n; | 33 bv->n = n; |
35 return bv; | 34 return bv; |
36 } | 35 } |
37 | 36 |
38 void | 37 void |
39 bvset(Bvec *bv, int32 i) | 38 bvset(Bvec *bv, int32 i) |
(...skipping 19 matching lines...) Expand all Loading... | |
59 | 58 |
60 int | 59 int |
61 bvget(Bvec *bv, int32 i) | 60 bvget(Bvec *bv, int32 i) |
62 { | 61 { |
63 uint32 mask, word; | 62 uint32 mask, word; |
64 | 63 |
65 if(i < 0 || i >= bv->n) | 64 if(i < 0 || i >= bv->n) |
66 fatal("bvget: index %d is out of bounds with length %d\n", i, bv ->n); | 65 fatal("bvget: index %d is out of bounds with length %d\n", i, bv ->n); |
67 mask = 1 << (i % WORDBITS); | 66 mask = 1 << (i % WORDBITS); |
68 word = bv->b[i / WORDBITS] & mask; | 67 word = bv->b[i / WORDBITS] & mask; |
69 » return (word ? 1 : 0); | 68 » return word ? 1 : 0; |
iant
2013/05/22 00:41:00
I think the style is to omit the parentheses here.
cshapiro1
2013/05/22 06:35:21
Parenthesis are gone.
| |
70 } | 69 } |
71 | 70 |
72 static int32 | 71 int |
73 popcnt(uint32 x) | 72 bvisempty(Bvec *bv) |
74 { | 73 { |
75 » x = x - ((x >> 1) & 0x55555555); | 74 » int32 i; |
76 » x = (x & 0x33333333) + ((x >> 2) & 0x33333333); | 75 |
77 » x = (x + (x >> 4)) & 0x0f0f0f0f; | 76 » for(i = 0; i < bv->n; i += WORDBITS) |
78 » x = x + (x >> 8); | 77 » » if(bv->b[i / WORDBITS] != 0) |
79 » x = x + (x >> 16); | 78 » » » return 0; |
80 » return x & 0x0000003f; | 79 » return 1; |
81 } | 80 } |
82 | 81 |
83 int32 | 82 int bvcmp(Bvec *bv1, Bvec *bv2) |
84 bvpopcnt(Bvec *bv) | |
85 { | 83 { |
86 » int32 i, sum; | 84 » int32 i; |
87 | 85 |
88 » sum = 0; | 86 » if(bv1->n != bv2->n) { |
89 » for(i = 0; i < bv->n; i += WORDBITS) | 87 » » fatal("bvcmp: size %d != %d\n", bv1->n, bv2->n); |
90 » » sum += popcnt(bv->b[i / WORDBITS]); | 88 » } |
91 » return sum; | 89 » for(i = 0; i < bv1->n; i += WORDBITS) { |
90 » » if(bv1->b[i / WORDBITS] != bv2->b[i / WORDBITS]) { | |
91 » » » fatal("bvcmp: element %x != %x @ %d\n", bv1->b[i/WORDBIT S], bv2->b[i/WORDBITS], i/WORDBITS); | |
92 » » } | |
93 » } | |
94 » return 0; | |
92 } | 95 } |
LEFT | RIGHT |