OLD | NEW |
1 package gkvlite | 1 package gkvlite |
2 | 2 |
3 import ( | 3 import ( |
4 "encoding/binary" | 4 "encoding/binary" |
5 "fmt" | 5 "fmt" |
| 6 "sync" |
6 "sync/atomic" | 7 "sync/atomic" |
7 "unsafe" | |
8 ) | 8 ) |
9 | 9 |
10 // A persistable node. | 10 // A persistable node. |
11 type node struct { | 11 type node struct { |
12 numNodes, numBytes uint64 | 12 numNodes, numBytes uint64 |
13 item itemLoc | 13 item itemLoc |
14 left, right nodeLoc | 14 left, right nodeLoc |
15 next *node // For free-list tracking. | 15 next *node // For free-list tracking. |
16 } | 16 } |
17 | 17 |
18 // A persistable node and its persistence location. | 18 // A persistable node and its persistence location. |
19 type nodeLoc struct { | 19 type nodeLoc struct { |
20 » loc unsafe.Pointer // *ploc - can be nil if node is dirty (not yet pers
isted). | 20 » m sync.Mutex |
21 » node unsafe.Pointer // *node - can be nil if node is not fetched into me
mory yet. | 21 |
22 » next *nodeLoc // For free-list tracking. | 22 » loc *ploc // *ploc - can be nil if node is dirty (not yet persisted)
. |
| 23 » node *node // *node - can be nil if node is not fetched into memory y
et. |
| 24 » next *nodeLoc // For free-list tracking. |
23 } | 25 } |
24 | 26 |
25 var empty_nodeLoc = &nodeLoc{} // Sentinel. | 27 var empty_nodeLoc = &nodeLoc{} // Sentinel. |
26 | 28 |
27 func (nloc *nodeLoc) Loc() *ploc { | 29 func (nloc *nodeLoc) Loc() *ploc { |
28 » return (*ploc)(atomic.LoadPointer(&nloc.loc)) | 30 » nloc.m.Lock() |
| 31 » defer nloc.m.Unlock() |
| 32 » return nloc.loc |
| 33 } |
| 34 |
| 35 func (nloc *nodeLoc) setLoc(n *ploc) { |
| 36 » nloc.m.Lock() |
| 37 » defer nloc.m.Unlock() |
| 38 » nloc.loc = n |
29 } | 39 } |
30 | 40 |
31 func (nloc *nodeLoc) Node() *node { | 41 func (nloc *nodeLoc) Node() *node { |
32 » return (*node)(atomic.LoadPointer(&nloc.node)) | 42 » nloc.m.Lock() |
| 43 » defer nloc.m.Unlock() |
| 44 » return nloc.node |
| 45 } |
| 46 |
| 47 func (nloc *nodeLoc) setNode(n *node) { |
| 48 » nloc.m.Lock() |
| 49 » defer nloc.m.Unlock() |
| 50 » nloc.node = n |
33 } | 51 } |
34 | 52 |
35 func (nloc *nodeLoc) Copy(src *nodeLoc) *nodeLoc { | 53 func (nloc *nodeLoc) Copy(src *nodeLoc) *nodeLoc { |
36 if src == nil { | 54 if src == nil { |
37 return nloc.Copy(empty_nodeLoc) | 55 return nloc.Copy(empty_nodeLoc) |
38 } | 56 } |
39 » atomic.StorePointer(&nloc.loc, unsafe.Pointer(src.Loc())) | 57 » newloc := src.Loc() |
40 » atomic.StorePointer(&nloc.node, unsafe.Pointer(src.Node())) | 58 » newnode := src.Node() |
| 59 |
| 60 » nloc.m.Lock() |
| 61 » defer nloc.m.Unlock() |
| 62 » nloc.loc = newloc |
| 63 » nloc.node = newnode |
41 return nloc | 64 return nloc |
42 } | 65 } |
43 | 66 |
44 func (nloc *nodeLoc) isEmpty() bool { | 67 func (nloc *nodeLoc) isEmpty() bool { |
45 return nloc == nil || (nloc.Loc().isEmpty() && nloc.Node() == nil) | 68 return nloc == nil || (nloc.Loc().isEmpty() && nloc.Node() == nil) |
46 } | 69 } |
47 | 70 |
48 func (nloc *nodeLoc) write(o *Store) error { | 71 func (nloc *nodeLoc) write(o *Store) error { |
49 if nloc != nil && nloc.Loc().isEmpty() { | 72 if nloc != nil && nloc.Loc().isEmpty() { |
50 node := nloc.Node() | 73 node := nloc.Node() |
(...skipping 12 matching lines...) Expand all Loading... |
63 binary.BigEndian.PutUint64(b[pos:pos+8], node.numBytes) | 86 binary.BigEndian.PutUint64(b[pos:pos+8], node.numBytes) |
64 pos += 8 | 87 pos += 8 |
65 if pos != length { | 88 if pos != length { |
66 return fmt.Errorf("nodeLoc.write() pos: %v didn't match
length: %v", | 89 return fmt.Errorf("nodeLoc.write() pos: %v didn't match
length: %v", |
67 pos, length) | 90 pos, length) |
68 } | 91 } |
69 if _, err := o.file.WriteAt(b, offset); err != nil { | 92 if _, err := o.file.WriteAt(b, offset); err != nil { |
70 return err | 93 return err |
71 } | 94 } |
72 atomic.StoreInt64(&o.size, offset+int64(length)) | 95 atomic.StoreInt64(&o.size, offset+int64(length)) |
73 » » atomic.StorePointer(&nloc.loc, | 96 » » nloc.setLoc(&ploc{Offset: offset, Length: uint32(length)}) |
74 » » » unsafe.Pointer(&ploc{Offset: offset, Length: uint32(leng
th)})) | |
75 } | 97 } |
76 return nil | 98 return nil |
77 } | 99 } |
78 | 100 |
79 func (nloc *nodeLoc) read(o *Store) (n *node, err error) { | 101 func (nloc *nodeLoc) read(o *Store) (n *node, err error) { |
80 if nloc == nil { | 102 if nloc == nil { |
81 return nil, nil | 103 return nil, nil |
82 } | 104 } |
83 n = nloc.Node() | 105 n = nloc.Node() |
84 if n != nil { | 106 if n != nil { |
(...skipping 10 matching lines...) Expand all Loading... |
95 b := make([]byte, loc.Length) | 117 b := make([]byte, loc.Length) |
96 if _, err := o.file.ReadAt(b, loc.Offset); err != nil { | 118 if _, err := o.file.ReadAt(b, loc.Offset); err != nil { |
97 return nil, err | 119 return nil, err |
98 } | 120 } |
99 pos := 0 | 121 pos := 0 |
100 atomic.AddUint64(&o.nodeAllocs, 1) | 122 atomic.AddUint64(&o.nodeAllocs, 1) |
101 n = &node{} | 123 n = &node{} |
102 var p *ploc | 124 var p *ploc |
103 p = &ploc{} | 125 p = &ploc{} |
104 p, pos = p.read(b, pos) | 126 p, pos = p.read(b, pos) |
105 » n.item.loc = unsafe.Pointer(p) | 127 » n.item.loc = p |
106 p = &ploc{} | 128 p = &ploc{} |
107 p, pos = p.read(b, pos) | 129 p, pos = p.read(b, pos) |
108 » n.left.loc = unsafe.Pointer(p) | 130 » n.left.loc = p |
109 p = &ploc{} | 131 p = &ploc{} |
110 p, pos = p.read(b, pos) | 132 p, pos = p.read(b, pos) |
111 » n.right.loc = unsafe.Pointer(p) | 133 » n.right.loc = p |
112 n.numNodes = binary.BigEndian.Uint64(b[pos : pos+8]) | 134 n.numNodes = binary.BigEndian.Uint64(b[pos : pos+8]) |
113 pos += 8 | 135 pos += 8 |
114 n.numBytes = binary.BigEndian.Uint64(b[pos : pos+8]) | 136 n.numBytes = binary.BigEndian.Uint64(b[pos : pos+8]) |
115 pos += 8 | 137 pos += 8 |
116 if pos != len(b) { | 138 if pos != len(b) { |
117 return nil, fmt.Errorf("nodeLoc.read() pos: %v didn't match leng
th: %v", | 139 return nil, fmt.Errorf("nodeLoc.read() pos: %v didn't match leng
th: %v", |
118 pos, len(b)) | 140 pos, len(b)) |
119 } | 141 } |
120 » atomic.StorePointer(&nloc.node, unsafe.Pointer(n)) | 142 » nloc.setNode(n) |
121 return n, nil | 143 return n, nil |
122 } | 144 } |
123 | 145 |
124 func numInfo(o *Store, left *nodeLoc, right *nodeLoc) ( | 146 func numInfo(o *Store, left *nodeLoc, right *nodeLoc) ( |
125 leftNum uint64, leftBytes uint64, rightNum uint64, rightBytes uint64, er
r error) { | 147 leftNum uint64, leftBytes uint64, rightNum uint64, rightBytes uint64, er
r error) { |
126 leftNode, err := left.read(o) | 148 leftNode, err := left.read(o) |
127 if err != nil { | 149 if err != nil { |
128 return 0, 0, 0, 0, err | 150 return 0, 0, 0, 0, err |
129 } | 151 } |
130 rightNode, err := right.read(o) | 152 rightNode, err := right.read(o) |
(...skipping 24 matching lines...) Expand all Loading... |
155 } | 177 } |
156 fmt.Printf("%p - %v\n", nNode, k) | 178 fmt.Printf("%p - %v\n", nNode, k) |
157 dump(o, &nNode.right, level+1) | 179 dump(o, &nNode.right, level+1) |
158 } | 180 } |
159 | 181 |
160 func dumpIndent(level int) { | 182 func dumpIndent(level int) { |
161 for i := 0; i < level; i++ { | 183 for i := 0; i < level; i++ { |
162 fmt.Print(" ") | 184 fmt.Print(" ") |
163 } | 185 } |
164 } | 186 } |
OLD | NEW |