« back to all changes in this revision
Viewing changes to bzrlib/btree_index.py
- browse files at revision 5390
- compare with another revision
- compare with revision 5401
- download diff
- download tarball
- view history from revision 5390
- Committer: Canonical.com Patch Queue Manager
- Date: 2010-08-24 23:20:14 UTC
- mfrom: (5365.5.29 2.3-btree-chk-leaf)
- Revision ID: pqm@pqm.ubuntu.com-20100824232014-nu9owzel2zym2jk2
(jam) Use a custom C type for CHK index entries, saves memory
- files added:
- bzrlib/tests/test__btree_serializer.py
- files modified:
- NEWS
added
removed
bzrlib/btree_index.py
602
602
"""In memory index's have no known corruption at the moment."""
603
603
604
604
605
class _LeafNode(object):
605
class _LeafNode(dict):
606
606
"""A leaf node for a serialised B+Tree index."""
607
607
608
__slots__ = ('keys', 'min_key', 'max_key')
608
__slots__ = ('min_key', 'max_key', '_keys')
609
609
610
610
def __init__(self, bytes, key_length, ref_list_length):
611
611
"""Parse bytes to create a leaf node object."""
617
617
self.max_key = key_list[-1][0]
618
618
else:
619
619
self.min_key = self.max_key = None
620
self.keys = dict(key_list)
620
super(_LeafNode, self).__init__(key_list)
621
self._keys = dict(self)
622
623
def all_items(self):
624
"""Return a sorted list of (key, (value, refs)) items"""
625
items = self.items()
626
items.sort()
627
return items
628
629
def all_keys(self):
630
"""Return a sorted list of all keys."""
631
keys = self.keys()
632
keys.sort()
633
return keys
621
634
622
635
623
636
class _InternalNode(object):
672
685
self._recommended_pages = self._compute_recommended_pages()
673
686
self._root_node = None
674
687
self._base_offset = offset
688
self._leaf_factory = _LeafNode
675
689
# Default max size is 100,000 leave values
676
690
self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
677
691
if unlimited_cache:
950
964
"""Cache directly from key => value, skipping the btree."""
951
965
if self._leaf_value_cache is not None:
952
966
for node in nodes.itervalues():
953
for key, value in node.keys.iteritems():
967
for key, value in node.all_items():
954
968
if key in self._leaf_value_cache:
955
969
# Don't add the rest of the keys, we've seen this node
956
970
# before.
980
994
if self._row_offsets[-1] == 1:
981
995
# There is only the root node, and we read that via key_count()
982
996
if self.node_ref_lists:
983
for key, (value, refs) in sorted(self._root_node.keys.items()):
997
for key, (value, refs) in self._root_node.all_items():
984
998
yield (self, key, value, refs)
985
999
else:
986
for key, (value, refs) in sorted(self._root_node.keys.items()):
1000
for key, (value, refs) in self._root_node.all_items():
987
1001
yield (self, key, value)
988
1002
return
989
1003
start_of_leaves = self._row_offsets[-2]
999
1013
# for spilling index builds to disk.
1000
1014
if self.node_ref_lists:
1001
1015
for _, node in nodes:
1002
for key, (value, refs) in sorted(node.keys.items()):
1016
for key, (value, refs) in node.all_items():
1003
1017
yield (self, key, value, refs)
1004
1018
else:
1005
1019
for _, node in nodes:
1006
for key, (value, refs) in sorted(node.keys.items()):
1020
for key, (value, refs) in node.all_items():
1007
1021
yield (self, key, value)
1008
1022
1009
1023
@staticmethod
1170
1184
continue
1171
1185
node = nodes[node_index]
1172
1186
for next_sub_key in sub_keys:
1173
if next_sub_key in node.keys:
1174
value, refs = node.keys[next_sub_key]
1187
if next_sub_key in node:
1188
value, refs = node[next_sub_key]
1175
1189
if self.node_ref_lists:
1176
1190
yield (self, next_sub_key, value, refs)
1177
1191
else:
1245
1259
# sub_keys is all of the keys we are looking for that should exist
1246
1260
# on this page, if they aren't here, then they won't be found
1247
1261
node = nodes[node_index]
1248
node_keys = node.keys
1249
1262
parents_to_check = set()
1250
1263
for next_sub_key in sub_keys:
1251
if next_sub_key not in node_keys:
1264
if next_sub_key not in node:
1252
1265
# This one is just not present in the index at all
1253
1266
missing_keys.add(next_sub_key)
1254
1267
else:
1255
value, refs = node_keys[next_sub_key]
1268
value, refs = node[next_sub_key]
1256
1269
parent_keys = refs[ref_list_num]
1257
1270
parent_map[next_sub_key] = parent_keys
1258
1271
parents_to_check.update(parent_keys)
1265
1278
while parents_to_check:
1266
1279
next_parents_to_check = set()
1267
1280
for key in parents_to_check:
1268
if key in node_keys:
1269
value, refs = node_keys[key]
1281
if key in node:
1282
value, refs = node[key]
1270
1283
parent_keys = refs[ref_list_num]
1271
1284
parent_map[key] = parent_keys
1272
1285
next_parents_to_check.update(parent_keys)
1546
1559
continue
1547
1560
bytes = zlib.decompress(data)
1548
1561
if bytes.startswith(_LEAF_FLAG):
1549
node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
1562
node = self._leaf_factory(bytes, self._key_length,
1563
self.node_ref_lists)
1550
1564
elif bytes.startswith(_INTERNAL_FLAG):
1551
1565
node = _InternalNode(bytes)
1552
1566
else:
1571
1585
pass
1572
1586
1573
1587
1588
_gcchk_factory = _LeafNode
1589
1574
1590
try:
1575
1591
from bzrlib import _btree_serializer_pyx as _btree_serializer
1592
_gcchk_factory = _btree_serializer._parse_into_chk
1576
1593
except ImportError, e:
1577
1594
osutils.failed_to_load_extension(e)
1578
1595
from bzrlib import _btree_serializer_py as _btree_serializer
Loggerhead is a web-based interface for Breezy
Version: 2.0.1