From: Stefan Beller <sbeller@google.com>
To: sbeller@google.com
Cc: git@vger.kernel.org, jonathantanmy@google.com, l.s.r@web.de,
pclouds@gmail.com, sandals@crustytoothpaste.net,
sunshine@sunshineco.com
Subject: [PATCH 01/15] replace_object: use oidmap
Date: Wed, 11 Apr 2018 17:21:04 -0700 [thread overview]
Message-ID: <20180412002118.102976-2-sbeller@google.com> (raw)
In-Reply-To: <20180412002118.102976-1-sbeller@google.com>
From: René Scharfe <l.s.r@web.de>
Load the replace objects into an oidmap to allow for easy lookups in
constant time.
Signed-off-by: Rene Scharfe <l.s.r@web.de>
Signed-off-by: Stefan Beller <sbeller@google.com>
---
replace_object.c | 76 ++++++++++--------------------------------------
1 file changed, 16 insertions(+), 60 deletions(-)
diff --git a/replace_object.c b/replace_object.c
index 336357394d..a757a5ebf2 100644
--- a/replace_object.c
+++ b/replace_object.c
@@ -1,54 +1,14 @@
#include "cache.h"
-#include "sha1-lookup.h"
+#include "oidmap.h"
#include "refs.h"
#include "commit.h"
-/*
- * An array of replacements. The array is kept sorted by the original
- * sha1.
- */
-static struct replace_object {
- struct object_id original;
+struct replace_object {
+ struct oidmap_entry original;
struct object_id replacement;
-} **replace_object;
-
-static int replace_object_alloc, replace_object_nr;
+};
-static const unsigned char *replace_sha1_access(size_t index, void *table)
-{
- struct replace_object **replace = table;
- return replace[index]->original.hash;
-}
-
-static int replace_object_pos(const unsigned char *sha1)
-{
- return sha1_pos(sha1, replace_object, replace_object_nr,
- replace_sha1_access);
-}
-
-static int register_replace_object(struct replace_object *replace,
- int ignore_dups)
-{
- int pos = replace_object_pos(replace->original.hash);
-
- if (0 <= pos) {
- if (ignore_dups)
- free(replace);
- else {
- free(replace_object[pos]);
- replace_object[pos] = replace;
- }
- return 1;
- }
- pos = -pos - 1;
- ALLOC_GROW(replace_object, replace_object_nr + 1, replace_object_alloc);
- replace_object_nr++;
- if (pos < replace_object_nr)
- MOVE_ARRAY(replace_object + pos + 1, replace_object + pos,
- replace_object_nr - pos - 1);
- replace_object[pos] = replace;
- return 0;
-}
+static struct oidmap replace_map = OIDMAP_INIT;
static int register_replace_ref(const char *refname,
const struct object_id *oid,
@@ -59,7 +19,7 @@ static int register_replace_ref(const char *refname,
const char *hash = slash ? slash + 1 : refname;
struct replace_object *repl_obj = xmalloc(sizeof(*repl_obj));
- if (get_oid_hex(hash, &repl_obj->original)) {
+ if (get_oid_hex(hash, &repl_obj->original.oid)) {
free(repl_obj);
warning("bad replace ref name: %s", refname);
return 0;
@@ -69,7 +29,7 @@ static int register_replace_ref(const char *refname,
oidcpy(&repl_obj->replacement, oid);
/* Register new object */
- if (register_replace_object(repl_obj, 1))
+ if (oidmap_put(&replace_map, repl_obj))
die("duplicate replace ref: %s", refname);
return 0;
@@ -84,7 +44,7 @@ static void prepare_replace_object(void)
for_each_replace_ref(register_replace_ref, NULL);
replace_object_prepared = 1;
- if (!replace_object_nr)
+ if (!replace_map.map.tablesize)
check_replace_refs = 0;
}
@@ -100,21 +60,17 @@ static void prepare_replace_object(void)
*/
const struct object_id *do_lookup_replace_object(const struct object_id *oid)
{
- int pos, depth = MAXREPLACEDEPTH;
+ int depth = MAXREPLACEDEPTH;
const struct object_id *cur = oid;
prepare_replace_object();
/* Try to recursively replace the object */
- do {
- if (--depth < 0)
- die("replace depth too high for object %s",
- oid_to_hex(oid));
-
- pos = replace_object_pos(cur->hash);
- if (0 <= pos)
- cur = &replace_object[pos]->replacement;
- } while (0 <= pos);
-
- return cur;
+ while (depth-- > 0) {
+ struct replace_object *repl_obj = oidmap_get(&replace_map, cur);
+ if (!repl_obj)
+ return cur;
+ cur = &repl_obj->replacement;
+ }
+ die("replace depth too high for object %s", oid_to_hex(oid));
}
--
2.17.0.484.g0c8726318c-goog
next prev parent reply other threads:[~2018-04-12 0:21 UTC|newest]
Thread overview: 92+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-04-06 23:21 [RFC PATCH 00/19] object-store refactoring 3 (replace objects, main ref store) Stefan Beller
2018-04-06 23:21 ` [PATCH 01/19] replace_object.c: rename to use dash in file name Stefan Beller
2018-04-06 23:21 ` [PATCH 02/19] replace-object: move replace_object to object store Stefan Beller
2018-04-09 13:51 ` Derrick Stolee
2018-04-06 23:21 ` [PATCH 03/19] object-store: move lookup_replace_object to replace-object.h Stefan Beller
2018-04-06 23:21 ` [PATCH 04/19] replace-object: move replace objects prepared flag to object store Stefan Beller
2018-04-06 23:21 ` [PATCH 05/19] replace-object: check_replace_refs is safe in multi repo environment Stefan Beller
2018-04-06 23:21 ` [PATCH 06/19] refs: add repository argument to get_main_ref_store Stefan Beller
2018-04-07 6:53 ` Eric Sunshine
2018-04-09 18:51 ` Stefan Beller
2018-04-06 23:21 ` [PATCH 07/19] refs: add repository argument to for_each_replace_ref Stefan Beller
2018-04-06 23:21 ` [PATCH 08/19] replace-object: add repository argument to replace_object_pos Stefan Beller
2018-04-06 23:21 ` [PATCH 09/19] replace-object: add repository argument to register_replace_object Stefan Beller
2018-04-06 23:21 ` [PATCH 10/19] replace-object: add repository argument to prepare_replace_object Stefan Beller
2018-04-06 23:21 ` [PATCH 11/19] replace-object: add repository argument to do_lookup_replace_object Stefan Beller
2018-04-06 23:21 ` [PATCH 12/19] replace-object: add repository argument to lookup_replace_object Stefan Beller
2018-04-06 23:21 ` [PATCH 13/19] refs: store the main ref store inside the repository struct Stefan Beller
2018-04-07 6:54 ` Eric Sunshine
2018-04-06 23:21 ` [PATCH 14/19] refs: allow for_each_replace_ref to handle arbitrary repositories Stefan Beller
2018-04-06 23:21 ` [PATCH 15/19] replace-object: allow replace_object_pos " Stefan Beller
2018-04-06 23:21 ` [PATCH 16/19] replace-object: allow register_replace_object " Stefan Beller
2018-04-06 23:21 ` [PATCH 17/19] replace-object: allow prepare_replace_object " Stefan Beller
2018-04-06 23:21 ` [PATCH 18/19] replace-object: allow do_lookup_replace_object " Stefan Beller
2018-04-06 23:21 ` [PATCH 19/19] replace-object: allow lookup_replace_object " Stefan Beller
2018-04-07 4:58 ` [RFC PATCH 00/19] object-store refactoring 3 (replace objects, main ref store) René Scharfe
2018-04-09 17:44 ` Stefan Beller
2018-04-07 9:50 ` Duy Nguyen
2018-04-09 17:39 ` Stefan Beller
2018-04-09 13:58 ` Derrick Stolee
[not found] ` <nycvar.QRO.7.76.6.1804091038430.55@ZVAVAG-6OXH6DA.rhebcr.pbec.zvpebfbsg.pbz>
2018-04-09 17:36 ` Stefan Beller
2018-04-09 22:45 ` [PATCHv2 00/16] " Stefan Beller
2018-04-09 22:45 ` [PATCH 01/16] replace_object: use oidmap Stefan Beller
2018-04-10 2:57 ` Junio C Hamano
2018-04-10 2:57 ` Junio C Hamano
2018-04-09 22:45 ` [PATCH 02/16] replace_object.c: rename to use dash in file name Stefan Beller
2018-04-10 3:00 ` Junio C Hamano
2018-04-10 17:57 ` Stefan Beller
2018-04-10 21:26 ` [PATCH 0/6] Rename files to use dashes instead of underscores Stefan Beller
2018-04-10 21:26 ` [PATCH 1/6] write_or_die.c: rename to use dashes in file name Stefan Beller
2018-04-10 21:26 ` [PATCH 2/6] unicode_width.h: rename to use dash " Stefan Beller
2018-04-10 21:26 ` [PATCH 3/6] exec_cmd: " Stefan Beller
2018-04-10 21:26 ` [PATCH 4/6] sha1_name.c: " Stefan Beller
2018-04-10 21:26 ` [PATCH 5/6] sha1_file.c: " Stefan Beller
2018-04-10 21:26 ` [PATCH 6/6] replace_object.c: " Stefan Beller
2018-04-10 21:28 ` [PATCH 0/6] Rename files to use dashes instead of underscores Stefan Beller
2018-04-10 22:39 ` Johannes Schindelin
2018-04-10 22:47 ` Stefan Beller
2018-04-11 23:13 ` brian m. carlson
2018-04-09 22:45 ` [PATCH 03/16] replace-object: move replace_map to object store Stefan Beller
2018-04-10 3:10 ` Junio C Hamano
2018-04-09 22:45 ` [PATCH 04/16] object-store: move lookup_replace_object to replace-object.h Stefan Beller
2018-04-09 22:45 ` [PATCH 05/16] replace-object: eliminate replace objects prepared flag Stefan Beller
2018-04-10 3:21 ` Junio C Hamano
2018-04-10 7:32 ` René Scharfe
2018-04-09 22:45 ` [PATCH 06/16] replace-object: check_replace_refs is safe in multi repo environment Stefan Beller
2018-04-10 3:37 ` Junio C Hamano
2018-04-09 22:45 ` [PATCH 07/16] refs: add repository argument to get_main_ref_store Stefan Beller
2018-04-10 13:36 ` Michael Haggerty
2018-04-10 18:27 ` Stefan Beller
2018-04-09 22:45 ` [PATCH 08/16] refs: add repository argument to for_each_replace_ref Stefan Beller
2018-04-09 22:45 ` [PATCH 09/16] replace-object: add repository argument to prepare_replace_object Stefan Beller
2018-04-09 22:45 ` [PATCH 10/16] replace-object: add repository argument to do_lookup_replace_object Stefan Beller
2018-04-09 22:45 ` [PATCH 11/16] replace-object: add repository argument to lookup_replace_object Stefan Beller
2018-04-09 22:45 ` [PATCH 12/16] refs: store the main ref store inside the repository struct Stefan Beller
2018-04-09 23:24 ` Brandon Williams
2018-04-09 23:29 ` Stefan Beller
2018-04-09 23:35 ` Brandon Williams
2018-04-10 14:02 ` Michael Haggerty
2018-04-10 18:38 ` Stefan Beller
2018-04-09 22:45 ` [PATCH 13/16] refs: allow for_each_replace_ref to handle arbitrary repositories Stefan Beller
2018-04-09 22:45 ` [PATCH 14/16] replace-object: allow prepare_replace_object " Stefan Beller
2018-04-09 22:45 ` [PATCH 15/16] replace-object: allow do_lookup_replace_object " Stefan Beller
2018-04-09 22:45 ` [PATCH 16/16] replace-object: allow lookup_replace_object " Stefan Beller
2018-04-09 23:25 ` [PATCHv2 00/16] object-store refactoring 3 (replace objects, main ref store) Brandon Williams
2018-04-09 23:31 ` Stefan Beller
2018-04-12 0:21 ` [PATCHv3 00/15] replace_object.c: rename to use dash in file name Stefan Beller
2018-04-12 0:21 ` Stefan Beller [this message]
2018-04-12 0:21 ` [PATCH 02/15] replace-object: move replace_map to object store Stefan Beller
2018-04-12 0:21 ` [PATCH 03/15] object-store: move lookup_replace_object to replace-object.h Stefan Beller
2018-04-12 0:21 ` [PATCH 04/15] replace-object: eliminate replace objects prepared flag Stefan Beller
2018-04-12 0:21 ` [PATCH 05/15] replace-object: check_replace_refs is safe in multi repo environment Stefan Beller
2018-04-12 0:21 ` [PATCH 06/15] refs: add repository argument to get_main_ref_store Stefan Beller
2018-04-12 0:21 ` [PATCH 07/15] refs: add repository argument to for_each_replace_ref Stefan Beller
2018-04-12 0:21 ` [PATCH 08/15] replace-object: add repository argument to prepare_replace_object Stefan Beller
2018-04-12 0:21 ` [PATCH 09/15] replace-object: add repository argument to do_lookup_replace_object Stefan Beller
2018-04-12 0:21 ` [PATCH 10/15] replace-object: add repository argument to lookup_replace_object Stefan Beller
2018-04-12 0:21 ` [PATCH 11/15] refs: store the main ref store inside the repository struct Stefan Beller
2018-04-12 0:21 ` [PATCH 12/15] refs: allow for_each_replace_ref to handle arbitrary repositories Stefan Beller
2018-04-12 0:21 ` [PATCH 13/15] replace-object: allow prepare_replace_object " Stefan Beller
2018-04-12 0:21 ` [PATCH 14/15] replace-object: allow do_lookup_replace_object " Stefan Beller
2018-04-12 0:21 ` [PATCH 15/15] replace-object: allow lookup_replace_object " Stefan Beller
2018-04-12 11:43 ` [PATCHv3 00/15] replace_object.c: rename to use dash in file name Derrick Stolee
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=20180412002118.102976-2-sbeller@google.com \
--to=sbeller@google.com \
--cc=git@vger.kernel.org \
--cc=jonathantanmy@google.com \
--cc=l.s.r@web.de \
--cc=pclouds@gmail.com \
--cc=sandals@crustytoothpaste.net \
--cc=sunshine@sunshineco.com \
/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
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public 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).