1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
|
# Copyright 2016-2017 Lars Wirzenius
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.
#
# =*= License: GPL-3+ =*=
import copy
import obnamlib
class CowTree(object):
def __init__(self):
self._store = None
self._leaf_list = _LeafList()
self._max_keys_per_leaf = 1024 # FIXME: This should be configurable?
def set_leaf_store(self, leaf_store):
self._store = leaf_store
def set_list_node(self, leaf_id):
fake_leaf = self._store.get_leaf(leaf_id)
self._leaf_list.from_dict(fake_leaf.lookup('leaf_list'))
def set_max_leaf_size(self, max_keys):
assert max_keys >= 2
self._max_keys_per_leaf = max_keys
def lookup(self, key):
leaf_id = self._leaf_list.find_leaf_for_key(key)
if leaf_id is None:
return None
leaf = self._store.get_leaf(leaf_id)
assert leaf is not None
return leaf.lookup(key)
def insert(self, key, value):
leaf_id = self._leaf_list.find_leaf_for_key(key)
if leaf_id is None:
self._add_new_leaf(key, value)
else:
self._insert_into_leaf(leaf_id, key, value)
def _add_new_leaf(self, key, value):
leaf = obnamlib.CowLeaf()
leaf.insert(key, value)
leaf_id = self._store.put_leaf(leaf)
self._leaf_list.insert_leaf(key, key, leaf_id)
def _insert_into_leaf(self, leaf_id, key, value):
leaf = self._store.get_leaf(leaf_id)
assert leaf is not None
leaf.insert(key, value)
keys = list(sorted(leaf.keys()))
self._leaf_list.update_leaf(leaf_id, keys[0], keys[-1])
if len(leaf) > self._max_keys_per_leaf:
self._leaf_list.drop_leaf(leaf_id)
self._store.remove_leaf(leaf_id)
self._split_leaf(leaf)
else:
self._leaf_list.drop_leaf(leaf_id)
self._make_split_leaf(leaf, list(sorted(leaf.keys())))
self._store.remove_leaf(leaf_id)
def _split_leaf(self, leaf):
sorted_keys = list(sorted(leaf.keys()))
n = len(sorted_keys) / 2
self._make_split_leaf(leaf, sorted_keys[:n])
self._make_split_leaf(leaf, sorted_keys[n:])
def _make_split_leaf(self, leaf, sorted_keys):
new = obnamlib.CowLeaf()
for key in sorted_keys:
new.insert(key, leaf.lookup(key))
new_id = self._store.put_leaf(new)
self._leaf_list.insert_leaf(sorted_keys[0], sorted_keys[-1], new_id)
def remove(self, key):
leaf_id = self._leaf_list.find_leaf_for_key(key)
if leaf_id is not None:
self._leaf_list.drop_leaf(leaf_id)
leaf = self._store.get_leaf(leaf_id)
leaf.remove(key)
self._store.remove_leaf(leaf_id)
if len(leaf) > 0:
self._make_split_leaf(leaf, list(sorted(leaf.keys())))
def keys(self):
leaf_ids = list(self._leaf_list.leaf_ids())
if leaf_ids:
for leaf_id in leaf_ids:
leaf = self._store.get_leaf(leaf_id)
for key in leaf.keys():
yield key
def commit(self):
fake_leaf = obnamlib.CowLeaf()
fake_leaf.insert('leaf_list', self._leaf_list.as_dict())
list_id = self._store.put_leaf(fake_leaf)
self._store.flush()
return list_id
class _LeafList(object):
def __init__(self):
self._leaf_list = []
def as_dict(self):
# This isn't really returning a dict, but that's OK. We only
# need to return something that serialise_object can handle.
return copy.deepcopy(self._leaf_list)
def from_dict(self, some_dict):
self._leaf_list = some_dict
def leaf_ids(self):
for leaf_info in self._leaf_list:
yield leaf_info['id']
def find_leaf_for_key(self, key):
# If there are no leaves, we can't pick one for key.
if not self._leaf_list:
return None
# Pick last one if key is too big.
last = self._leaf_list[-1]
if key >= last['last_key']:
return last['id']
# Otherwise, pick first leaf whose last key >= key. We now
# know there is such a node.
for leaf_info in self._leaf_list:
if leaf_info['last_key'] >= key:
return leaf_info['id']
# If we get here, something's badly wrong.
assert False # pragma: no cover
def insert_leaf(self, first_key, last_key, leaf_id):
leaf_info = {
'first_key': first_key,
'last_key': last_key,
'id': leaf_id,
}
self._leaf_list.append(leaf_info)
self._leaf_list.sort(key=lambda li: li['first_key'])
def update_leaf(self, leaf_id, first_key, last_key):
for leaf_info in self._leaf_list:
if leaf_info['id'] == leaf_id:
leaf_info['first_key'] = first_key
leaf_info['last_key'] = last_key
def drop_leaf(self, leaf_id):
self._leaf_list = [
leaf_info
for leaf_info in self._leaf_list
if leaf_info['id'] != leaf_id
]
|
