Mercurial > hg
annotate mercurial/revlogutils/nodemap.py @ 44307:c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
This python code aims to be as "simple" as possible. It is a reference
implementation of the data we are going to write on disk (and possibly,
later a way for pure python install to make sure the on disk data are up to
date).
It is not optimized for performance and rebuild the full data structure from
the index every time.
This is a stepping stone toward a persistent nodemap on disk.
Differential Revision: https://phab.mercurial-scm.org/D7834
author | Pierre-Yves David <pierre-yves.david@octobus.net> |
---|---|
date | Wed, 15 Jan 2020 15:47:12 +0100 |
parents | ab595920de0e |
children | 5962fd0d1045 |
rev | line source |
---|---|
44034
ab595920de0e
revlogutils: move the NodeMap class in a dedicated nodemap module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
1 # nodemap.py - nodemap related code and utilities |
ab595920de0e
revlogutils: move the NodeMap class in a dedicated nodemap module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
2 # |
ab595920de0e
revlogutils: move the NodeMap class in a dedicated nodemap module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
3 # Copyright 2019 Pierre-Yves David <pierre-yves.david@octobus.net> |
ab595920de0e
revlogutils: move the NodeMap class in a dedicated nodemap module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
4 # Copyright 2019 George Racinet <georges.racinet@octobus.net> |
ab595920de0e
revlogutils: move the NodeMap class in a dedicated nodemap module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
5 # |
ab595920de0e
revlogutils: move the NodeMap class in a dedicated nodemap module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
6 # This software may be used and distributed according to the terms of the |
ab595920de0e
revlogutils: move the NodeMap class in a dedicated nodemap module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
7 # GNU General Public License version 2 or any later version. |
ab595920de0e
revlogutils: move the NodeMap class in a dedicated nodemap module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
8 |
ab595920de0e
revlogutils: move the NodeMap class in a dedicated nodemap module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
9 from __future__ import absolute_import |
44307
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
10 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
11 import struct |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
12 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
13 from .. import ( |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
14 error, |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
15 node as nodemod, |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
16 pycompat, |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
17 ) |
44034
ab595920de0e
revlogutils: move the NodeMap class in a dedicated nodemap module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
18 |
ab595920de0e
revlogutils: move the NodeMap class in a dedicated nodemap module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
19 |
ab595920de0e
revlogutils: move the NodeMap class in a dedicated nodemap module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
20 class NodeMap(dict): |
ab595920de0e
revlogutils: move the NodeMap class in a dedicated nodemap module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
21 def __missing__(self, x): |
ab595920de0e
revlogutils: move the NodeMap class in a dedicated nodemap module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
22 raise error.RevlogError(b'unknown node: %s' % x) |
44307
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
23 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
24 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
25 ### Nodemap Trie |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
26 # |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
27 # This is a simple reference implementation to compute and persist a nodemap |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
28 # trie. This reference implementation is write only. The python version of this |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
29 # is not expected to be actually used, since it wont provide performance |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
30 # improvement over existing non-persistent C implementation. |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
31 # |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
32 # The nodemap is persisted as Trie using 4bits-address/16-entries block. each |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
33 # revision can be adressed using its node shortest prefix. |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
34 # |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
35 # The trie is stored as a sequence of block. Each block contains 16 entries |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
36 # (signed 64bit integer, big endian). Each entry can be one of the following: |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
37 # |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
38 # * value >= 0 -> index of sub-block |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
39 # * value == -1 -> no value |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
40 # * value < -1 -> a revision value: rev = -(value+10) |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
41 # |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
42 # The implementation focus on simplicity, not on performance. A Rust |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
43 # implementation should provide a efficient version of the same binary |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
44 # persistence. This reference python implementation is never meant to be |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
45 # extensively use in production. |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
46 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
47 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
48 def persistent_data(index): |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
49 """return the persistent binary form for a nodemap for a given index |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
50 """ |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
51 trie = _build_trie(index) |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
52 return _persist_trie(trie) |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
53 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
54 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
55 S_BLOCK = struct.Struct(">" + ("l" * 16)) |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
56 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
57 NO_ENTRY = -1 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
58 # rev 0 need to be -2 because 0 is used by block, -1 is a special value. |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
59 REV_OFFSET = 2 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
60 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
61 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
62 def _transform_rev(rev): |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
63 """Return the number used to represent the rev in the tree. |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
64 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
65 (or retrieve a rev number from such representation) |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
66 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
67 Note that this is an involution, a function equal to its inverse (i.e. |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
68 which gives the identity when applied to itself). |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
69 """ |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
70 return -(rev + REV_OFFSET) |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
71 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
72 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
73 def _to_int(hex_digit): |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
74 """turn an hexadecimal digit into a proper integer""" |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
75 return int(hex_digit, 16) |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
76 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
77 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
78 def _build_trie(index): |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
79 """build a nodemap trie |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
80 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
81 The nodemap stores revision number for each unique prefix. |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
82 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
83 Each block is a dictionary with keys in `[0, 15]`. Values are either |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
84 another block or a revision number. |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
85 """ |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
86 root = {} |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
87 for rev in range(len(index)): |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
88 hex = nodemod.hex(index[rev][7]) |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
89 _insert_into_block(index, 0, root, rev, hex) |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
90 return root |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
91 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
92 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
93 def _insert_into_block(index, level, block, current_rev, current_hex): |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
94 """insert a new revision in a block |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
95 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
96 index: the index we are adding revision for |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
97 level: the depth of the current block in the trie |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
98 block: the block currently being considered |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
99 current_rev: the revision number we are adding |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
100 current_hex: the hexadecimal representation of the of that revision |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
101 """ |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
102 hex_digit = _to_int(current_hex[level : level + 1]) |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
103 entry = block.get(hex_digit) |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
104 if entry is None: |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
105 # no entry, simply store the revision number |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
106 block[hex_digit] = current_rev |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
107 elif isinstance(entry, dict): |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
108 # need to recurse to an underlying block |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
109 _insert_into_block(index, level + 1, entry, current_rev, current_hex) |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
110 else: |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
111 # collision with a previously unique prefix, inserting new |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
112 # vertices to fit both entry. |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
113 other_hex = nodemod.hex(index[entry][7]) |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
114 other_rev = entry |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
115 new = {} |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
116 block[hex_digit] = new |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
117 _insert_into_block(index, level + 1, new, other_rev, other_hex) |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
118 _insert_into_block(index, level + 1, new, current_rev, current_hex) |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
119 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
120 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
121 def _persist_trie(root): |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
122 """turn a nodemap trie into persistent binary data |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
123 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
124 See `_build_trie` for nodemap trie structure""" |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
125 block_map = {} |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
126 chunks = [] |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
127 for tn in _walk_trie(root): |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
128 block_map[id(tn)] = len(chunks) |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
129 chunks.append(_persist_block(tn, block_map)) |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
130 return b''.join(chunks) |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
131 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
132 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
133 def _walk_trie(block): |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
134 """yield all the block in a trie |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
135 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
136 Children blocks are always yield before their parent block. |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
137 """ |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
138 for (_, item) in sorted(block.items()): |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
139 if isinstance(item, dict): |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
140 for sub_block in _walk_trie(item): |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
141 yield sub_block |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
142 yield block |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
143 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
144 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
145 def _persist_block(block_node, block_map): |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
146 """produce persistent binary data for a single block |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
147 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
148 Children block are assumed to be already persisted and present in |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
149 block_map. |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
150 """ |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
151 data = tuple(_to_value(block_node.get(i), block_map) for i in range(16)) |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
152 return S_BLOCK.pack(*data) |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
153 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
154 |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
155 def _to_value(item, block_map): |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
156 """persist any value as an integer""" |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
157 if item is None: |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
158 return NO_ENTRY |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
159 elif isinstance(item, dict): |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
160 return block_map[id(item)] |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
161 else: |
c577bb4a04d4
nodemap: have some python code writing a nodemap in persistent binary form
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44034
diff
changeset
|
162 return _transform_rev(item) |