Re: [PATCH 01/16] replace_object: use oidmap

[Junio C Hamano]

Stefan Beller  writes:

> -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;
> +};

The oidmap key can also serve as the original side, which is good
;-)

> @@ -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;

The original checks _nr (i.e. how many do we actually have) as
opposed to _alloc; on the other hand, .tablesize is not about the
number of contents in the table.

But before or after the patch, what the code really wants to check
is if the table is _initialized_, so from that point of view,
checking .tablesize is good enough.

So, I guess this step is quite right ;-)

[PATCH 01/16] replace_object: use oidmap

[Stefan Beller]

From: René Scharfe 

Load the replace objects into an oidmap to allow for easy lookups in
constant time.

Signed-off-by: Rene Scharfe 
Signed-off-by: Stefan Beller 
---
 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