« back to all changes in this revision
Viewing changes to bzrlib/btree_index.py
- browse files at revision 3641.3.8
- compare with another revision
- compare with revision 6523.2.1
- download diff
- download tarball
- view history from revision 3641.3.8
- Committer: John Arbash Meinel
- Date: 2008-08-20 20:41:34 UTC
- mto: This revision was merged to the branch mainline in revision 3644.
- Revision ID: john@arbash-meinel.com-20080820204134-irezo791nj00wq91
Move the add_key helper function into a separate func
- files modified:
- bzrlib/btree_index.py
added
removed
bzrlib/btree_index.py
237
237
except StopIteration:
238
238
current_values[pos] = None
239
239
240
def _add_key(self, string_key, key_line, rows):
241
"""Add a key to the current chunk.
242
243
:param string_key: The key to add.
244
:param key_line: The fully serialised key and value.
245
"""
246
if rows[-1].writer is None:
247
# opening a new leaf chunk;
248
for pos, internal_row in enumerate(rows[:-1]):
249
# flesh out any internal nodes that are needed to
250
# preserve the high of the tree
251
if internal_row.writer is None:
252
length = _PAGE_SIZE
253
if internal_row.nodes == 0:
254
length -= _RESERVED_HEADER_BYTES # padded
255
internal_row.writer = chunk_writer.ChunkWriter(
256
length, 0)
257
internal_row.writer.write(_INTERNAL_FLAG)
258
internal_row.writer.write(_INTERNAL_OFFSET +
259
str(rows[pos + 1].nodes) + "\n")
260
# add a new leaf
261
length = _PAGE_SIZE
262
if rows[-1].nodes == 0:
263
length -= _RESERVED_HEADER_BYTES # padded
264
rows[-1].writer = chunk_writer.ChunkWriter(length)
265
rows[-1].writer.write(_LEAF_FLAG)
266
if rows[-1].writer.write(key_line):
267
# this key did not fit in the node:
268
rows[-1].finish_node()
269
next_key_line = string_key + "\n"
270
new_row = True
271
for row in reversed(rows[:-1]):
272
# Mark the start of the next node in the node above. If it
273
# doesn't fit then propogate upwards until we find one that
274
# it does fit into.
275
if row.writer.write(next_key_line):
276
row.finish_node()
277
else:
278
# We've found a node that can handle the pointer.
279
new_row = False
280
break
281
# If we reached the current root without being able to mark the
282
# division point, then we need a new root:
283
if new_row:
284
# We need a new row
285
if 'index' in debug.debug_flags:
286
trace.mutter('Inserting new global row.')
287
new_row = _InternalBuilderRow()
288
reserved_bytes = 0
289
rows.insert(0, new_row)
290
# This will be padded, hence the -100
291
new_row.writer = chunk_writer.ChunkWriter(
292
_PAGE_SIZE - _RESERVED_HEADER_BYTES,
293
reserved_bytes)
294
new_row.writer.write(_INTERNAL_FLAG)
295
new_row.writer.write(_INTERNAL_OFFSET +
296
str(rows[1].nodes - 1) + "\n")
297
new_row.writer.write(next_key_line)
298
self._add_key(string_key, key_line, rows)
299
240
300
def _write_nodes(self, node_iterator):
241
301
"""Write node_iterator out as a B+Tree.
242
302
255
315
# A stack with the number of nodes of each size. 0 is the root node
256
316
# and must always be 1 (if there are any nodes in the tree).
257
317
self.row_lengths = []
258
def add_key(string_key, key_line):
259
"""Add a key to the current chunk.
260
261
:param string_key: The key to add.
262
:param key_line: The fully serialised key and value.
263
"""
264
if rows[-1].writer is None:
265
# opening a new leaf chunk;
266
for pos, internal_row in enumerate(rows[:-1]):
267
# flesh out any internal nodes that are needed to
268
# preserve the high of the tree
269
if internal_row.writer is None:
270
length = _PAGE_SIZE
271
if internal_row.nodes == 0:
272
length -= _RESERVED_HEADER_BYTES # padded
273
internal_row.writer = chunk_writer.ChunkWriter(
274
length, 0)
275
internal_row.writer.write(_INTERNAL_FLAG)
276
internal_row.writer.write(_INTERNAL_OFFSET +
277
str(rows[pos + 1].nodes) + "\n")
278
# add a new leaf
279
length = _PAGE_SIZE
280
if rows[-1].nodes == 0:
281
length -= _RESERVED_HEADER_BYTES # padded
282
rows[-1].writer = chunk_writer.ChunkWriter(length)
283
rows[-1].writer.write(_LEAF_FLAG)
284
if rows[-1].writer.write(line):
285
# this key did not fit in the node:
286
rows[-1].finish_node()
287
key_line = string_key + "\n"
288
new_row = True
289
for row in reversed(rows[:-1]):
290
# Mark the start of the next node in the node above. If it
291
# doesn't fit then propogate upwards until we find one that
292
# it does fit into.
293
if row.writer.write(key_line):
294
row.finish_node()
295
else:
296
# We've found a node that can handle the pointer.
297
new_row = False
298
break
299
# If we reached the current root without being able to mark the
300
# division point, then we need a new root:
301
if new_row:
302
# We need a new row
303
if 'index' in debug.debug_flags:
304
trace.mutter('Inserting new global row.')
305
new_row = _InternalBuilderRow()
306
reserved_bytes = 0
307
rows.insert(0, new_row)
308
# This will be padded, hence the -100
309
new_row.writer = chunk_writer.ChunkWriter(
310
_PAGE_SIZE - _RESERVED_HEADER_BYTES,
311
reserved_bytes)
312
new_row.writer.write(_INTERNAL_FLAG)
313
new_row.writer.write(_INTERNAL_OFFSET +
314
str(rows[1].nodes - 1) + "\n")
315
new_row.writer.write(key_line)
316
add_key(string_key, key_line)
317
318
# Loop over all nodes adding them to the bottom row
318
319
# (rows[-1]). When we finish a chunk in a row,
319
320
# propogate the key that didn't fit (comes after the chunk) to the
333
334
string_key = '\x00'.join(node[1])
334
335
line = ("%s\x00%s\x00%s\n" % (string_key,
335
336
'\t'.join(flattened_references), node[2]))
336
add_key(string_key, line)
337
self._add_key(string_key, line, rows)
337
338
for row in reversed(rows):
338
339
pad = (type(row) != _LeafBuilderRow)
339
340
row.finish_node(pad=pad)
Loggerhead is a web-based interface for Breezy
Version: 2.0.1