author | Pierre-Yves David <pierre-yves.david@octobus.net> |
Wed, 15 Jan 2020 15:47:31 +0100 | |
changeset 44309 | 6c07480d6659 |
parent 44308 | 5962fd0d1045 |
child 44310 | daad3aace942 |
permissions | -rw-r--r-- |
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 |
|
44309
6c07480d6659
nodemap: add a function to read the data from disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44308
diff
changeset
|
25 |
def persisted_data(revlog): |
6c07480d6659
nodemap: add a function to read the data from disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44308
diff
changeset
|
26 |
"""read the nodemap for a revlog from disk""" |
6c07480d6659
nodemap: add a function to read the data from disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44308
diff
changeset
|
27 |
if revlog.nodemap_file is None: |
6c07480d6659
nodemap: add a function to read the data from disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44308
diff
changeset
|
28 |
return None |
6c07480d6659
nodemap: add a function to read the data from disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44308
diff
changeset
|
29 |
return revlog.opener.tryread(revlog.nodemap_file) |
6c07480d6659
nodemap: add a function to read the data from disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44308
diff
changeset
|
30 |
|
6c07480d6659
nodemap: add a function to read the data from disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44308
diff
changeset
|
31 |
|
44308
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
32 |
def setup_persistent_nodemap(tr, revlog): |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
33 |
"""Install whatever is needed transaction side to persist a nodemap on disk |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
34 |
|
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
35 |
(only actually persist the nodemap if this is relevant for this revlog) |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
36 |
""" |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
37 |
if revlog.nodemap_file is None: |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
38 |
return # we do not use persistent_nodemap on this revlog |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
39 |
callback_id = b"revlog-persistent-nodemap-%s" % revlog.nodemap_file |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
40 |
if tr.hasfinalize(callback_id): |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
41 |
return # no need to register again |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
42 |
tr.addfinalize(callback_id, lambda tr: _persist_nodemap(tr, revlog)) |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
43 |
|
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
44 |
|
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
45 |
def _persist_nodemap(tr, revlog): |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
46 |
"""Write nodemap data on disk for a given revlog |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
47 |
""" |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
48 |
if getattr(revlog, 'filteredrevs', ()): |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
49 |
raise error.ProgrammingError( |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
50 |
"cannot persist nodemap of a filtered changelog" |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
51 |
) |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
52 |
if revlog.nodemap_file is None: |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
53 |
msg = "calling persist nodemap on a revlog without the feature enableb" |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
54 |
raise error.ProgrammingError(msg) |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
55 |
data = persistent_data(revlog.index) |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
56 |
# EXP-TODO: if this is a cache, this should use a cache vfs, not a |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
57 |
# store vfs |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
58 |
with revlog.opener(revlog.nodemap_file, b'w') as f: |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
59 |
f.write(data) |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
60 |
# EXP-TODO: if the transaction abort, we should remove the new data and |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
61 |
# reinstall the old one. (This will be simpler when the file format get a |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
62 |
# bit more advanced) |
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
63 |
|
5962fd0d1045
nodemap: write nodemap data on disk
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
44307
diff
changeset
|
64 |
|
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
|
65 |
### 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
|
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 |
# 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
|
68 |
# 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
|
69 |
# 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
|
70 |
# 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
|
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 |
# 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
|
73 |
# 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
|
74 |
# |
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 |
# 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
|
76 |
# (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
|
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 |
# * 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
|
79 |
# * 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
|
80 |
# * 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
|
81 |
# |
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 |
# 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
|
83 |
# 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
|
84 |
# 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
|
85 |
# 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
|
86 |
|
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 |
|
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 |
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
|
89 |
"""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
|
90 |
""" |
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 |
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
|
92 |
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
|
93 |
|
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 |
|
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 |
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
|
96 |
|
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 |
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
|
98 |
# 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
|
99 |
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
|
100 |
|
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 |
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
|
103 |
"""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
|
104 |
|
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 |
(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
|
106 |
|
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 |
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
|
108 |
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
|
109 |
""" |
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 |
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
|
111 |
|
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 |
|
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 |
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
|
114 |
"""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
|
115 |
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
|
116 |
|
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 |
|
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 |
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
|
119 |
"""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
|
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 |
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
|
122 |
|
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 |
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
|
124 |
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
|
125 |
""" |
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 |
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
|
127 |
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
|
128 |
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
|
129 |
_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
|
130 |
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
|
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 _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
|
134 |
"""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
|
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 |
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
|
137 |
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
|
138 |
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
|
139 |
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
|
140 |
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
|
141 |
""" |
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 |
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
|
143 |
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
|
144 |
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
|
145 |
# 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
|
146 |
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
|
147 |
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
|
148 |
# 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
|
149 |
_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
|
150 |
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
|
151 |
# 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
|
152 |
# 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
|
153 |
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
|
154 |
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
|
155 |
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
|
156 |
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
|
157 |
_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
|
158 |
_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
|
159 |
|
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 |
|
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 |
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
|
162 |
"""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
|
163 |
|
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
|
164 |
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
|
165 |
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
|
166 |
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
|
167 |
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
|
168 |
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
|
169 |
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
|
170 |
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
|
171 |
|
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
|
172 |
|
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
|
173 |
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
|
174 |
"""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
|
175 |
|
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
|
176 |
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
|
177 |
""" |
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
|
178 |
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
|
179 |
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
|
180 |
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
|
181 |
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
|
182 |
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
|
183 |
|
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
|
184 |
|
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
|
185 |
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
|
186 |
"""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
|
187 |
|
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
|
188 |
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
|
189 |
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
|
190 |
""" |
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
|
191 |
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
|
192 |
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
|
193 |
|
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
|
194 |
|
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
|
195 |
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
|
196 |
"""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
|
197 |
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
|
198 |
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
|
199 |
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
|
200 |
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
|
201 |
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
|
202 |
return _transform_rev(item) |