From: "Han-Wen Nienhuys via GitGitGadget" <gitgitgadget@gmail.com> To: git@vger.kernel.org Cc: "Han-Wen Nienhuys" <hanwen@google.com>, "Jeff King" <peff@peff.net>, "Ramsay Jones" <ramsay@ramsayjones.plus.com>, "Jonathan Nieder" <jrnieder@gmail.com>, "Johannes Schindelin" <Johannes.Schindelin@gmx.de>, "Jonathan Tan" <jonathantanmy@google.com>, "Josh Steadmon" <steadmon@google.com>, "Emily Shaffer" <emilyshaffer@google.com>, "Patrick Steinhardt" <ps@pks.im>, "Ævar Arnfjörð Bjarmason" <avarab@gmail.com>, "Felipe Contreras" <felipe.contreras@gmail.com>, "Han-Wen Nienhuys" <hanwenn@gmail.com>, "Han-Wen Nienhuys" <hanwen@google.com> Subject: [PATCH v4 08/15] reftable: a generic binary tree implementation Date: Wed, 09 Dec 2020 14:00:22 +0000 [thread overview] Message-ID: <6968dbc3828f22369cc92bf56e3a7855769415fa.1607522429.git.gitgitgadget@gmail.com> (raw) In-Reply-To: <pull.847.v4.git.git.1607522429.gitgitgadget@gmail.com> From: Han-Wen Nienhuys <hanwen@google.com> The reftable format includes support for an (OID => ref) map. This map can speed up visibility and reachability checks. In particular, various operations along the fetch/push path within Gerrit have ben sped up by using this structure. The map is constructed with help of a binary tree. Object IDs are hashes, so they are uniformly distributed. Hence, the tree does not attempt forced rebalancing. Signed-off-by: Han-Wen Nienhuys <hanwen@google.com> --- Makefile | 4 ++- reftable/tree.c | 63 ++++++++++++++++++++++++++++++++++++++++ reftable/tree.h | 34 ++++++++++++++++++++++ reftable/tree_test.c | 61 ++++++++++++++++++++++++++++++++++++++ t/helper/test-reftable.c | 1 + 5 files changed, 162 insertions(+), 1 deletion(-) create mode 100644 reftable/tree.c create mode 100644 reftable/tree.h create mode 100644 reftable/tree_test.c diff --git a/Makefile b/Makefile index abe0dda5777..734c05655b2 100644 --- a/Makefile +++ b/Makefile @@ -2395,12 +2395,14 @@ REFTABLE_OBJS += reftable/block.o REFTABLE_OBJS += reftable/blocksource.o REFTABLE_OBJS += reftable/publicbasics.o REFTABLE_OBJS += reftable/record.o +REFTABLE_OBJS += reftable/tree.o REFTABLE_OBJS += reftable/zlib-compat.o +REFTABLE_TEST_OBJS += reftable/basics_test.o REFTABLE_TEST_OBJS += reftable/block_test.o REFTABLE_TEST_OBJS += reftable/record_test.o REFTABLE_TEST_OBJS += reftable/test_framework.o -REFTABLE_TEST_OBJS += reftable/basics_test.o +REFTABLE_TEST_OBJS += reftable/tree_test.o TEST_OBJS := $(patsubst %$X,%.o,$(TEST_PROGRAMS)) $(patsubst %,t/helper/%,$(TEST_BUILTINS_OBJS)) OBJECTS := $(LIB_OBJS) $(BUILTIN_OBJS) $(PROGRAM_OBJS) $(TEST_OBJS) \ diff --git a/reftable/tree.c b/reftable/tree.c new file mode 100644 index 00000000000..0061d14e306 --- /dev/null +++ b/reftable/tree.c @@ -0,0 +1,63 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#include "tree.h" + +#include "basics.h" +#include "system.h" + +struct tree_node *tree_search(void *key, struct tree_node **rootp, + int (*compare)(const void *, const void *), + int insert) +{ + int res; + if (*rootp == NULL) { + if (!insert) { + return NULL; + } else { + struct tree_node *n = + reftable_calloc(sizeof(struct tree_node)); + n->key = key; + *rootp = n; + return *rootp; + } + } + + res = compare(key, (*rootp)->key); + if (res < 0) + return tree_search(key, &(*rootp)->left, compare, insert); + else if (res > 0) + return tree_search(key, &(*rootp)->right, compare, insert); + return *rootp; +} + +void infix_walk(struct tree_node *t, void (*action)(void *arg, void *key), + void *arg) +{ + if (t->left != NULL) { + infix_walk(t->left, action, arg); + } + action(arg, t->key); + if (t->right != NULL) { + infix_walk(t->right, action, arg); + } +} + +void tree_free(struct tree_node *t) +{ + if (t == NULL) { + return; + } + if (t->left != NULL) { + tree_free(t->left); + } + if (t->right != NULL) { + tree_free(t->right); + } + reftable_free(t); +} diff --git a/reftable/tree.h b/reftable/tree.h new file mode 100644 index 00000000000..fbdd002e23a --- /dev/null +++ b/reftable/tree.h @@ -0,0 +1,34 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#ifndef TREE_H +#define TREE_H + +/* tree_node is a generic binary search tree. */ +struct tree_node { + void *key; + struct tree_node *left, *right; +}; + +/* looks for `key` in `rootp` using `compare` as comparison function. If insert + * is set, insert the key if it's not found. Else, return NULL. + */ +struct tree_node *tree_search(void *key, struct tree_node **rootp, + int (*compare)(const void *, const void *), + int insert); + +/* performs an infix walk of the tree. */ +void infix_walk(struct tree_node *t, void (*action)(void *arg, void *key), + void *arg); + +/* + * deallocates the tree nodes recursively. Keys should be deallocated separately + * by walking over the tree. */ +void tree_free(struct tree_node *t); + +#endif diff --git a/reftable/tree_test.c b/reftable/tree_test.c new file mode 100644 index 00000000000..26d1e694252 --- /dev/null +++ b/reftable/tree_test.c @@ -0,0 +1,61 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#include "tree.h" + +#include "basics.h" +#include "record.h" +#include "test_framework.h" +#include "reftable-tests.h" + +static int test_compare(const void *a, const void *b) +{ + return (char *)a - (char *)b; +} + +struct curry { + void *last; +}; + +static void check_increasing(void *arg, void *key) +{ + struct curry *c = (struct curry *)arg; + if (c->last != NULL) { + assert(test_compare(c->last, key) < 0); + } + c->last = key; +} + +static void test_tree(void) +{ + struct tree_node *root = NULL; + + void *values[11] = { NULL }; + struct tree_node *nodes[11] = { NULL }; + int i = 1; + struct curry c = { NULL }; + do { + nodes[i] = tree_search(values + i, &root, &test_compare, 1); + i = (i * 7) % 11; + } while (i != 1); + + for (i = 1; i < ARRAY_SIZE(nodes); i++) { + assert(values + i == nodes[i]->key); + assert(nodes[i] == + tree_search(values + i, &root, &test_compare, 0)); + } + + infix_walk(root, check_increasing, &c); + tree_free(root); +} + +int tree_test_main(int argc, const char *argv[]) +{ + RUN_TEST(test_tree); + return 0; +} diff --git a/t/helper/test-reftable.c b/t/helper/test-reftable.c index c9deeaf08c7..050551fa698 100644 --- a/t/helper/test-reftable.c +++ b/t/helper/test-reftable.c @@ -6,5 +6,6 @@ int cmd__reftable(int argc, const char **argv) basics_test_main(argc, argv); block_test_main(argc, argv); record_test_main(argc, argv); + tree_test_main(argc, argv); return 0; } -- gitgitgadget
next prev parent reply other threads:[~2020-12-09 14:04 UTC|newest] Thread overview: 251+ messages / expand[flat|nested] mbox.gz Atom feed top 2020-09-16 19:10 [PATCH 00/13] reftable library Han-Wen Nienhuys via GitGitGadget 2020-09-16 19:10 ` [PATCH 01/13] reftable: add LICENSE Han-Wen Nienhuys via GitGitGadget 2020-09-16 19:10 ` [PATCH 02/13] reftable: define the public API Han-Wen Nienhuys via GitGitGadget 2020-09-16 19:10 ` [PATCH 03/13] vcxproj: adjust for the reftable changes Johannes Schindelin via GitGitGadget 2020-09-16 19:10 ` [PATCH 04/13] reftable: add a barebones unittest framework Han-Wen Nienhuys via GitGitGadget 2020-09-16 19:10 ` [PATCH 05/13] reftable: utility functions Han-Wen Nienhuys via GitGitGadget 2020-09-16 19:10 ` [PATCH 06/13] reftable: (de)serialization for the polymorphic record type Han-Wen Nienhuys via GitGitGadget 2020-09-20 1:00 ` Junio C Hamano 2020-09-21 13:13 ` Han-Wen Nienhuys 2020-09-24 7:21 ` Jeff King 2020-09-24 7:31 ` Jeff King 2020-09-24 17:22 ` Junio C Hamano 2020-09-16 19:10 ` [PATCH 07/13] reftable: reading/writing blocks Han-Wen Nienhuys via GitGitGadget 2020-09-16 19:10 ` [PATCH 08/13] reftable: a generic binary tree implementation Han-Wen Nienhuys via GitGitGadget 2020-09-16 19:10 ` [PATCH 09/13] reftable: write reftable files Han-Wen Nienhuys via GitGitGadget 2020-09-16 19:10 ` [PATCH 10/13] reftable: read " Han-Wen Nienhuys via GitGitGadget 2020-09-16 19:10 ` [PATCH 11/13] reftable: file level tests Han-Wen Nienhuys via GitGitGadget 2020-09-16 19:10 ` [PATCH 12/13] reftable: rest of library Han-Wen Nienhuys via GitGitGadget 2020-09-16 19:10 ` [PATCH 13/13] reftable: "test-tool dump-reftable" command Han-Wen Nienhuys via GitGitGadget 2020-10-01 16:10 ` [PATCH v2 00/13] reftable library Han-Wen Nienhuys via GitGitGadget 2020-10-01 16:10 ` [PATCH v2 01/13] reftable: add LICENSE Han-Wen Nienhuys via GitGitGadget 2020-10-02 3:18 ` Jonathan Nieder 2020-10-01 16:10 ` [PATCH v2 02/13] reftable: define the public API Han-Wen Nienhuys via GitGitGadget 2020-10-02 3:58 ` Jonathan Nieder 2020-10-09 21:13 ` Emily Shaffer 2020-10-10 17:03 ` Han-Wen Nienhuys 2020-11-30 14:44 ` Han-Wen Nienhuys 2020-10-10 13:43 ` Han-Wen Nienhuys 2020-10-12 16:57 ` Jonathan Nieder 2020-11-30 14:55 ` Han-Wen Nienhuys 2020-10-08 1:41 ` Jonathan Tan 2020-10-10 16:57 ` Han-Wen Nienhuys 2020-10-01 16:10 ` [PATCH v2 03/13] vcxproj: adjust for the reftable changes Johannes Schindelin via GitGitGadget 2020-10-02 4:02 ` Jonathan Nieder 2020-10-02 11:43 ` Johannes Schindelin 2020-10-01 16:10 ` [PATCH v2 04/13] reftable: add a barebones unittest framework Han-Wen Nienhuys via GitGitGadget 2020-10-02 4:05 ` Jonathan Nieder 2020-10-08 1:45 ` Jonathan Tan 2020-10-08 22:31 ` Josh Steadmon 2020-10-01 16:10 ` [PATCH v2 05/13] reftable: utility functions Han-Wen Nienhuys via GitGitGadget 2020-10-02 4:12 ` Jonathan Nieder 2020-10-10 17:32 ` Han-Wen Nienhuys 2020-10-12 15:25 ` Jonathan Nieder 2020-10-12 17:05 ` Patrick Steinhardt 2020-10-12 17:45 ` Jonathan Nieder 2020-10-13 12:12 ` Johannes Schindelin 2020-10-13 15:47 ` Junio C Hamano 2020-10-15 11:46 ` Johannes Schindelin 2020-10-15 16:23 ` Junio C Hamano 2020-10-15 19:39 ` Johannes Schindelin 2020-10-16 9:15 ` Patrick Steinhardt 2020-10-02 14:01 ` Johannes Schindelin 2020-10-02 20:47 ` Junio C Hamano 2020-10-03 8:07 ` Johannes Schindelin 2020-10-08 1:48 ` Jonathan Tan 2020-10-10 17:28 ` Han-Wen Nienhuys 2020-10-11 10:52 ` Johannes Schindelin 2020-10-12 15:19 ` Jonathan Nieder 2020-10-12 18:44 ` Johannes Schindelin 2020-10-12 19:41 ` Jonathan Nieder 2020-10-12 20:27 ` Johannes Schindelin 2020-10-12 16:42 ` Junio C Hamano 2020-10-12 19:01 ` Johannes Schindelin 2020-10-23 9:13 ` Ævar Arnfjörð Bjarmason 2020-10-23 17:36 ` Junio C Hamano 2020-10-01 16:10 ` [PATCH v2 06/13] reftable: (de)serialization for the polymorphic record type Han-Wen Nienhuys via GitGitGadget 2020-10-01 19:23 ` Junio C Hamano 2020-10-01 19:59 ` Ramsay Jones 2020-10-01 16:10 ` [PATCH v2 07/13] reftable: reading/writing blocks Han-Wen Nienhuys via GitGitGadget 2020-10-01 16:10 ` [PATCH v2 08/13] reftable: a generic binary tree implementation Han-Wen Nienhuys via GitGitGadget 2020-10-01 16:10 ` [PATCH v2 09/13] reftable: write reftable files Han-Wen Nienhuys via GitGitGadget 2020-10-01 16:11 ` [PATCH v2 10/13] reftable: read " Han-Wen Nienhuys via GitGitGadget 2020-10-01 16:11 ` [PATCH v2 11/13] reftable: file level tests Han-Wen Nienhuys via GitGitGadget 2020-10-01 16:11 ` [PATCH v2 12/13] reftable: rest of library Han-Wen Nienhuys via GitGitGadget 2020-10-02 13:57 ` Johannes Schindelin 2020-10-02 17:08 ` Junio C Hamano 2020-10-04 18:39 ` Johannes Schindelin 2020-10-01 16:11 ` [PATCH v2 13/13] reftable: "test-tool dump-reftable" command Han-Wen Nienhuys via GitGitGadget 2020-11-26 19:42 ` [PATCH v3 00/16] reftable library Han-Wen Nienhuys via GitGitGadget 2020-11-26 19:42 ` [PATCH v3 01/16] move sleep_millisec to git-compat-util.h Han-Wen Nienhuys via GitGitGadget 2020-11-26 19:42 ` [PATCH v3 02/16] init-db: set the_repository->hash_algo early on Han-Wen Nienhuys via GitGitGadget 2020-11-27 10:22 ` Ævar Arnfjörð Bjarmason 2020-11-26 19:42 ` [PATCH v3 03/16] reftable: add LICENSE Han-Wen Nienhuys via GitGitGadget 2020-11-27 10:23 ` Ævar Arnfjörð Bjarmason 2020-11-30 11:26 ` Han-Wen Nienhuys 2020-11-30 20:25 ` Han-Wen Nienhuys 2020-11-30 21:21 ` Felipe Contreras 2020-12-01 9:51 ` Han-Wen Nienhuys 2020-12-01 10:38 ` Felipe Contreras 2020-12-01 11:45 ` Ævar Arnfjörð Bjarmason 2020-12-01 13:34 ` Han-Wen Nienhuys 2020-12-01 23:13 ` Felipe Contreras 2020-12-01 23:03 ` Felipe Contreras 2020-11-26 19:42 ` [PATCH v3 04/16] reftable: add error related functionality Han-Wen Nienhuys via GitGitGadget 2020-11-27 9:13 ` Felipe Contreras 2020-11-27 10:25 ` Ævar Arnfjörð Bjarmason 2020-11-30 11:27 ` Han-Wen Nienhuys 2020-11-26 19:42 ` [PATCH v3 05/16] reftable: utility functions Han-Wen Nienhuys via GitGitGadget 2020-11-27 10:18 ` Felipe Contreras 2020-11-27 10:33 ` Ævar Arnfjörð Bjarmason 2020-11-26 19:42 ` [PATCH v3 06/16] reftable: add blocksource, an abstraction for random access reads Han-Wen Nienhuys via GitGitGadget 2020-11-26 19:42 ` [PATCH v3 07/16] reftable: (de)serialization for the polymorphic record type Han-Wen Nienhuys via GitGitGadget 2020-11-26 19:42 ` [PATCH v3 08/16] reftable: reading/writing blocks Han-Wen Nienhuys via GitGitGadget 2020-11-26 19:42 ` [PATCH v3 09/16] reftable: a generic binary tree implementation Han-Wen Nienhuys via GitGitGadget 2020-11-26 19:42 ` [PATCH v3 10/16] reftable: write reftable files Han-Wen Nienhuys via GitGitGadget 2020-11-26 19:42 ` [PATCH v3 11/16] reftable: read " Han-Wen Nienhuys via GitGitGadget 2020-11-26 19:42 ` [PATCH v3 12/16] reftable: reftable file level tests Han-Wen Nienhuys via GitGitGadget 2020-11-26 19:42 ` [PATCH v3 13/16] reftable: rest of library Han-Wen Nienhuys via GitGitGadget 2020-11-26 19:42 ` [PATCH v3 14/16] Reftable support for git-core Han-Wen Nienhuys via GitGitGadget 2020-11-27 10:59 ` Ævar Arnfjörð Bjarmason 2020-11-26 19:42 ` [PATCH v3 15/16] git-prompt: prepare for reftable refs backend SZEDER Gábor via GitGitGadget 2020-11-26 19:42 ` [PATCH v3 16/16] Add "test-tool dump-reftable" command Han-Wen Nienhuys via GitGitGadget 2020-12-09 14:00 ` [PATCH v4 00/15] reftable library Han-Wen Nienhuys via GitGitGadget 2020-12-09 14:00 ` [PATCH v4 01/15] init-db: set the_repository->hash_algo early on Han-Wen Nienhuys via GitGitGadget 2020-12-09 14:00 ` [PATCH v4 02/15] reftable: add LICENSE Han-Wen Nienhuys via GitGitGadget 2020-12-09 14:00 ` [PATCH v4 03/15] reftable: add error related functionality Han-Wen Nienhuys via GitGitGadget 2020-12-09 14:00 ` [PATCH v4 04/15] reftable: utility functions Han-Wen Nienhuys via GitGitGadget 2020-12-09 14:00 ` [PATCH v4 05/15] reftable: add blocksource, an abstraction for random access reads Han-Wen Nienhuys via GitGitGadget 2020-12-09 14:00 ` [PATCH v4 06/15] reftable: (de)serialization for the polymorphic record type Han-Wen Nienhuys via GitGitGadget 2020-12-09 14:00 ` [PATCH v4 07/15] reftable: reading/writing blocks Han-Wen Nienhuys via GitGitGadget 2020-12-09 14:00 ` Han-Wen Nienhuys via GitGitGadget [this message] 2020-12-09 14:00 ` [PATCH v4 09/15] reftable: write reftable files Han-Wen Nienhuys via GitGitGadget 2020-12-09 14:00 ` [PATCH v4 10/15] reftable: read " Han-Wen Nienhuys via GitGitGadget 2020-12-09 14:00 ` [PATCH v4 11/15] reftable: reftable file level tests Han-Wen Nienhuys via GitGitGadget 2020-12-09 14:00 ` [PATCH v4 12/15] reftable: rest of library Han-Wen Nienhuys via GitGitGadget 2020-12-09 14:00 ` [PATCH v4 13/15] Reftable support for git-core Han-Wen Nienhuys via GitGitGadget 2021-01-21 15:55 ` Ævar Arnfjörð Bjarmason 2021-01-21 16:14 ` Han-Wen Nienhuys 2021-01-21 16:21 ` Han-Wen Nienhuys 2021-01-26 13:44 ` Ævar Arnfjörð Bjarmason 2021-04-23 10:22 ` Han-Wen Nienhuys 2021-04-26 13:23 ` Ævar Arnfjörð Bjarmason 2021-04-26 16:17 ` Han-Wen Nienhuys 2021-04-28 16:32 ` Ævar Arnfjörð Bjarmason 2021-04-28 17:40 ` Han-Wen Nienhuys 2021-02-22 0:41 ` [PATCH] refs: introduce API function to write invalid null ref Stefan Beller 2021-02-22 1:20 ` Eric Sunshine 2021-02-22 3:09 ` Eric Sunshine 2021-02-22 18:38 ` Han-Wen Nienhuys 2020-12-09 14:00 ` [PATCH v4 14/15] git-prompt: prepare for reftable refs backend SZEDER Gábor via GitGitGadget 2020-12-09 14:00 ` [PATCH v4 15/15] Add "test-tool dump-reftable" command Han-Wen Nienhuys via GitGitGadget 2021-03-12 20:19 ` [PATCH v5 00/15] reftable library Han-Wen Nienhuys via GitGitGadget 2021-03-12 20:19 ` [PATCH v5 01/15] init-db: set the_repository->hash_algo early on Han-Wen Nienhuys via GitGitGadget 2021-03-12 20:19 ` [PATCH v5 02/15] reftable: add LICENSE Han-Wen Nienhuys via GitGitGadget 2021-03-12 20:19 ` [PATCH v5 03/15] reftable: add error related functionality Han-Wen Nienhuys via GitGitGadget 2021-03-12 20:19 ` [PATCH v5 04/15] reftable: utility functions Han-Wen Nienhuys via GitGitGadget 2021-03-12 20:19 ` [PATCH v5 05/15] reftable: add blocksource, an abstraction for random access reads Han-Wen Nienhuys via GitGitGadget 2021-03-12 20:19 ` [PATCH v5 06/15] reftable: (de)serialization for the polymorphic record type Han-Wen Nienhuys via GitGitGadget 2021-03-12 20:19 ` [PATCH v5 07/15] reftable: reading/writing blocks Han-Wen Nienhuys via GitGitGadget 2021-03-12 20:19 ` [PATCH v5 08/15] reftable: a generic binary tree implementation Han-Wen Nienhuys via GitGitGadget 2021-03-12 20:19 ` [PATCH v5 09/15] reftable: write reftable files Han-Wen Nienhuys via GitGitGadget 2021-03-12 20:19 ` [PATCH v5 10/15] reftable: read " Han-Wen Nienhuys via GitGitGadget 2021-03-12 20:19 ` [PATCH v5 11/15] reftable: reftable file level tests Han-Wen Nienhuys via GitGitGadget 2021-03-12 20:19 ` [PATCH v5 12/15] reftable: rest of library Han-Wen Nienhuys via GitGitGadget 2021-03-12 20:19 ` [PATCH v5 13/15] Reftable support for git-core Han-Wen Nienhuys via GitGitGadget 2021-03-23 11:40 ` Derrick Stolee 2021-03-23 12:20 ` Ævar Arnfjörð Bjarmason 2021-03-23 20:14 ` Junio C Hamano 2021-03-23 20:12 ` Junio C Hamano 2021-03-12 20:19 ` [PATCH v5 14/15] git-prompt: prepare for reftable refs backend SZEDER Gábor via GitGitGadget 2021-03-12 20:19 ` [PATCH v5 15/15] Add "test-tool dump-reftable" command Han-Wen Nienhuys via GitGitGadget 2021-04-12 19:25 ` [PATCH v6 00/20] reftable library Han-Wen Nienhuys via GitGitGadget 2021-04-12 19:25 ` [PATCH v6 01/20] init-db: set the_repository->hash_algo early on Han-Wen Nienhuys via GitGitGadget 2021-04-12 19:25 ` [PATCH v6 02/20] reftable: add LICENSE Han-Wen Nienhuys via GitGitGadget 2021-04-13 7:28 ` Ævar Arnfjörð Bjarmason 2021-04-13 10:50 ` Han-Wen Nienhuys 2021-04-13 13:41 ` Ævar Arnfjörð Bjarmason 2021-04-12 19:25 ` [PATCH v6 03/20] reftable: add error related functionality Han-Wen Nienhuys via GitGitGadget 2021-04-12 19:25 ` [PATCH v6 04/20] reftable: utility functions Han-Wen Nienhuys via GitGitGadget 2021-04-13 8:02 ` Ævar Arnfjörð Bjarmason 2021-04-13 10:58 ` Han-Wen Nienhuys 2021-04-13 12:56 ` Ævar Arnfjörð Bjarmason 2021-04-13 13:14 ` Ævar Arnfjörð Bjarmason 2021-04-15 15:00 ` Han-Wen Nienhuys 2021-04-12 19:25 ` [PATCH v6 05/20] reftable: add blocksource, an abstraction for random access reads Han-Wen Nienhuys via GitGitGadget 2021-04-12 19:25 ` [PATCH v6 06/20] reftable: (de)serialization for the polymorphic record type Han-Wen Nienhuys via GitGitGadget 2021-04-12 19:25 ` [PATCH v6 07/20] reftable: reading/writing blocks Han-Wen Nienhuys via GitGitGadget 2021-04-12 21:40 ` Junio C Hamano 2021-04-13 8:19 ` Ævar Arnfjörð Bjarmason 2021-04-15 8:57 ` Han-Wen Nienhuys 2021-04-12 19:25 ` [PATCH v6 08/20] reftable: a generic binary tree implementation Han-Wen Nienhuys via GitGitGadget 2021-04-12 19:25 ` [PATCH v6 09/20] reftable: write reftable files Han-Wen Nienhuys via GitGitGadget 2021-04-12 19:25 ` [PATCH v6 10/20] reftable: generic interface to tables Han-Wen Nienhuys via GitGitGadget 2021-04-12 19:25 ` [PATCH v6 11/20] reftable: read reftable files Han-Wen Nienhuys via GitGitGadget 2021-04-12 19:25 ` [PATCH v6 12/20] reftable: reftable file level tests Han-Wen Nienhuys via GitGitGadget 2021-04-12 19:25 ` [PATCH v6 13/20] reftable: add a heap-based priority queue for reftable records Han-Wen Nienhuys via GitGitGadget 2021-04-12 19:25 ` [PATCH v6 14/20] reftable: add merged table view Han-Wen Nienhuys via GitGitGadget 2021-04-12 19:25 ` [PATCH v6 15/20] reftable: implement refname validation Han-Wen Nienhuys via GitGitGadget 2021-04-12 19:25 ` [PATCH v6 16/20] reftable: implement stack, a mutable database of reftable files Han-Wen Nienhuys via GitGitGadget 2021-04-12 19:25 ` [PATCH v6 17/20] reftable: add dump utility Han-Wen Nienhuys via GitGitGadget 2021-04-12 19:25 ` [PATCH v6 18/20] Reftable support for git-core Han-Wen Nienhuys via GitGitGadget 2021-04-13 7:18 ` Ævar Arnfjörð Bjarmason 2021-04-14 16:44 ` Han-Wen Nienhuys 2021-04-16 14:55 ` Ævar Arnfjörð Bjarmason 2021-04-16 18:47 ` Junio C Hamano 2021-04-12 19:25 ` [PATCH v6 19/20] git-prompt: prepare for reftable refs backend SZEDER Gábor via GitGitGadget 2021-04-12 19:25 ` [PATCH v6 20/20] Add "test-tool dump-reftable" command Han-Wen Nienhuys via GitGitGadget 2021-04-19 11:37 ` [PATCH v7 00/28] reftable library Han-Wen Nienhuys via GitGitGadget 2021-04-19 11:37 ` [PATCH v7 01/28] refs: ref_iterator_peel returns boolean, rather than peel_status Han-Wen Nienhuys via GitGitGadget 2021-04-20 18:47 ` Junio C Hamano 2021-04-21 10:15 ` Han-Wen Nienhuys 2021-04-21 23:28 ` Junio C Hamano 2021-04-19 11:37 ` [PATCH v7 02/28] refs: document reflog_expire_fn's flag argument Han-Wen Nienhuys via GitGitGadget 2021-04-20 19:34 ` Junio C Hamano 2021-04-27 15:21 ` Han-Wen Nienhuys 2021-04-19 11:37 ` [PATCH v7 03/28] refs/debug: trace into reflog expiry too Han-Wen Nienhuys via GitGitGadget 2021-04-20 19:41 ` Junio C Hamano 2021-04-22 17:27 ` Han-Wen Nienhuys 2021-04-19 11:37 ` [PATCH v7 04/28] hash.h: provide constants for the hash IDs Han-Wen Nienhuys via GitGitGadget 2021-04-20 19:49 ` Junio C Hamano 2021-04-21 1:04 ` brian m. carlson 2021-04-21 9:43 ` Han-Wen Nienhuys 2021-07-22 8:31 ` Han-Wen Nienhuys 2021-04-19 11:37 ` [PATCH v7 05/28] init-db: set the_repository->hash_algo early on Han-Wen Nienhuys via GitGitGadget 2021-04-19 11:37 ` [PATCH v7 06/28] reftable: add LICENSE Han-Wen Nienhuys via GitGitGadget 2021-04-21 7:48 ` Ævar Arnfjörð Bjarmason 2021-04-21 9:15 ` Han-Wen Nienhuys 2021-04-19 11:37 ` [PATCH v7 07/28] reftable: add error related functionality Han-Wen Nienhuys via GitGitGadget 2021-04-19 11:37 ` [PATCH v7 08/28] reftable: utility functions Han-Wen Nienhuys via GitGitGadget 2021-04-19 11:37 ` [PATCH v7 09/28] reftable: add blocksource, an abstraction for random access reads Han-Wen Nienhuys via GitGitGadget 2021-04-19 11:37 ` [PATCH v7 10/28] reftable: (de)serialization for the polymorphic record type Han-Wen Nienhuys via GitGitGadget 2021-05-04 17:23 ` Andrzej Hunt 2021-05-18 13:12 ` Han-Wen Nienhuys 2021-04-19 11:37 ` [PATCH v7 11/28] Provide zlib's uncompress2 from compat/zlib-compat.c Han-Wen Nienhuys via GitGitGadget 2021-04-19 11:37 ` [PATCH v7 12/28] reftable: reading/writing blocks Han-Wen Nienhuys via GitGitGadget 2021-04-19 11:37 ` [PATCH v7 13/28] reftable: a generic binary tree implementation Han-Wen Nienhuys via GitGitGadget 2021-04-19 11:37 ` [PATCH v7 14/28] reftable: write reftable files Han-Wen Nienhuys via GitGitGadget 2021-04-19 11:37 ` [PATCH v7 15/28] reftable: generic interface to tables Han-Wen Nienhuys via GitGitGadget 2021-04-19 11:37 ` [PATCH v7 16/28] reftable: read reftable files Han-Wen Nienhuys via GitGitGadget 2021-04-19 11:37 ` [PATCH v7 17/28] reftable: reftable file level tests Han-Wen Nienhuys via GitGitGadget 2021-04-19 11:37 ` [PATCH v7 18/28] reftable: add a heap-based priority queue for reftable records Han-Wen Nienhuys via GitGitGadget 2021-04-19 11:37 ` [PATCH v7 19/28] reftable: add merged table view Han-Wen Nienhuys via GitGitGadget 2021-04-19 11:37 ` [PATCH v7 20/28] reftable: implement refname validation Han-Wen Nienhuys via GitGitGadget 2021-04-19 11:37 ` [PATCH v7 21/28] reftable: implement stack, a mutable database of reftable files Han-Wen Nienhuys via GitGitGadget 2021-04-19 11:37 ` [PATCH v7 22/28] reftable: add dump utility Han-Wen Nienhuys via GitGitGadget 2021-04-19 11:37 ` [PATCH v7 23/28] Reftable support for git-core Han-Wen Nienhuys via GitGitGadget 2021-04-20 22:44 ` Junio C Hamano 2021-04-21 10:19 ` Han-Wen Nienhuys 2021-04-21 23:22 ` Junio C Hamano 2021-05-04 17:24 ` Andrzej Hunt 2021-05-18 13:18 ` Han-Wen Nienhuys 2021-05-18 13:30 ` Han-Wen Nienhuys 2021-04-19 11:37 ` [PATCH v7 24/28] git-prompt: prepare for reftable refs backend SZEDER Gábor via GitGitGadget 2021-04-19 11:37 ` [PATCH v7 25/28] Add "test-tool dump-reftable" command Han-Wen Nienhuys via GitGitGadget 2021-04-19 11:37 ` [PATCH v7 26/28] t1301: document what needs to be done for REFTABLE Han-Wen Nienhuys via GitGitGadget 2021-04-19 11:37 ` [PATCH v7 27/28] t1401,t2011: parameterize HEAD.lock " Han-Wen Nienhuys via GitGitGadget 2021-04-19 11:37 ` [PATCH v7 28/28] t1404: annotate test cases with REFFILES Han-Wen Nienhuys via GitGitGadget 2021-04-21 7:45 ` [PATCH v7 00/28] reftable library Ævar Arnfjörð Bjarmason 2021-04-21 9:52 ` Han-Wen Nienhuys 2021-04-21 11:21 ` Ævar Arnfjörð Bjarmason 2021-04-26 17:59 ` Han-Wen Nienhuys
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style List information: http://vger.kernel.org/majordomo-info.html * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=6968dbc3828f22369cc92bf56e3a7855769415fa.1607522429.git.gitgitgadget@gmail.com \ --to=gitgitgadget@gmail.com \ --cc=Johannes.Schindelin@gmx.de \ --cc=avarab@gmail.com \ --cc=emilyshaffer@google.com \ --cc=felipe.contreras@gmail.com \ --cc=git@vger.kernel.org \ --cc=hanwen@google.com \ --cc=hanwenn@gmail.com \ --cc=jonathantanmy@google.com \ --cc=jrnieder@gmail.com \ --cc=peff@peff.net \ --cc=ps@pks.im \ --cc=ramsay@ramsayjones.plus.com \ --cc=steadmon@google.com \ --subject='Re: [PATCH v4 08/15] reftable: a generic binary tree implementation' \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: link
Code repositories for project(s) associated with this inbox: https://80x24.org/mirrors/git.git This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).