~bzr-pqm/bzr/bzr.dev : revision 4771

52

registry,

53

trace,

54

)

55

from bzrlib.static_tuple import StaticTuple

55

56

57

# approx 4MB

57

58

# If each line is 50 bytes, and you have 255 internal pages, with 255-way fan

114

115

"""

115

116

delete_count = 0

116

117

# Check preconditions first.

117

new_items = set([key for (old, key, value) in delta if key is not None

118

and old is None])

118

as_st = StaticTuple.from_sequence

119

new_items = set([as_st(key) for (old, key, value) in delta

120

if key is not None and old is None])

119

121

existing_new = list(self.iteritems(key_filter=new_items))

120

122

if existing_new:

121

123

raise errors.InconsistentDeltaDelta(delta,

135

137

136

138

def _ensure_root(self):

137

139

"""Ensure that the root node is an object not a key."""

138

if type(self._root_node) is tuple:

140

if type(self._root_node) is StaticTuple:

139

141

# Demand-load the root

140

142

self._root_node = self._get_node(self._root_node)

141

143

149

151

:param node: A tuple key or node object.

150

152

:return: A node object.

151

153

"""

152

if type(node) is tuple:

154

if type(node) is StaticTuple:

153

155

bytes = self._read_bytes(node)

154

156

return _deserialise(bytes, node,

155

157

search_key_func=self._search_key_func)

196

198

for key, value in sorted(node._items.iteritems()):

197

199

# Don't use prefix nor indent here to line up when used in

198

200

# tests in conjunction with assertEqualDiff

199

result.append(' %r %r' % (key, value))

201

result.append(' %r %r' % (tuple(key), value))

200

202

return result

201

203

202

204

@classmethod

220

222

root_key = klass._create_directly(store, initial_value,

221

223

maximum_size=maximum_size, key_width=key_width,

222

224

search_key_func=search_key_func)

225

if type(root_key) is not StaticTuple:

226

raise AssertionError('we got a %s instead of a StaticTuple'

227

% (type(root_key),))

223

228

return root_key

224

229

225

230

@classmethod

240

245

node = LeafNode(search_key_func=search_key_func)

241

246

node.set_maximum_size(maximum_size)

242

247

node._key_width = key_width

243

node._items = dict(initial_value)

248

as_st = StaticTuple.from_sequence

249

node._items = dict([(as_st(key), val) for key, val

250

in initial_value.iteritems()])

244

251

node._raw_size = sum([node._key_value_len(key, value)

245

for key,value in initial_value.iteritems()])

252

for key,value in node._items.iteritems()])

246

253

node._len = len(node._items)

247

254

node._compute_search_prefix()

248

255

node._compute_serialised_prefix()

484

491

def iteritems(self, key_filter=None):

485

492

"""Iterate over the entire CHKMap's contents."""

486

493

self._ensure_root()

494

if key_filter is not None:

495

as_st = StaticTuple.from_sequence

496

key_filter = [as_st(key) for key in key_filter]

487

497

return self._root_node.iteritems(self._store, key_filter=key_filter)

488

498

489

499

def key(self):

490

500

"""Return the key for this map."""

491

if type(self._root_node) is tuple:

501

if type(self._root_node) is StaticTuple:

492

502

return self._root_node

493

503

else:

494

504

return self._root_node._key

503

513

:param key: A key to map.

504

514

:param value: The value to assign to key.

505

515

"""

516

key = StaticTuple.from_sequence(key)

506

517

# Need a root object.

507

518

self._ensure_root()

508

519

prefix, node_details = self._root_node.map(self._store, key, value)

519

530

def _node_key(self, node):

520

531

"""Get the key for a node whether it's a tuple or node."""

521

532

if type(node) is tuple:

533

node = StaticTuple.from_sequence(node)

534

if type(node) is StaticTuple:

522

535

return node

523

536

else:

524

537

return node._key

525

538

526

539

def unmap(self, key, check_remap=True):

527

540

"""remove key from the map."""

541

key = StaticTuple.from_sequence(key)

528

542

self._ensure_root()

529

543

if type(self._root_node) is InternalNode:

530

544

unmapped = self._root_node.unmap(self._store, key,

544

558

545

559

:return: The key of the root node.

546

560

"""

547

if type(self._root_node) is tuple:

561

if type(self._root_node) is StaticTuple:

548

562

# Already saved.

549

563

return self._root_node

550

564

keys = list(self._root_node.serialise(self._store))

881

895

lines.append(serialized[prefix_len:])

882

896

lines.extend(value_lines)

883

897

sha1, _, _ = store.add_lines((None,), (), lines)

884

self._key = ("sha1:" + sha1,)

898

self._key = StaticTuple("sha1:" + sha1,).intern()

885

899

bytes = ''.join(lines)

886

900

if len(bytes) != self._current_size():

887

901

raise AssertionError('Invalid _current_size')

1004

1018

:param key: The key that the serialised node has.

1005

1019

:return: An InternalNode instance.

1006

1020

"""

1021

if type(key) is not StaticTuple:

1022

raise AssertionError('deserialise should be called with a'

1023

' StaticTuple not %s' % (type(key),))

1007

1024

return _deserialise_internal_node(bytes, key,

1008

1025

search_key_func=search_key_func)

1009

1026

1034

1051

# for whatever we are missing

1035

1052

shortcut = True

1036

1053

for prefix, node in self._items.iteritems():

1037

if node.__class__ is tuple:

1054

if node.__class__ is StaticTuple:

1038

1055

keys[node] = (prefix, None)

1039

1056

else:

1040

1057

yield node, None

1069

1086

# A given key can only match 1 child node, if it isn't

1070

1087

# there, then we can just return nothing

1071

1088

return

1072

if node.__class__ is tuple:

1089

if node.__class__ is StaticTuple:

1073

1090

keys[node] = (search_prefix, [key])

1074

1091

else:

1075

1092

# This is loaded, and the only thing that can match,

1102

1119

# We can ignore this one

1103

1120

continue

1104

1121

node_key_filter = prefix_to_keys[search_prefix]

1105

if node.__class__ is tuple:

1122

if node.__class__ is StaticTuple:

1106

1123

keys[node] = (search_prefix, node_key_filter)

1107

1124

else:

1108

1125

yield node, node_key_filter

1117

1134

if sub_prefix in length_filter:

1118

1135

node_key_filter.extend(prefix_to_keys[sub_prefix])

1119

1136

if node_key_filter: # this key matched something, yield it

1120

if node.__class__ is tuple:

1137

if node.__class__ is StaticTuple:

1121

1138

keys[node] = (prefix, node_key_filter)

1122

1139

else:

1123

1140

yield node, node_key_filter

1255

1272

:return: An iterable of the keys inserted by this operation.

1256

1273

"""

1257

1274

for node in self._items.itervalues():

1258

if type(node) is tuple:

1275

if type(node) is StaticTuple:

1259

1276

# Never deserialised.

1260

1277

continue

1261

1278

if node._key is not None:

1272

1289

lines.append('%s\n' % (self._search_prefix,))

1273

1290

prefix_len = len(self._search_prefix)

1274

1291

for prefix, node in sorted(self._items.items()):

1275

if type(node) is tuple:

1292

if type(node) is StaticTuple:

1276

1293

key = node[0]

1277

1294

else:

1278

1295

key = node._key[0]

1282

1299

% (serialised, self._search_prefix))

1283

1300

lines.append(serialised[prefix_len:])

1284

1301

sha1, _, _ = store.add_lines((None,), (), lines)

1285

self._key = ("sha1:" + sha1,)

1302

self._key = StaticTuple("sha1:" + sha1,).intern()

1286

1303

_page_cache.add(self._key, ''.join(lines))

1287

1304

yield self._key

1288

1305

1317

1334

raise AssertionError("unserialised nodes have no refs.")

1318

1335

refs = []

1319

1336

for value in self._items.itervalues():

1320

if type(value) is tuple:

1337

if type(value) is StaticTuple:

1321

1338

refs.append(value)

1322

1339

else:

1323

1340

refs.append(value.key())

1437

1454

1438

1455

def __init__(self, store, new_root_keys, old_root_keys,

1439

1456

search_key_func, pb=None):

1457

# TODO: Should we add a StaticTuple barrier here? It would be nice to

1458

# force callers to use StaticTuple, because there will often be

1459

# lots of keys passed in here. And even if we cast it locally,

1460

# that just meanst that we will have *both* a StaticTuple and a

1461

# tuple() in memory, referring to the same object. (so a net

1462

# increase in memory, not a decrease.)

1440

1463

self._store = store

1441

1464

self._new_root_keys = new_root_keys

1442

1465

self._old_root_keys = old_root_keys

1444

1467

# All uninteresting chks that we have seen. By the time they are added

1445

1468

# here, they should be either fully ignored, or queued up for

1446

1469

# processing

1470

# TODO: This might grow to a large size if there are lots of merge

1471

# parents, etc. However, it probably doesn't scale to O(history)

1472

# like _processed_new_refs does.

1447

1473

self._all_old_chks = set(self._old_root_keys)

1448

1474

# All items that we have seen from the old_root_keys

1449

1475

self._all_old_items = set()

1450

1476

# These are interesting items which were either read, or already in the

1451

1477

# interesting queue (so we don't need to walk them again)

1478

# TODO: processed_new_refs becomes O(all_chks), consider switching to

1479

# SimpleSet here.

1452

1480

self._processed_new_refs = set()

1453

1481

self._search_key_func = search_key_func

1454

1482

1466

1494

# this code. (We may want to evaluate saving the raw bytes into the

1467

1495

# page cache, which would allow a working tree update after the fetch

1468

1496

# to not have to read the bytes again.)

1497

as_st = StaticTuple.from_sequence

1469

1498

stream = self._store.get_record_stream(keys, 'unordered', True)

1470

1499

for record in stream:

1471

1500

if self._pb is not None:

1478

1507

if type(node) is InternalNode:

1479

1508

# Note we don't have to do node.refs() because we know that

1480

1509

# there are no children that have been pushed into this node

1510

# Note: Using as_st() here seemed to save 1.2MB, which would

1511

# indicate that we keep 100k prefix_refs around while

1512

# processing. They *should* be shorter lived than that...

1513

# It does cost us ~10s of processing time

1514

#prefix_refs = [as_st(item) for item in node._items.iteritems()]

1481

1515

prefix_refs = node._items.items()

1482

1516

items = []

1483

1517

else:

1484

1518

prefix_refs = []

1519

# Note: We don't use a StaticTuple here. Profiling showed a

1520

# minor memory improvement (0.8MB out of 335MB peak 0.2%)

1521

# But a significant slowdown (15s / 145s, or 10%)

1485

1522

items = node._items.items()

1486

1523

yield record, node, prefix_refs, items

1487

1524

1495

1532

if p_r[1] not in all_old_chks]

1496

1533

new_refs = [p_r[1] for p_r in prefix_refs]

1497

1534

all_old_chks.update(new_refs)

1535

# TODO: This might be a good time to turn items into StaticTuple

1536

# instances and possibly intern them. However, this does not

1537

# impact 'initial branch' performance, so I'm not worrying

1538

# about this yet

1498

1539

self._all_old_items.update(items)

1499

1540

# Queue up the uninteresting references

1500

1541

# Don't actually put them in the 'to-read' queue until we have

1553

1594

# current design allows for this, as callers will do the work

1554

1595

# to make the results unique. We might profile whether we

1555

1596

# gain anything by ensuring unique return values for items

1597

# TODO: This might be a good time to cast to StaticTuple, as

1598

# self._new_item_queue will hold the contents of multiple

1599

# records for an extended lifetime

1556

1600

new_items = [item for item in items

1557

1601

if item not in self._all_old_items]

1558

1602

self._new_item_queue.extend(new_items)

1583

1627

if new_items:

1584

1628

yield None, new_items

1585

1629

refs = refs.difference(all_old_chks)

1630

processed_new_refs.update(refs)

1586

1631

while refs:

1632

# TODO: Using a SimpleSet for self._processed_new_refs and

1633

# saved as much as 10MB of peak memory. However, it requires

1634

# implementing a non-pyrex version.

1587

1635

next_refs = set()

1588

1636

next_refs_update = next_refs.update

1589

1637

# Inlining _read_nodes_from_store improves 'bzr branch bzr.dev'

1590

1638

# from 1m54s to 1m51s. Consider it.

1591

1639

for record, _, p_refs, items in self._read_nodes_from_store(refs):

1592

items = [item for item in items

1593

if item not in all_old_items]

1640

if all_old_items:

1641

# using the 'if' check saves about 145s => 141s, when

1642

# streaming initial branch of Launchpad data.

1643

items = [item for item in items

1644

if item not in all_old_items]

1594

1645

yield record, items

1595

1646

next_refs_update([p_r[1] for p_r in p_refs])

1647

del p_refs

1648

# set1.difference(set/dict) walks all of set1, and checks if it

1649

# exists in 'other'.

1650

# set1.difference(iterable) walks all of iterable, and does a

1651

# 'difference_update' on a clone of set1. Pick wisely based on the

1652

# expected sizes of objects.

1653

# in our case it is expected that 'new_refs' will always be quite

1654

# small.

1596

1655

next_refs = next_refs.difference(all_old_chks)

1597

1656

next_refs = next_refs.difference(processed_new_refs)

1598

1657

processed_new_refs.update(next_refs)

1605

1664

self._old_queue = []

1606

1665

all_old_chks = self._all_old_chks

1607

1666

for record, _, prefix_refs, items in self._read_nodes_from_store(refs):

1667

# TODO: Use StaticTuple here?

1608

1668

self._all_old_items.update(items)

1609

1669

refs = [r for _,r in prefix_refs if r not in all_old_chks]

1610

1670

self._old_queue.extend(refs)

1660

1720

)

1661

1721

search_key_registry.register('hash-16-way', _search_key_16)

1662

1722

search_key_registry.register('hash-255-way', _search_key_255)

1723

1724

1725

def _check_key(key):

1726

"""Helper function to assert that a key is properly formatted.

1727

1728

This generally shouldn't be used in production code, but it can be helpful

1729

to debug problems.

1730

"""

1731

if type(key) is not StaticTuple:

1732

raise TypeError('key %r is not StaticTuple but %s' % (key, type(key)))

1733

if len(key) != 1:

1734

raise ValueError('key %r should have length 1, not %d' % (key, len(key),))

1735

if type(key[0]) is not str:

1736

raise TypeError('key %r should hold a str, not %r'

1737

% (key, type(key[0])))

1738

if not key[0].startswith('sha1:'):

1739

raise ValueError('key %r should point to a sha1:' % (key,))

1740

1741