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" |
7 "sync/atomic" | 7 "sync/atomic" |
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 var nodeLocGL = sync.RWMutex{} |
| 19 |
18 // A persistable node and its persistence location. | 20 // A persistable node and its persistence location. |
19 type nodeLoc struct { | 21 type nodeLoc struct { |
20 m sync.Mutex | |
21 | |
22 loc *ploc // *ploc - can be nil if node is dirty (not yet persisted)
. | 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. | 23 node *node // *node - can be nil if node is not fetched into memory y
et. |
24 next *nodeLoc // For free-list tracking. | 24 next *nodeLoc // For free-list tracking. |
25 } | 25 } |
26 | 26 |
27 var empty_nodeLoc = &nodeLoc{} // Sentinel. | 27 var empty_nodeLoc = &nodeLoc{} // Sentinel. |
28 | 28 |
29 func (nloc *nodeLoc) Loc() *ploc { | 29 func (nloc *nodeLoc) Loc() *ploc { |
30 » nloc.m.Lock() | 30 » nodeLocGL.RLock() |
31 » defer nloc.m.Unlock() | 31 » defer nodeLocGL.RUnlock() |
32 return nloc.loc | 32 return nloc.loc |
33 } | 33 } |
34 | 34 |
35 func (nloc *nodeLoc) setLoc(n *ploc) { | 35 func (nloc *nodeLoc) setLoc(n *ploc) { |
36 » nloc.m.Lock() | 36 » nodeLocGL.Lock() |
37 » defer nloc.m.Unlock() | 37 » defer nodeLocGL.Unlock() |
38 nloc.loc = n | 38 nloc.loc = n |
39 } | 39 } |
40 | 40 |
41 func (nloc *nodeLoc) Node() *node { | 41 func (nloc *nodeLoc) Node() *node { |
42 » nloc.m.Lock() | 42 » nodeLocGL.RLock() |
43 » defer nloc.m.Unlock() | 43 » defer nodeLocGL.RUnlock() |
44 return nloc.node | 44 return nloc.node |
45 } | 45 } |
46 | 46 |
47 func (nloc *nodeLoc) setNode(n *node) { | 47 func (nloc *nodeLoc) setNode(n *node) { |
48 » nloc.m.Lock() | 48 » nodeLocGL.Lock() |
49 » defer nloc.m.Unlock() | 49 » defer nodeLocGL.Unlock() |
50 nloc.node = n | 50 nloc.node = n |
51 } | 51 } |
52 | 52 |
| 53 func (nloc *nodeLoc) LocNode() (*ploc, *node) { |
| 54 nodeLocGL.RLock() |
| 55 defer nodeLocGL.RUnlock() |
| 56 return nloc.loc, nloc.node |
| 57 } |
| 58 |
53 func (nloc *nodeLoc) Copy(src *nodeLoc) *nodeLoc { | 59 func (nloc *nodeLoc) Copy(src *nodeLoc) *nodeLoc { |
54 if src == nil { | 60 if src == nil { |
55 return nloc.Copy(empty_nodeLoc) | 61 return nloc.Copy(empty_nodeLoc) |
56 } | 62 } |
57 newloc := src.Loc() | |
58 newnode := src.Node() | |
59 | 63 |
60 » nloc.m.Lock() | 64 » nodeLocGL.Lock() |
61 » defer nloc.m.Unlock() | 65 » defer nodeLocGL.Unlock() |
62 » nloc.loc = newloc | 66 » // NOTE: This trick only works because of the global lock. No reason to
lock |
63 » nloc.node = newnode | 67 » // src independently of nlock. |
| 68 » nloc.loc = src.loc |
| 69 » nloc.node = src.node |
64 return nloc | 70 return nloc |
65 } | 71 } |
66 | 72 |
67 func (nloc *nodeLoc) isEmpty() bool { | 73 func (nloc *nodeLoc) isEmpty() bool { |
68 » return nloc == nil || (nloc.Loc().isEmpty() && nloc.Node() == nil) | 74 » nodeLocGL.RLock() |
| 75 » defer nodeLocGL.RUnlock() |
| 76 » return nloc == nil || (nloc.loc.isEmpty() && nloc.node == nil) |
69 } | 77 } |
70 | 78 |
71 func (nloc *nodeLoc) write(o *Store) error { | 79 func (nloc *nodeLoc) write(o *Store) error { |
72 » if nloc != nil && nloc.Loc().isEmpty() { | 80 » loc, node := nloc.LocNode() |
73 » » node := nloc.Node() | 81 |
| 82 » if nloc != nil && loc.isEmpty() { |
74 if node == nil { | 83 if node == nil { |
75 return nil | 84 return nil |
76 } | 85 } |
77 offset := atomic.LoadInt64(&o.size) | 86 offset := atomic.LoadInt64(&o.size) |
78 length := ploc_length + ploc_length + ploc_length + 8 + 8 | 87 length := ploc_length + ploc_length + ploc_length + 8 + 8 |
79 b := make([]byte, length) | 88 b := make([]byte, length) |
80 pos := 0 | 89 pos := 0 |
81 pos = node.item.Loc().write(b, pos) | 90 pos = node.item.Loc().write(b, pos) |
82 pos = node.left.Loc().write(b, pos) | 91 pos = node.left.Loc().write(b, pos) |
83 pos = node.right.Loc().write(b, pos) | 92 pos = node.right.Loc().write(b, pos) |
(...skipping 11 matching lines...) Expand all Loading... |
95 atomic.StoreInt64(&o.size, offset+int64(length)) | 104 atomic.StoreInt64(&o.size, offset+int64(length)) |
96 nloc.setLoc(&ploc{Offset: offset, Length: uint32(length)}) | 105 nloc.setLoc(&ploc{Offset: offset, Length: uint32(length)}) |
97 } | 106 } |
98 return nil | 107 return nil |
99 } | 108 } |
100 | 109 |
101 func (nloc *nodeLoc) read(o *Store) (n *node, err error) { | 110 func (nloc *nodeLoc) read(o *Store) (n *node, err error) { |
102 if nloc == nil { | 111 if nloc == nil { |
103 return nil, nil | 112 return nil, nil |
104 } | 113 } |
105 » n = nloc.Node() | 114 » loc, n := nloc.LocNode() |
106 if n != nil { | 115 if n != nil { |
107 return n, nil | 116 return n, nil |
108 } | 117 } |
109 loc := nloc.Loc() | |
110 if loc.isEmpty() { | 118 if loc.isEmpty() { |
111 return nil, nil | 119 return nil, nil |
112 } | 120 } |
113 if loc.Length != uint32(ploc_length+ploc_length+ploc_length+8+8) { | 121 if loc.Length != uint32(ploc_length+ploc_length+ploc_length+8+8) { |
114 return nil, fmt.Errorf("unexpected node loc.Length: %v != %v", | 122 return nil, fmt.Errorf("unexpected node loc.Length: %v != %v", |
115 loc.Length, ploc_length+ploc_length+ploc_length+8+8) | 123 loc.Length, ploc_length+ploc_length+ploc_length+8+8) |
116 } | 124 } |
117 b := make([]byte, loc.Length) | 125 b := make([]byte, loc.Length) |
118 if _, err := o.file.ReadAt(b, loc.Offset); err != nil { | 126 if _, err := o.file.ReadAt(b, loc.Offset); err != nil { |
119 return nil, err | 127 return nil, err |
(...skipping 57 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
177 } | 185 } |
178 fmt.Printf("%p - %v\n", nNode, k) | 186 fmt.Printf("%p - %v\n", nNode, k) |
179 dump(o, &nNode.right, level+1) | 187 dump(o, &nNode.right, level+1) |
180 } | 188 } |
181 | 189 |
182 func dumpIndent(level int) { | 190 func dumpIndent(level int) { |
183 for i := 0; i < level; i++ { | 191 for i := 0; i < level; i++ { |
184 fmt.Print(" ") | 192 fmt.Print(" ") |
185 } | 193 } |
186 } | 194 } |
OLD | NEW |