Merge branch 'hn/reftable'

The "reftable" backend for the refs API, without integrating into
the refs subsystem, has been added.

* hn/reftable:
  Add "test-tool dump-reftable" command.
  reftable: add dump utility
  reftable: implement stack, a mutable database of reftable files.
  reftable: implement refname validation
  reftable: add merged table view
  reftable: add a heap-based priority queue for reftable records
  reftable: reftable file level tests
  reftable: read reftable files
  reftable: generic interface to tables
  reftable: write reftable files
  reftable: a generic binary tree implementation
  reftable: reading/writing blocks
  Provide zlib's uncompress2 from compat/zlib-compat.c
  reftable: (de)serialization for the polymorphic record type.
  reftable: add blocksource, an abstraction for random access reads
  reftable: utility functions
  reftable: add error related functionality
  reftable: add LICENSE
  hash.h: provide constants for the hash IDs

2 files changed, 96 insertions, 0 deletions

diff --git a/compat/.gitattributes b/compat/.gitattributes
new file mode 100644
index 0000000000..40dbfb170d
--- /dev/null
+++ b/compat/.gitattributes
@@ -0,0 +1 @@
+/zlib-uncompress2.c	whitespace=-indent-with-non-tab,-trailing-space
diff --git a/compat/zlib-uncompress2.c b/compat/zlib-uncompress2.c
new file mode 100644
index 0000000000..722610b971
--- /dev/null
+++ b/compat/zlib-uncompress2.c
@@ -0,0 +1,95 @@
+/* taken from zlib's uncompr.c
+
+   commit cacf7f1d4e3d44d871b605da3b647f07d718623f
+   Author: Mark Adler <madler@alumni.caltech.edu>
+   Date:   Sun Jan 15 09:18:46 2017 -0800
+
+       zlib 1.2.11
+
+*/
+
+#include "../reftable/system.h"
+#define z_const
+
+/*
+ * Copyright (C) 1995-2003, 2010, 2014, 2016 Jean-loup Gailly, Mark Adler
+ * For conditions of distribution and use, see copyright notice in zlib.h
+ */
+
+#include <zlib.h>
+
+/* clang-format off */
+
+/* ===========================================================================
+     Decompresses the source buffer into the destination buffer.  *sourceLen is
+   the byte length of the source buffer. Upon entry, *destLen is the total size
+   of the destination buffer, which must be large enough to hold the entire
+   uncompressed data. (The size of the uncompressed data must have been saved
+   previously by the compressor and transmitted to the decompressor by some
+   mechanism outside the scope of this compression library.) Upon exit,
+   *destLen is the size of the decompressed data and *sourceLen is the number
+   of source bytes consumed. Upon return, source + *sourceLen points to the
+   first unused input byte.
+
+     uncompress returns Z_OK if success, Z_MEM_ERROR if there was not enough
+   memory, Z_BUF_ERROR if there was not enough room in the output buffer, or
+   Z_DATA_ERROR if the input data was corrupted, including if the input data is
+   an incomplete zlib stream.
+*/
+int ZEXPORT uncompress2 (
+    Bytef *dest,
+    uLongf *destLen,
+    const Bytef *source,
+    uLong *sourceLen) {
+    z_stream stream;
+    int err;
+    const uInt max = (uInt)-1;
+    uLong len, left;
+    Byte buf[1];    /* for detection of incomplete stream when *destLen == 0 */
+
+    len = *sourceLen;
+    if (*destLen) {
+	left = *destLen;
+	*destLen = 0;
+    }
+    else {
+	left = 1;
+	dest = buf;
+    }
+
+    stream.next_in = (z_const Bytef *)source;
+    stream.avail_in = 0;
+    stream.zalloc = (alloc_func)0;
+    stream.zfree = (free_func)0;
+    stream.opaque = (voidpf)0;
+
+    err = inflateInit(&stream);
+    if (err != Z_OK) return err;
+
+    stream.next_out = dest;
+    stream.avail_out = 0;
+
+    do {
+	if (stream.avail_out == 0) {
+	    stream.avail_out = left > (uLong)max ? max : (uInt)left;
+	    left -= stream.avail_out;
+	}
+	if (stream.avail_in == 0) {
+	    stream.avail_in = len > (uLong)max ? max : (uInt)len;
+	    len -= stream.avail_in;
+	}
+	err = inflate(&stream, Z_NO_FLUSH);
+    } while (err == Z_OK);
+
+    *sourceLen -= len + stream.avail_in;
+    if (dest != buf)
+	*destLen = stream.total_out;
+    else if (stream.total_out && err == Z_BUF_ERROR)
+	left = 1;
+
+    inflateEnd(&stream);
+    return err == Z_STREAM_END ? Z_OK :
+	   err == Z_NEED_DICT ? Z_DATA_ERROR  :
+	   err == Z_BUF_ERROR && left + stream.avail_out ? Z_DATA_ERROR :
+	   err;
+}