Re: [RFC PATCH 00/19] object-store refactoring 3 (replace objects, main ref store)

> Am 07.04.2018 um 01:21 schrieb Stefan Beller:
>> This applies on top of 464416a2eaadf84d2bfdf795007863d03b222b7c
>> (sb/packfiles-in-repository).
>> It is also available at https://github.com/stefanbeller/git/tree/object-store-3
>
> This series conflicts with 1731a1e239 (replace_object: convert struct
> replace_object to object_id) and b383a13cc0 (Convert
> lookup_replace_object to struct object_id), which are in next.

>
>> This series will bring the replacement mechanism (git replace)
>> into the object store.
>
> Good idea.

>
>>   $ git diff 464416a2eaadf84d2bfdf795007863d03b222b7c..HEAD -- object-store.h repository.h
>> diff --git a/object-store.h b/object-store.h
>> index fef33f345f..be90c02db6 100644
>> --- a/object-store.h
>> +++ b/object-store.h
>> @@ -93,6 +93,22 @@ struct raw_object_store {
>>          struct alternate_object_database *alt_odb_list;
>>          struct alternate_object_database **alt_odb_tail;
>>
>> +       /*
>> +        * Objects that should be substituted by other objects
>> +        * (see git-replace(1)).
>> +        */
>> +       struct replace_objects {
>> +               /*
>> +                * An array of replacements.  The array is kept sorted by the original
>> +                * sha1.
>> +                */
>> +               struct replace_object **items;
>> +
>> +               int alloc, nr;
>> +
>> +               unsigned prepared : 1;
>> +       } replacements;
>
> An oidmap would be a better fit -- lookups should be quicker and
> memory consumption not much worse.  I meant to submit something like
> this eventually after Brian's series lands:
>
> -- >8 --
> Subject: [PATCH] replace_object: use oidmap
>
> 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>
> ---
> This is on top of next.

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