ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/CBOR-XS/doc/value-sharing.pod
(Generate patch)

Comparing CBOR-XS/doc/value-sharing.pod (file contents):
Revision 1.1 by root, Tue Nov 26 09:43:39 2013 UTC vs.
Revision 1.2 by root, Thu Nov 28 10:16:50 2013 UTC

1=head1 REGISTRATION INFORMATION 1=head1 REGISTRATION INFORMATION
2 2
3 Tag <unassigned> (shareable) 3 Tag 28 (shareable)
4 Data Item multiple 4 Data Item multiple
5 Semantics mark value as (potentially) shared 5 Semantics mark value as (potentially) shared
6 Reference http://cbor.schmorp.de/value-sharing 6 Reference http://cbor.schmorp.de/value-sharing
7 Contact Marc A. Lehmann <cbor@schmorp.de> 7 Contact Marc A. Lehmann <cbor@schmorp.de>
8 8
9 Tag <unassigned> (sharedref) 9 Tag 29 (sharedref)
10 Data Item unsigned integer 10 Data Item unsigned integer
11 Semantics reference nth marked value 11 Semantics reference nth marked value
12 Reference http://cbor.schmorp.de/value-sharing 12 Reference http://cbor.schmorp.de/value-sharing
13 Contact Marc A. Lehmann <cbor@schmorp.de> 13 Contact Marc A. Lehmann <cbor@schmorp.de>
14 14
… …
34encoding duplicated values only once - the shared values are supposed 34encoding duplicated values only once - the shared values are supposed
35to refer to the same value after decoding (e.g. when implemented as a 35to refer to the same value after decoding (e.g. when implemented as a
36pointer, all references to the value should point to the same memory 36pointer, all references to the value should point to the same memory
37object). 37object).
38 38
39Space saving is a side effect of encoding data structures with large
40shared substructures using this extension - the CBOR representation will
41then have similar space requirements as the original dats structure.
42
39=head1 DESCRIPTION 43=head1 DESCRIPTION
40 44
41To share values, the first occurrence of the value must be explicitly 45To share values, the first occurrence of the value must be explicitly
42tagged with the shareable tag (value <unassigned>). 46tagged with the shareable tag (value C<28>).
43 47
44Subsequent occurrences can then be encoded by encoding the index 48Subsequent occurrences can then be encoded by encoding the index
45of a previously marked value tagged with the sharedref tag (value 49of a previously marked value tagged with the sharedref tag (value
46<unassigned>). That is, index 0 refers to the first value marked as 50C<29>). That is, index 0 refers to the first value marked as
47shareable in the CBOR stream, index 1 to the second and so on. 51shareable in the CBOR stream, index 1 to the second and so on.
48 52
49There is no requirement to actually refer to a value marked as 53There is no requirement to actually refer to a value marked as
50shareable - encoders can mark any value they want without ever 54shareable - encoders can mark any value they want without ever
51referring to them. 55referring to them.
… …
70 74
71The semantics of shareable/sharedref tags require the decoder to be 75The semantics of shareable/sharedref tags require the decoder to be
72aware and the encoder to be under control of the sequence in which data 76aware and the encoder to be under control of the sequence in which data
73items are encoded into the CBOR stream. This means these tags cannot be 77items are encoded into the CBOR stream. This means these tags cannot be
74implemented on top of every generic CBOR encoder/decoder (which might 78implemented on top of every generic CBOR encoder/decoder (which might
75reorder entries in a map); they need to be integrated into their works. 79reorder entries in a map); they typically need to be integrated into their
80works.
76 81
77=head1 EXAMPLES 82=head1 EXAMPLES
78 83
79<TBD> 84=head2 A simple shared array
80 85
86The following Perl fragment creates an array reference with three entries,
87all of which array references themselves. All of them contain the same
88data, but the first two actually reference the same (shared) data
89structure:
90
91 $data = [ ([]) x 2, [] ];
92
93This is another way to create it:
94
95 my $shared = [];
96 $data = [ $shared, $shared, [] ];
97
98The shared aspect means that setting an element of the first nested
99arrayref also makes it visible inside the second nested arrayref, as it is
100the same array:
101
102 $data->[0][0] = "test";
103 # results in: [["test"],["test"],[]]
104
105A standard CBOR en-/decoder will encode three separate arrays, which
106will decode into three separate arrays again. So when the original data
107structure is en- and then decoded, the arrays will be unshared:
108
109 $unshared = decode_cbor encode_cbor [ ([]) x 2, [] ];
110 $unshared->[0][0] = "test";
111 # results in: [["test"],[],[]]
112
113The CBOR encoding might be:
114
115 83 # array(3)
116 80 # array(0)
117 80 # array(0)
118 80 # array(0)
119
120The value-sharing extension allows an encoder to flag the two arrays and
121keep the shared arrays actually shared. For example, the CBOR::XS encoder,
122when configured to use the value sharing extension, will emit this CBOR
123value:
124
125 [28([]), 29(0), []]
126
127 83 # array(3)
128 d8 1c # tag(28)
129 80 # array(0)
130 d8 1d # tag(29)
131 00 # unsigned(0)
132 80 # array(0)
133
134When decoding it, the first two array references will point to the same array.
135
136=head2 A cyclic data structure
137
138The following cyclic Perl data structure references itself from within
139itself. Here a decoder will see a reference to the shared value I<before>
140it has decoded the shared value itself:
141
142 $data = [];
143 $data->[0] = $data; # make the first array eleemnt refer to the array
144
145This data structure is not representable in standard CBOR. Using the value
146sharing extension, it can be encoded as follows:
147
148 28([29(0)])
149
150 d8 1c # tag(28)
151 81 # array(1)
152 d8 1d # tag(29)
153 00 # unsigned(0)
154

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines