You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@subversion.apache.org by st...@apache.org on 2013/03/27 22:53:02 UTC
svn commit: r1461865 - in /subversion/branches/fsfs-format7/subversion:
include/private/svn_packed_data.h include/svn_error_codes.h
libsvn_subr/packed_data.c
Author: stefan2
Date: Wed Mar 27 21:52:57 2013
New Revision: 1461865
URL: http://svn.apache.org/r1461865
Log:
On the fsfs-format7: Introduce a framework for space and time-
efficient storage of binary data. For details, see the header
file documentation.
* subversion/include/private/svn_packed_data.h
(): new header
(SVN__PACKED_DATA_BUFFER_SIZE): new constant
(svn__packed_data_root_t,
svn__packed_byte_stream_t,
svn__packed_int_stream_t): new data types
(svn__packed_data_create_root,
svn__packed_create_int_stream,
svn__packed_create_int_substream,
svn__packed_create_bytes_stream,
svn__packed_create_bytes_substream,
svn__packed_data_flush_buffer,
svn__packed_add_uint,
svn__packed_add_int,
svn__packed_add_bytes,
svn__packed_data_write): declare data write API
(svn__packed_first_int_stream,
svn__packed_first_byte_stream,
svn__packed_next_int_stream,
svn__packed_next_byte_stream,
svn__packed_first_int_substream,
svn__packed_first_byte_substream,
svn__packed_int_count,
svn__packed_byte_count,
svn__packed_data_fill_buffer,
svn__packed_get_uint,
svn__packed_get_int,
svn__packed_get_bytes,
svn__packed_data_read): declare data read API
* subversion/include/svn_error_codes.h
(SVN_ERR_CORRUPT_PACKED_DATA): define new error code
* subversion/libsvn_subr/packed_data.c
(): new source
(packed_int_private_t): new private data type
(svn__packed_byte_stream_t,
svn__packed_data_root_t): define data types
(create_bytes_stream_body,
packed_data_create_bytes_substream_body,
write_packed_uint_body,
write_packed_uint,
write_int_stream_structure,
write_byte_stream_structure,
write_stream_uint,
packed_int_stream_length,
packed_byte_stream_length,
append_int_stream,
append_byte_stream,
write_stream_data,
read_packed_uint_body,
read_stream_uint,
read_packed_uint,
read_int_stream_structure,
read_byte_stream_structure,
read_stream_data,
unflatten_int_stream,
unflatten_byte_stream): new utility functions
(svn__packed_data_create_root,
svn__packed_create_int_stream,
svn__packed_create_int_substream,
svn__packed_create_bytes_stream,
svn__packed_create_bytes_substream,
svn__packed_data_flush_buffer,
svn__packed_add_uint,
svn__packed_add_int,
svn__packed_add_bytes,
svn__packed_data_write): implement data write API
(svn__packed_first_int_stream,
svn__packed_first_byte_stream,
svn__packed_next_int_stream,
svn__packed_next_byte_stream,
svn__packed_first_int_substream,
svn__packed_first_byte_substream,
svn__packed_int_count,
svn__packed_byte_count,
svn__packed_data_fill_buffer,
svn__packed_get_uint,
svn__packed_get_int,
svn__packed_get_bytes,
svn__packed_data_read): implement data read API
Added:
subversion/branches/fsfs-format7/subversion/include/private/svn_packed_data.h
subversion/branches/fsfs-format7/subversion/libsvn_subr/packed_data.c
Modified:
subversion/branches/fsfs-format7/subversion/include/svn_error_codes.h
Added: subversion/branches/fsfs-format7/subversion/include/private/svn_packed_data.h
URL: http://svn.apache.org/viewvc/subversion/branches/fsfs-format7/subversion/include/private/svn_packed_data.h?rev=1461865&view=auto
==============================================================================
--- subversion/branches/fsfs-format7/subversion/include/private/svn_packed_data.h (added)
+++ subversion/branches/fsfs-format7/subversion/include/private/svn_packed_data.h Wed Mar 27 21:52:57 2013
@@ -0,0 +1,269 @@
+/* packed_data.h : Interface to the packed binary stream data structure
+ *
+ * ====================================================================
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ * ====================================================================
+ */
+
+#include "svn_string.h"
+#include "svn_io.h"
+
+/* This API provides Yet Another Serialization Framework.
+ *
+ * It is geared towards efficiently encoding collections of structured
+ * binary data (e.g. an array of noderev objects). The basic idea is to
+ * transform them into hierarchies of streams with each stream usually
+ * corresponding to a single attribute in the original data structures.
+ * The user is free model the mapping structure <-> streams mapping as she
+ * sees fit.
+ *
+ * With all data inside the same (sub-)stream carrying similar attribute
+ * values, the whole stream lends itself to data compression. Strings /
+ * plain byte sequences will be stored as is. Numbers use a 7b/8b encoding
+ * scheme to eliminate leading zeros. Because values are often dependent
+ * (increasing offsets, roughly similar revision number, etc.), streams
+ * can be configured as storing (hopefully shorter) deltas instead of the
+ * original value.
+ *
+ * Two stream types are provided: integer and byte streams. While the
+ * first store 64 bit integers only and can be configured to assume
+ * signed and / or deltifyable data, the second will store arbitrary
+ * byte sequences including their length. At the root level, you may
+ * create an arbitrary number of integer and byte streams. Any stream
+ * may have an arbitrary number of sub-streams of the same kind. You
+ * should create the full stream hierarchy before writing any data to it.
+ *
+ * As a convenience, when an integer stream has sub-streams, you may write
+ * to the parent stream instead of all sub-streams individually and the
+ * values will be passed down automatically in a round-robin fashion.
+ * Reading from the parent stream is similarly supported.
+ *
+ * When all data has been added to the stream, it can be written to an
+ * ordinary svn_stream_t. First, we write a description of the stream
+ * structure (types, sub-streams, sizes and configurations) followed by
+ * zlib compressed stream content. For each top-level stream, all sub-
+ * stream data will be concatenated and then compressed as a single block.
+ * To maximize the effect of this, make sure all data in that stream
+ * hierarchy has a similar value distribution.
+ *
+ * Reading data starts with an svn_stream_t and automatically recreates
+ * the stream hierarchies. You only need to extract data from it in the
+ * same order as you wrote it.
+ *
+ * Although not enforced programmatically, you may either only write to a
+ * stream hierarchy or only read from it but you cannot do both on the
+ * same data structure.
+ */
+
+
+
+/* We pack / unpack integers en block to minimize calling and setup overhead.
+ * This is the number of integers we put into a buffer before writing them
+ * them to / after reading them from the 7b/8b stream. Under 64 bits, this
+ * value creates a 128 byte data structure (14 + 2 integers, 8 bytes each).
+ */
+#define SVN__PACKED_DATA_BUFFER_SIZE 14
+
+
+/* Data types. */
+
+/* Opaque type for the root object.
+ */
+typedef struct svn__packed_data_root_t svn__packed_data_root_t;
+
+/* Opaque type for byte streams.
+ */
+typedef struct svn__packed_byte_stream_t svn__packed_byte_stream_t;
+
+/* Semi-opaque type for integer streams. We expose the unpacked buffer
+ * to allow for replacing svn__packed_add_uint and friends by macros.
+ */
+typedef struct svn__packed_int_stream_t
+{
+ /* pointer to the remainder of the data structure */
+ void *private_data;
+
+ /* number of value entries in BUFFER */
+ apr_size_t buffer_used;
+
+ /* unpacked integers (either yet to be packed or pre-fetched from the
+ * packed buffers). Only the first BUFFER_USED entries are valid. */
+ apr_uint64_t buffer[SVN__PACKED_DATA_BUFFER_SIZE];
+} svn__packed_int_stream_t;
+
+
+/* Writing data. */
+
+/* Return a new serialization root object, allocated in POOL.
+ */
+svn__packed_data_root_t *
+svn__packed_data_create_root(apr_pool_t *pool);
+
+/* Create and return a new top-level integer stream in ROOT. If signed,
+ * negative numbers will be put into that stream, SIGNED_INTS should be
+ * TRUE as a more efficient encoding will be used in that case. Set
+ * DIFF to TRUE if you expect the difference between consecutive numbers
+ * to be much smaller (~100 times) than the actual numbers.
+ */
+svn__packed_int_stream_t *
+svn__packed_create_int_stream(svn__packed_data_root_t *root,
+ svn_boolean_t diff,
+ svn_boolean_t signed_ints);
+
+/* Create and return a sub-stream to the existing integer stream PARENT.
+ * If signed, negative numbers will be put into that stream, SIGNED_INTS
+ * should be TRUE as a more efficient encoding will be used in that case.
+ * Set DIFF to TRUE if you expect the difference between consecutive numbers
+ * to be much smaller (~100 times) than the actual numbers.
+ */
+svn__packed_int_stream_t *
+svn__packed_create_int_substream(svn__packed_int_stream_t *parent,
+ svn_boolean_t diff,
+ svn_boolean_t signed_ints);
+
+/* Create and return a new top-level byte sequence stream in ROOT.
+ */
+svn__packed_byte_stream_t *
+svn__packed_create_bytes_stream(svn__packed_data_root_t *root);
+
+/* Create and return a new sub-stream to the existing byte sequence stream
+ * PARENT.
+ */
+svn__packed_byte_stream_t *
+svn__packed_create_bytes_substream(svn__packed_byte_stream_t *parent);
+
+/* Empty the unprocessed integer buffer in STREAM by either pushing the
+ * data to the sub-streams or writing to the packed data (in case there
+ * are no sub-streams). Users don't need to call this explicitly as it
+ * will be called by svn__packed_add_uint, svn__packed_add_int and
+ * svn__packed_data_write as necessary.
+ */
+void
+svn__packed_data_flush_buffer(svn__packed_int_stream_t *stream);
+
+/* Write the unsigned integer VALUE to STEAM.
+ */
+void
+svn__packed_add_uint(svn__packed_int_stream_t *stream,
+ apr_uint64_t value);
+
+/* Write the signed integer VALUE to STEAM.
+ */
+void
+svn__packed_add_int(svn__packed_int_stream_t *stream,
+ apr_int64_t value);
+
+/* Write the sequence stating at DATA containing LEN bytes to STEAM.
+ */
+void
+svn__packed_add_bytes(svn__packed_byte_stream_t *stream,
+ const char *data,
+ apr_size_t len);
+
+/* Write all contents of ROOT (including all sub-streams) to STREAM.
+ * Use SCRATCH_POOL for temporary allocations.
+ */
+svn_error_t *
+svn__packed_data_write(svn_stream_t *stream,
+ svn__packed_data_root_t *root,
+ apr_pool_t *scratch_pool);
+
+
+/* Reading data. */
+
+/* Return the first integer stream in ROOT. Returns NULL in case there
+ * aren't any.
+ */
+svn__packed_int_stream_t *
+svn__packed_first_int_stream(svn__packed_data_root_t *root);
+
+/* Return the first byte sequence stream in ROOT. Returns NULL in case
+ * there aren't any.
+ */
+svn__packed_byte_stream_t *
+svn__packed_first_byte_stream(svn__packed_data_root_t *root);
+
+/* Return the next (sibling) integer stream to STREAM. Returns NULL in
+ * case there isn't any.
+ */
+svn__packed_int_stream_t *
+svn__packed_next_int_stream(svn__packed_int_stream_t *stream);
+
+/* Return the next (sibling) byte sequence stream to STREAM. Returns NULL
+ * in case there isn't any.
+ */
+svn__packed_byte_stream_t *
+svn__packed_next_byte_stream(svn__packed_byte_stream_t *stream);
+
+/* Return the first sub-stream of STREAM. Returns NULL in case there
+ * isn't any.
+ */
+svn__packed_int_stream_t *
+svn__packed_first_int_substream(svn__packed_int_stream_t *stream);
+
+/* Return the first sub-stream of STREAM. Returns NULL in case there
+ * isn't any.
+ */
+svn__packed_byte_stream_t *
+svn__packed_first_byte_substream(svn__packed_byte_stream_t *stream);
+
+/* Return the number of integers left to read from STREAM.
+ */
+apr_size_t
+svn__packed_int_count(svn__packed_int_stream_t *stream);
+
+/* Return the number of bytes left to read from STREAM.
+ */
+apr_size_t
+svn__packed_byte_count(svn__packed_byte_stream_t *stream);
+
+/* Return the number of bytes left to read from STREAM.
+ */
+void
+svn__packed_data_fill_buffer(svn__packed_int_stream_t *stream);
+
+/* Return the next number from STREAM as unsigned integer. Returns 0 when
+ * reading beyond the end of the stream.
+ */
+apr_uint64_t
+svn__packed_get_uint(svn__packed_int_stream_t *stream);
+
+/* Return the next number from STREAM as signed integer. Returns 0 when
+ * reading beyond the end of the stream.
+ */
+apr_int64_t
+svn__packed_get_int(svn__packed_int_stream_t *stream,
+ apr_int64_t value);
+
+/* Return the next byte sequence from STREAM and set *LEN to the length
+ * of that sequence. Sets *LEN to 0 when reading beyond the end of the
+ * stream.
+ */
+const char *
+svn__packed_get_bytes(svn__packed_byte_stream_t *stream,
+ apr_size_t *len);
+
+/* Allocate a new packed data root in RESULT_POOL, read its structure and
+ * stream contents from STREAM and return it in *ROOT_P. Use SCRATCH_POOL
+ * for temporary allocations.
+ */
+svn_error_t *
+svn__packed_data_read(svn__packed_data_root_t **root_p,
+ svn_stream_t *stream,
+ apr_pool_t *result_pool,
+ apr_pool_t *scratch_pool);
Modified: subversion/branches/fsfs-format7/subversion/include/svn_error_codes.h
URL: http://svn.apache.org/viewvc/subversion/branches/fsfs-format7/subversion/include/svn_error_codes.h?rev=1461865&r1=1461864&r2=1461865&view=diff
==============================================================================
--- subversion/branches/fsfs-format7/subversion/include/svn_error_codes.h (original)
+++ subversion/branches/fsfs-format7/subversion/include/svn_error_codes.h Wed Mar 27 21:52:57 2013
@@ -1460,6 +1460,11 @@ SVN_ERROR_START
SVN_ERR_MISC_CATEGORY_START + 38,
"Atomic data storage is corrupt")
+ /** @since New in 1.9. */
+ SVN_ERRDEF(SVN_ERR_CORRUPT_PACKED_DATA,
+ SVN_ERR_MISC_CATEGORY_START + 39,
+ "Packed data stream is corrupt")
+
/* command-line client errors */
SVN_ERRDEF(SVN_ERR_CL_ARG_PARSING_ERROR,
Added: subversion/branches/fsfs-format7/subversion/libsvn_subr/packed_data.c
URL: http://svn.apache.org/viewvc/subversion/branches/fsfs-format7/subversion/libsvn_subr/packed_data.c?rev=1461865&view=auto
==============================================================================
--- subversion/branches/fsfs-format7/subversion/libsvn_subr/packed_data.c (added)
+++ subversion/branches/fsfs-format7/subversion/libsvn_subr/packed_data.c Wed Mar 27 21:52:57 2013
@@ -0,0 +1,1130 @@
+/* packed_data.c : implement the packed binary stream data structure
+ *
+ * ====================================================================
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ * ====================================================================
+ */
+
+#include <apr_tables.h>
+
+#include "svn_string.h"
+#include "svn_sorts.h"
+#include "private/svn_string_private.h"
+#include "private/svn_subr_private.h"
+#include "private/svn_delta_private.h"
+#include "private/svn_packed_data.h"
+
+#include "svn_private_config.h"
+
+
+
+/* Private int stream data referenced by svn__packed_int_stream_t.
+ */
+typedef struct packed_int_private_t
+{
+ /* First sub-stream, if any. NULL otherwise. */
+ svn__packed_int_stream_t *first_substream;
+
+ /* Last sub-stream, if any. NULL otherwise. */
+ svn__packed_int_stream_t *last_substream;
+
+ /* Current sub-stream to read from / write to, if any. NULL otherwise.
+ This will be initialized to FIRST_SUBSTREAM and then advanced in a
+ round-robin scheme after each number being read. */
+ svn__packed_int_stream_t *current_substream;
+
+ /* Number of sub-streams. */
+ apr_size_t substream_count;
+
+ /* Next (sibling) integer stream. If this is the last one, points to
+ the first in the list (i.e. this forms a ring list). Never NULL. */
+ svn__packed_int_stream_t *next;
+
+ /* 7b/8b encoded integer values (previously diff'ed and sign-handled,
+ if indicated by the flags below). The contents are disjoint from
+ the unparsed number buffer. May be NULL while not written to. */
+ svn_stringbuf_t *packed;
+
+ /* Initialized to 0. Latest value written to / read from PACKED.
+ Undefined if DIFF is FALSE. */
+ apr_uint64_t last_value;
+
+ /* Deltify data before storing it in PACKED. */
+ svn_boolean_t diff;
+
+ /* Numbers are likely to contain negative values with small absolutes.
+ If TRUE, store the signed bit in LSB before encoding. */
+ svn_boolean_t is_signed;
+
+ /* Number of integers in this stream. */
+ apr_size_t item_count;
+
+ /* TRUE for the last stream in a list of siblings. */
+ svn_boolean_t is_last;
+
+ /* Pool to use for allocations. */
+ apr_pool_t *pool;
+} packed_int_private_t;
+
+/* A byte sequence stream. Please note that NEXT is defined different
+ * from the NEXT member in integer streams.
+ */
+struct svn__packed_byte_stream_t
+{
+ /* First sub-stream, if any. NULL otherwise. */
+ svn__packed_byte_stream_t *first_substream;
+
+ /* Last sub-stream, if any. NULL otherwise. */
+ svn__packed_byte_stream_t *last_substream;
+
+ /* Number of sub-streams. */
+ apr_size_t substream_count;
+
+ /* Next (sibling) byte sequence stream, if any. NULL otherwise. */
+ svn__packed_byte_stream_t *next;
+
+ /* Stream to store the sequence lengths. */
+ svn__packed_int_stream_t *lengths_stream;
+
+ /* It's index (relative to its parent). */
+ apr_size_t lengths_stream_index;
+
+ /* Concatenated byte sequences. */
+ svn_stringbuf_t *packed;
+
+ /* Pool to use for allocations. */
+ apr_pool_t *pool;
+};
+
+/* The serialization root object. It references the top-level streams.
+ */
+struct svn__packed_data_root_t
+{
+ /* First top-level integer stream, if any. NULL otherwise. */
+ svn__packed_int_stream_t *first_int_stream;
+
+ /* Last top-level integer stream, if any. NULL otherwise. */
+ svn__packed_int_stream_t *last_int_stream;
+
+ /* Number of top-level integer streams. */
+ apr_size_t int_stream_count;
+
+ /* First top-level byte sequence stream, if any. NULL otherwise. */
+ svn__packed_byte_stream_t *first_byte_stream;
+
+ /* Last top-level byte sequence stream, if any. NULL otherwise. */
+ svn__packed_byte_stream_t *last_byte_stream;
+
+ /* Number of top-level byte sequence streams. */
+ apr_size_t byte_stream_count;
+
+ /* Pool to use for allocations. */
+ apr_pool_t *pool;
+};
+
+/* Write access. */
+
+svn__packed_data_root_t *
+svn__packed_data_create_root(apr_pool_t *pool)
+{
+ svn__packed_data_root_t *root = apr_pcalloc(pool, sizeof(*root));
+ root->pool = pool;
+
+ return root;
+}
+
+svn__packed_int_stream_t *
+svn__packed_create_int_stream(svn__packed_data_root_t *root,
+ svn_boolean_t diff,
+ svn_boolean_t signed_ints)
+{
+ /* allocate and initialize the stream node */
+ packed_int_private_t *private_data
+ = apr_pcalloc(root->pool, sizeof(*private_data));
+ svn__packed_int_stream_t *stream
+ = apr_palloc(root->pool, sizeof(*stream));
+
+ private_data->diff = diff;
+ private_data->is_signed = signed_ints;
+ private_data->is_last = TRUE;
+ private_data->pool = root->pool;
+
+ stream->buffer_used = 0;
+ stream->private_data = private_data;
+
+ /* maintain the ring list */
+ if (root->last_int_stream)
+ {
+ packed_int_private_t *previous_private_data
+ = root->last_int_stream->private_data;
+ previous_private_data->next = stream;
+ previous_private_data->is_last = FALSE;
+ }
+ else
+ {
+ root->first_int_stream = stream;
+ }
+
+ root->last_int_stream = stream;
+ root->int_stream_count++;
+
+ return stream;
+}
+
+svn__packed_int_stream_t *
+svn__packed_create_int_substream(svn__packed_int_stream_t *parent,
+ svn_boolean_t diff,
+ svn_boolean_t signed_ints)
+{
+ packed_int_private_t *parent_private = parent->private_data;
+
+ /* allocate and initialize the stream node */
+ packed_int_private_t *private_data
+ = apr_pcalloc(parent_private->pool, sizeof(*private_data));
+ svn__packed_int_stream_t *stream
+ = apr_palloc(parent_private->pool, sizeof(*stream));
+
+ private_data->diff = diff;
+ private_data->is_signed = signed_ints;
+ private_data->is_last = TRUE;
+ private_data->pool = parent_private->pool;
+
+ stream->buffer_used = 0;
+ stream->private_data = private_data;
+
+ /* maintain the ring list */
+ if (parent_private->last_substream)
+ {
+ packed_int_private_t *previous_private_data
+ = parent_private->last_substream->private_data;
+ previous_private_data->next = stream;
+ previous_private_data->is_last = FALSE;
+ }
+ else
+ {
+ parent_private->first_substream = stream;
+ parent_private->current_substream = stream;
+ }
+
+ parent_private->last_substream = stream;
+ parent_private->substream_count++;
+ private_data->next = parent_private->first_substream;
+
+ return stream;
+}
+
+/* Returns a new top-level byte sequence stream for ROOT but does not
+ * initialize the LENGTH_STREAM member.
+ */
+static svn__packed_byte_stream_t *
+create_bytes_stream_body(svn__packed_data_root_t *root)
+{
+ svn__packed_byte_stream_t *stream
+ = apr_pcalloc(root->pool, sizeof(*stream));
+
+ stream->packed = svn_stringbuf_create_empty(root->pool);
+
+ if (root->last_byte_stream)
+ root->last_byte_stream->next = stream;
+ else
+ root->first_byte_stream = stream;
+
+ root->last_byte_stream = stream;
+ root->byte_stream_count++;
+
+ return stream;
+}
+
+svn__packed_byte_stream_t *
+svn__packed_create_bytes_stream(svn__packed_data_root_t *root)
+{
+ svn__packed_byte_stream_t *stream
+ = create_bytes_stream_body(root);
+
+ stream->lengths_stream_index = root->int_stream_count;
+ stream->lengths_stream = svn__packed_create_int_stream(root, FALSE, FALSE);
+
+ return stream;
+}
+
+/* Returns a new sub-stream for PARENT but does not initialize the
+ * LENGTH_STREAM member.
+ */
+static svn__packed_byte_stream_t *
+packed_data_create_bytes_substream_body(svn__packed_byte_stream_t *parent)
+{
+ svn__packed_byte_stream_t *stream
+ = apr_pcalloc(parent->pool, sizeof(*stream));
+
+ stream->packed = svn_stringbuf_create_empty(parent->pool);
+
+ if (parent->last_substream)
+ parent->last_substream->next = stream;
+ else
+ parent->first_substream = stream;
+
+ parent->last_substream = stream;
+ parent->substream_count++;
+
+ return stream;
+}
+
+svn__packed_byte_stream_t *
+svn__packed_create_bytes_substream(svn__packed_byte_stream_t *parent)
+{
+ packed_int_private_t *parent_length_private
+ = parent->lengths_stream->private_data;
+ svn__packed_byte_stream_t *stream
+ = packed_data_create_bytes_substream_body(parent);
+
+ stream->lengths_stream_index = parent_length_private->substream_count;
+ stream->lengths_stream
+ = svn__packed_create_int_substream(parent->lengths_stream,
+ FALSE, FALSE);
+
+ return stream;
+}
+
+void
+svn__packed_add_uint(svn__packed_int_stream_t *stream,
+ apr_uint64_t value)
+{
+ stream->buffer[stream->buffer_used] = value;
+ if (++stream->buffer_used == SVN__PACKED_DATA_BUFFER_SIZE)
+ svn__packed_data_flush_buffer(stream);
+}
+
+void
+svn__packed_add_int(svn__packed_int_stream_t *stream,
+ apr_int64_t value)
+{
+ svn__packed_add_uint(stream, (apr_uint64_t)value);
+}
+
+void
+svn__packed_add_bytes(svn__packed_byte_stream_t *stream,
+ const char *data,
+ apr_size_t len)
+{
+ svn__packed_add_uint(stream->lengths_stream, len);
+ svn_stringbuf_appendbytes(stream->packed, data, len);
+}
+
+/* Write the 7b/8b representation of VALUE into BUFFER. BUFFER must
+ * provide at least 10 bytes space.
+ * Returns the first position behind the written data.
+ */
+static unsigned char *
+write_packed_uint_body(unsigned char *buffer, apr_uint64_t value)
+{
+ while (value >= 0x80)
+ {
+ *(buffer++) = (unsigned char)((value % 0x80) + 0x80);
+ value /= 0x80;
+ }
+
+ *(buffer++) = (unsigned char)value;
+ return buffer;
+}
+
+void
+svn__packed_data_flush_buffer(svn__packed_int_stream_t *stream)
+{
+ packed_int_private_t *private_data = stream->private_data;
+ apr_size_t i;
+
+ /* if we have sub-streams, push the data down to them */
+ if (private_data->current_substream)
+ for (i = 0; i < stream->buffer_used; ++i)
+ {
+ packed_int_private_t *current_private_data
+ = private_data->current_substream->private_data;
+
+ svn__packed_add_uint(private_data->current_substream,
+ stream->buffer[i]);
+ private_data->current_substream = current_private_data->next;
+ }
+ else
+ {
+ /* pack the numbers into our local PACKED buffer */
+
+ /* temporary buffer, max 10 bytes required per 7b/8b encoded number */
+ unsigned char local_buffer[10 * SVN__PACKED_DATA_BUFFER_SIZE];
+ unsigned char *p = local_buffer;
+
+ /* if configured, deltify numbers before packing them.
+ Since delta may be negative, always use the 'signed' encoding. */
+ if (private_data->diff)
+ {
+ apr_uint64_t last_value = private_data->last_value;
+ for (i = 0; i < stream->buffer_used; ++i)
+ {
+ apr_uint64_t temp = stream->buffer[i];
+ apr_uint64_t diff = temp - last_value;
+ stream->buffer[i] = diff < 0 ? 1 - 2 * diff : 2 * diff;
+ last_value = temp;
+ }
+
+ private_data->last_value = last_value;
+ }
+
+ /* if configured and not already done by the deltification above,
+ transform to 'signed' encoding. Store the sign in the LSB and
+ the absolute value (-1 for negative values) in the remaining
+ 63 bits. */
+ if (!private_data->diff && private_data->is_signed)
+ for (i = 0; i < stream->buffer_used; ++i)
+ stream->buffer[i] = stream->buffer[i] < 0
+ ? 1 - 2 * stream->buffer[i]
+ : 2 * stream->buffer[i];
+
+ /* auto-create packed data buffer. Give it some reasonable initial
+ size - just enough for a few tens of values. */
+ if (private_data->packed == NULL)
+ private_data->packed
+ = svn_stringbuf_create_ensure(256, private_data->pool);
+
+ /* encode numbers into our temp buffer. */
+ for (i = 0; i < stream->buffer_used; ++i)
+ p = write_packed_uint_body(p, stream->buffer[i]);
+
+ /* append them to the final packed data */
+ svn_stringbuf_appendbytes(private_data->packed,
+ (char *)local_buffer,
+ p - local_buffer);
+ }
+
+ /* maintain counters */
+ private_data->item_count += stream->buffer_used;
+ stream->buffer_used = 0;
+}
+
+/* Append the 7b/8b encoded representation of VALUE to PACKED.
+ */
+static void
+write_packed_uint(svn_stringbuf_t* packed, apr_uint64_t value)
+{
+ if (value < 0x80)
+ {
+ svn_stringbuf_appendbyte(packed, (char)value);
+ }
+ else
+ {
+ unsigned char buffer[10];
+ unsigned char *p = write_packed_uint_body(buffer, value);
+
+ svn_stringbuf_appendbytes(packed, (char *)buffer, p - buffer);
+ }
+}
+
+/* Recursively write the structure (config parameters, sub-streams, data
+ * sizes) of the STREAM and all its siblings to the TREE_STRUCT buffer.
+ */
+static void
+write_int_stream_structure(svn_stringbuf_t* tree_struct,
+ svn__packed_int_stream_t* stream)
+{
+ while (stream)
+ {
+ /* store config parameters and number of sub-streams in 1 number */
+ packed_int_private_t *private_data = stream->private_data;
+ write_packed_uint(tree_struct, (private_data->substream_count << 2)
+ + (private_data->diff ? 1 : 0)
+ + (private_data->is_signed ? 2 : 0));
+
+ /* store item count and length their of packed representation */
+ svn__packed_data_flush_buffer(stream);
+
+ write_packed_uint(tree_struct, private_data->item_count);
+ write_packed_uint(tree_struct, private_data->packed
+ ? private_data->packed->len
+ : 0);
+
+ /* append all sub-stream structures */
+ write_int_stream_structure(tree_struct, private_data->first_substream);
+
+ /* continue with next sibling */
+ stream = private_data->is_last ? NULL : private_data->next;
+ }
+}
+
+/* Recursively write the structure (sub-streams, data sizes) of the STREAM
+ * and all its siblings to the TREE_STRUCT buffer.
+ */
+static void
+write_byte_stream_structure(svn_stringbuf_t* tree_struct,
+ svn__packed_byte_stream_t* stream)
+{
+ /* for this and all siblings */
+ for (; stream; stream = stream->next)
+ {
+ /* this stream's structure and size */
+ write_packed_uint(tree_struct, stream->substream_count);
+ write_packed_uint(tree_struct, stream->lengths_stream_index);
+ write_packed_uint(tree_struct, stream->packed->len);
+
+ /* followed by all its sub-streams */
+ write_byte_stream_structure(tree_struct, stream->first_substream);
+ }
+}
+
+/* Write the 7b/8b encoded representation of VALUE to STREAM.
+ */
+static svn_error_t *
+write_stream_uint(svn_stream_t *stream,
+ apr_uint64_t value)
+{
+ unsigned char buffer[10];
+ apr_size_t count = write_packed_uint_body(buffer, value) - buffer;
+
+ SVN_ERR(svn_stream_write(stream, (char *)buffer, &count));
+
+ return SVN_NO_ERROR;
+}
+
+/* Return the total size of all packed data in STREAM, its siblings and
+ * all sub-streams. To get an accurate value, flush all buffers prior to
+ * calling this function.
+ */
+static apr_size_t
+packed_int_stream_length(svn__packed_int_stream_t *stream)
+{
+ packed_int_private_t *private_data = stream->private_data;
+ apr_size_t result = private_data->packed ? private_data->packed->len : 0;
+
+ stream = private_data->first_substream;
+ while (stream)
+ {
+ private_data = stream->private_data;
+ result += packed_int_stream_length(stream);
+ stream = private_data->is_last ? NULL : private_data->next;
+ }
+
+ return result;
+}
+
+/* Return the total size of all byte sequences data in STREAM, its siblings
+ * and all sub-streams.
+ */
+static apr_size_t
+packed_byte_stream_length(svn__packed_byte_stream_t *stream)
+{
+ apr_size_t result = stream->packed->len;
+
+ for (stream = stream->first_substream; stream; stream = stream->next)
+ result += packed_byte_stream_length(stream);
+
+ return result;
+}
+
+/* Append all packed data in STREAM, its siblings and all sub-streams to
+ * COMBINED.
+ */
+static void
+append_int_stream(svn__packed_int_stream_t *stream,
+ svn_stringbuf_t *combined)
+{
+ packed_int_private_t *private_data = stream->private_data;
+ if (private_data->packed)
+ svn_stringbuf_appendstr(combined, private_data->packed);
+
+ stream = private_data->first_substream;
+ while (stream)
+ {
+ private_data = stream->private_data;
+ append_int_stream(stream, combined);
+ stream = private_data->is_last ? NULL : private_data->next;
+ }
+}
+
+/* Append all byte sequences in STREAM, its siblings and all sub-streams
+ * to COMBINED.
+ */
+static void
+append_byte_stream(svn__packed_byte_stream_t *stream,
+ svn_stringbuf_t *combined)
+{
+ svn_stringbuf_appendstr(combined, stream->packed);
+
+ for (stream = stream->first_substream; stream; stream = stream->next)
+ append_byte_stream(stream, combined);
+}
+
+/* Take the binary data in UNCOMPRESSED, zip it into COMPRESSED and write
+ * it to STREAM. COMPRESSED simply acts as a re-usable memory buffer.
+ * Clear all buffers (COMPRESSED, UNCOMPRESSED) at the end of the function.
+ */
+static svn_error_t *
+write_stream_data(svn_stream_t *stream,
+ svn_stringbuf_t *uncompressed,
+ svn_stringbuf_t *compressed)
+{
+ SVN_ERR(svn__compress(uncompressed,
+ compressed,
+ SVN_DELTA_COMPRESSION_LEVEL_DEFAULT));
+
+ SVN_ERR(write_stream_uint(stream, compressed->len));
+ SVN_ERR(svn_stream_write(stream, compressed->data, &compressed->len));
+
+ svn_stringbuf_setempty(uncompressed);
+ svn_stringbuf_setempty(compressed);
+
+ return SVN_NO_ERROR;
+}
+
+svn_error_t *
+svn__packed_data_write(svn_stream_t *stream,
+ svn__packed_data_root_t *root,
+ apr_pool_t *scratch_pool)
+{
+ svn__packed_int_stream_t *int_stream;
+ svn__packed_byte_stream_t *byte_stream;
+
+ /* re-usable data buffers */
+ svn_stringbuf_t *compressed
+ = svn_stringbuf_create_ensure(1024, scratch_pool);
+ svn_stringbuf_t *uncompressed
+ = svn_stringbuf_create_ensure(1024, scratch_pool);
+
+ /* write tree structure */
+ svn_stringbuf_t *tree_struct
+ = svn_stringbuf_create_ensure(127, scratch_pool);
+
+ write_packed_uint(tree_struct, root->int_stream_count);
+ write_int_stream_structure(tree_struct, root->first_int_stream);
+
+ write_packed_uint(tree_struct, root->byte_stream_count);
+ write_byte_stream_structure(tree_struct, root->first_byte_stream);
+
+ SVN_ERR(write_stream_uint(stream, tree_struct->len));
+ SVN_ERR(svn_stream_write(stream, tree_struct->data, &tree_struct->len));
+
+ /* flatten sub-streams, zip them and write them to disk */
+
+ for (int_stream = root->first_int_stream;
+ int_stream;
+ int_stream = ((packed_int_private_t*)int_stream->private_data)->next)
+ {
+ apr_size_t len = packed_int_stream_length(int_stream);
+ svn_stringbuf_ensure(uncompressed, len);
+
+ append_int_stream(int_stream, uncompressed);
+ SVN_ERR(write_stream_data(stream, uncompressed, compressed));
+ }
+
+ for (byte_stream = root->first_byte_stream;
+ byte_stream;
+ byte_stream = byte_stream->next)
+ {
+ apr_size_t len = packed_byte_stream_length(byte_stream);
+ svn_stringbuf_ensure(uncompressed, len);
+
+ append_byte_stream(byte_stream, uncompressed);
+ SVN_ERR(write_stream_data(stream, uncompressed, compressed));
+ }
+
+ return SVN_NO_ERROR;
+}
+
+
+/* Read access. */
+
+svn__packed_int_stream_t *
+svn__packed_first_int_stream(svn__packed_data_root_t *root)
+{
+ return root->first_int_stream;
+}
+
+svn__packed_byte_stream_t *
+svn__packed_first_byte_stream(svn__packed_data_root_t *root)
+{
+ return root->first_byte_stream;
+}
+
+svn__packed_int_stream_t *
+svn__packed_next_int_stream(svn__packed_int_stream_t *stream)
+{
+ packed_int_private_t *private_data = stream->private_data;
+ return private_data->is_last ? NULL : private_data->next;
+}
+
+svn__packed_byte_stream_t *
+svn__packed_next_byte_stream(svn__packed_byte_stream_t *stream)
+{
+ return stream->next;
+}
+
+svn__packed_int_stream_t *
+svn__packed_first_int_substream(svn__packed_int_stream_t *stream)
+{
+ packed_int_private_t *private_data = stream->private_data;
+ return private_data->first_substream;
+}
+
+svn__packed_byte_stream_t *
+svn__packed_first_byte_substream(svn__packed_byte_stream_t *stream)
+{
+ return stream->first_substream;
+}
+
+apr_size_t
+svn__packed_int_count(svn__packed_int_stream_t *stream)
+{
+ packed_int_private_t *private_data = stream->private_data;
+ return private_data->item_count + stream->buffer_used;
+}
+
+apr_size_t
+svn__packed_byte_count(svn__packed_byte_stream_t *stream)
+{
+ return stream->packed->len;
+}
+
+apr_uint64_t
+svn__packed_get_uint(svn__packed_int_stream_t *stream)
+{
+ if (stream->buffer_used == 0)
+ svn__packed_data_fill_buffer(stream);
+
+ return stream->buffer_used ? stream->buffer[--stream->buffer_used] : 0;
+}
+
+apr_int64_t
+svn__packed_get_int(svn__packed_int_stream_t *stream,
+ apr_int64_t value)
+{
+ return (apr_int64_t)svn__packed_get_uint(stream);
+}
+
+const char *
+svn__packed_get_bytes(svn__packed_byte_stream_t *stream,
+ apr_size_t *len)
+{
+ const char *result = stream->packed->data;
+ apr_size_t count = svn__packed_get_uint(stream->lengths_stream);
+
+ if (count > stream->packed->len)
+ count = stream->packed->len;
+
+ /* advance packed buffer */
+ stream->packed->data += count;
+ stream->packed->len -= count;
+ stream->packed->blocksize -= count;
+
+ *len = count;
+ return result;
+}
+
+/* Read one 7b/8b encoded value from *P and return it in *RESULT. Returns
+ * the first position after the parsed data.
+ *
+ * Overflows will be detected in the sense that it will end parsing the
+ * input but the result is undefined.
+ */
+static unsigned char *
+read_packed_uint_body(unsigned char *p, apr_uint64_t *result)
+{
+ if (*p < 0x80)
+ {
+ *result = *p;
+ }
+ else
+ {
+ apr_uint64_t shift = 0;
+ apr_uint64_t value = 0;
+ while (*p >= 0x80)
+ {
+ value += (apr_uint64_t)(*p & 0x7f) << shift;
+ ++p;
+
+ shift += 7;
+ if (shift > 64)
+ {
+ /* a definite overflow. Note, that numbers of 65 .. 70
+ bits will not be detected as an overflow as they don't
+ threaten to exceed the input buffer. */
+ *result = 0;
+ return p;
+ }
+ }
+
+ *result = value + ((apr_uint64_t)*p << shift);
+ }
+
+ return ++p;
+}
+
+/* Read one 7b/8b encoded value from STREAM and return it in *RESULT.
+ *
+ * Overflows will be detected in the sense that it will end parsing the
+ * input but the result is undefined.
+ */
+static svn_error_t *
+read_stream_uint(svn_stream_t *stream, apr_uint64_t *result)
+{
+ apr_uint64_t shift = 0;
+ apr_uint64_t value = 0;
+ unsigned char c;
+
+ do
+ {
+ apr_size_t len = 1;
+ SVN_ERR(svn_stream_read(stream, (char *)&c, &len));
+ if (len != 1)
+ return svn_error_create(SVN_ERR_CORRUPT_PACKED_DATA, NULL,
+ _("Unexpected end of stream"));
+
+ value += (apr_uint64_t)(c & 0x7f) << shift;
+ shift += 7;
+ if (shift > 64)
+ return svn_error_create(SVN_ERR_CORRUPT_PACKED_DATA, NULL,
+ _("Integer representation too long"));
+ }
+ while (c >= 0x80);
+
+ *result = value;
+ return SVN_NO_ERROR;
+}
+
+void
+svn__packed_data_fill_buffer(svn__packed_int_stream_t *stream)
+{
+ packed_int_private_t *private_data = stream->private_data;
+ apr_size_t i;
+ apr_size_t end = MIN(SVN__PACKED_DATA_BUFFER_SIZE,
+ private_data->item_count);
+
+ /* in case, some user calls us explicitly without a good reason ... */
+ if (stream->buffer_used)
+ return;
+
+ /* can we get data from the sub-streams or do we have to decode it from
+ our local packed container? */
+ if (private_data->current_substream)
+ for (i = end; i > 0; --i)
+ {
+ packed_int_private_t *current_private_data
+ = private_data->current_substream->private_data;
+ stream->buffer[i-1]
+ = svn__packed_get_uint(private_data->current_substream);
+ private_data->current_substream = current_private_data->next;
+ }
+ else
+ {
+ /* use this local buffer only if the packed data is shorter than this.
+ The goal is that we don't need to check for overflows that is not
+ detected by read_packed_uint_body. */
+ unsigned char local_buffer[10 * SVN__PACKED_DATA_BUFFER_SIZE];
+ unsigned char *p;
+ unsigned char *start;
+ apr_size_t packed_read;
+
+ if (private_data->packed->len < sizeof(local_buffer))
+ {
+ apr_size_t trail = sizeof(local_buffer) - private_data->packed->len;
+ memcpy(local_buffer,
+ private_data->packed->data,
+ private_data->packed->len);
+ memset(local_buffer + private_data->packed->len, 0, MIN(trail, end));
+
+ p = local_buffer;
+ }
+ else
+ p = (unsigned char *)private_data->packed->data;
+
+ /* unpack numbers */
+ start = p;
+ for (i = end; i > 0; --i)
+ p = read_packed_uint_body(p, &stream->buffer[i-1]);
+
+ /* adjust remaining packed data buffer */
+ packed_read = p - start;
+ private_data->packed->data += packed_read;
+ private_data->packed->len -= packed_read;
+ private_data->packed->blocksize -= packed_read;
+
+ /* undeltify numbers, if configured */
+ if (private_data->diff)
+ {
+ apr_uint64_t last_value = private_data->last_value;
+ for (i = end; i > 0; --i)
+ {
+ apr_uint64_t temp = stream->buffer[i-1];
+ temp = (temp % 2) ? 0 - (temp + 1) / 2 : temp / 2;
+ last_value += temp;
+ stream->buffer[i-1] = last_value;
+ }
+
+ private_data->last_value = last_value;
+ }
+
+ /* handle signed values, if configured and not handled already */
+ if (!private_data->diff && private_data->is_signed)
+ for (i = 0; i < end; ++i)
+ stream->buffer[i] = (stream->buffer[i] % 2)
+ ? 0 - (stream->buffer[i] + 1) / 2
+ : stream->buffer[i] / 2;
+ }
+
+ stream->buffer_used = end;
+ private_data->item_count -= end;
+}
+
+/* Extract and return the next integer from PACKED and make PACKED point
+ * to the next integer.
+ */
+static apr_uint64_t
+read_packed_uint(svn_stringbuf_t *packed)
+{
+ apr_uint64_t result = 0;
+ unsigned char *p = (unsigned char *)packed->data;
+ apr_size_t read = read_packed_uint_body(p, &result) - p;
+
+ if (read > packed->len)
+ read = packed->len;
+
+ packed->data += read;
+ packed->blocksize -= read;
+ packed->len -= read;
+
+ return result;
+}
+
+/* Read the integer stream structure and recreate it in STREAM, including
+ * sub-streams, from TREE_STRUCT.
+ */
+static void
+read_int_stream_structure(svn_stringbuf_t *tree_struct,
+ svn__packed_int_stream_t *stream)
+{
+ packed_int_private_t *private_data = stream->private_data;
+ apr_uint64_t value = read_packed_uint(tree_struct);
+ apr_size_t substream_count;
+ apr_size_t i;
+
+ /* extract local parameters */
+ private_data->diff = (value & 1) != 0;
+ private_data->is_signed = (value & 2) != 0;
+ substream_count = (apr_size_t)(value >> 2);
+
+ /* read item count & packed size; allocate packed data buffer */
+ private_data->item_count = (apr_size_t)read_packed_uint(tree_struct);
+ value = read_packed_uint(tree_struct);
+ if (value)
+ {
+ private_data->packed = svn_stringbuf_create_ensure((apr_size_t)value,
+ private_data->pool);
+ private_data->packed->len = (apr_size_t)value;
+ }
+
+ /* add sub-streams and read their config, too */
+ for (i = 0; i < substream_count; ++i)
+ read_int_stream_structure(tree_struct,
+ svn__packed_create_int_substream(stream,
+ FALSE,
+ FALSE));
+}
+
+/* Read the integer stream structure and recreate it in STREAM, including
+ * sub-streams, from TREE_STRUCT. FIRST_INT_STREAM is the integer stream
+ * that would correspond to lengths_stream_index 0.
+ */
+static void
+read_byte_stream_structure(svn_stringbuf_t *tree_struct,
+ svn__packed_byte_stream_t *stream,
+ svn__packed_int_stream_t *first_int_stream)
+{
+ /* read parameters from the TREE_STRUCT buffer */
+ apr_size_t substream_count = (apr_size_t)read_packed_uint(tree_struct);
+ apr_size_t lengths_stream_index = (apr_size_t)read_packed_uint(tree_struct);
+ apr_size_t packed_size = (apr_size_t)read_packed_uint(tree_struct);
+ apr_size_t i;
+
+ /* allocate byte sequence buffer size */
+ svn_stringbuf_ensure(stream->packed, packed_size);
+ stream->packed->len = packed_size;
+
+ /* navigate to the (already existing) lengths_stream */
+ stream->lengths_stream_index = lengths_stream_index;
+ stream->lengths_stream = first_int_stream;
+ for (i = 0; i < lengths_stream_index; ++i)
+ {
+ packed_int_private_t *length_private
+ = stream->lengths_stream->private_data;
+ stream->lengths_stream = length_private->next;
+ }
+
+ /* reconstruct sub-streams */
+ for (i = 0; i < substream_count; ++i)
+ {
+ svn__packed_byte_stream_t *substream
+ = packed_data_create_bytes_substream_body(stream);
+ packed_int_private_t *length_private
+ = stream->lengths_stream->private_data;
+ read_byte_stream_structure(tree_struct,
+ substream,
+ length_private->first_substream);
+ }
+}
+
+/* Read a compressed block from STREAM and uncompress it into UNCOMPRESSED.
+ * UNCOMPRESSED_LEN is the expected size of the stream. COMPRESSED is a
+ * re-used buffer for temporary data.
+ */
+static svn_error_t *
+read_stream_data(svn_stream_t *stream,
+ apr_size_t uncompressed_len,
+ svn_stringbuf_t *uncompressed,
+ svn_stringbuf_t *compressed)
+{
+ apr_uint64_t len;
+ apr_size_t compressed_len;
+
+ SVN_ERR(read_stream_uint(stream, &len));
+ compressed_len = (apr_size_t)len;
+
+ svn_stringbuf_ensure(compressed, compressed_len);
+ compressed->len = compressed_len;
+ SVN_ERR(svn_stream_read(stream, compressed->data, &compressed->len));
+ compressed->data[compressed_len] = '\0';
+
+ SVN_ERR(svn__decompress(compressed, uncompressed, uncompressed_len));
+
+ return SVN_NO_ERROR;
+}
+
+/* Read the packed contents from COMBINED, starting at *OFFSET and store
+ * it in STREAM. Update *OFFSET to point to the next stream's data and
+ * continue with the sub-streams.
+ */
+static void
+unflatten_int_stream(svn__packed_int_stream_t *stream,
+ svn_stringbuf_t *combined,
+ apr_size_t *offset)
+{
+ packed_int_private_t *private_data = stream->private_data;
+ if (private_data->packed)
+ {
+ memcpy(private_data->packed->data,
+ combined->data + *offset,
+ private_data->packed->len);
+
+ private_data->packed->data[private_data->packed->len] = '\0';
+ *offset += private_data->packed->len;
+ }
+
+ stream = private_data->first_substream;
+ while (stream)
+ {
+ private_data = stream->private_data;
+ unflatten_int_stream(stream, combined, offset);
+ stream = private_data->is_last ? NULL : private_data->next;
+ }
+}
+
+/* Read the packed contents from COMBINED, starting at *OFFSET and store
+ * it in STREAM. Update *OFFSET to point to the next stream's data and
+ * continue with the sub-streams.
+ */
+static void
+unflatten_byte_stream(svn__packed_byte_stream_t *stream,
+ svn_stringbuf_t *combined,
+ apr_size_t *offset)
+{
+ memcpy(stream->packed->data,
+ combined->data + *offset,
+ stream->packed->len);
+ stream->packed->data[stream->packed->len] = '\0';
+
+ *offset += stream->packed->len;
+ for (stream = stream->first_substream; stream; stream = stream->next)
+ unflatten_byte_stream(stream, combined, offset);
+}
+
+svn_error_t *
+svn__packed_data_read(svn__packed_data_root_t **root_p,
+ svn_stream_t *stream,
+ apr_pool_t *result_pool,
+ apr_pool_t *scratch_pool)
+{
+ apr_size_t i;
+ apr_size_t count;
+
+ svn__packed_int_stream_t *int_stream;
+ svn__packed_byte_stream_t *byte_stream;
+ svn__packed_data_root_t *root = svn__packed_data_create_root(result_pool);
+
+ svn_stringbuf_t *compressed
+ = svn_stringbuf_create_ensure(1024, scratch_pool);
+ svn_stringbuf_t *uncompressed
+ = svn_stringbuf_create_ensure(1024, scratch_pool);
+
+ /* read tree structure */
+
+ apr_uint64_t tree_struct_size;
+ svn_stringbuf_t *tree_struct;
+
+ SVN_ERR(read_stream_uint(stream, &tree_struct_size));
+ tree_struct
+ = svn_stringbuf_create_ensure((apr_size_t)tree_struct_size, scratch_pool);
+ tree_struct->len = (apr_size_t)tree_struct_size;
+
+ SVN_ERR(svn_stream_read(stream, tree_struct->data, &tree_struct->len));
+ tree_struct->data[tree_struct->len] = '\0';
+
+ /* reconstruct tree structure */
+
+ count = read_packed_uint(tree_struct);
+ for (i = 0; i < count; ++i)
+ read_int_stream_structure(tree_struct,
+ svn__packed_create_int_stream(root, FALSE,
+ FALSE));
+
+ count = read_packed_uint(tree_struct);
+ for (i = 0; i < count; ++i)
+ read_byte_stream_structure(tree_struct,
+ create_bytes_stream_body(root),
+ root->first_int_stream);
+
+ /* read sub-stream data from disk, unzip it and buffer it */
+
+ for (int_stream = root->first_int_stream;
+ int_stream;
+ int_stream = ((packed_int_private_t*)int_stream->private_data)->next)
+ {
+ apr_size_t offset = 0;
+ SVN_ERR(read_stream_data(stream,
+ packed_int_stream_length(int_stream),
+ uncompressed, compressed));
+ unflatten_int_stream(int_stream, uncompressed, &offset);
+ }
+
+ for (byte_stream = root->first_byte_stream;
+ byte_stream;
+ byte_stream = byte_stream->next)
+ {
+ apr_size_t offset = 0;
+ SVN_ERR(read_stream_data(stream,
+ packed_byte_stream_length(byte_stream),
+ uncompressed, compressed));
+ unflatten_byte_stream(byte_stream, uncompressed, &offset);
+ }
+
+ *root_p = root;
+ return SVN_NO_ERROR;
+}
Re: svn commit: r1461865 - in /subversion/branches/fsfs-format7/subversion:
include/private/svn_packed_data.h include/svn_error_codes.h libsvn_subr/packed_data.c
Posted by Stefan Fuhrmann <st...@wandisco.com>.
On Thu, Mar 28, 2013 at 10:57 AM, Daniel Shahaf <d....@daniel.shahaf.name>wrote:
> stefan2@apache.org wrote on Wed, Mar 27, 2013 at 21:53:02 -0000:
> > Author: stefan2
> > Date: Wed Mar 27 21:52:57 2013
> > New Revision: 1461865
> >
> > URL: http://svn.apache.org/r1461865
> > Log:
> > On the fsfs-format7: Introduce a framework for space and time-
> > efficient storage of binary data. For details, see the header
> > file documentation.
> >
>
> We almost never use the 'SVN__' namespace. Shouldn't these bits be
> 'svn_packed__*'?
>
Done in r1462837.
Thanks for the review!
-- Stefan^2.
--
*Join one of our free daily demo sessions on* *Scaling Subversion for the
Enterprise <http://www.wandisco.com/training/webinars>*
*
*
Re: svn commit: r1461865 - in /subversion/branches/fsfs-format7/subversion:
include/private/svn_packed_data.h include/svn_error_codes.h libsvn_subr/packed_data.c
Posted by Stefan Fuhrmann <st...@wandisco.com>.
On Thu, Mar 28, 2013 at 10:57 AM, Daniel Shahaf <d....@daniel.shahaf.name>wrote:
> stefan2@apache.org wrote on Wed, Mar 27, 2013 at 21:53:02 -0000:
> > Author: stefan2
> > Date: Wed Mar 27 21:52:57 2013
> > New Revision: 1461865
> >
> > URL: http://svn.apache.org/r1461865
> > Log:
> > On the fsfs-format7: Introduce a framework for space and time-
> > efficient storage of binary data. For details, see the header
> > file documentation.
> >
>
> We almost never use the 'SVN__' namespace. Shouldn't these bits be
> 'svn_packed__*'?
>
Done in r1462837.
Thanks for the review!
-- Stefan^2.
--
*Join one of our free daily demo sessions on* *Scaling Subversion for the
Enterprise <http://www.wandisco.com/training/webinars>*
*
*
Re: svn commit: r1461865 - in
/subversion/branches/fsfs-format7/subversion:
include/private/svn_packed_data.h include/svn_error_codes.h
libsvn_subr/packed_data.c
Posted by Daniel Shahaf <d....@daniel.shahaf.name>.
stefan2@apache.org wrote on Wed, Mar 27, 2013 at 21:53:02 -0000:
> Author: stefan2
> Date: Wed Mar 27 21:52:57 2013
> New Revision: 1461865
>
> URL: http://svn.apache.org/r1461865
> Log:
> On the fsfs-format7: Introduce a framework for space and time-
> efficient storage of binary data. For details, see the header
> file documentation.
>
We almost never use the 'SVN__' namespace. Shouldn't these bits be 'svn_packed__*'?
(This isn't nitpicking, this is a commit review that only reviews the
log message. :-) )
> * subversion/include/private/svn_packed_data.h
> (): new header
> (SVN__PACKED_DATA_BUFFER_SIZE): new constant
> (svn__packed_data_root_t,
> svn__packed_byte_stream_t,
> svn__packed_int_stream_t): new data types
> (svn__packed_data_create_root,
> svn__packed_create_int_stream,
> svn__packed_create_int_substream,
> svn__packed_create_bytes_stream,
> svn__packed_create_bytes_substream,
> svn__packed_data_flush_buffer,
> svn__packed_add_uint,
> svn__packed_add_int,
> svn__packed_add_bytes,
> svn__packed_data_write): declare data write API
> (svn__packed_first_int_stream,
> svn__packed_first_byte_stream,
> svn__packed_next_int_stream,
> svn__packed_next_byte_stream,
> svn__packed_first_int_substream,
> svn__packed_first_byte_substream,
> svn__packed_int_count,
> svn__packed_byte_count,
> svn__packed_data_fill_buffer,
> svn__packed_get_uint,
> svn__packed_get_int,
> svn__packed_get_bytes,
> svn__packed_data_read): declare data read API
>
> * subversion/include/svn_error_codes.h
> (SVN_ERR_CORRUPT_PACKED_DATA): define new error code
>
> * subversion/libsvn_subr/packed_data.c
> (): new source
> (packed_int_private_t): new private data type
> (svn__packed_byte_stream_t,
> svn__packed_data_root_t): define data types
> (create_bytes_stream_body,
> packed_data_create_bytes_substream_body,
> write_packed_uint_body,
> write_packed_uint,
> write_int_stream_structure,
> write_byte_stream_structure,
> write_stream_uint,
> packed_int_stream_length,
> packed_byte_stream_length,
> append_int_stream,
> append_byte_stream,
> write_stream_data,
> read_packed_uint_body,
> read_stream_uint,
> read_packed_uint,
> read_int_stream_structure,
> read_byte_stream_structure,
> read_stream_data,
> unflatten_int_stream,
> unflatten_byte_stream): new utility functions
> (svn__packed_data_create_root,
> svn__packed_create_int_stream,
> svn__packed_create_int_substream,
> svn__packed_create_bytes_stream,
> svn__packed_create_bytes_substream,
> svn__packed_data_flush_buffer,
> svn__packed_add_uint,
> svn__packed_add_int,
> svn__packed_add_bytes,
> svn__packed_data_write): implement data write API
> (svn__packed_first_int_stream,
> svn__packed_first_byte_stream,
> svn__packed_next_int_stream,
> svn__packed_next_byte_stream,
> svn__packed_first_int_substream,
> svn__packed_first_byte_substream,
> svn__packed_int_count,
> svn__packed_byte_count,
> svn__packed_data_fill_buffer,
> svn__packed_get_uint,
> svn__packed_get_int,
> svn__packed_get_bytes,
> svn__packed_data_read): implement data read API
>
> Added:
> subversion/branches/fsfs-format7/subversion/include/private/svn_packed_data.h
> subversion/branches/fsfs-format7/subversion/libsvn_subr/packed_data.c
> Modified:
> subversion/branches/fsfs-format7/subversion/include/svn_error_codes.h
Re: svn commit: r1461865 - in
/subversion/branches/fsfs-format7/subversion:
include/private/svn_packed_data.h include/svn_error_codes.h
libsvn_subr/packed_data.c
Posted by Daniel Shahaf <d....@daniel.shahaf.name>.
stefan2@apache.org wrote on Wed, Mar 27, 2013 at 21:53:02 -0000:
> Author: stefan2
> Date: Wed Mar 27 21:52:57 2013
> New Revision: 1461865
>
> URL: http://svn.apache.org/r1461865
> Log:
> On the fsfs-format7: Introduce a framework for space and time-
> efficient storage of binary data. For details, see the header
> file documentation.
>
We almost never use the 'SVN__' namespace. Shouldn't these bits be 'svn_packed__*'?
(This isn't nitpicking, this is a commit review that only reviews the
log message. :-) )
> * subversion/include/private/svn_packed_data.h
> (): new header
> (SVN__PACKED_DATA_BUFFER_SIZE): new constant
> (svn__packed_data_root_t,
> svn__packed_byte_stream_t,
> svn__packed_int_stream_t): new data types
> (svn__packed_data_create_root,
> svn__packed_create_int_stream,
> svn__packed_create_int_substream,
> svn__packed_create_bytes_stream,
> svn__packed_create_bytes_substream,
> svn__packed_data_flush_buffer,
> svn__packed_add_uint,
> svn__packed_add_int,
> svn__packed_add_bytes,
> svn__packed_data_write): declare data write API
> (svn__packed_first_int_stream,
> svn__packed_first_byte_stream,
> svn__packed_next_int_stream,
> svn__packed_next_byte_stream,
> svn__packed_first_int_substream,
> svn__packed_first_byte_substream,
> svn__packed_int_count,
> svn__packed_byte_count,
> svn__packed_data_fill_buffer,
> svn__packed_get_uint,
> svn__packed_get_int,
> svn__packed_get_bytes,
> svn__packed_data_read): declare data read API
>
> * subversion/include/svn_error_codes.h
> (SVN_ERR_CORRUPT_PACKED_DATA): define new error code
>
> * subversion/libsvn_subr/packed_data.c
> (): new source
> (packed_int_private_t): new private data type
> (svn__packed_byte_stream_t,
> svn__packed_data_root_t): define data types
> (create_bytes_stream_body,
> packed_data_create_bytes_substream_body,
> write_packed_uint_body,
> write_packed_uint,
> write_int_stream_structure,
> write_byte_stream_structure,
> write_stream_uint,
> packed_int_stream_length,
> packed_byte_stream_length,
> append_int_stream,
> append_byte_stream,
> write_stream_data,
> read_packed_uint_body,
> read_stream_uint,
> read_packed_uint,
> read_int_stream_structure,
> read_byte_stream_structure,
> read_stream_data,
> unflatten_int_stream,
> unflatten_byte_stream): new utility functions
> (svn__packed_data_create_root,
> svn__packed_create_int_stream,
> svn__packed_create_int_substream,
> svn__packed_create_bytes_stream,
> svn__packed_create_bytes_substream,
> svn__packed_data_flush_buffer,
> svn__packed_add_uint,
> svn__packed_add_int,
> svn__packed_add_bytes,
> svn__packed_data_write): implement data write API
> (svn__packed_first_int_stream,
> svn__packed_first_byte_stream,
> svn__packed_next_int_stream,
> svn__packed_next_byte_stream,
> svn__packed_first_int_substream,
> svn__packed_first_byte_substream,
> svn__packed_int_count,
> svn__packed_byte_count,
> svn__packed_data_fill_buffer,
> svn__packed_get_uint,
> svn__packed_get_int,
> svn__packed_get_bytes,
> svn__packed_data_read): implement data read API
>
> Added:
> subversion/branches/fsfs-format7/subversion/include/private/svn_packed_data.h
> subversion/branches/fsfs-format7/subversion/libsvn_subr/packed_data.c
> Modified:
> subversion/branches/fsfs-format7/subversion/include/svn_error_codes.h